Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
From MaRDI portal
Publication:4764307
DOI10.1137/0805002zbMath0833.90087OpenAlexW1963753244MaRDI 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 optimizationsemidefinite programminginterior point methodsperfect graphslinear equality constraintsmaximum cliquemaximum stable setclassical cone duality
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
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∗, A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants, A new perspective on low-rank optimization, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, Distance to a constitutive tensor isotropy stratum by the Lasserre polynomial optimization method, Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates, Corrector-predictor interior-point method with new search direction for semidefinite optimization, PCA Sparsified, A class of new search directions for full-NT step feasible interior point method in semidefinite optimization, Lagrangian duality in convex conic programming with simple proofs, Unnamed Item, Semidefinite programming and combinatorial optimization, The omnipresence of Lagrange, Identifying redundant linear constraints in systems of linear matrix inequality constraints, Sparse Approximate Solutions to Semidefinite Programs, Complexity, exactness, and rationality in polynomial optimization, Complexity, exactness, and rationality in polynomial optimization, Random Spectrahedra, A new wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization, Witnessing entanglement by proxy, A Semidefinite Hierarchy for Containment of Spectrahedra, A primal–dual regularized interior-point method for semidefinite programming, Douglas-Rachford splitting method for semidefinite programming, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, A linear-time algorithm for trust region problems, Problems of distance geometry and convex properties of quadratic maps, A new wide-neighborhood predictor-corrector interior-point method for semidefinite optimization, Community detection with a subsampled semidefinite program, An inexact non-interior continuation method for semidefinite programming: convergence analysis and numerical results, Approximability of maximum splitting of k-sets and some other Apx-complete problems, Conic mixed-integer rounding cuts, \(\ell ^2_2\) spreading metrics for vertex ordering problems, A full Nesterov-Todd-step feasible primal-dual interior point algorithm for convex quadratic semi-definite optimization, A feasible primal-dual interior point method for linear semidefinite programming, Some geometric results in semidefinite programming, Semidefinite programming in combinatorial optimization, Cuts, matrix completions and graph rigidity, Stochastic semidefinite programming: a new paradigm for stochastic optimization, Graph coloring and semidefinite rank, 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, Sufficient conditions for global optimality of semidefinite optimization, Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs, Linear programming, complexity theory and elementary functional analysis, A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function, Polynomial time solvability of non-symmetric semidefinite programming, A second order Mehrotra-type predictor-corrector algorithm for semidefinite optimization, Newton's method for computing the nearest correlation matrix with a simple upper bound, A new second-order corrector interior-point algorithm for semidefinite programming, Computing maximin efficient experimental designs using the methods of semidefinite programming, Distance metric learning by minimal distance maximization, Nonsingularity of FB system and constraint nondegeneracy in semidefinite programming, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, Optimality theorems for convex semidefinite vector optimization problems, Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme, A filter-type method for solving nonlinear semidefinite programming, The \(Q\) method for symmetric cone programming, On global optimization with indefinite quadratics, Semidefinite programming and matrix scaling over the semidefinite cone., Inexact SA method for constrained stochastic convex SDP and application in Chinese stock market, A quantum characterization of NP, A novel neural network for solving semidefinite programming problems with some applications, On the extension of an arc-search interior-point algorithm for semidefinite optimization, A performance guaranteed sampled-data event-triggered consensus approach for linear multi-agent systems, Best ellipsoidal relaxation to solve a nonconvex problem., Alternating direction method of multipliers for sparse principal component analysis, Semidefinite programming relaxations for the graph partitioning problem, Primal-dual interior-point algorithm for convex quadratic semi-definite optimization, Convergence analysis on matrix splitting iteration algorithm for semidefinite linear complementarity problems, Indefinite stochastic LQ control with cross term via semidefinite programming, A potential reduction algorithm for an extended SDP problem, Graph rigidity via Euclidean distance matrices, Numerical algebraic geometry and semidefinite programming, Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION, Return-mapping algorithms for associative isotropic hardening plasticity using conic optimization, DC formulations and algorithms for sparse optimization problems, Random Laplacian matrices and convex relaxations, An \(O(\sqrt nL)\) wide neighborhood interior-point algorithm for semidefinite optimization, Optimality criteria without constraint qualifications for linear semidefinite problems, An adaptive infeasible-interior-point method with the one-norm wide neighborhood for semi-definite programming, Semi-definite programming techniques for structured quadratic inverse eigenvalue problems, An interior point method for solving semidefinite programs using cutting planes and weighted analytic centers, Semidefinite programming for discrete optimization and matrix completion problems, Semi-definite relaxation algorithm of multiple knapsack problem, Bandgap optimization of two-dimensional photonic crystals using semidefinite programming and subspace methods, Extension of smoothing Newton algorithms to solve linear programming over symmetric cones, The bounded smooth reformulation and a trust region algorithm for semidefinite complementarity problems, On self-regular IPMs (with comments and rejoinder), A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs, 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, Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term, Linear operators and positive semidefiniteness of symmetric tensor spaces, Inverse conic programming with applications, An efficient parameterized logarithmic kernel function for semidefinite optimization, A survey on conic relaxations of optimal power flow problem, Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems, Lower-order penalization approach to nonlinear semidefinite programming, Low-order penalty equations for semidefinite linear complementarity problems, A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization, An arc-search infeasible interior-point method for semidefinite optimization with the negative infinity neighborhood, Central paths in semidefinite programming, generalized proximal-point method and Cauchy trajectories in Riemannian manifolds, A polynomial-iteration infeasible interior-point algorithm with arc-search for semidefinite optimization, 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, Decomposed structured subsets for semidefinite and sum-of-squares optimization, Complexity aspects of local minima and related notions, 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, 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, Applications of semidefinite programming, On weighted centers for semidefinite programming, Analyticity of the central path at the boundary point in semidefinite programming, A long-step primal-dual path-following method for semidefinite programming, Heuristics for semirandom graph problems, Primal-dual Newton method with steepest descent for the linear semidefinite programming problem: Newton's system of equations