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
Cited by
Items 101–129 of 129
Tao, D., Li, X., Wu, X., Hu, W., & Maybank, S. J. (2007) · Knowledge and Information Systems · doi:10.1007/s10115-006-0050-6 · Cited by 299
A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers
Negahban, S. N., Ravikumar, P., Wainwright, M. J., & Yu, B. (2012) · Statistical Science · doi:10.1214/12-sts400 · Cited by 287
Computing quantum discord is NP-complete
Huang, Y. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/3/033027 · Cited by 286
Optimal Dispatch of Photovoltaic Inverters in Residential Distribution Systems
Dall'Anese, E., Dhople, S. V., & Giannakis, G. B. (2014) · IEEE Transactions on Sustainable Energy · doi:10.1109/tste.2013.2292828 · Cited by 285
SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group
Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364918784361 · Cited by 282
Robustness of asymmetry and coherence of quantum states
Piani, M., Cianciaruso, M., Bromley, T. R., Napoli, C., Johnston, N., & Adesso, G. (2016) · Physical Review A · doi:10.1103/physreva.93.042107 · Cited by 279
Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
Benson, S. J., Ye, Y., & Zhang, X. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497328008 · Cited by 276
Verification methods: Rigorous results using floating-point arithmetic
Rump, S. M. (2010) · Acta Numerica · doi:10.1017/s096249291000005x · Cited by 276
Spectral Methods for Dimensionality Reduction
Saul, L. K., Weinberger, K. Q., Sha, F., Ham, J., & Lee, D. D. (2006) · Semi-Supervised Learning · doi:10.7551/mitpress/6173.003.0022 · Cited by 272
Quantum feedback: Theory, experiments, and applications
Zhang, J., Liu, Y.-X., Wu, R.-B., Jacobs, K., & Nori, F. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.02.003 · Cited by 272
Carving out the space of 4D CFTs
Poland, D., Simmons-Duffin, D., & Vichi, A. (2012) · Journal of High Energy Physics · doi:10.1007/jhep05(2012)110 · Cited by 270
Resolution of Conflicts Involving Many Aircraft via Semidefinite Programming
Frazzoli, E., Mao, Z.-H., Oh, J.-H., & Feron, E. (2001) · Journal of Guidance, Control, and Dynamics · doi:10.2514/2.4678 · Cited by 269
An Introduction to Polynomial and Semi-Algebraic Optimization
Lasserre, J. B. (2015) · Cambridge University Press eBooks · doi:10.1017/cbo9781107447226 · Cited by 260
Optimized Stochastic Policies for Task Allocation in Swarms of Robots
Berman, S., Halasz, A., Hsieh, M. A., & Kumar, V. (2009) · IEEE Transactions on Robotics · doi:10.1109/tro.2009.2024997 · Cited by 258
A review of optimization methodologies in support vector machines
Shawe-Taylor, J., & Sun, S. (2011) · Neurocomputing · doi:10.1016/j.neucom.2011.06.026 · Cited by 256
Primal and dual linear decision rules in stochastic and robust optimization
Kuhn, D., Wiesemann, W., & Georghiou, A. (2011) · Mathematical Programming · doi:10.1007/s10107-009-0331-4 · Cited by 256
Gaussian Process Models for Computer Experiments With Qualitative and Quantitative Factors
Qian, P. Z. G., Wu, H., & Wu, C. F. J. (2008) · Technometrics · doi:10.1198/004017008000000262 · Cited by 255
Quantum Speed-Ups for Solving Semidefinite Programs
Brandao, F. G. S. L., & Svore, K. M. (2017) · 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) · doi:10.1109/focs.2017.45 · Cited by 142
Theory and applications of robust optimization
Bertsimas, D., Brown, D. B., & Caramanis, C. (2011) · SIAM Review · doi:10.1137/080734510 · Cited by 134
Cooperative Multigroup Multicast Transmission in Integrated Terrestrial-Satellite Networks
Zhu, X., Jiang, C., Yin, L., Kuang, L., Ge, N., & Lu, J. (2018) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2018.2832780 · Cited by 108
Large Margin Local Estimate With Applications to Medical Image Classification
Song, Y., Cai, W., Huang, H., Zhou, Y., Feng, D. D., Wang, Y., Fulham, M. J., & Chen, M. (2015) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2015.2393954 · Cited by 87
A convex relaxation for approximate global optimization in simultaneous localization and mapping
Rosen, D. M., DuHadway, C., & Leonard, J. J. (2015) · 2015 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2015.7140014 · Cited by 56
“it can be expressed as the solution set for a linear matrix inequality [10]).”
BackgroundIntelligent labeling based on fisher information for medical image segmentation using deep learning
Sourati, J., Gholipour, A., Dy, J. G., Tomas-Fernandez, X., Kurugol, S., & Warfield, S. K. (2019) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2019.2907805 · Cited by 50
Optimizing Linear Optics Quantum Gates
Eisert, J. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.040502 · Cited by 46
The Complexity of Relating Quantum Channels to Master Equations
Cubitt, T. S., Eisert, J., & Wolf, M. M. (2012) · Communications in Mathematical Physics · doi:10.1007/s00220-011-1402-y · Cited by 44
All entangled states display some hidden nonlocality
Liang, Y.-C., Masanes, L., & Rosset, D. (2012) · Physical Review A · doi:10.1103/physreva.86.052115 · Cited by 40
Optimization Beyond Prediction: Prescriptive Price Optimization
Ito, S., & Fujimaki, R. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098188 · Cited by 39
Deisgn of look-up table based architecture for wideband beamforming
Hu, Z., Guo, N., Qiu, R., Bonior, J., Liou, L., Lin, D., Longbrake, M., Buxa, P., Dalrymple, T., Hong, S., et al. (2010) · 2010 International Waveform Diversity and Design Conference · doi:10.1109/wdd.2010.5592322 · Cited by 5
A Biresolution Spectral Framework for Product Quantization
Mukherjee, L., Peng, J., Ravi, S. N., & Singh, V. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00351 · Cited by 2
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.