Status determination by interior-point methods for convex optimization problems in domain-driven form

DOI10.1007/S10107-021-01663-WzbMATH Open1494.90079arXiv1901.07084OpenAlexW3173759678MaRDI QIDQ2149574FDOQ2149574

Authors: Mehdi Karimi, Levent Tunçel 

Publication date: 29 June 2022

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

Abstract: We study the geometry of convex optimization problems given in a Domain-Driven form and categorize possible statuses of these problems using duality theory. Our duality theory for the Domain-Driven form, which accepts both conic and non-conic constraints, lets us determine and certify statuses of a problem as rigorously as the best approaches for conic formulations (which have been demonstrably very efficient in this context). We analyze the performance of an infeasible-start primal-dual algorithm for the Domain-Driven form in returning the certificates for the defined statuses. Our iteration complexity bounds for this more practical Domain-Driven form match the best ones available for conic formulations. At the end, we propose some stopping criteria for practical algorithms based on insights gained from our analyses.

Full work available at URL: https://arxiv.org/abs/1901.07084

Recommendations

• Primal-dual interior-point methods for domain-driven formulations
• Generalization of primal-dual interior-point methods to convex optimization problems in conic form
• On the generic properties of convex optimization problems in conic form
• ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods
• New stopping criteria for detecting infeasibility in conic optimization

zbMATH Keywords

convex optimizationinterior-point methodsduality theoryprimal-dual algorithmsstatus determination

Mathematics Subject Classification ID

Convex programming (90C25) Complexity and performance of numerical algorithms (65Y20) Interior-point methods (90C51) Duality theory (optimization) (49N15)

Cites Work

• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Title not available (Why is that?)
• On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
• Some perturbation theory for linear programming
• A simplified homogeneous and self-dual linear programming algorithm and its implementation
• Strong duality and minimal representations for cone optimization
• On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
• Title not available (Why is that?)
• An Implementation of a Primal-Dual Interior Point Method for Linear Programming
• Title not available (Why is that?)
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
• Conic convex programming and self-dual embedding
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Feasibility issues in a primal-dual interior-point method for linear programming
• A tutorial on geometric programming
• A polynomial-time algorithm for a class of linear complementarity problems
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Towards non-symmetric conic optimization
• Polynomiality of infeasible-interior-point algorithms for linear programming
• Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
• Interior path following primal-dual algorithms. I: Linear programming
• A primal-dual infeasible-interior-point algorithm for linear programming
• A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
• Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming
• Computational experience with a primal-dual interior point method for linear programming
• A little theorem of the big \({\mathcal M}\) in interior point algorithms
• ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods
• Lectures on convex optimization
• User'S guide To Lipsol linear-programming interior point solvers V0.4
• Generalization of primal-dual interior-point methods to convex optimization problems in conic form
• A constant-potential infeasible-start interior-point algorithm with computational experiments and applications
• On the behavior of the homogeneous self-dual model for conic convex optimization
• It is possible to know a problem instance is ill-posed? Some foundations for a general theory of condition numbers
• Convex optimization problems involving finite autocorrelation sequences
• Detecting infeasibility in infeasible-interior-point methods for optimization
• A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
• Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m^10/7 log W) Time (Extended Abstract)
• On the behavior of Lagrange multipliers in convex and nonconvex infeasible interior point methods
• Primal-Dual Interior-Point Methods for Domain-Driven Formulations

Uses Software

• SeDuMi
• SDPT3
• DDS

This page was built for publication: Status determination by interior-point methods for convex optimization problems in domain-driven form

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