Special Seminar – Faculty Candidate Yue Xie

Title – On Complexity of Constrained Nonconvex Optimization
Abstract
Deriving complexity guarantees for nonconvex optimization problems are driven by long standing theoretical interests and by their relevance to machine learning and data science. This talk discusses complexity of algorithms for two important types of constrained nonconvex optimization problems: bound-constrained and nonlinear equality constrained optimization. Applications include nonnegative matrix factorization (NMF) and dictionary learning.

For nonconvex optimization with bound constraints, we observe from the past work that pursuit of the state-of-art complexity guarantees can compromise the practicality of an algorithm. Therefore, we propose two practical projected Newton types of methods with complexity guarantees matching the best known. The first method is a scaled variant of Bertsekas’ two-metric projection method, with the best complexity guarantee to find an approximate first-order point. The second is a projected Newton-Conjugate Gradient method, equipped with a competitive complexity guarantee to locate an approximate second-order point with high probability. Preliminary numerical experiments on NMF indicate practicality of the latter algorithm.

For nonconvex optimization with nonlinear equality constraints, we analyze complexity of the proximal augmented Lagrangian (AL) framework, in which a Newton-Conjugate-Gradient scheme is used to find approximate solutions of the subproblems. This scheme has three levels of iterations, and we obtain bounds on the number of iterations at each level.

These are joint works with Stephen J. Wright.

For zoom information email Meg Tully  – [email protected]