Self-Scaled Barriers and Interior-Point Methods for Convex Programming
From MaRDI portal
Publication:4339371
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
interior-point algorithmspath-followingself-scaled conepotential-reduction algorithmsself-scaled barrier
Convex programming (90C25) Linear programming (90C05) Complexity and performance of numerical algorithms (65Y20)
Related Items
A modified infeasible interior-point algorithm with full-Newton step for semidefinite optimization, On the central paths in symmetric cone programming, An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path, A primal-dual interior-point algorithm for symmetric optimization based on a new kernel function with trigonometric barrier term yielding the best known iteration bounds, Interior-point methods based on kernel functions for symmetric optimization, 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, Solving symmetric matrix word equations via symmetric space machinery, 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, Todd's maximum-volume ellipsoid problem on symmetric cones, 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 ϵ−1) iteration complexity, Solving Natural Conic Formulations with Hypatia.jl, A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ, Convergence to a second-order critical point by a primal-dual interior point trust-region method for nonlinear semidefinite programming, A NEW POLYNOMIAL INTERIOR-POINT ALGORITHM FOR THE MONOTONE LINEAR COMPLEMENTARITY PROBLEM OVER SYMMETRIC CONES WITH FULL NT-STEPS, An \(\epsilon\)-sensitivity analysis for semidefinite programming, Local Superlinear Convergence of Polynomial-Time Interior-Point Methods for Hyperbolicity Cone Optimization Problems, A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization, On the nonlinear matrix equation Xp = A#t(MT (X–1 + B)–1 M), A corrector–predictor path-following algorithm for semidefinite optimization, A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming, Two wide neighborhood interior-point methods for symmetric cone optimization, 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, Primal-dual potential reduction algorithm for symmetric programming problems with nonlinear objective functions, A new corrector-predictor interior-point method for symmetric cone optimization, On a box-constrained linear symmetric cone optimization problem, New complexity analysis of a full Nesterov–Todd step interior-point method for semidefinite optimization, A corrector–predictor path-following method for second-order cone optimization, Several Jordan-algebraic aspects of 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, A full NT-step infeasible interior-point algorithm for semidefinite optimization, 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, $LDL^T$ Direction Interior Point Method for Semidefinite Programming, 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 Corrector-Predictor Interior-Point Algorithm for P∗(κ)-HLCPs Over Cartesian Product of Symmetric Cones, A new infeasible interior-point method based on Darvay's technique for symmetric optimization, The Karcher mean of linearly independent triples, An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming, The solution of euclidean norm trust region SQP subproblems via second-order cone programs: an overview and elementary introduction, Invariance and efficiency of convex representations, \(\mathcal{UV}\)-theory of a class of semidefinite programming and its applications, A long-step interior-point algorithm for symmetric cone Cartesian P*(κ)-HLCP, Interior Point Methods for Nonlinear Optimization, Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming, Extension of primal-dual interior point methods to diff-convex problems on symmetric cones, \(\varGamma \)-commuting triples of positive definite matrices and midpoint equations on unitary matrices, 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, An inexact interior-point method for system analysis, A corrector-predictor path-following method for convex quadratic symmetric cone optimization, Mesh adaptive computation of upper and lower bounds in limit analysis, On the behavior of the homogeneous self-dual model for conic convex optimization, Unnamed Item, Implementation of interior point methods for mixed semidefinite and second order cone optimization problems, Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem, Unnamed Item, Primal-Dual Interior-Point Methods for Domain-Driven Formulations, Quadratic convergence to the optimal solution of second-order conic optimization without strict complementarity, 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 wide neighbourhood interior-point method with iteration-complexity bound for semidefinite programming, An Introduction to Formally Real Jordan Algebras and Their Applications in Optimization, Self-Regular Interior-Point Methods for Semidefinite Optimization, On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0, Intrinsic volumes of symmetric cones and applications in convex programming, On theP*(κ)horizontal linear complementarity problems over Cartesian product of symmetric cones, Advances in the simulation of viscoplastic fluid flows using interior-point methods, 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, A primal-dual interior-point algorithm for symmetric cone convex quadratic programming based on the commutative class directions, Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms, Simplified full Nesterov-Todd step infeasible interior-point algorithm for semidefinite optimization based on a kernel function, New complexity analysis of full Nesterov-Todd step infeasible interior point method for second-order cone optimization, A predictor-corrector infeasible-interior-point method for the Cartesian -LCP over symmetric cones with iteration complexity, 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, Unnamed Item, Low-rank exploitation in semidefinite programming for control, The inverse mean problem of geometric mean and contraharmonic means, 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, On long-step predictor-corrector interior-point algorithm for semidefinite programming with Monteiro-Zhang unified search directions, 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, Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones, 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, Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp∗, 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, 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, Hessian distances and their applications in the complexity analysis of interior-point methods, Interior-point methods for symmetric optimization based on a class of non-coercive kernel functions, Full Nesterov–Todd step feasible interior-point method for the CartesianP*(κ)-SCLCP, A full-step interior-point algorithm for second-order cone optimization based on a simple locally kernel function, Second-order cone programming approaches to static shakedown analysis in steel plasticity, A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms, Linear optimization over homogeneous matrix cones, Distance to a constitutive tensor isotropy stratum by the Lasserre polynomial optimization method, Performance enhancements for a generic conic interior point algorithm, 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, Unnamed Item, An easy way to teach interior-point methods., A primal-dual interior-point algorithm for symmetric optimization based on a new method for finding search directions, A long-step primal--dual algorithm for the symmetric programming problem, New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction, A robust algorithm for semidefinite programming, Towards non-symmetric conic optimization, Approximate minimum enclosing balls in high dimensions using core-sets, A Single-Phase, Proximal Path-Following Framework, Computation of condition numbers for linear programming problems using Peña’s method, Implementation of infinite-dimensional interior-point method for solving multi-criteria linear-quadratic control problem, A new wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization, Unnamed Item, Projectively Self-Concordant Barriers
