$$\rho$$ ρ -regularization subproblems: strong duality and an eigensolver-based algorithm

Liaoyuan Zeng () and Ting Kei Pong ()
Additional contact information
Liaoyuan Zeng: The Hong Kong Polytechnic University
Ting Kei Pong: The Hong Kong Polytechnic University

Computational Optimization and Applications, 2022, vol. 81, issue 2, No 1, 337-368

Abstract: Abstract 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 $$\rho$$ ρ RS), which covers TRS and pRS as special cases. We derive a strong duality theorem for $$\rho$$ ρ 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 $$\rho$$ ρ 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 $$\rho$$ ρ 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.

Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-021-00341-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:81:y:2022:i:2:d:10.1007_s10589-021-00341-z

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-021-00341-z

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().