Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization

DOI10.1137/0805002zbMath0833.90087OpenAlexW1963753244MaRDI 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 optimizationsemidefinite programminginterior point methodsperfect graphslinear equality constraintsmaximum cliquemaximum stable setclassical cone duality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Convex programming (90C25) Integer programming (90C10) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Eigenvalues, singular values, and eigenvectors (15A18)

Related Items (only showing first 100 items - show all)

An predictor–corrector interior-point algorithm for semidefinite optimization based on a wide neighbourhood ⋮ Credible autocoding of convex optimization algorithms ⋮ A modified infeasible interior-point algorithm with full-Newton step for semidefinite optimization ⋮ A quadratic semidefinite relaxation approach for resource allocation in orthogonal frequency division multiple access ⋮ A FULL NT-STEP INFEASIBLE INTERIOR-POINT ALGORITHM FOR SEMIDEFINITE OPTIMIZATION BASED ON A SELF-REGULAR PROXIMITY ⋮ Symmetry in Mathematical Programming ⋮ The bundle scheme for solving arbitrary eigenvalue optimizations ⋮ Mathematical Programming Models and Exact Algorithms ⋮ SOS Is Not Obviously Automatizable, Even Approximately ⋮ A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ ⋮ Algorithmic and explicit determination of the Lovász number for certain circulant graphs ⋮ A Newton's method for perturbed second-order cone programs ⋮ Some Recent Developments in Spectrahedral Computation ⋮ A corrector–predictor path-following algorithm for semidefinite optimization ⋮ Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set 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 ⋮ Primal-dual interior point methods for Semidefinite programming based on a new type of kernel functions ⋮ On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ An exact semidefinite programming approach for the max-mean dispersion problem ⋮ Primal-dual Newton method with steepest descent for the linear semidefinite programming problem: iterative process ⋮ An exact algorithm for semi-supervised minimum sum-of-squares clustering ⋮ New complexity analysis of a full Nesterov–Todd step interior-point method for semidefinite optimization ⋮ Complexity of the primal–dual path-following algorithms for the weighted determinant maximization problems with linear matrix inequalities in the narrow neighbourhood ⋮ An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem ⋮ An exact approach for the multi-constraint graph partitioning problem ⋮ A second-order corrector infeasible interior-point method for semidefinite optimization based on a wide neighborhood ⋮ A logarithm barrier method for semi-definite programming ⋮ On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities ⋮ SDPT3 — A Matlab software package for semidefinite programming, Version 1.3 ⋮ Approximation algorithms for maximum cut with limited unbalance ⋮ A Mehrotra predictor-corrector interior-point algorithm for semidefinite optimization ⋮ A guide to conic optimisation and its applications ⋮ COSMO: a conic operator splitting method for convex conic problems ⋮ Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices ⋮ Semidefinite Optimization Estimating Bounds on Linear Functionals Defined on Solutions of Linear ODEs ⋮ \(\mathcal{UV}\)-theory of a class of semidefinite programming and its applications ⋮ Iterated linear optimization ⋮ A class of polynomial volumetric barrier decomposition algorithms for stochastic semidefinite programming ⋮ Solvability of semidefinite complementarity problems ⋮ An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity ⋮ Interior Point Methods for Nonlinear Optimization ⋮ An SDP primal-dual algorithm for approximating the Lovász-theta function ⋮ An admissible dual internal point method for a linear semidefinite programming problem ⋮ A projected gradient algorithm for solving the maxcut SDP relaxation ⋮ Unnamed Item ⋮ Exploiting semidefinite relaxations in constraint programming ⋮ 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 ⋮ Solving semidefinite programming problems via alternating direction methods ⋮ Monte Carlo Algorithms for the Detection of Necessary Linear Matrix Inequality Constraints ⋮ Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem ⋮ Computation of the distance to semi-algebraic sets ⋮ Modeling, inference and optimization of regulatory networks based on time series data ⋮ Fast linear iterations for distributed averaging ⋮ Computational experience with a SDP-based algorithm for maximum cut with limited unbalance ⋮ Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra ⋮ Remarks on some properties of conic yield restrictions in limit analysis ⋮ Towards non-symmetric conic optimization ⋮ A wide neighbourhood interior-point method with iteration-complexity bound for semidefinite programming ⋮ Semidefinite programming relaxations and algebraic optimization in control ⋮ Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved ⋮ An Introduction to Formally Real Jordan Algebras and Their Applications in Optimization ⋮ Self-Regular Interior-Point Methods for Semidefinite Optimization ⋮ Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Sparse PCA: Convex Relaxations, Algorithms and Applications ⋮ New results for recognizing convex-QP adverse graphs ⋮ Reformulations in Mathematical Programming: Definitions and Systematics ⋮ Unnamed Item ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs ⋮ Kernel-function Based Algorithms for Semidefinite Optimization ⋮ Imaging with highly incomplete and corrupted data ⋮ Successive Quadratic Upper-Bounding for Discrete Mean-Risk Minimization and Network Interdiction ⋮ A new barrier for a class of semidefinite problems ⋮ FLOW ON DATA NETWORK AND A POSITIVE SEMIDEFINITE REPRESENTABLE DELAY FUNCTION ⋮ A new second-order Mehrotra-type predictor-corrector algorithm for SDO ⋮ 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 ⋮ A max-cut approach to heterogeneity in cryo-electron microscopy ⋮ A Maximum Likelihood Approach to Density Estimation with Semidefinite Programming ⋮ Orthogonal Trace-Sum Maximization: Applications, Local Algorithms, and Global Optimality ⋮ Solving SDP completely with an interior point oracle ⋮ Scalable Semidefinite Programming ⋮ Cuts for mixed 0-1 conic programming ⋮ A novel approach for solving semidefinite programs ⋮ Computing weighted analytic center for linear matrix inequalities using infeasible Newton's method ⋮ Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition ⋮ 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 ⋮ Detection of Lines by Combinatorial Optimization ⋮ 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^∗ ⋮ Semidefinite programming and eigenvalue bounds for the graph partition problem ⋮ Unnamed Item ⋮ Penalty/Barrier multiplier algorthm for semidefinit programming^∗

This page was built for publication: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization