The Gauss-Newton direction in semidefinite programming

作     者：Kruk, S Muramatsu, M Rendl, F Vanderbei, RJ Wolkowicz, H 

作者机构：Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Sophia Univ Dept Mech Engn Chiyoda Ku Tokyo 102 Japan Univ Klagenfurt Inst Math A-9020 Klagenfurt Austria Princeton Univ Princeton NJ 08544 USA 

出 版 物：《OPTIMIZATION METHODS & SOFTWARE》 (最优化方法与软件)

年 卷 期：2001年第15卷第1期

页      面：1-28页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 

主　　题：semidefinite programming Newton direction symmetrization 

摘      要：Most of the directions used in practical interior-point methods far semidefinite programming try to follow the approach used in linear programming, i.e., they are defined using the optimality conditions which are modified with a symmetrization of the perturbed complementarity conditions to allow for application of Newton s method. It is now understood that all the Monteiro-Zhang family, which include, among others, the popular AHO, NT, HKM, Gu, and Toh directions, can be expressed as a scaling of the problem data and of the iterate followed by the solution of the AHO system of equations, followed by the inverse scaling. All these directions therefore share a defining system of equations. The focus of this work is to propose a defining system of equations that is essentially different from the AHO system: the over-determined system obtained from the minimization of a nonlinear equation. The resulting solution is called the Gauss-Newton search direction. We state some of the properties of this system that make it attractive for accurate solutions of semidefinite programs. We also offer some preliminary numerical results that highlight the conditioning of the system and the accuracy of the resulting solutions.