An inexact first-order method for constrained nonlinear optimization

Abstract

The primary focus of this paper is on designing an inexact first-order algorithm for solving constrained nonlinear optimization problems. By controlling the inexactness of the subproblem solution, we can significantly reduce the computational cost needed for each iteration. A penalty parameter updating strategy during the process of solving the subproblem enables the algorithm to automatically detect infeasibility. Global convergence for both feasible and infeasible cases is proved. Complexity analysis for the KKT residual is also derived under mild assumptions. Numerical experiments exhibit the ability of the proposed algorithm to rapidly find inexact optimal solution through cheap computational cost.

Keywords:

• Nonlinear optimization
• sequential linear optimization
• constrained problems
• exact penalty functions
• convex composite optimization
• first-order methods

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 https://github.com/DataCorrupted/FoNCO.

Additional information

Notes on contributors

Hao Wang

Dr. Hao Wang obtained his PhD degree in Industrial Engineering, Lehigh University, USA in May 2015, and received his Bachelor's and Master's degree in Mathematics, Beihang University (BUAA) in 2010 and 2007, respectively. He has participated in research internship opportunities at ExxonMobil Corporate Strategic Research Lab, Mitsubishi Electric Research Lab, and GroupM R&D Department during his PhD study. Hao has worked in the area of nonlinear optimization and machine learning. His research has been published in the top journal SIAM Journal on Optimization. His current interests include penalty methods, inexact algorithms, regularization problems, and many other machine learning problems. Dr Hao Wang joined the School of Information Science and Technology at ShanghaiTech University as an Assistant Professor, PI, in March 2016.

Fan Zhang

Fan Zhang is a PhD candidate from School of Information Science and Technology at ShanghaiTech University, supervised by Hao Wang. His research interests are at the intersection of Optimization and Machine Learning.

Jiashan Wang

Jiashan Wang obtained his PhD from the mathematics department of the University of Washington with a research focus on large scale optimization algorithms.

Yuyang Rong

Yuyang Rong gained his Bachelor's degree from the School of Information Science and Technology at ShanghaiTech University. He is now a PhD candidate at UC Davis. His research interest is now software security.