Optimization Online


Identifying Active Manifolds in Regularization Problems

Warren Hare (warren.hare***at***ubc.ca)

Abstract: In this work we consider the problem $\min_x \{ f(x) + P(x) \}$, where $f$ is $\mathcal{C}^2$ and $P$ is nonsmooth, but contains an underlying smooth substructure. Specifically, we assume the function $P$ is prox-regular partly smooth with respect to a active manifold $\M$. Recent work by Tseng and Yun \cite{tseng-yun-2009}, showed that such a problem can be approached by minimizing the sum of a quadratic approximation of $f$ and the prox-regular partly smooth function $P$ $$x_{k+1} = \min_x \{ \langle \nabla f(x_k), x - x_k \rangle + (x - x_k)' H_k (x - x_k) + P(p)\}.$$ When $P$ is well structured this provides a practical approach to solving the original problem. In this work we examine Tseng and Yun's approach in terms of active set identification. In particular, we show that this method will correctly identify the active manifold $\M$ in a finite number of iteration. Furthermore, we confirm a conjecture of Tseng that, regardless of what technique is used to solve the original problem, the subproblem $p_k = \argmin_p \{ \langle \nabla f(x_k), p \rangle + \frac{r}{2}|x_k - p|^2 + P(p)\}$ would correctly identify the active manifold in a finite number of iterations.

Keywords: Nonconvex Optimization, Active Constraint Identification, Regularization Problems, Prox-regular, Partly Smooth

Category 1: Convex and Nonsmooth Optimization (Generalized Convexity/Monoticity )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 11/23/2009
Entry Accepted: 11/23/2009
Entry Last Modified: 12/05/2009

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 Programming Society