PAL-Hom method for QP and an application to LP
From MaRDI portal
Abstract: In this paper, a proximal augmented Lagrangian homotopy (PAL-Hom) method for solving convex quadratic programming problems is proposed. This method takes the proximal augmented Lagrangian method as the outer iteration. To solve the proximal augmented Lagrangian subproblems, a homotopy method is presented as the inner iteration. The homotopy method tracks the piecewise-linear solution path of a parametric quadratic programming problem whose start problem takes an approximate solution as its solution and the target problem is the subproblem to be solved. To improve the performance of the homotopy method, the accelerated proximal gradient method is used to obtain a fairly good approximate solution that implies a good prediction of the optimal active set. Moreover, a sorting technique for the Cholesky factor update as well as an -relaxation technique for checking primal-dual feasibility and correcting the active sets are presented to improve the efficiency and robustness of the homotopy method. Simultaneously, a proximal-point-based AL-Hom method which is shown to converge in finite number of steps, is applied to linear programming. Numerical experiments on randomly generated problems and the problems from the CUTEr and Netlib test collections, support vector machines (SVMs) and contact problems of elasticity demonstrate that PAL-Hom is faster than the active-set methods and the parametric active set methods and is competitive to the interior-point methods and the specialized algorithms designed for specific models (e.g., sequential minimal optimization (SMO) method for SVMs).
Recommendations
- QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
- scientific article; zbMATH DE number 1092140
- A reduced proximal-point homotopy method for large-scale non-convex BQP
- scientific article; zbMATH DE number 751232
- Primal and dual active-set methods for convex quadratic programming
Cites work
- A General Quadratic Programming Algorithm
- A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds
- A method for solving nonlinear maximum‐problems depending on parameters
- A New Active Set Algorithm for Box Constrained Optimization
- A new polynomial-time algorithm for linear programming
- An Algorithm for Large-Scale Quadratic Programming
- An online active set strategy to overcome the limitations of explicit MPC
- Analysis on a superlinearly convergent augmented Lagrangian method
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Augmented Lagrangians with Adaptive Precision Control for Quadratic Programming with Simple Bounds and Equality Constraints
- CUTE
- Duality-based domain decomposition with natural coarse-space for variational inequalities
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3850845 (Why is no real title available?)
- scientific article; zbMATH DE number 107545 (Why is no real title available?)
- scientific article; zbMATH DE number 1215253 (Why is no real title available?)
- scientific article; zbMATH DE number 3309655 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- Implementing proximal point methods for linear programming
- Iterative Solution of Linear Programs
- Methods for convex and general quadratic programming
- Multiplier and gradient methods
- Newton's Method for Large Bound-Constrained Optimization Problems
- Nonlinear Perturbation of Linear Programs
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- On the Implementation of a Primal-Dual Interior Point Method
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- Optimization Methods in Finance
- Primal and dual active-set methods for convex quadratic programming
- qpOASES: a parametric active-set algorithm for~quadratic programming
- Smooth minimization of non-smooth functions
- Solution of contact problems by FETI domain decomposition with natural coarse space projections
- Solving large-scale linear programs by interior-point methods under the Matlab∗Environment†
- Stable reduced Hessian updates for indefinite quadratic programming
- Working set selection using second order information for training support vector machines
Describes a project that uses
Uses Software
This page was built for publication: PAL-Hom method for QP and an application to LP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419548)
