An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
From MaRDI portal
Abstract: Powerful interior-point methods (IPM) based commercial solvers, such as Gurobi and Mosek, have been hugely successful in solving large-scale linear programming (LP) problems. The high efficiency of these solvers depends critically on the sparsity of the problem data and advanced matrix factorization techniques. For a large scale LP problem with data matrix that is dense (possibly structured) or whose corresponding normal matrix has a dense Cholesky factor (even with re-ordering), these solvers may require excessive computational cost and/or extremely heavy memory usage in each interior-point iteration. Unfortunately, the natural remedy, i.e., the use of iterative methods based IPM solvers, although can avoid the explicit computation of the coefficient matrix and its factorization, is not practically viable due to the inherent extreme ill-conditioning of the large scale normal equation arising in each interior-point iteration. To provide a better alternative choice for solving large scale LPs with dense data or requiring expensive factorization of its normal equation, we propose a semismooth Newton based inexact proximal augmented Lagrangian ({sc Snipal}) method. Different from classical IPMs, in each iteration of {sc Snipal}, iterative methods can efficiently be used to solve simpler yet better conditioned semismooth Newton linear systems. Moreover, {sc Snipal} not only enjoys a fast asymptotic superlinear convergence but is also proven to enjoy a finite termination property. Numerical comparisons with Gurobi have demonstrated encouraging potential of {sc Snipal} for handling large-scale LP problems where the constraint matrix has a dense representation or has a dense factorization even with an appropriate re-ordering.
Recommendations
- An augmented Lagrangian based semismooth Newton method for a class of bilinear programming problems
- The linear and asymptotically superlinear convergence rates of the augmented Lagrangian method with a practical relative error criterion
- Superlinearly convergent approximate Newton methods for LC\(^ 1\) optimization problems
- On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
- An efficient augmented Lagrangian method with semismooth Newton solver for total generalized variation
- scientific article; zbMATH DE number 1329062
- Analysis on a superlinearly convergent augmented Lagrangian method
- The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming
Cites work
- A Class of Inexact Variable Metric Proximal Point Algorithms
- A family of variable metric proximal methods
- A new class of preconditioners for large-scale linear systems from interior point methods for linear programming
- A Newton method for linear programming
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A Variable Metric Proximal Point Algorithm for Monotone Operators
- An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems
- Asymptotic Convergence Analysis of the Proximal Point Algorithm
- Augmented Lagrangian method for large-scale linear programming problems
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Clustering with qualitative information
- Convex Analysis
- Convex analysis and monotone operator theory in Hilbert spaces
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- scientific article; zbMATH DE number 4015993 (Why is no real title available?)
- scientific article; zbMATH DE number 4033496 (Why is no real title available?)
- scientific article; zbMATH DE number 4059113 (Why is no real title available?)
- scientific article; zbMATH DE number 1306982 (Why is no real title available?)
- scientific article; zbMATH DE number 1953446 (Why is no real title available?)
- scientific article; zbMATH DE number 1559033 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- Implementation of an interior point method with basis preconditioning
- Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning
- Implementing proximal point methods for linear programming
- Monotone Operators and the Proximal Point Algorithm
- Nonlinear Perturbation of Linear Programs
- Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
- Nonsmooth equations in optimization. Regularity, calculus, methods and applications
- On finite termination of an iterative method for linear complementarity problems
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
- On the minimum norm solution of linear programs
- On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating
- Optimization and nonsmooth analysis
- Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming
- Preconditioning indefinite systems in interior point methods for large scale linear optimisation
- Preconditioning indefinite systems in interior point methods for optimization
- Proximal quasi-Newton methods for nondifferentiable convex optimization
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Some continuity properties of polyhedral multifunctions
- Testing and non-linear preconditioning of the proximal point method
- Variational Analysis
Cited in
(28)- An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems
- An augmented Lagrangian based semismooth Newton method for a class of bilinear programming problems
- scientific article; zbMATH DE number 1329062 (Why is no real title available?)
- A Feasible Semismooth Gauss-Newton Method for Solving a Class of SLCPs
- An ADMM-based interior-point method for large-scale linear programming
- Efficient sparse Hessian-based semismooth Newton algorithms for Dantzig selector
- A primal-dual flow for affine constrained convex optimization
- General-purpose preconditioning for regularized interior point methods
- A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
- A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
- Faster first-order primal-dual methods for linear programming using restarts and sharpness
- Fast sinkhorn. II: Collinear triangular matrix and linear time accurate computation of optimal transport
- A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
- A fast and effective algorithm for sparse linear regression with \(\ell_p\)-norm data fidelity and elastic net regularization
- A highly efficient algorithm for solving exclusive lasso problems
- An accelerated proximal alternating direction method of multipliers for optimal decentralized control of uncertain systems
- Nonconvex truncated conditional value at risk-based sparse linear regression
- Optimization over convex polyhedra via Hadamard parametrizations
- A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
- An efficient active-set method with applications to sparse approximations and risk minimization
- An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems
- On the geometry and refined rate of primal-dual hybrid gradient for linear programming
- An efficient algorithm for the _p norm based metric nearness problem
- Accelerating preconditioned ADMM via degenerate proximal point mappings
- On the analysis of semismooth Newton-type methods for composite optimization
- A sparse smoothing Newton method for solving discrete optimal transport problems
- Multiple regression for matrix and vector predictors: models, theory, algorithms, and beyond
- Fast computation of superquantile-constrained optimization through implicit scenario reduction
This page was built for publication: An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124003)
