On the p-regularized trust region subproblem

Abstract

The $p$-regularized subproblem (p-RS) is a regularisation technique in computing a Newton-like step for unconstrained optimization, which globally minimizes a local quadratic approximation of the objective function while incorporating with a weighted regularisation term $\frac{\sigma }{p}\Vert x{\Vert }^p$. The global solution of the $p$-regularized subproblem for $p=3$, also known as the cubic regularization, has been characterized in literature. In this paper, we resolve both the global and the local non-global minimizers of (p-RS) for $p>2$ with necessary and sufficient optimality conditions. Moreover, we prove a parallel result of Mart\'ınez \cite{Mar} that the (p-RS) for $p>2$, analogous to the trust region subproblem, can have at most one local non-global minimizer. When the (p-RS) is subject to a fixed number $m$ additional linear inequality constraints, we show that the uniqueness of the local solution of the (p-RS) (if exists at all), especially for $p=4$, can be applied to solve such an extension in polynomial time.

19pages

References in corpus (1)

• Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity

Cited by in corpus (4)

• Trust-region and $p$-regularized subproblems: local nonglobal minimum is the second smallest objective function value among all first-order stationary points
• A survey of hidden convex optimization
• Unifying Farkas lemma and S-lemma: new theory and applications in nonquadratic nonconvex optimization
• Local Optimality Conditions for a Class of Hidden Convex Optimization