Asymptotic behavior of the central path for a special class of degenerate SDP problems |
| |
Authors: | João X da Cruz Neto Orizon P Ferreira Renato D C Monteiro |
| |
Institution: | (1) DM, Universidade Federal do Piauí, Teresina, PI, 64049-500, Brazil;(2) IME, Universidade Federal de Goiás, Goiânia, GO, 74001-970, Brazil;(3) School of ISyE, Georgia Tech, Atlanta, Georgia 30332, USA |
| |
Abstract: | This paper studies the asymptotic behavior of the central path (X(ν),S(ν),y(ν)) as ν↓0 for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” of the central path are assumed to satisfy We establish the convergence of the central path towards a primal-dual optimal solution, which is characterized as being the unique optimal solution of a certain log-barrier problem. A characterization of the class of SDP problems which satisfy our assumptions are also provided. It is shown that the re-parametrization t>0→(X(t4),S(t4),y(t4)) of the central path is analytic at t=0. The limiting behavior of the derivative of the central path is also investigated and it is shown that the order of convergence of the central path towards its limit point is Finally, we apply our results to the convex quadratically constrained convex programming (CQCCP) problem and characterize the class of CQCCP problems which can be formulated as SDPs satisfying the assumptions of this paper. In particular, we show that CQCCP problems with either a strictly convex objective function or at least one strictly convex constraint function lie in this class.This author was supported in part by CAPES and PRONEX-Otimização (FAPERJ/CNPq).This author was supported in part by FUNAPE/UFG, CAPES, PADCT-CNPq and PRONEX-Otimização (FAPERJ/CNPq).This author was supported in part by NSF Grants CCR-9902010, CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.Mathematics Subject Classification (1991): 90C20, 90C22, 90C25, 90C30, 90C33, 90C45, 90C51 |
| |
Keywords: | Limiting behavior Central path Semidefinite programming Convex quadratic programming Convex quadratically constrained programming |
本文献已被 SpringerLink 等数据库收录! |
|