Handbook of Semidefinite Programming

by Wolkowicz, Henry; Saigal, Romesh; Vandenberghe, Lieven

• ISBN13: 9780792377719
• ISBN10: 0792377710
• Format: Hardcover
• Copyright: 2000-03-31
• Publisher: Kluwer Academic Pub

Summary

Semidefinite programming (SDP) is one of the most exciting and active research areas in optimization. It has and continues to attract researchers with very diverse backgrounds, including experts in convex programming, linear algebra, numerical optimization, combinatorial optimization, control theory, and statistics. This tremendous research activity has been prompted by the discovery of important applications in combinatorial optimization and control theory, the development of efficient interior-point algorithms for solving SDP problems, and the depth and elegance of the underlying optimization theory. The Handbook of Semidefinite Programming offers an advanced and broad overview of the current state of the field. It contains nineteen chapters written by the leading experts on the subject. The chapters are organized in three parts: Theory, Algorithms, and Applications and Extensions.

Table of Contents

Contents
Contributing Authors
List of Figures
List of Tables
Preface
Introduction	1	(12)
Henry Wolkowicz
Romesh Saigal
Lieven Vandenberghe
Semidefinite programming	1	(1)
Overview of the handbook	2	(3)
Notation	5	(8)
General comments	5	(2)
Overview	7	(6)
Part I THEORY
Convex Analysis on Symmetric Matrices	13	(16)
Florian Jarre
Introduction	13	(1)
Symmetric matrices	14	(2)
Operations on symmetric matrices	15	(1)
Analysis with symmetric matrices	16	(13)
Continuity of eigenvalues	16	(1)
Smoothness of eigenvalues	17	(2)
The Courant-Fischer-Theorem and its consequences	19	(1)
Positive definite matrices	20	(2)
Monotonicity of the Lowner partial order	22	(2)
Majorization	24	(2)
Convex matrix functions	26	(1)
Convex real-valued functions of matrices	26	(3)
The Geometry of Semidefinite Programming	29	(38)
Gabor Pataki
Introduction	29	(2)
Preliminaries	31	(6)
The geometry of cone-lp's: main results	37	(17)
Facial structure, nondegeneracy and strict complementarity	37	(9)
Tangent spaces	46	(1)
The boundary structure inequalities	47	(4)
The geometry of the feasible sets expressed with different variables	51	(1)
A detailed example	52	(2)
Semidefinite Combinatorics	54	(6)
The Multiplicity of Optimal Eigenvalues	55	(3)
The geometry of a max-cut relaxation	58	(1)
The embeddability of graphs	59	(1)
Two algorithmic aspects	60	(2)
Finding an extreme point solution	60	(1)
Sensitivity Analysis	61	(1)
Literature	62	(1)
Appendices	63	(4)
A: The faces of the semidefinite cone	63	(1)
B: Proof of Lemma 3.3.1	64	(3)
Duality and Optimality Conditions	67	(44)
Alexander Shapiro
Katya Scheinberg
Duality, optimality conditions, and perturbation analysis	67	(25)
Alexander Shapiro
Introduction	68	(1)
Duality	69	(9)
Optimality conditions	78	(8)
Stability and sensitivity analysis	86	(5)
Notes	91	(1)
Parametric Linear Semidefinite Programming	92	(19)
Katya Scheinberg
Optimality conditions	92	(4)
Parametric Objective Function	96	(4)
Optimal Partition	100	(5)
Sensitivity Analysis	105	(4)
Conclusions	109	(2)
Self-Dual Embeddings	111	(28)
Etienne de Klerk
Tamas Terlaky
Kees Roos
Introduction	111	(2)
Preliminaries	113	(3)
The embedding strategy	116	(5)
Solving the embedding problem	121	(3)
Existence of the central path - a constructive proof	124	(1)
Obtaining maximally complementary solutions	125	(3)
Separating small and large variables	128	(3)
Remaining duality and feasibility issues	131	(5)
Embedding extended Lagrange-Slater duals	136	(1)
Summary	137	(2)
Robustness	139	(24)
Aharon Ben-Tal
Laurent El Ghaoui
Arkadi Nemirovski
Introduction	139	(3)
SDPs with uncertain data	139	(2)
Problem definition	141	(1)
Affine perturbations	142	(4)
Quality of approximation	144	(2)
Rational Dependence	146	(5)
Linear-fractional representations	146	(1)
Robustness analysis via Lagrange relaxations	147	(3)
Comparison with earlier results	150	(1)
Special cases	151	(4)
Linear programming with affine uncertainty	151	(2)
Robust quadratic programming with affine uncertainty	153	(1)
Robust conic quadratic programming	153	(2)
Operator-norm bounds	155	(1)
Examples	155	(7)
A link with combinatorial optimization	155	(1)
A link with Lyapunov theory in control	156	(1)
Interval computations	157	(2)
Worst-case simulation for uncertain dynamical systems	159	(1)
Robust structural design	159	(3)
Concluding Remarks	162	(1)
Error Analysis	163	(32)
Zhiquan Luo
Jos Sturm
Introduction	163	(2)
Preliminaries	165	(6)
Forward and backward error	166	(1)
Faces of the cone	167	(1)
Second order cone	167	(2)
Positive semidefinite cone	169	(1)
General case	170	(1)
The regularized backward error	171	(5)
Regularization steps	176	(5)
Infeasible systems	181	(2)
Systems of quadratic inequalities	183	(12)
Convex quadratic systems	183	(5)
Generalized convex quadratic systems	188	(7)
Part II ALGORITHMS
Symmetric Cones, Potential Reduction Methods	195	(40)
Farid Alizadeh
Stefan Schmieta
Introduction	195	(3)
Semidefinite programming: Cone-LP over symmetric cones	198	(1)
Euclidean Jordan algebras	199	(15)
Definitions and basic properties	199	(4)
Eigenvalues, degree, rank and norms	203	(5)
Simple Jordan algebras and decomposition theorem	208	(3)
symmetric and Hermitian matrices	211	(1)
The algebra of quadratic forms	212	(1)
The Exceptional Albert algebra	213	(1)
Complementarity in semidefinite programming	213	(1)
Potential reduction algorithms for semidefinite programming	214	(21)
The logarithmic barrier function for symmetric cones	214	(1)
Potential functions	215	(1)
Potential reduction and polynomial time solvability	216	(2)
Feasibility and boundedness	218	(1)
Properties of Potential functions	219	(1)
Properties of Linear scalings	220	(2)
A potential reduction algorithm using linear scaling	222	(5)
Properties of projective scaling	227	(1)
Potential reduction with projective scaling	228	(3)
The Recipe	231	(4)
Potential Reduction and Primal-Dual Methods	235	(32)
Levent Tuncel
Introduction	235	(4)
Fundamental ingredients	239	(4)
What are the uses of a potential function?	243	(5)
Kojima-Shindoh-Hara Approach	248	(2)
Nesterov-Todd Approach	250	(3)
Self-scaled Barriers and Long Steps	252	(1)
Scaling, notions of primal-dual symmetry and scale invariance	253	(6)
An Abstraction of the v-space Approach	258	(1)
A potential reduction framework	259	(8)
Path-Following Methods	267	(40)
Renato Monteiro
Michael Todd
Introduction	267	(3)
The central path	270	(8)
Search directions	278	(4)
Primal-dual path-following methods	282	(25)
The MZ primal-dual framework and a scaling procedure	283	(3)
Short-step and predictor-corrector algorithms	286	(8)
Long-step method	294	(6)
Convergence results for other families of directions	300	(1)
Monteiro and Tsuchiya family	301	(3)
KSH family	304	(3)
Bundle Methods and Eigenvalue Functions	307	(36)
Christoph Helmberg
Francois Oustry
Introduction	307	(2)
The maximum eigenvalue function	309	(1)
General scheme	310	(3)
The proximal bundle method	313	(2)
The spectral bundle method	315	(3)
The mixed polyhedral-semidefinite method	318	(2)
A second-order proximal bundle method	320	(5)
Second-order development of f	321	(1)
Quadratic step	321	(2)
The dual metric	323	(1)
The second-order proximal bundle method	324	(1)
Implementations	325	(4)
Computing the eigenvalues	325	(1)
Structure of the mapping	326	(1)
Solving the quadratic semidefinite program	327	(1)
The rich oracle	328	(1)
Numerical results	329	(14)
The spectral bundle method	329	(6)
The mixed polyhedral-semidefinite bundle method	335	(1)
The second-order proximal bundle method	336	(7)
Part III APPLICATIONS AND EXTENSIONS
Combinatorial Optimization	343	(18)
Michel Goemans
Franz Rendl
From combinatorial optimization to SDP	343	(3)
Quadratic problems in binary variables as SDP	343	(2)
Modeling linear inequalities	345	(1)
Specific combinatorial optimization problems	346	(8)
Equipartition	347	(2)
Stable sets and the &thetas; function	349	(1)
Perfect graphs	350	(1)
Traveling salesman problem	350	(3)
Quadratic assignment problem	353	(1)
Computational aspects	354	(1)
SDPs reducing to eigenvalue bounds	355	(3)
Approximation results through SDP	358	(3)
Nonconvex Quadratic Optimization	361	(60)
Yuri Nesterov
Henry Wolkowicz
Yinyu Ye
Introduction	361	(2)
Lagrange Multipliers for Q2P	363	(1)
Global Quadratic Optimization via Conic Relaxation	363	(24)
Yuri Nesterov
Convex conic constraints on squared variables	365	(4)
Using additional information	369	(3)
General constraints on squared variables	372	(4)
Why the linear constraints are difficult?	376	(1)
Maximization with a smooth constraint	377	(5)
Some applications	382	(2)
Discussion	384	(3)
Quadratic Constraints	387	(8)
Yinyu Ye
Positive Semi-Definite Relaxation	389	(1)
Approximation Analysis	390	(5)
Results for Other Quadratic Problems	395	(1)
Relaxations of Q2P	395	(26)
Henry Wolkowicz
Relaxations for the Max-cut Problem	396	(1)
Several Different Relaxations	396	(3)
A Strengthened Bound for MC	399	(1)
Alternative Strengthened Relaxation	400	(2)
General Q2P	402	(1)
The Lagrangian Relaxation of a General Q2P	403	(1)
Valid Inequalities	404	(1)
Specific Instances of SDP Relaxation	404	(7)
Strong Duality	411	(1)
Convex Quadratic Programs	412	(1)
Nonconvex Quadratic Programs	413	(1)
Rayleigh Quotient	413	(1)
Trust Region Subproblem	413	(2)
Two Trust Region Subproblem	415	(1)
General Q2P	415	(1)
Orthogonally Constrained Programs with Zero Duality Gaps	416	(5)
SDP in Systems and Control Theory	421	(22)
Venkataramanan Balakrishnan
Fan Wang
Introduction	421	(1)
Control system analysis and design: An introduction	422	(5)
Linear fractional representation of uncertain systems	423	(2)
Polytopic systems	425	(1)
Robust stability analysis and design problems	425	(2)
Robustness analysis and design for linear polytopic systems using quadratic Lyapunov functions	427	(4)
Robust stability analysis	427	(1)
Stabilizing state-feedback controller synthesis	428	(1)
Gain-scheduled output feedback controller synthesis	429	(2)
Robust stability analysis of LFR systems in the IQC framework	431	(5)
Diagonal nonlinearities	434	(1)
Parametric uncertainities	435	(1)
Structured dynamic uncertainities	436	(1)
Stabilizing controller design for LFR systems	436	(5)
Quadratic stability analysis of LFR systems	437	(1)
State feedback controller design for LFR systems	438	(1)
Gain-scheduled output feedback controller design	438	(3)
Conclusion	441	(2)
Structural Design	443	(26)
Aharon Ben Tal
Arkadi Nemirovski
Structural design: general setting	443	(4)
Semidefinite reformulation of (Pini)	447	(6)
From primal to dual	453	(5)
From dual to primal	458	(2)
Explicit forms of the standard truss and shape problems	460	(5)
Concluding remarks	465	(4)
Moment Problems and Semidefinite Optimization	469	(42)
Dimitris Bertsimas
Jay Sethuraman
Introduction	469	(4)
Semidefinite Relaxations for Stochastic Optimization Problems	473	(10)
Model description	473	(1)
The performance optimization problem	474	(1)
Linear constraints	475	(5)
Positive semidefinite constraints	480	(1)
On the power of the semidefinite relaxation	481	(2)
Optimal Bounds in Probability	483	(13)
Optimal bounds for the univariate case using semidifinite optimization	487	(7)
Explicit bounds for the (n, 1, Ω), (n, 2, Rn)-bound problems	494	(2)
The complexity of the (n, 2, Rn+), (n, k, Rn)-bound problems	496	(1)
Moment Problems in Finance	496	(11)
Bounds in one dimension	498	(4)
Bounds in multiple dimensions	502	(5)
Moment Problems in Discrete Optimization	507	(2)
Concluding Remarks	509	(2)
Design of Experiments in Statistics	511	(22)
Valerii Fedorov
Jon Lee
Design of Regression Experiments	511	(17)
Valerii Fedorov
Main Optimization Problem	511	(1)
Models and Information Matrix	511	(3)
Characterization of Optimal Designs	514	(5)
Constraints Imposed on Designs	519	(1)
Linear Constraints	519	(1)
Linearization of Nonlinear Convex Constraints	520	(1)
Directly Constrained Design Measurers	521	(1)
Marginal Design Measurers	522	(1)
Numerical Construction of Optimal Designs	523	(1)
Direct Approaches	523	(1)
The First Order Algorithms	523	(2)
Second Order Algorithms	525	(1)
Linear Constraints. Direct First Order Algorithm.	526	(1)
Nonlinear Constraints	527	(1)
Semidefinite programming in experimental design	528	(5)
Jon Lee
Covariance Matrices	528	(1)
Reliability of Test Scores	529	(1)
Maximum-Entropy Sampling	529	(2)
Linear Models	531	(1)
E-Optimal Design	531	(1)
A-Optimal Design	532	(1)
D-Optimal Design	532	(1)
Matrix Completion Problems	533	(14)
Abdo Alfakih
Henry Wolkowicz
Introduction	533	(1)
Weighted Closest Euclidean Distance Matrix	534	(8)
Distance Geometry	534	(2)
Program Formulations	536	(1)
Duality and Optimality	537	(1)
Primal-Dual Interior-Point Algorithm	538	(4)
Weighted Closest Positive Semidefinite Matrix	542	(2)
Primal-Dual Interior-Point Algorithms	543	(1)
Other Completion Problems	544	(3)
Eigenvalue Problems and Nonconvex Minimization	547	(16)
Florian Jarre
Introduction	547	(1)
Selected Eigenvalue Problems	548	(3)
Generalization of Newtons method	551	(3)
An algorithm for unconstrained minimization	552	(2)
Discussion	554	(1)
A method for constrained problems	554	(8)
The constrained problem	554	(1)
Outline of the method	555	(1)
Solving the barrier subproblem (``centering step'')	556	(2)
The predictor step	558	(1)
The overall algorithm	559	(3)
Conclusion	562	(1)
General Nonlinear Programming	563	(14)
Serge Kruk
Henry Wolkowicz
Introduction	563	(1)
The Simplest Case	564	(2)
Multiple Trust-Regions	566	(4)
Approximations of Nonlinear Programs	570	(2)
Quadratically Constrained Quadratic Programming	572	(2)
Conclusion	574	(3)
References	577	(66)
Appendix	643
A-.1 Conclusion and Further Historical Notes	643
A-1.1 Combinatorial Problems	644
A-1.2 Complementarity Problems	644
A-1.3 Complexity, Distance to Ill-Posedness, and Condition Numbers	644
A-1.4 Cone Programming	645
A-1.5 Eigenvalue Functions	645
A-1.6 Engineering Applications	645
A-1.7 Financial Applications	645
A-1.8 Generalized Convexity	645
A-1.9 Geometry	645
A-1.10 Implementation	646
A-1.11 Matrix Completion Problems	646
A-1.12 Nonlinear and Nonconvex SDPs	646
A-1.13 Nonlinear Programming	647
A-1.14 Quadratic Constrained Quadratic Programs	647
A-1.15 Sensitivity Analysis	647
A-1.16 Statistics	647
A-1.17 Books and Related Material	647
A-1.18 Review Articles	648
A-1.19 Computer Packages and Test Problems	648
A-.2 Index	649