Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
From MaRDI portal
Publication:4764307
DOI10.1137/0805002zbMATH Open0833.90087OpenAlexW1963753244MaRDI QIDQ4764307FDOQ4764307
Authors: 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
Recommendations
interior point methodssemidefinite programmingmaximum cliqueeigenvalue optimizationmaximum stable setperfect graphslinear equality constraintsclassical cone duality
Convex programming (90C25) Linear programming (90C05) Programming involving graphs or networks (90C35) Eigenvalues, singular values, and eigenvectors (15A18) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Integer programming (90C10)
Cited In (only showing first 100 items - show all)
- A second order Mehrotra-type predictor-corrector algorithm for semidefinite optimization
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- Analyticity of the central path at the boundary point in semidefinite programming
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step
- Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra
- Sparse PCA: convex relaxations, algorithms and applications
- Primal-dual interior-point algorithm for convex quadratic semi-definite optimization
- Cuts for mixed 0-1 conic programming
- Sparse Approximate Solutions to Semidefinite Programs
- A class of polynomial volumetric barrier decomposition algorithms for stochastic semidefinite programming
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Semidefinite programming relaxations for the graph partitioning problem
- Extending Mehrotra and Gondzio higher order methods to mixed semidefinite-quadratic-linear programming
- Semi-definite programming techniques for structured quadratic inverse eigenvalue problems
- The omnipresence of Lagrange
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Semidefinite programming for discrete optimization and matrix completion problems
- Optimality theorems for convex semidefinite vector optimization problems
- Detection of Lines by Combinatorial Optimization
- Towards non-symmetric conic optimization
- A logarithm barrier method for semi-definite programming
- A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function
- A sequential quadratic penalty method for nonlinear semidefinite programming
- Douglas-Rachford splitting method for semidefinite programming
- Stochastic semidefinite programming: a new paradigm for stochastic optimization
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- Reformulations in Mathematical Programming: Definitions and Systematics
- Applications of semidefinite programming
- A quantum characterization of NP
- A Maximum Likelihood Approach to Density Estimation with Semidefinite Programming
- A linear-time algorithm for trust region problems
- Semidefinite programming in combinatorial optimization
- Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem
- A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization
- A quadratic semidefinite relaxation approach for resource allocation in orthogonal frequency division multiple access
- Implementation of interior point methods for mixed semidefinite and second order cone optimization problems
- Full-Newton step infeasible interior-point algorithm for SDO problems
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- SDPLIB 1.2, a library of semidefinite programming test problems
- Symmetric primal-dual path-following algorithms for semidefinite programming
- New complexity analysis of a full Nesterov-Todd step interior-point method for semidefinite optimization
- An inexact non-interior continuation method for semidefinite programming: convergence analysis and numerical results
- Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs
- Topics in semidefinite and interior-point methods
- An interior point constraint generation algorithm for semi-infinite optimization with health-care application
- A second-order mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming
- Credible autocoding of convex optimization algorithms
- A Newton's method for perturbed second-order cone programs
- Problems of distance geometry and convex properties of quadratic maps
- Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling
- Interior Point Methods for Nonlinear Optimization
- Linear operators and positive semidefiniteness of symmetric tensor spaces
- Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- Fast linear iterations for distributed averaging
- Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
- Conic mixed-integer rounding cuts
- A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs
- A feasible primal-dual interior point method for linear semidefinite programming
- Inexact non-interior continuation method for solving large-scale monotone SDCP
- Lower-order penalization approach to nonlinear semidefinite programming
- A full NT-step infeasible interior-point algorithm for semidefinite optimization based on a self-regular proximity
- Cone-LP's and semidefinite programs: geometry and a simplex-type method
- Extension of smoothing Newton algorithms to solve linear programming over symmetric cones
- Kernel-function Based Algorithms for Semidefinite Optimization
- SDP relaxations for some combinatorial optimization problems
- Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems
- Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
- An exact approach for the multi-constraint graph partitioning problem
- Inverse conic programming with applications
- Solvability of semidefinite complementarity problems
- Robust stability and performance analysis of uncertain systems using linear matrix inequalities
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Linear programming, complexity theory and elementary functional analysis
- Symmetry in mathematical programming
- A projected gradient algorithm for solving the maxcut SDP relaxation
- Alternating direction method of multipliers for sparse principal component analysis
- Some geometric results in semidefinite programming
- Title not available (Why is that?)
- Modeling, inference and optimization of regulatory networks based on time series data
- Sufficient conditions for global optimality of semidefinite optimization
- Solving semidefinite programming problems via alternating direction methods
- On weighted centers for semidefinite programming
- Title not available (Why is that?)
- A potential reduction algorithm for an extended SDP problem
- Newton's method for computing the nearest correlation matrix with a simple upper bound
- Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved
- Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp∗
- Theory of semidefinite programming for sensor network localization
- A novel approach for solving semidefinite programs
- Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants
- A new primal-dual path-following interior-point algorithm for semidefinite optimization
- Monte Carlo Algorithms for the Detection of Necessary Linear Matrix Inequality Constraints
- Optimality criteria without constraint qualifications for linear semidefinite problems
- An exact semidefinite programming approach for the max-mean dispersion problem
- Iterated linear optimization
- Mathematical programming models and exact algorithms
- Affine scaling algorithm fails for semidefinite programming
- Semi-definite relaxation algorithm of multiple knapsack problem
This page was built for publication: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4764307)
