  


Asymptotic behavior of the central path for a special class of degenerate SDP problems
Joao X. Cruz Neto (jxavierufpi.br) Abstract: This paper studies the asymptotic behavior of the central path $(X(\nu),S(\nu),y(\nu))$ as $\nu \downarrow 0$ for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primaldual optimal solutions and whose ``degenerate diagonal blocks'' $X_{\cT}(\nu)$ and $S_{\cT}(\nu)$ of the central path are assumed to satisfy $\max\{ \X_{\cT}(\nu)\, \S_{\cT}(\nu)\ \} = {\cal O}(\sqrt{\nu})$. We establish the convergence of the central path towards a primaldual optimal solution, which is characterized as being the unique optimal solution of a certain logbarrier problem. A characterization of the class of SDP problems which satisfy our assumptions are also provided.It is shown that the reparametrization $t>0 \to (X(t^4),S(t^4),y(t^4))$ 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 ${\cal O}(\sqrt{\nu})$. 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. Keywords: Limiting behavior, central path, semidefinite programming, convex quadratic programming, convex quadratically constrained programming Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Manuscript,School of Industrial and Systems Engineering,Georgia Institute of Technology,Atlanta,GA 303320205,USA,July 2003 Download: [Postscript] Entry Submitted: 07/07/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  