TY - JOUR

T1 - Polynomial primal-dual cone affine scaling for semidefinite programming

AU - Berkelaar, Arjan B.

AU - Sturm, Jos F.

AU - Zhang, Shuzhong

N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 1999/3

Y1 - 1999/3

N2 - Semidefinite programming concerns the problem of optimizing a linear function over a section of the cone of semidefinite matrices. In the cone affine scaling approach, we replace the cone of semidefinite matrices by a certain inscribed cone, in such a way that the resulting optimization problem is analytically solvable. The now easily obtained solution to this modified problem serves as an approximate solution to the semidefinite programming problem. The inscribed cones that we use are affine transformations of second order cones, hence the name 'cone affine scaling'. Compared to other primal-dual affine scaling algorithms for semidefinite programming (see de Klerk, Roos and Terlaky (1997)), our algorithm enjoys the lowest computational complexity.

AB - Semidefinite programming concerns the problem of optimizing a linear function over a section of the cone of semidefinite matrices. In the cone affine scaling approach, we replace the cone of semidefinite matrices by a certain inscribed cone, in such a way that the resulting optimization problem is analytically solvable. The now easily obtained solution to this modified problem serves as an approximate solution to the semidefinite programming problem. The inscribed cones that we use are affine transformations of second order cones, hence the name 'cone affine scaling'. Compared to other primal-dual affine scaling algorithms for semidefinite programming (see de Klerk, Roos and Terlaky (1997)), our algorithm enjoys the lowest computational complexity.

KW - Affine scaling

KW - Primal-dual interior point methods

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=0040437615&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040437615&partnerID=8YFLogxK

U2 - 10.1016/S0168-9274(98)00100-7

DO - 10.1016/S0168-9274(98)00100-7

M3 - Article

AN - SCOPUS:0040437615

VL - 29

SP - 317

EP - 333

JO - Applied Numerical Mathematics

JF - Applied Numerical Mathematics

SN - 0168-9274

IS - 3

ER -