-regularization subproblems: strong duality and an eigensolver-based algorithm
From MaRDI portal
Publication:2114814
DOI10.1007/S10589-021-00341-ZzbMATH Open1487.90609arXiv2109.01829OpenAlexW3198203964MaRDI QIDQ2114814FDOQ2114814
Authors: Liaoyuan Zeng, Ting Kei Pong 
Publication date: 15 March 2022
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Abstract: Trust-region (TR) type method, based on a quadratic model such as the trust-region subproblem (TRS) and -regularization subproblem (RS), 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 RS 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 RS's, and on a new class of regularized problem that combines TRS and RS, to illustrate our algorithm.
Full work available at URL: https://arxiv.org/abs/2109.01829
Recommendations
- A regularized strong duality for nonsymmetric semidefinite least squares problem
- scientific article; zbMATH DE number 4069627
- scientific article
- Strong convergence of a regularization algorithm for common solutions with applications
- On regularization in multiparameter eigenvalue problems
- \(S_{1/2}\) regularization methods and fixed point algorithms for affine rank minimization problems
- Theory and application of \(p\)-regularized subproblems for \(p>2\)
- Solving regularized total least squares problems based on eigenproblems
- A dual regularized method in convex finite-dimensional optimization problems
- scientific article; zbMATH DE number 6500912
Cites Work
- Computing a Trust Region Step
- Solving the Trust-Region Subproblem using the Lanczos Method
- Convex Analysis
- Title not available (Why is that?)
- Trust Region Methods
- Title not available (Why is that?)
- The generalized trust region subproblem
- Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
- Convex analysis and nonlinear optimization. Theory and examples
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- A new matrix-free algorithm for the large-scale trust-region subproblem
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- On solving trust-region and other regularised subproblems in optimization
- Minimizing a quadratic over a sphere
- Cubic regularization of Newton method and its global performance
- The trust region subproblem and semidefinite programming*
- Algorithm 873
- Solving the Trust-Region Subproblem By a Generalized Eigenvalue Problem
- Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem
- Theory and application of p-regularized subproblems for p>2
- Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
Uses Software
This page was built for publication: \(\rho\)-regularization subproblems: strong duality and an eigensolver-based algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2114814)
