An Interior Point-Proximal Method of Multipliers for Linear Positive Semi-Definite Programming
Open Access
- 28 October 2021
- journal article
- research article
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 192 (1) , 97-129
Abstract
In this paper we generalize the Interior Point-Proximal Method of Multipliers (IP-PMM) presented in Pougkakiotis and Gondzio (Comput Optim Appl 78:307–351, 2021.10.1007/s10589-020-00240-9) for the solution of linear positive Semi-Definite Programming (SDP) problems, allowing inexactness in the solution of the associated Newton systems. In particular, we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM) and interpret the algorithm (IP-PMM) as a primal-dual regularized IPM, suitable for solving SDP problems. We apply some iterations of an IPM to each sub-problem of the PMM until a satisfactory solution is found. We then update the PMM parameters, form a new IPM neighbourhood, and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under mild assumptions, and without requiring exact computations for the Newton directions. We furthermore provide a necessary condition for lack of strong duality, which can be used as a basis for constructing detection mechanisms for identifying pathological cases within IP-PMM.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Uniform boundedness of the inverse of a Jacobian matrix arising in regularized interior-point methodsMathematical Programming, 2011
- A Newton-CG Augmented Lagrangian Method for Semidefinite ProgrammingSIAM Journal on Optimization, 2010
- Polynomiality of an inexact infeasible interior point algorithm for semidefinite programmingMathematical Programming, 2004
- Semidefinite Programming in Systems and Control Theory2000
- Primal-Dual Interior-Point Methods for Semidefinite Programming in Finite PrecisionSIAM Journal on Optimization, 2000
- Applications of semidefinite programmingApplied Numerical Mathematics, 1999
- Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimizationOptimization Methods and Software, 1999
- A study of search directions in primal-dual interior-point methods for semidefinite programmingOptimization Methods and Software, 1999
- On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite ProgrammingSIAM Journal on Optimization, 1998
- Monotone Operators and the Proximal Point AlgorithmSIAM Journal on Control and Optimization, 1976