Lectures on Modern Convex Optimization

by Ben-Tal, Aharon; Nemirovskii, Arkadii Semenovich

• ISBN13: 9780898714913
• ISBN10: 0898714915
• Format: Paperback
• Copyright: 2001-08-01
• Publisher: Society for Industrial & Applied

Summary

Here is a book devoted to well-structured and thus efficiently solvable convex optimization problems, with emphasis on conic quadratic and semidefinite programming. The authors present the basic theory underlying these problems as well as their numerous applications in engineering, including synthesis of filters, Lyapunov stability analysis, and structural design. The authors also discuss the complexity issues and provide an overview of the basic theory of state-of-the-art polynomial time interior point methods for linear, conic quadratic, and semidefinite programming. The book's focus on well-structured convex problems in conic form allows for unified theoretical and algorithmical treatment of a wide spectrum of important optimization problems arising in applications.

Author Biography

Aharon Ben-Tal is a professor at the Technion-Israel Institute of Technology and head of the MINERVA Optimization Center Arkadi Nemirovski is a professor at the Technion-Israel Institute of Technology

Table of Contents

Preface	xi
Linear Programming	1	(42)
Linear Programming: Basic notions	1	(1)
Example: Tschebyshev approximation and its applications	2	(9)
Best uniform approximation	2	(1)
Application: Synthesis of filters	3	(2)
Filter synthesis revisited	5	(2)
Synthesis of arrays of antennae	7	(4)
Duality in linear programming	11	(19)
Certificates for solvability and insolvability	12	(4)
Dual to a linear programming program: Origin	16	(1)
Linear programming duality theorem	17	(2)
Illustration: Problem dual to the Tschebyshev approximation problem	19	(2)
Application: Truss topology design	21	(9)
Exercises to Lecture 1	30	(13)
Uniform approximation	30	(4)
Theorem on the alternative	34	(1)
Proof of the homogeneous Farkas lemma	35	(3)
Helley theorem	38	(2)
How many bars are needed in an optimal truss?	40	(3)
From Linear Programming to Conic Programming	43	(36)
Orderings of Rm and convex cones	44	(2)
What is conic programming?	46	(4)
Conic duality	50	(7)
Geometry of the primal and dual problems	53	(4)
Conic duality theorem	57	(10)
Is something wrong with conic duality?	60	(1)
Consequences of the conic duality theorem	61	(3)
Robust solvability status	64	(3)
Conic duality revisited	67	(6)
Exercises to Lecture 2	73	(6)
Cones	73	(3)
Conic problems	76	(1)
Feasible and level sets of conic problems	77	(2)
Conic Quadratic Programming	79	(60)
Conic quadratic problems: Preliminaries	79	(2)
Examples of conic quadratic problems	81	(4)
Best linear approximation of complex-valued functions	81	(1)
Contact problems with static friction	82	(3)
What can be expressed via conic quadratic constraints?	85	(24)
More examples of conic quadratic-representable functions and sets	104	(5)
More applications	109	(22)
Tschebyshev approximation in relative scale	109	(1)
Robust linear programming	110	(10)
Truss topology design	120	(11)
Exercises to Lecture 3	131	(8)
Optimal control in discrete time linear dynamic system	131	(1)
Conic quadratic representations	132	(5)
Does conic quadratic programming exist?	137	(2)
Semidefinite Programming	139	(196)
Semidefinite cone and semidefinite programs	139	(5)
Preliminaries	139	(5)
What can be expressed via linear matrix inequalities?	144	(15)
Applications I: Combinatorics	159	(19)
Shor's semidefinite relaxation scheme	161	(3)
Stability number, Shannon capacity, and Lovasz capacity of a graph	164	(6)
MAXCUT problem	170	(2)
Extensions	172	(3)
S-lemma	175	(3)
Applications II: Stability analysis	178	(24)
Dynamic stability in mechanics	178	(2)
Lyapunov stability analysis and synthesis	180	(9)
Interval stability analysis and synthesis	189	(13)
Applications III: Robust quadratic programming	202	(8)
Applications IV: Synthesis of filters and antennae arrays	210	(9)
Applications V: Design of chips	219	(8)
Building the model	220	(6)
Wire sizing	226	(1)
Applications VI: Structural design	227	(30)
Building a model	228	(5)
Standard case	233	(3)
Semidefinite reformulation of the standard SSD problem	236	(7)
From primal to dual	243	(5)
Back to primal	248	(4)
Explicit forms of the standard truss and shape problems	252	(5)
Applications VII: Extremal ellipsoids	257	(19)
Ellipsoidal approximations of unions and intersections of ellipsoids	262	(2)
Approximating sums of ellipsoids	264	(12)
Exercises to Lecture 4	276	(59)
Around positive semidefiniteness, eigenvalues, and ≥ ordering	276	(15)
Semidefinite representations of epigraphs of convex polynomials	291	(2)
Lovasz capacity number and semidefinite relaxations of combinatorial problems	293	(6)
Lyapunov stability analysis	299	(1)
S-lemma	300	(23)
Antenna synthesis	323	(3)
Ellipsoidal approximations	326	(9)
Computational Tractability of Convex Programs	335	(42)
Numerical solution of optimization programs --- preliminaries	335	(7)
Mathematical programming programs	335	(1)
Solution methods and efficiency	336	(6)
Black box-represented convex programs	342	(10)
Polynomial solvability of convex programming	352	(11)
Polynomial solvability of convex programming	359	(4)
Difficult problems and NP-completeness	363	(14)
CCT --- a quick introduction	363	(4)
From the real arithmetic complexity theory to the CCT and back	367	(10)
Interior Point Polynominal Time Methods for Linear Programming, Conic Quadratic Programming, and Semidefinite Programming	377	(66)
Motivation	377	(2)
Interior point methods	378	(1)
Newton method and the interior penalty scheme	379	(5)
Unconstrained minimization and the Newton method	379	(1)
Classical interior penalty scheme: Construction	380	(2)
Classical interior penalty scheme: Drawbacks	382	(1)
But	382	(2)
Interior point methods for linear programming, conic quadratic programming, and semidefinite programming: Building blocks	384	(5)
Canonical cones and canonical barriers	384	(3)
Elementary properties of canonical barriers	387	(2)
Primal-dual pair of problems and the primal-dual central path	389	(8)
Problem(s)	389	(1)
Central path(s)	390	(7)
Tracing the central path	397	(24)
Path-following scheme	397	(1)
Speed of path-tracing	398	(4)
Primal and dual path-following methods	402	(3)
Semidefinite programming case	405	(16)
Complexity bounds for linear programming, conic quadratic programming, and semidefinite programming	421	(3)
Complexity of linear programming	422	(1)
Complexity of conic quadratic programming	423	(1)
Semidefinite programming	423	(1)
Concluding remarks	424	(2)
Exercises to Lecture 6	426	(17)
Canonical barriers	426	(1)
Scalings of canonical cones	427	(2)
Dikin ellipsoid	429	(2)
More on canonical barriers	431	(1)
Primal path-following method	432	(3)
Infeasible start path-following method	435	(8)
Solutions to Selected Exercises	443	(42)
Exercises to Lecture 1	443	(3)
Exercises to Lecture 2	446	(3)
Exercises to Lecture 3	449	(10)
Exercises to Lecture 4	459	(16)
Exercises to Lecture 6	475	(10)
Index	485