Theory and application of p-regularized subproblems for p>2

DOI10.1080/10556788.2016.1238917zbMATH Open1379.49022arXiv1409.4665OpenAlexW2558881672MaRDI QIDQ4594845FDOQ4594845

Authors: Yong Hsia, Ruey-Lin Sheu, Yaxiang Yuan 

Publication date: 24 November 2017

Published in: Optimization Methods \& Software (Search for Journal in Brave)

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 $fracsigmap|x{|}^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'{i}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.

Full work available at URL: https://arxiv.org/abs/1409.4665

Recommendations

• \(\rho\)-regularization subproblems: strong duality and an eigensolver-based algorithm
• P-regularity theory: applications to optimization
• Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming
• On local nonglobal minimum of trust-region subproblem and extension
• Optimality conditions for the constrained \(L_p\)-regularization

zbMATH Keywords

combinatorial optimizationnonlinear optimizationtrust-region subproblemweighted regularizationextended trust-region subproblemlocal non-global minimizer

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26) Optimality conditions for solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) (49K30)

Cited In (9)

• \(\rho\)-regularization subproblems: strong duality and an eigensolver-based algorithm
• A survey of hidden convex optimization
• A filter sequential adaptive cubic regularization algorithm for nonlinear constrained optimization
• P-regularity theory: applications to optimization
• New subspace minimization conjugate gradient methods based on regularization model for unconstrained optimization
• \(L_p\)-norm regularization algorithms for optimization over permutation matrices
• The maximal subspace for generation of \((a, k)\)-regularized families
• A sequential adaptive regularisation using cubics algorithm for solving nonlinear equality constrained optimization
• On local nonglobal minimum of trust-region subproblem and extension

This page was built for publication: Theory and application of \(p\)-regularized subproblems for \(p>2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4594845)