Lagrangian dual interior-point methods for semidefinite programs

Mituhiro Fukuda (mituhirois.titech.ac.jp)
Masakazu Kojima (kojimais.titech.ac.jp)
Masayuki Shida (shidacc.nda.ac.jp)

Abstract: This paper proposes a new predictor-corrector interior-point method for a class of semidefinite programs, which numerically traces the central trajectory in a space of Lagrange multipliers. The distinguished features of the method are full use of the BFGS quasi-Newton method in the corrector procedure and an application of the conjugate gradient method with an effective preconditioning matrix induced from the BFGS quasi-Newton method in the predictor procedure. Some preliminary numerical results are reported.

Keywords: Semidefinite Program, Linear Program Over Convex Cones, Second-Order Cone Program, Primal-Dual Interior-Point Method, Predictor-Corrector Method, Lagrangian Dual, Central Trajectory, BFGS Quasi-Newton Method, Conjugate Gradient Method.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: SIAM Journal on Optimization Vol 12, No.4, 1007-1031 (2002).

Download:

Entry Submitted: 04/03/2001
Entry Accepted: 04/04/2001
Entry Last Modified: 04/29/2004

Modify/Update this entry