Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
From MaRDI portal
Abstract: We study the problem of detecting infeasibility of large-scale linear programming problems using the primal-dual hybrid gradient method (PDHG) of Chambolle and Pock (2011). The literature on PDHG has mostly focused on settings where the problem at hand is assumed to be feasible. When the problem is not feasible, the iterates of the algorithm do not converge. In this scenario, we show that the iterates diverge at a controlled rate towards a well-defined ray. The direction of this ray is known as the infimal displacement vector . The first contribution of our work is to prove that this vector recovers certificates of primal and dual infeasibility whenever they exist. Based on this fact, we propose a simple way to extract approximate infeasibility certificates from the iterates of PDHG. We study three different sequences that converge to the infimal displacement vector: the difference of iterates, the normalized iterates, and the normalized average. All of them are easy to compute, and thus the approach is suitable for large-scale problems. Our second contribution is to establish tight convergence rates for these sequences. We demonstrate that the normalized iterates and the normalized average achieve a convergence rate of , improving over the known rate of . This rate is general and applies to any fixed-point iteration of a nonexpansive operator. Thus, it is a result of independent interest since it covers a broad family of algorithms, including, for example, ADMM, and can be applied settings beyond linear programming, such as quadratic and semidefinite programming. Further, in the case of linear programming we show that, under nondegeneracy assumptions, the iterates of PDHG identify the active set of an auxiliary feasible problem in finite time, which ensures that the difference of iterates exhibits eventual linear convergence to the infimal displacement vector.
Recommendations
- Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
- Polynomiality of infeasible-interior-point algorithms for linear programming
- Detecting infeasibility in infeasible-interior-point methods for optimization
- Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming
- Certificates of primal or dual infeasibility in linear programming
Cites work
- A \(\mathcal{VU}\)-algorithm for convex minimization
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
- Accelerated first-order methods for hyperbolic programming
- Active Sets, Nonsmoothness, and Sensitivity
- Algorithms for nonlinear constraints that use lagrangian functions
- An introduction to continuous optimization for imaging
- Asymptotic behavior of contractions in Hilbert space
- Computational techniques of the simplex method
- Computer Codes for the Analysis of Infeasible Linear Programs
- Conflict analysis in mixed integer programming
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Convergence rate analysis of several splitting schemes
- Convergence rates of forward-Douglas-Rachford splitting method
- Convex Analysis
- Convex analysis and monotone operator theory in Hilbert spaces
- Convex analysis and nonlinear optimization. Theory and examples.
- Exposing Constraints
- Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
- Finite termination of the proximal point algorithm
- First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 3671159 (Why is no real title available?)
- scientific article; zbMATH DE number 3740353 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1349588 (Why is no real title available?)
- Identifiable Surfaces in Constrained Optimization
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Local convergence properties of Douglas-Rachford and alternating direction method of multipliers
- Local linear convergence analysis of primal-dual splitting methods
- On finite convergence and constraint identification of subgradient projection methods
- On the convergence of primal-dual hybrid gradient algorithm
- On the convergence of projected gradient processes to singular critical points
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting
- On the Identification of Active Constraints
- On the Identification of Active Constraints II: The Nonconvex Case
- On the minimal displacement vector of the Douglas-Rachford operator
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Optimality, identifiability, and sensitivity
- OSQP: an operator splitting solver for quadratic programs
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Primal-Dual Gradient Structured Functions: Second-Order Results; Links to Epi-Derivatives and Partly Smooth Functions
- Projected gradient methods for linearly constrained problems
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Subgradient methods for huge-scale optimization problems
- The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces
- 𝒱𝒰-smoothness and proximal point results for some nonconvex functions
This page was built for publication: Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6188510)
