TY - JOUR

T1 - A strategy of global convergence for the affine scaling algorithm for convex semidefinite programming

AU - Qian, Xun

AU - Liao, Lizhi

AU - Sun, Jie

N1 - Publisher Copyright:
© 2018, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/1

Y1 - 2020/1

N2 - The affine scaling algorithm is one of the earliest interior point methods developed for linear programming. This algorithm is simple and elegant in terms of its geometric interpretation, but it is notoriously difficult to prove its convergence. It often requires additional restrictive conditions such as nondegeneracy, specific initial solutions, and/or small step length to guarantee its global convergence. This situation is made worse when it comes to applying the affine scaling idea to the solution of semidefinite optimization problems or more general convex optimization problems. In (Math Program 83(1–3):393–406, 1998), Muramatsu presented an example of linear semidefinite programming, for which the affine scaling algorithm with either short or long step converges to a non-optimal point. This paper aims at developing a strategy that guarantees the global convergence for the affine scaling algorithm in the context of linearly constrained convex semidefinite optimization in a least restrictive manner. We propose a new rule of step size, which is similar to the Armijo rule, and prove that such an affine scaling algorithm is globally convergent in the sense that each accumulation point of the sequence generated by the algorithm is an optimal solution as long as the optimal solution set is nonempty and bounded. The algorithm is least restrictive in the sense that it allows the problem to be degenerate and it may start from any interior feasible point.

AB - The affine scaling algorithm is one of the earliest interior point methods developed for linear programming. This algorithm is simple and elegant in terms of its geometric interpretation, but it is notoriously difficult to prove its convergence. It often requires additional restrictive conditions such as nondegeneracy, specific initial solutions, and/or small step length to guarantee its global convergence. This situation is made worse when it comes to applying the affine scaling idea to the solution of semidefinite optimization problems or more general convex optimization problems. In (Math Program 83(1–3):393–406, 1998), Muramatsu presented an example of linear semidefinite programming, for which the affine scaling algorithm with either short or long step converges to a non-optimal point. This paper aims at developing a strategy that guarantees the global convergence for the affine scaling algorithm in the context of linearly constrained convex semidefinite optimization in a least restrictive manner. We propose a new rule of step size, which is similar to the Armijo rule, and prove that such an affine scaling algorithm is globally convergent in the sense that each accumulation point of the sequence generated by the algorithm is an optimal solution as long as the optimal solution set is nonempty and bounded. The algorithm is least restrictive in the sense that it allows the problem to be degenerate and it may start from any interior feasible point.

KW - Affine scaling

KW - Convex semidefinite programming

KW - Interior point method

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

U2 - 10.1007/s10107-018-1314-0

DO - 10.1007/s10107-018-1314-0

M3 - Article

AN - SCOPUS:85050954021

SN - 0025-5610

VL - 179

SP - 1

EP - 19

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -