The DOI matches its Crossref record; 37 of the 37 references it cites were found in a registry or an index.
Semidefinite Programming
Abstract
In semidefinite programming, one minimizes a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so semidefinite programs are convex optimization problems. semidefinite programming unifies several standard problems (e.g., linear and quadratic programming) and finds many applications in engineering and combinatorial optimization. Although semidefinite programs are much more general than linear programs, they are not much harder to solve. Most interior-point methods for linear programming have been generalized to semidefinite programs. As in linear programming, these methods have polynomial worst-case complexity and perform very well in practice. This paper gives a survey of the theory and applications of semidefinite programs and an introduction to primaldual interior-point methods for their solution.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Linear Matrix Inequalities in System and Control Theory
Boyd, S., El Ghaoui, L., Feron, E., & Balakrishnan, V. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970777 · Cited by 21,687
Self-citationRockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
A new polynomial-time algorithm for linear programming
Karmarkar, N. (1984) · Combinatorica · doi:10.1007/bf02579150 · Cited by 4,794
LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
Paige, C. C., & Saunders, M. A. (1982) · ACM Transactions on Mathematical Software · doi:10.1145/355984.355989 · Cited by 4,387
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
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
Axelsson, O. (1994) · Cambridge University Press eBooks · doi:10.1017/cbo9780511624100 · Cited by 2,085
Solution of Sparse Indefinite Systems of Linear Equations
Paige, C. C., & Saunders, M. A. (1975) · SIAM Journal on Numerical Analysis · doi:10.1137/0712047 · Cited by 1,620
Minimization Methods for Non-Differentiable Functions
Shor, N. Z. (1985) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-82118-9 · Cited by 1,551
On a Theorem of Weyl Concerning Eigenvalues of Linear Transformations I
Fan, K. (1949) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.35.11.652 · Cited by 1,016
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
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
Alizadeh, F. (1995) · SIAM Journal on Optimization · doi:10.1137/0805002 · Cited by 892
An Interior-Point Method for Semidefinite Programming
Helmberg, C., Rendl, F., Vanderbei, R. J., & Wolkowicz, H. (1996) · SIAM Journal on Optimization · doi:10.1137/0806020 · Cited by 706
Lower Bounds for the Partitioning of Graphs
Donath, W. E., & Hoffman, A. J. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.175.0420 · Cited by 660
Methods of Descent for Nondifferentiable Optimization
Kiwiel, K. C. (1985) · Lecture notes in mathematics · doi:10.1007/bfb0074500 · Cited by 533
Nonlinear Programming: Sequential Unconstrained Minimization Techniques
Fiacco, A. V., & McCormick, G. P. (1990) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971316 · Cited by 470
Characterization of the subdifferential of some matrix norms
Watson, G. A. (1992) · Linear Algebra and its Applications · doi:10.1016/0024-3795(92)90407-2 · Cited by 364
Path-Following Methods for Linear Programming
Gonzaga, C. C. (1992) · SIAM Review · doi:10.1137/1034048 · Cited by 341
Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1994) · INFORMS journal on computing · doi:10.1287/ijoc.6.1.1 · Cited by 315
Borkowski, J. J., & Pukelsheim, F. (1994) · Technometrics · doi:10.2307/1270234 · Cited by 301
Franklin, J. (1980) · Undergraduate Texts in Mathematics · doi:10.1007/978-3-662-25317-5_2 · Cited by 220
Large-Scale Optimization of Eigenvalues
Overton, M. L. (1992) · SIAM Journal on Optimization · doi:10.1137/0802007 · Cited by 209
On Minimizing the Maximum Eigenvalue of a Symmetric Matrix
Overton, M. L. (1988) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0609021 · Cited by 206
Overton, M. L., & Womersley, R. S. (1993) · Mathematical Programming · doi:10.1007/bf01585173 · Cited by 189
An $$O(\sqrt n L)$$ iteration potential reduction algorithm for linear complementarity problems
Kojima, M., Mizuno, S., & Yoshise, A. (1991) · Mathematical Programming · doi:10.1007/bf01594942 · Cited by 173
A New Method for Optimal Truss Topology Design
Ben-Tal, A., & Bendsøe, M. P. (1993) · SIAM Journal on Optimization · doi:10.1137/0803015 · Cited by 166
Some geometric results in semidefinite programming
Ramana, M., & Goldman, A. J. (1995) · Journal of Global Optimization · doi:10.1007/bf01100204 · Cited by 162
Symmetric indefinite systems for interior point methods
Vanderbei, R. J., & Carpenter, T. J. (1993) · Mathematical Programming · doi:10.1007/bf01581257 · Cited by 148
Advances in Optimization and Parallel Computing
Pardalos, P. M. (1992) · Elsevier eBooks · Cited by 146
Eigenvalues in Combinatorial Optimization
Mohar, B., & Poljak, S. (1993) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4613-8354-3_5 · Cited by 140
The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices
Cullum, J. K., Donath, W. E., & Wolfe, P. (1975) · Mathematical programming studies · doi:10.1007/bfb0120698 · Cited by 122
On the Sum of the Largest Eigenvalues of a Symmetric Matrix
Overton, M. L., & Womersley, R. S. (1992) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0613006 · Cited by 115
An Interior-Point Method for Minimizing the Maximum Eigenvalue of a Linear Combination of Matrices
Jarre, F. (1993) · SIAM Journal on Control and Optimization · doi:10.1137/0331064 · Cited by 106
Bentler, P. M., & Woodward, J. A. (1980) · Psychometrika · doi:10.1007/bf02294079 · Cited by 97
Some applications of optimization in matrix theory
Wolkowicz, H. (1981) · Linear Algebra and its Applications · doi:10.1016/0024-3795(81)90143-9 · Cited by 62
Weighted Minimum Trace Factor Analysis
Shapiro, A. (1982) · Psychometrika · doi:10.1007/bf02294158 · Cited by 59
On Maximizing the Minimum Eigenvalue of a Linear Combination of Symmetric Matrices
Allwright, J. C. (1989) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0610026 · Cited by 19
Cited by
A Comprehensive Survey on Transfer Learning
Zhuang, F., Qi, Z., Duan, K., Xi, D., Zhu, Y., Zhu, H., Xiong, H., & He, Q. (2021) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3004555 · Cited by 6,678
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
(2006) · The MIT Press eBooks · doi:10.7551/mitpress/9780262033589.001.0001 · Cited by 4,280
Distance Metric Learning for Large Margin Nearest Neighbor Classification
Weinberger, K. Q., & Saul, L. K. (2009) · Journal of Machine Learning Research · doi:10.5555/1577069.1577078 · Cited by 4,044
Semidefinite Relaxation of Quadratic Optimization Problems
Luo, Z.-Q., Ma, W.-K., So, A., Ye, Y., & Zhang, S. (2010) · IEEE Signal Processing Magazine · doi:10.1109/msp.2010.936019 · Cited by 3,715
Metadata
- Authors
- Vandenberghe, L., & Boyd, S.
- Venue
- SIAM Review
- Published
- 1996-03
- Volume
- 38
- Issue
- 1
- Pages
- 49-95
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2912522929
- Cited by
- 4,105
- References
- 37
- FWCI
- 80.65
- 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.