Self-Scaled Barriers and Interior-Point Methods for Convex Programming

DOI10.1287/moor.22.1.1zbMath0871.90064OpenAlexW2117065890WikidataQ92421432 ScholiaQ92421432MaRDI QIDQ4339371

Michael J. Todd, Yu. E. Nesterov

Publication date: 9 June 1997

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/8975

zbMATH Keywords

interior-point algorithmspath-followingself-scaled conepotential-reduction algorithmsself-scaled barrier

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Complexity and performance of numerical algorithms (65Y20)

Related Items (only showing first 100 items - show all)

Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrier ⋮ A full step infeasible interior-point method for Cartesian \(P_{*}(\kappa)\)-SCLCP ⋮ Rapid smooth entry trajectory planning for high lift/drag hypersonic glide vehicles ⋮ Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Efficient solutions of interval programming problems with inexact parameters and second order cone constraints ⋮ An inexact non-interior continuation method for semidefinite programming: convergence analysis and numerical results ⋮ On verified numerical computations in convex programming ⋮ An interior-point algorithm for semidefinite least-squares problems. ⋮ Polynomial convergence of Mehrotra-type prediction-corrector infeasible-IPM for symmetric optimization based on the commutative class directions ⋮ On central-path proximity measures in interior-point methods ⋮ A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization ⋮ Interior-point methods: An old and new approach to nonlinear programming ⋮ Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems ⋮ A modified and simplified full Nesterov-Todd step \(\mathcal {O}(N)\) infeasible interior-point method for second-order cone optimization ⋮ Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling ⋮ An inexact interior point method for the large-scale simulation of granular material ⋮ Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm ⋮ Applications of second-order cone programming ⋮ A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization ⋮ A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming ⋮ A class of polynomial interior-point algorithms for the Cartesian \(P_{*}(\kappa )\) second-order cone linear complementarity problem ⋮ A large-update feasible interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function ⋮ A primal-dual symmetric relaxation for homogeneous conic systems ⋮ Carlson's iterative mean algorithm of positive definite matrices ⋮ A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function ⋮ A second order Mehrotra-type predictor-corrector algorithm for semidefinite optimization ⋮ The resolvent average on symmetric cones ⋮ A new second-order corrector interior-point algorithm for semidefinite programming ⋮ An adaptive infeasible interior-point algorithm with full Nesterov-Todd step for semidefinite optimization ⋮ Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones ⋮ Polynomial convergence of second-order mehrotra-type predictor-corrector algorithms over symmetric cones ⋮ A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization ⋮ A geometric mean of parameterized arithmetic and harmonic means of convex functions ⋮ Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step ⋮ A class of polynomial interior point algorithms for the Cartesian P-matrix linear complementarity problem over symmetric cones ⋮ Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming ⋮ Polynomial convergence of primal-dual path-following algorithms for symmetric cone programming based on wide neighborhoods and a new class of directions ⋮ Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems ⋮ On complexity analysis of the primal-dual interior-point method for semidefinite optimization problem based on a new proximity function ⋮ A new full Nesterov-Todd step feasible interior-point method for convex quadratic symmetric cone optimization ⋮ Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems ⋮ A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO ⋮ Full Nesterov-Todd step infeasible interior-point method for symmetric optimization ⋮ An interior-point method for a class of saddle-point problems ⋮ A smoothing Newton method with Fischer-Burmeister function for second-order cone complementarity problems ⋮ Semidefinite programming and matrix scaling over the semidefinite cone. ⋮ On the extension of an arc-search interior-point algorithm for semidefinite optimization ⋮ Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones ⋮ Primal-dual interior-point algorithm for convex quadratic semi-definite optimization ⋮ Homogeneous self-dual algorithms for stochastic second-order cone programming ⋮ A weighted-path-following method for symmetric cone linear complementarity problems ⋮ Large-neighborhood infeasible predictor-corrector algorithm for horizontal linear complementarity problems over Cartesian product of symmetric cones ⋮ A new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming ⋮ Improved complexity analysis of full Nesterov-Todd step feasible interior-point method for symmetric optimization ⋮ A polynomial time constraint-reduced algorithm for semidefinite optimization problems ⋮ An infeasible full-NT step interior point algorithm for CQSCO ⋮ Return-mapping algorithms for associative isotropic hardening plasticity using conic optimization ⋮ On the nonlinear matrix equation \(X^p = A + M^T (X \# B) M\) ⋮ The resolvent average on symmetric cones of JB-algebras ⋮ A polynomial primal-dual affine scaling algorithm for symmetric conic optimization ⋮ Largest dual ellipsoids inscribed in dual cones ⋮ An adaptive infeasible-interior-point method with the one-norm wide neighborhood for semi-definite programming ⋮ Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term ⋮ Two new predictor-corrector algorithms for second-order cone programming ⋮ Semidefinite programming for discrete optimization and matrix completion problems ⋮ Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence ⋮ Reflection-projection method for convex feasibility problems with an obtuse cone ⋮ On self-regular IPMs (with comments and rejoinder) ⋮ ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods ⋮ Efficient algorithms for the smallest enclosing ball problem ⋮ Product-form Cholesky factorization in interior point methods for second-order cone programming ⋮ A primal-dual interior point method for nonlinear semidefinite programming ⋮ Strengthened existence and uniqueness conditions for search directions in semidefinite program\-ming ⋮ Gaddum's test for symmetric cones ⋮ A survey on conic relaxations of optimal power flow problem ⋮ An infeasible interior point method for the monotone SDLCP based on a transformation of the central path ⋮ An interior-point method for the single-facility location problem with mixed norms using a conic formulation ⋮ A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step ⋮ Solvability for two forms of nonlinear matrix equations ⋮ A full Nesterov-Todd step feasible weighted primal-dual interior-point algorithm for symmetric optimization ⋮ Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions ⋮ An arc-search infeasible interior-point method for semidefinite optimization with the negative infinity neighborhood ⋮ Nonhomogeneous Karcher equations with vector fields on positive definite matrices ⋮ A new primal-dual path-following interior-point algorithm for semidefinite optimization ⋮ On the long-step path-following method for semidefinite programming ⋮ Risk optimization with \(p\)-order conic constraints: a linear programming approach ⋮ Similarity and other spectral relations for symmetric cones ⋮ Characterization of the barrier parameter of homogeneous convex cones ⋮ A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming ⋮ Affine scaling algorithm fails for semidefinite programming ⋮ Primal-dual potential reduction methods for semidefinite programming using affine-scaling directions ⋮ Polynomial primal-dual cone affine scaling for semidefinite programming ⋮ Symmetric primal-dual path-following algorithms for semidefinite programming ⋮ \texttt{Tenscalc}: a toolbox to generate fast code to solve nonlinear constrained minimizations and compute Nash equilibria ⋮ A new class of polynomial primal-dual methods for linear and semidefinite optimization ⋮ Interior-point methods ⋮ Nonnegative minimum biased quadratic estimation in mixed linear models ⋮ Semidefinite programming ⋮ Randomized interior point methods for sampling and optimization

This page was built for publication: Self-Scaled Barriers and Interior-Point Methods for Convex Programming