Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
From MaRDI portal
Publication:4764307
DOI10.1137/0805002zbMath0833.90087MaRDI QIDQ4764307
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
eigenvalue optimization; semidefinite programming; interior point methods; perfect graphs; linear equality constraints; maximum clique; maximum stable set; classical cone duality
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, 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, Lower-order penalization approach to nonlinear semidefinite programming, 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, Unnamed Item, Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp∗
