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

An predictor–corrector interior-point algorithm for semidefinite optimization based on a wide neighbourhood, Credible autocoding of convex optimization algorithms, A modified infeasible interior-point algorithm with full-Newton step for semidefinite optimization, On the central paths in symmetric cone programming, An infeasible full NT-step interior point method for circular optimization, An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path, Conic convex programming and self-dual embedding, Full Nesterov-Todd step feasible interior-point algorithm for symmetric cone horizontal linear complementarity problem based on a positive-asymptotic barrier function, An algorithm for nonsymmetric conic optimization inspired by MOSEK, An O(r(cond(G))1/4log¼ϵ−1) iteration predictor–corrector interior-point method with a new one-norm neighbourhood for symmetric cone optimization, A unified mathematical programming formulation of strain driven and interior point algorithms for shakedown and limit analysis, A New Iteration Large-Update Primal-Dual Interior-Point Method for Second-Order Cone Programming, A FULL NT-STEP INFEASIBLE INTERIOR-POINT ALGORITHM FOR SEMIDEFINITE OPTIMIZATION BASED ON A SELF-REGULAR PROXIMITY, A new infeasible-interior-point algorithm based on wide neighborhoods for symmetric cone programming, A primal–dual predictor–corrector interior-point method for symmetric cone programming with O(√r log ϵ⁻¹) iteration complexity, A method for weighted projections to the positive definite cone, Hessian distances and their applications in the complexity analysis of interior-point methods, Full Nesterov–Todd step feasible interior-point method for the CartesianP_*(κ)-SCLCP, A wide neighbourhood predictor–corrector infeasible-interior-point algorithm for symmetric cone programming, Convergence to a second-order critical point by a primal-dual interior point trust-region method for nonlinear semidefinite programming, Fast implementation for semidefinite programs with positive matrix completion, A NEW POLYNOMIAL INTERIOR-POINT ALGORITHM FOR THE MONOTONE LINEAR COMPLEMENTARITY PROBLEM OVER SYMMETRIC CONES WITH FULL NT-STEPS, A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization, A conversion of an SDP having free variables into the standard form SDP, A corrector–predictor path-following algorithm for semidefinite optimization, Second-order cone programming approaches to static shakedown analysis in steel plasticity, A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming, A new infeasible-interior-point algorithm for linear programming over symmetric cones, Kernel-function-based primal-dual interior-point methods for convex quadratic optimization over symmetric cone, A wide neighborhood interior-point algorithm for convex quadratic semidefinite optimization, A primal-dual interior-point method based on various selections of displacement step for symmetric optimization, A new corrector-predictor interior-point method for symmetric cone optimization, An infeasible interior-point algorithm for stochastic second-order cone optimization, The dual simplex-type method for linear second-order cone programming problem, New complexity analysis of a full Nesterov–Todd step interior-point method for semidefinite optimization, A variant of the affine-scaling method for a second-order cone program, A corrector–predictor path-following method for second-order cone optimization, Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming, Complexity of the primal–dual path-following algorithms for the weighted determinant maximization problems with linear matrix inequalities in the narrow neighbourhood, An infeasible full-NT step IPM for horizontal linear complementarity problem over Cartesian product of symmetric cones, New complexity analysis of interior-point methods for the Cartesian \(P_\ast ({\kappa})\)-SCLCP, New Interior-Point Algorithm for Symmetric Optimization Based on a Positive-Asymptotic Barrier Function, A long-step feasible predictor–corrector interior-point algorithm for symmetric cone optimization, A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem, A Corrector-Predictor Interior-Point Algorithm for P_∗(κ)-HLCPs Over Cartesian Product of Symmetric Cones, A second-order corrector infeasible interior-point method for semidefinite optimization based on a wide neighborhood, The Karcher mean of linearly independent triples, The solution of euclidean norm trust region SQP subproblems via second-order cone programs: an overview and elementary introduction, A wide neighborhood infeasible-interior-point method with arc-search for -SCLCPs, \(\mathcal{UV}\)-theory of a class of semidefinite programming and its applications, A long-step interior-point algorithm for symmetric cone Cartesian P_*(κ)-HLCP, A pseudo-equilibrium finite element for limit analysis of Reissner-Mindlin plates, A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function, Solvability of semidefinite complementarity problems, Primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, An iteration primal–dual path-following method, based on wide neighbourhood and large update, for second-order cone programming, A self-concordant exponential kernel function for primal–dual interior-point algorithm, Equivalence of two nondegeneracy conditions for semidefinite programs, A corrector-predictor path-following method for convex quadratic symmetric cone optimization, On the behavior of the homogeneous self-dual model for conic convex optimization, Implementation of interior point methods for mixed semidefinite and second order cone optimization problems, A Polynomial-time Interior-point Algorithm for Convex Quadratic Semidefinite Optimization, Primal-Dual Interior-Point Methods for Domain-Driven Formulations, Quadratic convergence to the optimal solution of second-order conic optimization without strict complementarity, Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra, A New Infeasible Interior-Point Method Based on a Non-Coercive Kernel Function with Improved Centering Steps for Second-Order Cone Optimization, Optimal Risk Transfer: A Numerical Optimization Approach, A robust algorithm for semidefinite programming, Interior-point methods for CartesianP_*(κ)-linear complementarity problems over symmetric cones based on the eligible kernel functions, Towards non-symmetric conic optimization, An Introduction to Formally Real Jordan Algebras and Their Applications in Optimization, Self-Regular Interior-Point Methods for Semidefinite Optimization, Latest Developments in the SDPA Family for Solving Large-Scale SDPs, Intrinsic volumes of symmetric cones and applications in convex programming, Approximate minimum enclosing balls in high dimensions using core-sets, A large-update primal–dual interior-point algorithm for second-order cone optimization based on a new proximity function, Successive Quadratic Upper-Bounding for Discrete Mean-Risk Minimization and Network Interdiction, Semidefinite and second-order cone optimization approach for the Toeplitz matrix approximation problem, A pivoting procedure for a class of second-order cone programming, A new second-order Mehrotra-type predictor-corrector algorithm for SDO, Infeasible Mehrotra-Type Predictor-Corrector Interior-Point Algorithm for the CartesianP_*(κ)-LCP Over Symmetric Cones, A primal-dual interior-point algorithm with arc-search for semidefinite programming, APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING, Simplified full Nesterov-Todd step infeasible interior-point algorithm for semidefinite optimization based on a kernel function, Some remarks on duality and optimality of a class of constrained convex quadratic minimization problems, A predictor-corrector infeasible-interior-point method for the Cartesian -LCP over symmetric cones with iteration complexity, A new wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization, Research Article: On Extending Primal-Dual Interior-Point Method for Linear Optimization to Convex Quadratic Symmetric Cone Optimization, A class of polynomial primal-dual interior-point algorithms for semidefinite optimization, A primal-dual interior point trust-region method for nonlinear semidefinite programming, Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function, A study of search directions in primal-dual interior-point methods for semidefinite programming, A note on the Nesterov-Todd and the Kojima-Shindoh-hara search directions in semidefinite programming, Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants, A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming, Sdpha: a Matlab implementation of homogeneous interior-point algorithms for semidefinite programming, Improved complexity analysis of full Nesterov-Todd step interior-point methods for semidefinite optimization, New complexity analysis of a Mehrotra-type predictor–corrector algorithm for semidefinite programming, Unnamed Item, A primal-dual interior point method for large-scale free material optimization, 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, Linear optimization over homogeneous matrix cones, Optimal Self-Concordant Barriers for Quantum Relative Entropies, Performance enhancements for a generic conic interior point algorithm, A preconditioned iterative interior point approach to the conic bundle subproblem, A wide neighbourhood primal-dual second-order corrector interior point algorithm for semidefinite optimization, Corrector-predictor interior-point method with new search direction for semidefinite optimization, A Geodesic Interior-Point Method for Linear Optimization over Symmetric Cones, A binomial expansion formula for weighted geometric means of unipotent matrices, Semidefinite programming and combinatorial optimization, A primal-dual interior-point algorithm for symmetric optimization based on a new method for finding search directions, New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction