A primal-dual symmetric relaxation for homogeneous conic systems
type: Item
instance of: scholarly article
title: A primal-dual symmetric relaxation for homogeneous conic systems
zbMATH Open document ID: 1118.65065
author: Juan Vera
author: Juan Carlos Rivera
author: Yao Hui
author: Javier Peña
published in: Journal of Complexity
publication date: 2007-06-04T00:00:00Z
review text: The authors consider the feasibility (existence of non-trivial solutions) of a pair of alternative conic systems of constraints . That pair of conic systems is reformulated as a primal-dual pair of conic programs. Each of the conic programs corresponds to a natural relaxation of each of the two conic systems. When the considered closed convex cone is a self-scaled cone with a known self-scaled barrier, the conic programming reformulation can be solved via an interior-point algorithm. A central feature of this approach is the conditioning of the system of equations that arise at each interior-point iteration. The condition number of such system of equations grows in a controlled manner and remains bounded by a constant factor of the square of Renegar's condition number of the matrix of the considered system of equations throughout the entire algorithm.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C51
zbMATH DE Number: 5161133
zbMATH Keywords: conic programming
zbMATH Keywords: condition numbers
zbMATH Keywords: interior-point methods
reviewed by: Nada Djuranović-Miličić
describes a project that uses: mctoolbox
MaRDI profile type: Publication
Wikidata QID: Q58051165
full work available at URL: j.jco.2007.01.002
OpenAlex ID: W2031269429
cites work: Second-order cone programming
cites work: A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
cites work: Solving linear programs with finite precision. II: Algorithms
cites work: Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
cites work: Complexity of convex optimization using geometry-based measures and a reference point
cites work: Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
cites work: Self-scaled barrier functions on symmetric cones and their classification
cites work: Q4864704
cites work: Q4324980
cites work: Self-Scaled Barriers and Interior-Point Methods for Convex Programming
cites work: Primal-Dual Interior-Point Methods for Self-Scaled Cones
cites work: Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
cites work: Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
cites work: Two properties of condition numbers for convex programs via implicitly defined barrier functions
cites work: A characterization of the distance to infeasibility under block-structured perturbations
cites work: Computing approximate solutions for convex conic systems of constraints
cites work: Linear programming, complexity theory and elementary functional analysis
cites work: A mathematical view of interior-point methods in convex optimization
cites work: Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones.
cites work: Condition numbers for polyhedra with real number data
cites work: On the complexity of linear programming under finite precision arithmetic
cites work: An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
DBLP publication ID: journals/jc/VeraRPH07
DOI: 10.1016/J.JCO.2007.01.002
description: scientific article; zbMATH DE number 5161133