Optimization Online


Run-and-Inspect Method for Nonconvex Optimization and Global Optimality Bounds for R-Local Minimizers

Yifan Chen (chenyifan14***at***mails.tsinghua.edu.cn)
Yuejiao Sun (sunyj***at***math.ucla.edu)
Wotao Yin (wotaoyin***at***math.ucla.edu)

Abstract: Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers and occasionally stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an "inspect" phase to existing algorithms that helps escape from non-global stationary points. The inspection samples a set of points in a radius $R$ around the current point. When a sample point yields a sufficient decrease in the objective, we move there and resume an existing algorithm. If no sufficient decrease is found, the current point is called an approximate $R$-local minimizer. We show that an $R$-local minimizer is globally optimal, up to a specific error depending on $R$, if the objective function can be implicitly decomposed into a smooth convex function plus a restricted function that is possibly nonconvex, nonsmooth. For high-dimensional problems, we introduce blockwise inspections to overcome the curse of dimensionality while still maintaining optimality bounds up to a factor equal to the number of blocks. Our method performs well on a set of artificial and realistic nonconvex problems by coupling with gradient descent, coordinate descent, EM, and prox-linear algorithms.

Keywords: R-local minimizer, Run-and-Inspect Method, nonconvex optimization, global minimum, global optimality

Category 1: Global Optimization (Theory )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: UCLA CAM 17-67

Download: [PDF]

Entry Submitted: 11/18/2017
Entry Accepted: 12/01/2017
Entry Last Modified: 12/01/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society