A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization

DOI10.1007/s11075-009-9270-7zbMath1180.65079OpenAlexW2132330039MaRDI QIDQ735073

D. Kharzeev

Publication date: 14 October 2009

Published in: Numerical Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11075-009-9270-7

zbMATH Keywords

algorithmconvex optimizationprimal-dual methodnumerical experimentssemidefinite optimizationpolynomial complexityinfeasible interior-point methodfull Newton steps

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Convex programming (90C25) Interior-point methods (90C51) Complexity and performance of numerical algorithms (65Y20)

Related Items

A modified infeasible interior-point algorithm with full-Newton step for semidefinite optimization, An infeasible interior-point algorithm for linear optimization over Cartesian symmetric cones, A new infeasible interior-point algorithm with full step for linear optimization based on a simple function, A path-following full Newton-step infeasible interior-point algorithm for \(P_*(\kappa)\)-HLCPs based on a kernel function, A FULL NT-STEP INFEASIBLE INTERIOR-POINT ALGORITHM FOR SEMIDEFINITE OPTIMIZATION BASED ON A SELF-REGULAR PROXIMITY, Infeasible interior-point methods for linear optimization based on large neighborhood, Polynomial interior-point algorithm for \(P_\ast(\kappa)\) horizontal linear complementarity problems, An infeasible interior-point algorithm with full-Newton steps for \(P_*(\kappa)\) horizontal linear complementarity problems based on a kernel function, A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization, A full-Newton step \(O(n)\) infeasible-interior-point algorithm for linear complementarity problems, An adaptive infeasible interior-point algorithm with full Nesterov-Todd step for semidefinite optimization, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step, A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions, Corrector-predictor interior-point method with new search direction for semidefinite optimization, A class of new search directions for full-NT step feasible interior point method in semidefinite optimization, 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, A Corrector-Predictor Interior-Point Algorithm for P_∗(κ)-HLCPs Over Cartesian Product of Symmetric Cones, A Mehrotra predictor-corrector interior-point algorithm for semidefinite optimization, Complexity analysis of infeasible interior-point method for semidefinite optimization based on a new trigonometric kernel function, Improved complexity analysis of full Nesterov-Todd step feasible interior-point method for symmetric optimization, A modified infeasible-interior-point algorithm for linear optimization problems, A unified complexity analysis of interior point methods for semidefinite problems based on trigonometric kernel functions, An \(O(\sqrt nL)\) wide neighborhood interior-point algorithm for semidefinite optimization, An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem, A full-Newton step infeasible interior-point method for the special weighted linear complementarity problem, Simplified full Nesterov-Todd step infeasible interior-point algorithm for semidefinite optimization based on a kernel function, A primal-dual interior-point method based on a new kernel function for linear complementarity problem, Improved complexity analysis of full Nesterov-Todd step interior-point methods for semidefinite optimization, Unnamed Item, Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Feasibility issues in a primal-dual interior-point method for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• Symmetric primal-dual path-following algorithms for semidefinite programming
• A primal-dual infeasible-interior-point algorithm for linear programming
• Primal-dual algorithms for linear programming based on the logarithmic barrier method
• Polynomiality of infeasible-interior-point algorithms for linear programming
• Initialization in semidefinite programming via a self-dual skew-symmetric embedding
• Complementarity and nondegeneracy in semidefinite programming
• Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs
• Graph partitioning using linear and semidefinite programming
• Semidefinite programming relaxations for semialgebraic problems
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points
• Self-regular functions and new search directions for linear and semidefinite optimization
• A primal-dual potential reduction method for problems involving matrix inequalities
• Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function
• Global Optimization with Polynomials and the Problem of Moments
• Lectures on Modern Convex Optimization
• Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
• An Interior-Point Method for Minimizing the Maximum Eigenvalue of a Linear Combination of Matrices
• SDP vs. LP Relaxations for the Moment Approach in Some Performance Evaluation Problems
• Semidefinite optimization
• On the Nesterov--Todd Direction in Semidefinite Programming
• A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
• Linear Matrix Inequalities in System and Control Theory
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Primal-Dual Interior-Point Methods for Self-Scaled Cones
• On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
• Solving Graph Bisection Problems with Semidefinite Programming
• A Spectral Bundle Method for Semidefinite Programming
• Conic convex programming and self-dual embedding
• A Comparative Study of Kernel Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• An Infeasible-Interior-Point Predictor-Corrector Algorithm for Linear Programming
• Semidefinite Programming
• An Interior-Point Method for Semidefinite Programming
• SimplifiedO(nL) infeasible interior-point algorithm for linear optimization using full-Newton steps
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• A Full-Newton Step O(n) Infeasible Interior-Point Algorithm for Linear Optimization
• Algorithmic Applications in Management
• Handbook of semidefinite programming. Theory, algorithms, and applications