-regularization subproblems: strong duality and an eigensolver-based algorithm
From MaRDI portal
Publication:2114814
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.
Recommendations
- A regularized strong duality for nonsymmetric semidefinite least squares problem
- scientific article; zbMATH DE number 4069627
- scientific article; zbMATH DE number 6496962
- 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
- scientific article; zbMATH DE number 439380 (Why is no real title available?)
- scientific article; zbMATH DE number 1807400 (Why is no real title available?)
- A new matrix-free algorithm for the large-scale trust-region subproblem
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- Algorithm 873
- Computing a Trust Region Step
- Convex Analysis
- Convex analysis and nonlinear optimization. Theory and examples
- Cubic regularization of Newton method and its global performance
- Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
- Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
- Minimizing a quadratic over a sphere
- On solving trust-region and other regularised subproblems in optimization
- Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem
- Solving the Trust-Region Subproblem using the Lanczos Method
- Solving the trust-region subproblem by a generalized eigenvalue problem
- The generalized trust region subproblem
- The trust region subproblem and semidefinite programming*
- Theory and application of \(p\)-regularized subproblems for \(p>2\)
- Trust Region Methods
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)
