Primal-Dual Interior-Point Methods for Self-Scaled Cones

DOI10.1137/S1052623495290209zbMath0922.90110WikidataQ92420174 ScholiaQ92420174MaRDI QIDQ4389195

Michael J. Todd, Yu. E. Nesterov

Publication date: 12 May 1998

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

zbMATH Keywords

interior-point algorithmsconvex programmingself-concordant barrierpath-following algorithmsself-scaled coneself-scaled barrierconical formsymmetric primal-dual algorithms

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 ⋮ Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming ⋮ Efficient solutions of interval programming problems with inexact parameters and second order cone constraints ⋮ A constraint-reduced algorithm for semidefinite optimization problems with superlinear convergence ⋮ A new wide-neighborhood predictor-corrector interior-point method for semidefinite optimization ⋮ An inexact non-interior continuation method for semidefinite programming: convergence analysis and numerical results ⋮ An interior-point algorithm for semidefinite least-squares problems. ⋮ Primal Newton method for the linear cone programming problem ⋮ 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 ⋮ A wide neighborhood primal-dual predictor-corrector interior-point method for symmetric cone optimization ⋮ Exploiting sparsity in primal-dual interior-point methods for semidefinite programming ⋮ Interior-point methods: An old and new approach to nonlinear programming ⋮ 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 ⋮ A homotopy method for nonlinear semidefinite programming ⋮ An arc-search predictor-corrector infeasible-interior-point algorithm for \(P_\ast(\kappa)\)-SCLCPs ⋮ Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs ⋮ 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 ⋮ An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones ⋮ A class of polynomial interior-point algorithms for the Cartesian \(P_{*}(\kappa )\) second-order cone linear complementarity problem ⋮ New complexity analysis for primal-dual interior-point methods for self-scaled optimization problems ⋮ 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 ⋮ A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function ⋮ A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy ⋮ A new second-order corrector interior-point algorithm for semidefinite programming ⋮ Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones ⋮ An inexact interior point method for \(L_{1}\)-regularized sparse covariance selection ⋮ 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 ⋮ 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 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 ⋮ 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 relaxed-certificate facial reduction algorithm based on subspace intersection ⋮ On the extension of an arc-search interior-point algorithm for semidefinite optimization ⋮ A smoothing Newton method for second-order cone optimization based on a new smoothing function ⋮ 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 ⋮ An arc search infeasible interior-point algorithm for symmetric optimization using a new wide neighborhood ⋮ A generic interior-point algorithm for monotone symmetric cone linear complementarity problems based on a new kernel function ⋮ Complexity analysis of infeasible interior-point method for semidefinite optimization based on a new trigonometric kernel function ⋮ 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 ⋮ Numerical algebraic geometry and semidefinite programming ⋮ Parabolic target space and primal-dual interior-point methods ⋮ An \(O(\sqrt nL)\) wide neighborhood interior-point algorithm for semidefinite optimization ⋮ 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 ⋮ Two new predictor-corrector algorithms for second-order cone programming ⋮ Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence ⋮ On self-regular IPMs (with comments and rejoinder) ⋮ ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods ⋮ A smoothing-type Newton method for second-order cone programming problems based on a new smooth function ⋮ A Mehrotra-type predictor-corrector infeasible-interior-point method with a new one-norm neighborhood for symmetric optimization ⋮ A new one-step smoothing Newton method for second-order cone programming. ⋮ Product-form Cholesky factorization in interior point methods for second-order cone programming ⋮ A primal-dual interior point method for nonlinear semidefinite programming ⋮ 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 ⋮ Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion ⋮ A new smoothing Newton-type method for second-order cone programming problems ⋮ A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step ⋮ A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization ⋮ Efficient semidefinite branch-and-cut for MAP-MRF inference ⋮ 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 ⋮ A polynomial-time interior-point method for circular cone programming based on kernel functions ⋮ Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP ⋮ On the long-step path-following method for semidefinite programming ⋮ Superlinear convergence of interior-point algorithms for semidefinite programming ⋮ Numerical experiments with universal barrier functions for cones of Chebyshev systems ⋮ 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 ⋮ Affine scaling algorithm fails for semidefinite programming ⋮ 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 long-step primal-dual path-following method for semidefinite programming ⋮ Interior-point methods ⋮ Nonnegative minimum biased quadratic estimation in mixed linear models ⋮ On a commutative class of search directions for linear programming over symmetric cones ⋮ Semidefinite programming

This page was built for publication: Primal-Dual Interior-Point Methods for Self-Scaled Cones