Principled algorithms for finding local minima
Abstract/Contents
- Abstract
- Convex optimization is the cornerstone of continuous optimization, but many real problems arising in machine learning and operations research are nonconvex. This two part thesis explores my work developing principled algorithms for finding local minima of nonconvex functions. Part I: The complexity of finding stationary points of nonconvex functions. For a long time, it was known that gradient descent achieved an $\epsilon^{-2}$ rate for finding stationary points of unconstrained nonconvex functions, but better rates for first-order methods were unknown. We show that, using an algorithm that judiciously utilizes Nesterov's accelerated gradient descent, it is possible to improve this rate to $\epsilon^{-7/4}$ rate for functions with Lipschitz first and second derivatives. Adding Lipschitz third derivatives improves this rate to $\epsilon^{-5/3}$. Moreover, we provide almost matching lower bounds to prove that (i) finding a stationary point is easier for convex functions and (ii) acceleration in nonconvex optimization requires assumptions beyond smoothness. Part II: Interior point methods for nonconvex optimization. The second part of this thesis focuses on an interior point method (IPM) for optimization problems with nonconvex constraints. The work of Wachter and Biegler suggests that infeasible-start interior point methods (IPMs) developed for linear programming cannot be adapted to nonlinear optimization without significant modification, i.e., using a two-phase or penalty method. We propose an IPM that, by careful initialization and updates of the slack variables, is guaranteed to find a first-order certificate of local infeasibility, local optimality or unboundedness of the (shifted) feasible region. Our proposed algorithm differs from other IPM methods for nonconvex programming because we reduce primal feasibility at the same rate as the barrier parameter. This gives an algorithm with more robust convergence properties and closely resembles successful algorithms from linear programming. Comparisons with IPOPT on a subset of CUTEst problems indicate less frequent failures and superior performance for detecting infeasibility. Finally, we develop a highly simplified version of our IPM method with nonconvex constraints that obtains an $\epsilon$-scaled KKT point in $\epsilon^{-7/4}$ iterations. This provides the first proof that IPMs with nonconvex constraints have a polynomial runtime in $1/\epsilon$.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Hinder, Oliver |
|---|---|
| Degree supervisor | Ye, Yinyu |
| Thesis advisor | Ye, Yinyu |
| Thesis advisor | Saunders, Michael A |
| Thesis advisor | Sidford, Aaron |
| Degree committee member | Saunders, Michael A |
| Degree committee member | Sidford, Aaron |
| Associated with | Stanford University, Department of Management Science and Engineering. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Oliver Hinder. |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Oliver Hamilton Hinder
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...