Perturbation Analysis of Singular Semidefinite Programs and Its Applications to Control Problems
- PDF / 441,196 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 49 Downloads / 200 Views
Perturbation Analysis of Singular Semidefinite Programs and Its Applications to Control Problems Yoshiyuki Sekiguchi1
· Hayato Waki2
Received: 5 August 2019 / Accepted: 3 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We consider sensitivity of a semidefinite program under perturbations in the case that the primal problem is strictly feasible and the dual problem is weakly feasible. When the coefficient matrices are perturbed, the optimal values can change discontinuously as explained in concrete examples. We show that the optimal value of such a semidefinite program changes continuously under conditions involving the behavior of the minimal faces of the perturbed dual problems. In addition, we determine what kinds of perturbations keep the minimal faces invariant, by using the reducing certificates, which are produced in facial reduction. Our results allow us to classify the behavior of the minimal face of a semidefinite program obtained from a control problem. Keywords Semidefinite programming · Sensitivity · Facial reduction · Minimal face · H-infinity feedback control problem Mathematics Subject Classification 90C31 · 90C22 · 90C51 · 93D15
1 Introduction A semidefinite program is the problem of maximizing a linear function subject to the constraint that an affine combination of matrices is positive semidefinite, where
Communicated by Levent Tunçel.
B
Yoshiyuki Sekiguchi [email protected] Hayato Waki [email protected]
1
Tokyo University of Marine Science and Technology, 2-1-6, Etchujima, Koto, Tokyo 135-8533, Japan
2
Institute of Mathematics for Industry, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan
123
Journal of Optimization Theory and Applications
the constraint is called a linear matrix inequality. Semidefinite programs have various applications, such as discrete optimization, polynomial optimization and control problems (e.g., [1,2] ). If the feasible sets of a semidefinite program and the dual problem satisfy the constraint qualifications, both of which are called strict feasibility, then interior point methods compute an approximation to an exact solution efficiently, see, e.g., [3,4]. With a lack of strict feasibility, interior point methods are numerically unstable and often give wrong optimal values [5–7]. To avoid such numerical instability, we can use the technique called facial reduction, which finds the minimal face among the faces of the positive semidefinite cone containing a feasible set. Such a face is called the minimal face of a semidefinite program [8–11]. Then, we obtain a semidefinite program that satisfies strict feasibility and has the same optimal value as the original problem. For applications of facial reduction, see the monograph [12] and the references therein. The first contribution of this paper is to provide sufficient conditions for continuity of the optimal value under perturbations, in the case that the primal problem is strictly feasible and the dual problem is feasible but not strictl
Data Loading...
