Facial reduction and partial polyhedrality
From MaRDI portal
Abstract: We present FRA-Poly, a facial reduction algorithm (FRA) for conic linear programs that is sensitive to the presence of polyhedral faces in the cone. The main goals of FRA and FRA-Poly are the same, i.e., finding the minimal face containing the feasible region and detecting infeasibility, but FRA-Poly treats polyhedral constraints separately. This idea enables us to reduce the number of iterations drastically when there are many linear inequality constraints. The worst case number of iterations for FRA-poly is written in the terms of a "distance to polyhedrality" quantity and provides better bounds than FRA under mild conditions. In particular, in the case of the doubly nonnegative cone, FRA-Poly gives a worst case bound of whereas the classical FRA is . Of possible independent interest, we prove a variant of Gordan-Stiemke's Theorem and a proper separation theorem that takes into account partial polyhedrality. We provide a discussion on the optimal facial reduction strategy and an instance that forces FRAs to perform many steps. We also present a few applications. In particular, we will use FRA-poly to improve the bounds recently obtained by Liu and Pataki on the dimension of certain affine subspaces which appear in weakly infeasible problems.
Recommendations
- Facial reduction algorithms for conic optimization problems
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- Strong duality in conic linear programming: facial reduction and extended duals
- Facial reduction in partially finite convex programming
Cites work
- A bound on the Carathéodory number
- A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
- A relaxed-certificate facial reduction algorithm based on subspace intersection
- A structural geometrical analysis of weakly infeasible SDPS
- Coordinate shadows of semidefinite and Euclidean distance matrices
- Error Bounds for Linear Matrix Inequalities
- Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
- Facial reduction algorithms for conic optimization problems
- Finding an interior point in the optimal face of linear programs
- Handbook of semidefinite programming. Theory, algorithms, and applications
- scientific article; zbMATH DE number 3728055 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 1534289 (Why is no real title available?)
- Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
- Initialization in semidefinite programming via a self-dual skew-symmetric embedding
- On polyhedral extension of some LP theorems
- Polyhedral and semidefinite programming methods in combinatorial optimization
- Polyhedral extensions of some theorems of linear programming
- Preprocessing and regularization for degenerate semidefinite programs
- Regularizing the abstract convex program
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Strong duality and minimal representations for cone optimization
- Strong duality in conic linear programming: facial reduction and extended duals
- Weak infeasibility in second order cone programming
Cited in
(18)- Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
- A relaxed-certificate facial reduction algorithm based on subspace intersection
- Kurdyka-Łojasiewicz exponent via inf-projection
- Amenable cones: error bounds without constraint qualifications
- Coincidences of simplex centers and related facial structures
- Facial reduction algorithms for conic optimization problems
- Solving SDP completely with an interior point oracle
- Refining the partition for multifold conic optimization problems
- Facially dual complete (nice) cones and lexicographic tangents
- Strong duality in conic linear programming: facial reduction and extended duals
- A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms
- Error bounds, facial residual functions and applications to the exponential cone
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- On the longest chain of faces of the completely positive and copositive cones
- Closing duality gaps of SDPs completely through perturbation when singularity degree is one
- Convergence rate of alternating projection method for the intersection of an affine subspace and the second-order cone
- Tight error bounds for log-determinant cones without constraint qualifications
- Facial structure of copositive and completely positive cones over a second-order cone
This page was built for publication: Facial reduction and partial polyhedrality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4586172)
