Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization

DOI10.1137/0805002zbMath0833.90087MaRDI QIDQ4764307

Farid Alizadeh

Publication date: 4 May 1995

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0c876ce34855898bbd57200ae28154343e2fe00e

zbMATH Keywords

eigenvalue optimization; semidefinite programming; interior point methods; perfect graphs; linear equality constraints; maximum clique; maximum stable set; classical cone duality

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C25: Convex programming

90C10: Integer programming

90C05: Linear programming

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

15A18: Eigenvalues, singular values, and eigenvectors

Related Items

SDPT3 — A Matlab software package for semidefinite programming, Version 1.3, Implementation of interior point methods for mixed semidefinite and second order cone optimization problems, On the connections between semidefinite optimization and vector optimization, A sequential quadratic penalty method for nonlinear semidefinite programming, A sequential quadratic penalty method for nonlinear semidefinite programming, Extending Mehrotra and Gondzio higher order methods to mixed semidefinite-quadratic-linear programming, Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants, SDPLIB 1.2, a library of semidefinite programming test problems, Penalty/Barrier multiplier algorthm for semidefinit programming^∗, A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ, Monte Carlo Algorithms for the Detection of Necessary Linear Matrix Inequality Constraints, A solution method for combined semi-infinite and semi-definite programming, Computation of the distance to semi-algebraic sets, Identifying redundant linear constraints in systems of linear matrix inequality constraints, Sparse Approximate Solutions to Semidefinite Programs, Semidefinite programming and combinatorial optimization, The omnipresence of Lagrange, Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION, Semidefinite programming for discrete optimization and matrix completion problems, Semi-definite relaxation algorithm of multiple knapsack problem, The bounded smooth reformulation and a trust region algorithm for semidefinite complementarity problems, A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization, Conic mixed-integer rounding cuts, \(\ell ^2_2\) spreading metrics for vertex ordering problems, Stochastic semidefinite programming: a new paradigm for stochastic optimization, Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling, Theory of semidefinite programming for sensor network localization, Properties of the augmented Lagrangian in nonlinear semidefinite optimization, Primal-dual interior-point algorithm for convex quadratic semi-definite optimization, Semi-definite programming techniques for structured quadratic inverse eigenvalue problems, Bandgap optimization of two-dimensional photonic crystals using semidefinite programming and subspace methods, Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems, Lower-order penalization approach to nonlinear semidefinite programming, Central paths in semidefinite programming, generalized proximal-point method and Cauchy trajectories in Riemannian manifolds, A new primal-dual path-following interior-point algorithm for semidefinite optimization, Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3, Inexact non-interior continuation method for solving large-scale monotone SDCP, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Robust stability and performance analysis of uncertain systems using linear matrix inequalities, 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, Applications of semidefinite programming, A long-step primal-dual path-following method for semidefinite programming, Problems of distance geometry and convex properties of quadratic maps, Approximability of maximum splitting of k-sets and some other Apx-complete problems, Semidefinite programming in combinatorial optimization, Cuts, matrix completions and graph rigidity, Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs, Semidefinite programming and matrix scaling over the semidefinite cone., Best ellipsoidal relaxation to solve a nonconvex problem., Indefinite stochastic LQ control with cross term via semidefinite programming, On weighted centers for semidefinite programming, Heuristics for semirandom graph problems, On self-regular IPMs (with comments and rejoinder), Discretization method for semi-definite programming, A new proof of the strong duality theorem for semidefinite programming, A unified class of directly solvable semidefinite programming problems, Inverse conic programming with applications, Analyticity of the central path at the boundary point in semidefinite programming, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Some geometric results in semidefinite programming, Linear programming, complexity theory and elementary functional analysis, Semidefinite programming relaxations for the graph partitioning problem, A potential reduction algorithm for an extended SDP problem, Graph rigidity via Euclidean distance matrices, Algorithmic and explicit determination of the Lovász number for certain circulant graphs, A Newton's method for perturbed second-order cone programs, Approximation algorithms for maximum cut with limited unbalance, Solvability of semidefinite complementarity problems, Exploiting semidefinite relaxations in constraint programming, On the behavior of the homogeneous self-dual model for conic convex optimization, Solving semidefinite programming problems via alternating direction methods, Fast linear iterations for distributed averaging, Cuts for mixed 0-1 conic programming, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, A projected gradient algorithm for solving the maxcut SDP relaxation, A Maximum Likelihood Approach to Density Estimation with Semidefinite Programming, Detection of Lines by Combinatorial Optimization, Complexity of the primal–dual path-following algorithms for the weighted determinant maximization problems with linear matrix inequalities in the narrow neighbourhood, A logarithm barrier method for semi-definite programming, Interior Point Methods for Nonlinear Optimization, Reformulations in Mathematical Programming: Definitions and Systematics, Kernel-function Based Algorithms for Semidefinite Optimization, A new barrier for a class of semidefinite problems, FLOW ON DATA NETWORK AND A POSITIVE SEMIDEFINITE REPRESENTABLE DELAY FUNCTION, Unnamed Item, Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp^∗