condition measures – Optimization Online

Level-Set Geometry and the Theoretical Performance of PDHG for Conic Linear Optimization

Published: 2026/09/30

We consider solving (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) — with heuristic enhancements and GPU implementation — has been very successful in solving huge-scale linear optimization problems (LPs). However, its application to more general conic convex optimization problems is … Read more

Projection and rescaling algorithm for finding most interior solutions to polyhedral conic systems

Published: 2020/03/19

Convex Optimization, Linear Programming condition measures, conic systems, duality, projection, rescaling

We propose a simple projection and rescaling algorithm that finds {\em most interior} solutions to the pair of feasibility problems \[ \text{find} x\in L\cap \R^n_{+} \text{ and } \text{find} \; \hat x\in L^\perp\cap\R^n_{+}, \] where $L$ is a linear subspace of $\R^n$ and $L^\perp$ is its orthogonal complement. The algorithm complements a basic procedure that … Read more

An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

Published: 2019/10/08, Updated: 2020/12/28

Convex Optimization, Linear Programming, Nonsmooth Optimization certificates, complexity, condition measures, ellipsoid algorithm, linear inequalities

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two … Read more

Equivalences among the chi measure, Hoffman constant, and Renegar’s distance to ill-posedness

Published: 2019/05/15

Convex Optimization, Linear Programming, Polyhedra chi measure, condition measures, distance to ill-posedness, hoffman constant, signed matrices

We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a … Read more

Condition and complexity measures for infeasibility certificates of systems of linear inequalities and their sensitivity analysis

Published: 2002/05/21

Linear, Cone and Semidefinite Programming complexity, condition measures, convex optimization, interior point methods, linear inequality systems, linear programming

We begin with a study of the infeasibility measures for linear programming problems. For this purpose, we consider feasibility problems in Karmarkar’s standard form. Our main focus is on the complexity measures which can be used to bound the amount of computational effort required to solve systems of linear inequalities and related problems in certain … Read more