Two properties of condition numbers for convex programs via implicitly defined barrier functions

DOI10.1007/S101070200294MaRDI QIDQ1849258zbMATH OpenOpenAlexFDO

Authors Javier Peña

Publication date 1 December 2002

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s101070200294

zbMATH Keywords

algorithmcondition numbersconvex programsdistance to infeasibilityinterior-point methods

Mathematics Subject Classification ID

Numerical computation of matrix norms, conditioning, scaling (65F35) Numerical mathematical programming methods (65K05) Sensitivity, stability, parametric optimization (90C31) Programming involving graphs or networks (90C35) Interior-point methods (90C51)

Review text

The potential explosive growth of the condition numbers of the linear equations arising in interior-point methods is discussed. Two types of estimates on the growth of these condition numbers along the central path have been previously developed. In this paper, two bounds for such estimates are derived and stated in fundamentally different ways and shown to be compatible. Conic systems and their distance to infeasibility is discussed. A generalization of an earlier algorithm is given. The implicitly defined function approach enables a succinct consolidation of several results regarding self-concordant functions, the central path of a convex program, and conic systems and their distance to infeasibility.

Recommendations

• Optimality conditions and a barrier method in optimization with convex geometric constraint
• A condition number theorem in convex programming
• Search of generalized solutions to improper linear and convex programming problems using barrier functions
• A barrier method in convex vector optimization with generalized inequality constraints
• Barrier function method and correction algorithms for improper convex programming problems
• A convex analysis view of the barrier problem
• The convergence of a modified barrier method for convex programming
• Condition numbers and error bounds in convex programming
• On the New Barrier Function and Specialized Algorithms for a Class of Semidefinite Programs
• Objective function and logarithmic barrier function properties in convex programming: level sets, solution attainment and strict convexity^*

Cited in

(5)

• Condition Numbers, the Barrier Method, and the Conjugate-Gradient Method
• Computation of condition numbers for linear programming problems using Peña’s method
• On two measures of problem instance complexity and their correlation with the performance of SeDuMi on second-order cone problems
• Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems
• A primal-dual symmetric relaxation for homogeneous conic systems

This page was built for publication: Two properties of condition numbers for convex programs via implicitly defined barrier functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849258)