TY - JOUR
T1 - ρ -regularization subproblems
T2 - strong duality and an eigensolver-based algorithm
AU - Zeng, Liaoyuan
AU - Pong, Ting Kei
N1 - Funding Information:
Ting Kei Pong was supported in part by an internal funding, G-UAKK, of the Hong Kong Polytechnic University.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2022/3
Y1 - 2022/3
N2 - Trust-region (TR) type method, based on a quadratic model such as the trust-region subproblem (TRS) and p-regularization subproblem (pRS), is arguably one of the most successful methods for unconstrained minimization. In this paper, we study a general regularized subproblem (named ρRS), which covers TRS and pRS as special cases. We derive a strong duality theorem for ρRS, and also its necessary and sufficient optimality condition under general assumptions on the regularization term. We then define the Rendl–Wolkowicz (RW) dual problem of ρRS, which is a maximization problem whose objective function is concave, and differentiable except possibly at two points. It is worth pointing out that our definition is based on an alternative derivation of the RW-dual problem for TRS. Then we propose an eigensolver-based algorithm for solving the RW-dual problem of ρRS. The algorithm is carried out by finding the smallest eigenvalue and its unit eigenvector of a certain matrix in each iteration. Finally, we present numerical results on randomly generated pRS’s, and on a new class of regularized problem that combines TRS and pRS, to illustrate our algorithm.
AB - Trust-region (TR) type method, based on a quadratic model such as the trust-region subproblem (TRS) and p-regularization subproblem (pRS), is arguably one of the most successful methods for unconstrained minimization. In this paper, we study a general regularized subproblem (named ρRS), which covers TRS and pRS as special cases. We derive a strong duality theorem for ρRS, and also its necessary and sufficient optimality condition under general assumptions on the regularization term. We then define the Rendl–Wolkowicz (RW) dual problem of ρRS, which is a maximization problem whose objective function is concave, and differentiable except possibly at two points. It is worth pointing out that our definition is based on an alternative derivation of the RW-dual problem for TRS. Then we propose an eigensolver-based algorithm for solving the RW-dual problem of ρRS. The algorithm is carried out by finding the smallest eigenvalue and its unit eigenvector of a certain matrix in each iteration. Finally, we present numerical results on randomly generated pRS’s, and on a new class of regularized problem that combines TRS and pRS, to illustrate our algorithm.
UR - http://www.scopus.com/inward/record.url?scp=85122850710&partnerID=8YFLogxK
U2 - 10.1007/s10589-021-00341-z
DO - 10.1007/s10589-021-00341-z
M3 - Journal article
AN - SCOPUS:85122850710
VL - 81
SP - 337
EP - 368
JO - Computational Optimization and Applications
JF - Computational Optimization and Applications
SN - 0926-6003
IS - 2
ER -