The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
Abstract
This paper studies the semidefinite programming SDP problem, i.e., the optimization problem of a linear function of a symmetric matrix subject to linear equality constraints and the additional condition that the matrix be positive semidefinite. First the classical cone duality is reviewed as it is specialized to SDP is reviewed. Next an interior point algorithm is presented that converges to the optimal solution in polynomial time. The approach is a direct extension of Ye’s projective method for linear programming. It is also argued that many known interior point methods for linear programs can be transformed in a mechanical way to algorithms for SDP with proofs of convergence and polynomial time complexity carrying over in a similar fashion. Finally, the significance of these results is studied in a variety of combinatorial optimization problems including the general 0-1 integer programs, the maximum clique and maximum stable set problems in perfect graphs, the maximum k-partite subgraph problem in graphs, and various graph partitioning and cut problems. As a result, barrier oracles are presented for certain combinatorial optimization problems (in particular, clique and stable set problem for perfect graphs) whose linear programming formulation requires exponentially many inequalities. Existence of such barrier oracles refutes the commonly believed notion that to solve a combinatorial optimization problem with interior point methods, its linear programming formulation is eeded explicitly.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Horn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280
A new polynomial-time algorithm for linear programming
Karmarkar, N. (1984) · Combinatorica · doi:10.1007/bf02579150 · Cited by 4,794
Interior-Point Polynomial Algorithms in Convex Programming
Nesterov, Y., & Nemirovskii, A. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970791 · Cited by 4,334
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
Theory of Linear and Integer Programming
Smith, D. K. (1987) · Journal of the Operational Research Society · doi:10.1057/jors.1987.94 · Cited by 2,708
The ellipsoid method and its consequences in combinatorial optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1981) · Combinatorica · doi:10.1007/bf02579273 · Cited by 2,011
On the Shannon capacity of a graph
Lovasz, L. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1055985 · Cited by 1,624
Cones of Matrices and Set-Functions and 0–1 Optimization
Lovász, L., & Schrijver, A. (1991) · SIAM Journal on Optimization · doi:10.1137/0801013 · Cited by 1,008
Cited by
Vandenberghe, L., & Boyd, S. (1996) · SIAM Review · doi:10.1137/1038003 · Cited by 4,105
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Fast linear iterations for distributed averaging
Xiao, L., & Boyd, S. (2004) · Systems & Control Letters · doi:10.1016/j.sysconle.2004.02.022 · Cited by 2,706
SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
Toh, K. C., Todd, M. J., & Tütüncü, R. H. (1999) · Optimization Methods and Software · doi:10.1080/10556789908805762 · Cited by 1,894
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
The Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
Towards Sharp Inapproximability For Any 2-CSP
Austrin, P. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.41 · Cited by 1,294
Solving semidefinite-quadratic-linear programs using SDPT3
T�t�nc�, R. H., Toh, K. C., & Todd, M. J. (2003) · Mathematical Programming · doi:10.1007/s10107-002-0347-5 · Cited by 1,152
Disciplined Convex Programming
Grant, M., Boyd, S., & Ye, Y. (2006) · Nonconvex Optimization and Its Applications · doi:10.1007/0-387-30528-9_7 · Cited by 1,026
Robust Solutions to Uncertain Semidefinite Programs
El Ghaoui, L., Oustry, F., & Lebret, H. (1998) · SIAM Journal on Optimization · doi:10.1137/s1052623496305717 · Cited by 935
Shock Graphs and Shape Matching
Siddiqi, K., Shokoufandeh, A., Dickinson, S. J., & Zucker, S. W. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008102926703 · Cited by 756
Fastest Mixing Markov Chain on a Graph
Boyd, S., Diaconis, P., & Xiao, L. (2004) · SIAM Review · doi:10.1137/s0036144503423264 · Cited by 744
A Direct Formulation for Sparse PCA Using Semidefinite Programming
d'Aspremont, A., El Ghaoui, L., Jordan, M. I., & Lanckriet, G. R. G. (2007) · SIAM Review · doi:10.1137/050645506 · Cited by 678
Determinant Maximization with Linear Matrix Inequality Constraints
Vandenberghe, L., Boyd, S., & Wu, S.-P. (1998) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479896303430 · Cited by 652
Network of time-multiplexed optical parametric oscillators as a coherent Ising machine
Marandi, A., Wang, Z., Takata, K., Byer, R. L., & Yamamoto, Y. (2014) · Nature Photonics · doi:10.1038/nphoton.2014.249 · Cited by 541
Domain Adaptation: Learning Bounds and Algorithms
Mansour, Y., Mohri, M., & Rostamizadeh, A. (2009) · arXiv · doi:10.48550/arxiv.0902.3430 · Cited by 504
A Spectral Bundle Method for Semidefinite Programming
Helmberg, C., & Rendl, F. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497328987 · Cited by 436
Some applications of Laplace eigenvalues of graphs
Mohar, B. (1997) · Graph Symmetry · doi:10.1007/978-94-015-8937-6_6 · Cited by 422
Expander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S., & Vazirani, U. (2009) · Journal of the ACM · doi:10.1145/1502793.1502794 · Cited by 418
Interior Point Methods for Nonlinear Optimization
Pólik, I., & Terlaky, T. (2010) · Lecture Notes in Mathematics · doi:10.1007/978-3-642-11339-0_4 · Cited by 394
Minimum Interference Channel Assignment in Multiradio Wireless Mesh Networks
Subramanian, A. P., Gupta, H., Das, S. R., & Cao, J. (2008) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2008.70 · Cited by 377
On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
Pataki, G. (1998) · Mathematics of Operations Research · doi:10.1287/moor.23.2.339 · Cited by 332
Theory of semidefinite programming for Sensor Network Localization
So, A. M.-C., & Ye, Y. (2007) · Mathematical Programming · doi:10.1007/s10107-006-0040-1 · Cited by 326
Expander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S., & Vazirani, U. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007355 · Cited by 297
Knuth, D. E. (1994) · The Electronic Journal of Combinatorics · doi:10.37236/1193 · Cited by 296
A Discriminative Metric Learning Based Anomaly Detection Method
Du, B., & Zhang, L. (2014) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2014.2303895 · Cited by 267
DC formulations and algorithms for sparse optimization problems
Gotoh, J.-Y., Takeda, A., & Tono, K. (2018) · Mathematical Programming · doi:10.1007/s10107-017-1181-0 · Cited by 184
Metadata
- Authors
- Alizadeh, F.
- Venue
- SIAM Journal on Optimization
- Published
- 1995-02
- Volume
- 5
- Issue
- 1
- Pages
- 13-51
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W1963753244
- Cited by
- 892
- References
- 27
- FWCI
- 36.88
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.