An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
From MaRDI portal
Publication:4294729
DOI10.1287/MOOR.19.1.53zbMath0799.90087OpenAlexW2022004439MaRDI QIDQ4294729
Michael J. Todd, Shinji Mizuno, Yinyu Ye
Publication date: 17 November 1994
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.19.1.53
Related Items (only showing first 100 items - show all)
CvxPnPL: a unified convex solution to the absolute pose estimation problem from point and line correspondences ⋮ A step-truncated method in a wide neighborhood interior-point algorithm for linear programming ⋮ Revisiting degeneracy, strict feasibility, stability, in linear programming ⋮ A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation ⋮ Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022 ⋮ Finite convergence into a convex polytope via facet reflections. ⋮ Embedding methods for semidefinite programming ⋮ A new infeasible interior-point algorithm with full step for linear optimization based on a simple function ⋮ 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 ⋮ Global convergence in infeasible-interior-point algorithms ⋮ An algorithm for nonsymmetric conic optimization inspired by MOSEK ⋮ A fixed point iterative approach to integer programming and its distributed computation ⋮ Conic optimization via operator splitting and homogeneous self-dual embedding ⋮ The practical behavior of the homogeneous self-dual formulations in interior point methods ⋮ A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones ⋮ A full-step interior-point algorithm for second-order cone optimization based on a simple locally kernel function ⋮ Crash start of interior point methods ⋮ Status determination by interior-point methods for convex optimization problems in domain-driven form ⋮ On two measures of problem instance complexity and their correlation with the performance of SeDuMi on second-order cone problems ⋮ A modified homogeneous potential reduction algorithm for solving the monotone semidefinite linear complementarity problem ⋮ Potential-reduction methods in mathematical programming ⋮ Improved complexity using higher-order correctors for primal-dual Dikin affine scaling ⋮ On homogeneous and self-dual algorithms for LCP ⋮ An alternating direction method for second-order conic programming ⋮ A generalized homogeneous and self-dual algorithm for linear programming ⋮ Initialization in semidefinite programming via a self-dual skew-symmetric embedding ⋮ A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems ⋮ An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution ⋮ An infeasible-interior-point algorithm using projections onto a convex set ⋮ An \(O(nL)\) infeasible-interior-point algorithm for LCP with quadratic convergence ⋮ A path-following interior-point algorithm for linear and quadratic problems ⋮ A simplified homogeneous and self-dual linear programming algorithm and its implementation ⋮ Primal-dual target-following algorithms for linear programming ⋮ Primal-Dual Path-Following Methods and the Trust-Region Updating Strategy for Linear Programming with Noisy Data ⋮ Complexity analysis of a full-{N}ewton step interior-point method for linear optimization ⋮ A primal-dual symmetric relaxation for homogeneous conic systems ⋮ A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy ⋮ A faster interior-point method for sum-of-squares optimization ⋮ A new corrector-predictor interior-point method for symmetric cone optimization ⋮ A corrector-predictor interior-point method with new search direction for linear optimization ⋮ Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems ⋮ First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games ⋮ A complementarity partition theorem for multifold conic systems ⋮ An \(O(\sqrt nL)\) iteration primal-dual second-order corrector algorithm for linear programming ⋮ Method of approximate centers for semi-definite programming ⋮ A predictor-corrector algorithm with multiple corrections for convex quadratic programming ⋮ Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations ⋮ A homogeneous smoothing-type algorithm for symmetric cone linear programs ⋮ SDPT3 — A Matlab software package for semidefinite programming, Version 1.3 ⋮ On the behavior of Lagrange multipliers in convex and nonconvex infeasible interior point methods ⋮ A new wide neighborhood primal-dual second-order corrector algorithm for linear optimization ⋮ A wide neighborhood predictor-infeasible corrector interior-point algorithm for linear optimization ⋮ A homogeneous model for monotone mixed horizontal linear complementarity problems ⋮ A Barzilai and Borwein regularization feasible direction algorithm for convex nonlinear SOC programming with linear constraints ⋮ A framework for solving mixed-integer semidefinite programs ⋮ New complexity analysis of IIPMs for linear optimization based on a specific self-regular function ⋮ Numerical algebraic geometry and semidefinite programming ⋮ Identification of optimal feedback control rules from micro-quadrotor and insect flight trajectories ⋮ Interior Point Methods for Nonlinear Optimization ⋮ Conic programming: infeasibility certificates and projective geometry ⋮ An adaptive infeasible interior-point algorithm with full-Newton step for linear optimization ⋮ A FULL-NEWTON STEP INFEASIBLE INTERIOR-POINT METHOD FOR LINEAR OPTIMIZATION BASED ON AN EXPONENTIAL KERNEL FUNCTION ⋮ On homogeneous interrior-point algorithms for semidefinite programming ⋮ The analyticity of interior-point-paths at strictly complementary solutions of linear programs ⋮ An easy way to teach interior-point methods. ⋮ Corrector-predictor methods for sufficient linear complementarity problems ⋮ An adaptive updating full-Newton step interior-point algorithm with modified Newton direction ⋮ 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 ⋮ Smoothing-type algorithm for solving linear programs by using an augmented complementarity problem ⋮ Grasping force optimization for multi-fingered robotic hands using projection and contraction methods ⋮ A survey on conic relaxations of optimal power flow problem ⋮ Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone ⋮ Primal-Dual Interior-Point Methods for Domain-Driven Formulations ⋮ New method for determining search directions for interior-point algorithms in linear optimization ⋮ The complexity of self-regular proximity based infeasible IPMs ⋮ Solution refinement at regular points of conic problems ⋮ Computational experience with a modified potential reduction algorithm for linear programming ⋮ Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions ⋮ The State-of-the-Art in Conic Optimization Software ⋮ On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0 ⋮ Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion ⋮ A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization ⋮ Efficient semidefinite branch-and-cut for MAP-MRF inference ⋮ Simplified infeasible interior-point algorithm for linear optimization based on a simple function ⋮ On implementation of a self-dual embedding method for convex programming ⋮ Chordal decomposition in operator-splitting methods for sparse semidefinite programs ⋮ A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs ⋮ A New Predictor-corrector Infeasible Interior-point Algorithm for Linear Optimization in aWide Neighborhood ⋮ Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming ⋮ Strict Complementarity in Semidefinite Optimization with Elliptopes Including the MaxCut SDP ⋮ Maximum-Stopping-Value Policies in Finite Markov Population Decision Chains ⋮ An ADMM-based interior-point method for large-scale linear programming ⋮ A primal-dual decomposition algorithm for multistage stochastic convex programming ⋮ An infeasible-start framework for convex quadratic optimization, with application to constraint-reduced interior-point and other methods ⋮ Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem ⋮ Interior-point methods ⋮ 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
This page was built for publication: An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
