An interior proximal gradient method for nonconvex optimization

De Marchi, Alberto; Themelis, Andreas

Open Journal of Mathematical Optimization, Tome 5 (2024), article no. 3, 22 p.

We consider structured minimization problems subject to smooth inequality constraints and present a flexible algorithm that combines interior point (IP) and proximal gradient schemes. While traditional IP methods cannot cope with nonsmooth objective functions and proximal algorithms cannot handle complicated constraints, their combined usage is shown to successfully compensate the respective shortcomings. We provide a theoretical characterization of the algorithm and its asymptotic properties, deriving convergence results for fully nonconvex problems, thus bridging the gap with previous works that successfully addressed the convex case. Our interior proximal gradient algorithm benefits from warm starting, generates strictly feasible iterates with decreasing objective value, and returns after finitely many iterations a primal-dual pair approximately satisfying suitable optimality conditions. As a byproduct of our analysis of proximal gradient iterations we demonstrate that a slight refinement of traditional backtracking techniques waives the need for upper bounding the stepsize sequence, as required in existing results for the nonconvex setting.

Keywords: Nonsmooth nonconvex optimization, interior point methods, proximal algorithms, locally Lipschitz gradient

[1] Ahookhosh, Masoud; Themelis, Andreas; Patrinos, Panagiotis A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima, SIAM J. Optim., Volume 31 (2021) no. 1, pp. 653-685 | MR | DOI | Zbl

[2] Altman, Anna; Gondzio, Jacek Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optim. Methods Softw., Volume 11 (1999) no. 1–4, pp. 275-302 | MR | DOI | Zbl

[3] Armand, Paul; Omheni, Riadh A Mixed Logarithmic Barrier-Augmented Lagrangian Method for Nonlinear Optimization, J. Optim. Theory Appl., Volume 173 (2017) no. 2, pp. 523-547 | MR | Zbl | DOI

[4] Beck, Amir; Guttmann-Beck, Nili FOM – a MATLAB toolbox of first-order methods for solving convex optimization problems, Optim. Methods Softw., Volume 34 (2019) no. 1, pp. 172-193 | MR | DOI | Zbl

[5] Behmandpoor, Pourya; Latafat, Puya; Themelis, Andreas; Moonen, Marc; Patrinos, Panagiotis SPIRAL: A Superlinearly Convergent Incremental Proximal Algorithm for Nonconvex Finite Sum Minimization, Comput. Optim. Appl., Volume 88 (2024) no. 1, pp. 71-106 | MR | DOI | Zbl

[6] Bertsekas, Dimitri P. Nonlinear Programming, Athena Scientific, 1999 | MR

[7] Birgin, Ernesto G.; Martínez, José Mario Practical Augmented Lagrangian Methods for Constrained Optimization, Society for Industrial and Applied Mathematics, 2014 | MR | DOI

[8] Bolte, Jérôme; Sabach, Shoham; Teboulle, Marc; Vaisbourd, Yakov First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems, SIAM J. Optim., Volume 28 (2018) no. 3, pp. 2131-2151 | MR | DOI | Zbl

[9] Brilli, Andrea; Liuzzi, Giampaolo; Lucidi, Stefano An interior point method for nonlinear constrained derivative-free optimization (2022) | arXiv

[10] Chen, Feishe; Shen, Lixin; Suter, Bruce W. Computing the proximity operator of the ${\ell }_p$ norm with $0<p<1$, IET Signal Process., Volume 10 (2016) no. 5, pp. 557-565 | DOI

[11] Chouzenoux, Emilie; Corbineau, Marie-Caroline; Pesquet, Jean-Christophe A Proximal Interior Point Algorithm with Applications to Image Processing, J. Math. Imaging Vis., Volume 62 (2020) no. 6, pp. 919-940 | MR | DOI | Zbl

[12] Curtis, Frank E. A penalty-interior-point algorithm for nonlinear constrained optimization, Math. Program. Comput., Volume 4 (2012) no. 2, pp. 181-209 | MR | DOI | Zbl

[13] De Marchi, Alberto Proximal gradient methods beyond monotony, Journal of Nonsmooth Analysis and Optimization, Volume 4 (2023) | MR | DOI

[14] De Marchi, Alberto; Jia, Xiaoxi; Kanzow, Christian; Mehlitz, Patrick Constrained composite optimization and augmented Lagrangian methods, Math. Program., Volume 201 (2023) no. 1, pp. 863-896 | MR | DOI | Zbl

[15] De Marchi, Alberto; Themelis, Andreas Proximal Gradient Algorithms under Local Lipschitz Gradient Continuity: A Convergence and Robustness Analysis of PANOC, J. Optim. Theory Appl., Volume 194 (2022) no. 3, pp. 771-794 | MR | DOI | Zbl

[16] Fiacco, Anthony V.; McCormick, Garth P. Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley & Sons, 1968 | MR

[17] Forsgren, Anders; Gill, Philip E.; Wright, Margaret H. Interior Methods for Nonlinear Optimization, SIAM Rev., Volume 44 (2002) no. 4, pp. 525-597 | MR | DOI | Zbl

[18] Frisch, Ragnar The logarithmic potential method of convex programming (1955) (Technical report)

[19] Gill, Philip E.; Murray, Walter; Saunders, Michael A.; Tomlin, John A.; Wright, Margaret H. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Math. Program., Volume 36 (1986) no. 2, pp. 183-209 | MR | DOI | Zbl

[20] Gondzio, Jacek Interior point methods 25 years later, Eur. J. Oper. Res., Volume 218 (2012) no. 3, pp. 587-601 | MR | DOI | Zbl

[21] Kanzow, Christian; Mehlitz, Patrick Convergence Properties of Monotone and Nonmonotone Proximal Gradient Methods Revisited, J. Optim. Theory Appl., Volume 195 (2022) no. 2, pp. 624-646 | MR | DOI | Zbl

[22] Karmarkar, Narendra A new polynomial-time algorithm for linear programming, Combinatorica, Volume 4 (1984) no. 4, pp. 373-395 | MR | DOI

[23] Khachiyan, Leonid G. A polynomial algorithm in linear programming, Sov. Math., Dokl., Volume 20 (1979), pp. 191-194

[24] Lai, Zhijian; Yoshise, Akiko Riemannian Interior Point Methods for Constrained Optimization on Manifolds, J. Optim. Theory Appl., Volume 201 (2024) no. 1, pp. 433-469 | MR | DOI | Zbl

[25] Latafat, Puya; Themelis, Andreas; Ahookhosh, Masoud; Patrinos, Panagiotis Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity, SIAM J. Optim., Volume 32 (2022) no. 3, pp. 2230-2262 | MR | DOI | Zbl

[26] Latafat, Puya; Themelis, Andreas; Patrinos, Panagiotis On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms (2023) | arXiv

[27] Latafat, Puya; Themelis, Andreas; Stella, Lorenzo; Patrinos, Panagiotis Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient (2023) | arXiv

[28] Lin, Tianyi; Ma, Shiqian; Ye, Yinyu; Zhang, Shuzhong An ADMM-based interior-point method for large-scale linear programming, Optim. Methods Softw., Volume 36 (2021) no. 2–3, pp. 389-424 | MR | DOI | Zbl

[29] Liu, Changshuo; Boumal, Nicolas Simple Algorithms for Optimization on Riemannian Manifolds with Constraints, Appl. Math. Optim., Volume 82 (2020) no. 3, pp. 949-981 | MR | DOI | Zbl

[30] Lu, Haihao; Freund, Robert M.; Nesterov, Yurii Relatively Smooth Convex Optimization by First-Order Methods, and Applications, SIAM J. Optim., Volume 28 (2018) no. 1, pp. 333-354 | MR | DOI | Zbl

[31] Mahajan, Ashutosh; Leyffer, Sven; Kirches, Christian Solving Mixed-Integer Nonlinear Programs by QP-Diving (2012) (Preprint ANL/MCS-P2071-0312) (Technical report)

[32] Malitsky, Yura; Mishchenko, Konstantin Adaptive Gradient Descent without Descent, Proceedings of the 37th International Conference on Machine Learning, Volume 119, PMLR (2020), pp. 6702-6712

[33] Malitsky, Yura; Mishchenko, Konstantin Adaptive Proximal Gradient Method for Convex Optimization (2023) | arXiv

[34] Montanari, Andrea; Richard, Emile Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics, IEEE Trans. Inf. Theory, Volume 62 (2016) no. 3, pp. 1458-1484 | MR | DOI | Zbl

[35] Mordukhovich, Boris S. Variational Analysis and Applications, Springer, 2018 | MR | DOI

[36] Moré, Jorge J.; Wild, Stefan M. Benchmarking Derivative-Free Optimization Algorithms, SIAM J. Optim., Volume 20 (2009) no. 1, pp. 172-191 | MR | DOI | Zbl

[37] Nesterov, Yurii; Nemirovkii, Arkadii Interior-Point Polynomial Algorithms in Convex Programming, Society for Industrial and Applied Mathematics, 1994 | MR | DOI

[38] Rockafellar, R. Tyrrell; Wets, Roger J. B. Variational analysis, Grundlehren der Mathematischen Wissenschaften, 317, Springer, 1998 | DOI

[39] Salzo, Saverio The Variable Metric Forward-Backward Splitting Algorithm Under Mild Differentiability Assumptions, SIAM J. Optim., Volume 27 (2017) no. 4, pp. 2153-2181 | MR | DOI | Zbl

[40] Sopasakis, Pantelis; Fresk, Emil; Patrinos, Panagiotis OpEn: Code Generation for Embedded Nonconvex Optimization, IFAC-PapersOnLine, Volume 53 (2020) no. 2, pp. 6548-6554 (21st IFAC World Congress) | DOI

[41] Themelis, Andreas; Stella, Lorenzo; Patrinos, Panagiotis Forward-Backward Envelope for the Sum of Two Nonconvex Functions: Further Properties and Nonmonotone Linesearch Algorithms, SIAM J. Optim., Volume 28 (2018) no. 3, pp. 2274-2303 | MR | DOI | Zbl

[42] Valkonen, Tuomo Interior-proximal primal-dual methods, Appl. Anal. Optim., Volume 3 (2019) no. 1, pp. 1-28 | MR | Zbl

[43] Vanderbei, Robert J.; Shanno, David F. An Interior-Point Algorithm for Nonconvex Nonlinear Programming, Comput. Optim. Appl., Volume 13 (1999) no. 1, pp. 231-252 | MR | DOI | Zbl

[44] Wächter, Andreas; Biegler, Lorenz T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., Volume 106 (2006) no. 1, pp. 25-57 | DOI | Zbl | MR

[45] Wang, Xianfu; Wang, Ziyuan A Bregman inertial forward-reflected-backward method for nonconvex minimization, J. Glob. Optim., Volume 89 (2023) no. 2, pp. 327-354 | DOI | Zbl | MR

[46] Wright, Margaret H. The interior-point revolution in optimization: history, recent developments, and lasting consequences, Bull. Am. Math. Soc., Volume 42 (2005) no. 1, pp. 39-56 | MR | DOI | Zbl

[47] Wright, Stephen J. Primal-Dual Interior-Point Methods, Society for Industrial and Applied Mathematics, 1997 | DOI | MR

[48] Xu, Zongben; Chang, Xiangyu; Xu, Fengmin; Zhang, Hai $L_{1/2}$ Regularization: A Thresholding Representation Theory and a Fast Solver, IEEE Trans. Neural Netw. Learn. Syst., Volume 23 (2012) no. 7, pp. 1013-1027 | DOI

[49] Yang, Tong; Jordan, Michael I.; Chavdarova, Tatjana Solving Constrained Variational Inequalities via a First-order Interior Point-based Method, The Eleventh International Conference on Learning Representations (ICLR) (2023)