An Interior-Point Method for Semidefinite Programming
From MaRDI portal
Publication:4884041
DOI10.1137/0806020zbMath0853.65066OpenAlexW2128202699MaRDI QIDQ4884041
Henry Wolkowicz, Robert J. Vanderbei, Christoph Helmberg, Franz Rendl
Publication date: 22 September 1996
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0806020
semidefinite programminginterior-point methodstable set problemgraph bisection problemsmax-cut relaxationsmax-min eigenvalue problems
Related Items
Credible autocoding of convex optimization algorithms ⋮ Decomposition-based interior point methods for stochastic quadratic second-order cone programming ⋮ 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 ⋮ Incomplete orthogonalization preconditioners for solving large and dense linear systems which arise from semidefinite programming ⋮ Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ An interior-point algorithm for semidefinite least-squares problems. ⋮ An \(\epsilon\)-sensitivity analysis for semidefinite programming ⋮ A modified homogeneous potential reduction algorithm for solving the monotone semidefinite linear complementarity problem ⋮ Optimal estimation of sensor biases for asynchronous multi-sensor data fusion ⋮ Phase retrieval for imaging problems ⋮ Exploiting sparsity in primal-dual interior-point methods for semidefinite programming ⋮ A trust region method for solving semidefinite programs ⋮ Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling ⋮ On the solution of large-scale SDP problems by the modified barrier method using iterative solvers ⋮ On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods ⋮ Semidefinite relaxations of ordering problems ⋮ A homotopy method for nonlinear semidefinite programming ⋮ Two wide neighborhood interior-point methods for symmetric cone optimization ⋮ Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs ⋮ An exact semidefinite programming approach for the max-mean dispersion problem ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ A second order Mehrotra-type predictor-corrector algorithm for semidefinite optimization ⋮ A primal-dual interior-point method based on various selections of displacement step for symmetric optimization ⋮ Lifting and separation procedures for the cut polytope ⋮ An infeasible interior-point algorithm for stochastic second-order cone optimization ⋮ On a box-constrained linear symmetric cone optimization problem ⋮ A new second-order corrector interior-point algorithm for semidefinite programming ⋮ 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 semidefinite optimization approach to the target visitation problem ⋮ Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems ⋮ Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming ⋮ Spectral methods for graph bisection problems. ⋮ A filter-type method for solving nonlinear semidefinite programming ⋮ A globally convergent filter-type trust region method for semidefinite programming ⋮ A novel neural network for solving semidefinite programming problems with some applications ⋮ A new semidefinite programming relaxation scheme for a class of quadratic matrix problems ⋮ An interior point method with a primal-dual quadratic barrier penalty function for nonlinear semidefinite programming ⋮ Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones ⋮ Homogeneous self-dual algorithms for stochastic second-order cone programming ⋮ Approximating the fixed linear crossing number ⋮ \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM ⋮ COSMO: a conic operator splitting method for convex conic problems ⋮ A convex relaxation bound for subgraph isomorphism ⋮ A polynomial time constraint-reduced algorithm for semidefinite optimization problems ⋮ Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques ⋮ Visualizing network communities with a semi-definite programming method ⋮ An \(O(\sqrt nL)\) wide neighborhood interior-point algorithm for semidefinite optimization ⋮ Performance of first-order methods for smooth convex minimization: a novel approach ⋮ Duality and profit efficiency for the hyperbolic measure model ⋮ An adaptive infeasible-interior-point method with the one-norm wide neighborhood for semi-definite programming ⋮ Equivalence of two nondegeneracy conditions for semidefinite programs ⋮ Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming ⋮ A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis ⋮ 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 ⋮ Local minima and convergence in low-rank semidefinite programming ⋮ The bounded smooth reformulation and a trust region algorithm for semidefinite complementarity problems ⋮ On self-regular IPMs (with comments and rejoinder) ⋮ Solving semidefinite programming problems via alternating direction methods ⋮ Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem ⋮ A primal-dual interior point method for nonlinear semidefinite programming ⋮ Strengthened existence and uniqueness conditions for search directions in semidefinite program\-ming ⋮ A survey on conic relaxations of optimal power flow problem ⋮ Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems ⋮ A relaxed cutting plane method for semi-infinite semi-definite programming ⋮ Data collection in population protocols with non-uniformly random scheduler ⋮ A novel formulation of the max-cut problem and related algorithm ⋮ Phase recovery, MaxCut and complex semidefinite programming ⋮ A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization ⋮ An efficient second-order cone programming approach for optimal selection in tree breeding ⋮ Chordal decomposition in operator-splitting methods for sparse semidefinite programs ⋮ A proximal augmented method for semidefinite programming problems ⋮ An arc-search infeasible interior-point method for semidefinite optimization with the negative infinity neighborhood ⋮ A polynomial-iteration infeasible interior-point algorithm with arc-search for semidefinite optimization ⋮ A conjugate gradient projection method for solving equations with convex constraints ⋮ 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 ⋮ A primal-dual interior point method for parametric semidefinite programming problems ⋮ Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations ⋮ A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming ⋮ Solving quadratic (0,1)-problems by semidefinite programs and cutting planes ⋮ Affine scaling algorithm fails for semidefinite programming ⋮ Inexact non-interior continuation method for solving large-scale monotone SDCP ⋮ Polynomial primal-dual cone affine scaling for semidefinite programming ⋮ Symmetric primal-dual path-following algorithms for semidefinite programming ⋮ Multilevel selective harmonic modulation via optimal control ⋮ Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT ⋮ A novel approach for solving semidefinite programs ⋮ A long-step primal-dual path-following method for semidefinite programming ⋮ On a commutative class of search directions for linear programming over symmetric cones ⋮ Semidefinite programming ⋮ Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem ⋮ A primal-dual interior point method for large-scale free material optimization ⋮ Novel kernel function with a hyperbolic barrier term to primal-dual interior point algorithm for SDP problems ⋮ Polynomial optimization with applications to stability analysis and control -- alternatives to sum of squares ⋮ A semi-definite programming approach for robust tracking ⋮ A modified infeasible interior-point algorithm with full-Newton step for semidefinite optimization ⋮ Exploiting low-rank structure in semidefinite programming by approximate operator splitting ⋮ Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems ⋮ Advances in Quantum Detection ⋮ Data Collection in Population Protocols with Non-uniformly Random Scheduler ⋮ Convergence to a second-order critical point by a primal-dual interior point trust-region method for nonlinear semidefinite programming ⋮ Three‐dimensional Mohr–Coulomb limit analysis using semidefinite programming ⋮ Fast implementation for semidefinite programs with positive matrix completion ⋮ Finding graph embeddings by incremental low-rank semidefinite programming ⋮ A conversion of an SDP having free variables into the standard form SDP ⋮ A continuation algorithm for max-cut problem ⋮ A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming ⋮ A solution method for combined semi-infinite and semi-definite programming ⋮ A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms ⋮ Combining semidefinite and polyhedral relaxations for integer programs ⋮ An upper bound on the minimum rank of a symmetric Toeplitz matrix completion problem ⋮ A branch and bound method solving the max–min linear discriminant analysis problem ⋮ Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B ⋮ Corrector-predictor interior-point method with new search direction for semidefinite optimization ⋮ A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems ⋮ A Geodesic Interior-Point Method for Linear Optimization over Symmetric Cones ⋮ Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials ⋮ A full NT-step infeasible interior-point algorithm for semidefinite optimization ⋮ $LDL^T$ Direction Interior Point Method for Semidefinite Programming ⋮ A team algorithm for robust stability analysis and control design of uncertain time-varying linear systems using piecewise quadratic Lyapunov functions ⋮ SDPT3 — A Matlab software package for semidefinite programming, Version 1.3 ⋮ A Mehrotra predictor-corrector interior-point algorithm for semidefinite optimization ⋮ FANOK: Knockoffs in Linear Time ⋮ Cone-LP's and semidefinite programs: Geometry and a simplex-type method ⋮ Quadratic knapsack relaxations using cutting planes and semidefinite programming ⋮ A NEW METHOD TO CALCULATE THE INCONCLUSIVE COEFFICIENTS IN THE QUANTUM STATE DISCRIMINATION ⋮ On homogeneous interrior-point algorithms for semidefinite programming ⋮ Semidefinite programming and combinatorial optimization ⋮ A projected gradient algorithm for solving the maxcut SDP relaxation ⋮ Mesh adaptive computation of upper and lower bounds in limit analysis ⋮ Implementation of interior point methods for mixed semidefinite and second order cone optimization problems ⋮ Global optimization in protein docking using clustering, underestimation and semidefinite programming ⋮ New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction ⋮ A robust algorithm for semidefinite programming ⋮ Interior-point methods for CartesianP*(κ)-linear complementarity problems over symmetric cones based on the eligible kernel functions ⋮ 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 ⋮ The State-of-the-Art in Conic Optimization Software ⋮ Latest Developments in the SDPA Family for Solving Large-Scale SDPs ⋮ On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0 ⋮ Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems ⋮ PREDICTOR–CORRECTOR SMOOTHING NEWTON METHOD FOR SOLVING SEMIDEFINITE PROGRAMMING ⋮ A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM ⋮ A new second-order Mehrotra-type predictor-corrector algorithm for SDO ⋮ Exact Solution Methods for the k-Item Quadratic Knapsack Problem ⋮ A primal-dual interior point trust-region method for nonlinear semidefinite programming ⋮ A relaxed logarithmic barrier method for semidefinite programming ⋮ Low-rank exploitation in semidefinite programming for control ⋮ Unnamed Item ⋮ Knowledge-based semidefinite linear programming classifiers ⋮ Global Registration of Multiple Point Clouds Using Semidefinite Programming ⋮ An efficient support vector machine learning method with second-order cone programming for large-scale problems ⋮ Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition ⋮ 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 ⋮ 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 ⋮ Sdpha: a Matlab implementation of homogeneous interior-point algorithms for semidefinite programming ⋮ CSDP, A C library for semidefinite programming ⋮ 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∗ ⋮ A primal–dual regularized interior-point method for semidefinite programming
