Status determination by interior-point methods for convex optimization problems in domain-driven form
From MaRDI portal
Publication:2149574
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.
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
Cites work
- scientific article; zbMATH DE number 4164543 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- A constant-potential infeasible-start interior-point algorithm with computational experiments and applications
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- A little theorem of the big \({\mathcal M}\) in interior point algorithms
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
- A polynomial-time algorithm for a class of linear complementarity problems
- A primal-dual infeasible-interior-point algorithm for linear programming
- A simplified homogeneous and self-dual linear programming algorithm and its implementation
- A tutorial on geometric programming
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- Computational experience with a primal-dual interior point method for linear programming
- Conic convex programming and self-dual embedding
- Convex optimization problems involving finite autocorrelation sequences
- Detecting infeasibility in infeasible-interior-point methods for optimization
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Feasibility issues in a primal-dual interior-point method for linear programming
- Generalization of primal-dual interior-point methods to convex optimization problems in conic form
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Infeasible-Interior-Point Primal-Dual Potential-Reduction 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
- It is possible to know a problem instance is ill-posed? Some foundations for a general theory of condition numbers
- Lectures on convex optimization
- Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
- On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
- On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
- On the behavior of Lagrange multipliers in convex and nonconvex infeasible interior point methods
- On the behavior of the homogeneous self-dual model for conic convex optimization
- On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
- Polynomiality of infeasible-interior-point algorithms for linear programming
- Primal-dual interior-point methods for domain-driven formulations
- Some perturbation theory for linear programming
- Strong duality and minimal representations for cone optimization
- Towards non-symmetric conic optimization
- User'S guide To Lipsol linear-programming interior point solvers V0.4
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods
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)
