Lectures on modern convex optimization

Main Notational Conventions From Linear to Conic Programming Linear programming: basic notions Duality in Linear Programming Certificates for solvability and insolvability Dual to an LP program: the origin The LP Duality Theorem Selected Engineering Applications of LP Sparsity-oriented Signal Processing and 1 minimization Sparse recovery from deficient observations s-goodness and nullspace property From nullspace property to error bounds for imperfect 1 recovery Compressed Sensing: Limits of performance Verifiable sufficient conditions for s-goodness Supervised Binary Machine Learning via LP Support Vector Machines Synthesis of linear controllers Discrete time linear dynamical systems Affine control Design specifications and the Analysis problem Synthesis problem Purified outputs and purified-output-based control laws Tractability of the Synthesis problem Clearing debts: justification of (*) From Linear to Conic Programming Orderings of Rm and cones ``Conic programming'' – what is it? Conic Duality Geometry of the primal and the dual problems Conic Duality Theorem Refinement Is something wrong with conic duality? Consequences of the Conic Duality Theorem Sufficient condition for infeasibility When is a scalar linear inequality a consequence of a given linear vector inequality? ``Robust solvability status'' Exercises for Lecture 1 Around General Theorem on Alternative Around cones Calculus of cones Primal-dual pairs of cones and orthogonal pairs of subspaces Several interesting cones Around conic problems: Several primal-dual pairs Feasible and level sets of conic problems Operational exercises on engineering applications of LP Conic Quadratic Programming Conic Quadratic problems: preliminaries Examples of conic quadratic problems Contact problems with static friction BoydSO What can be expressed via conic quadratic constraints? Elementary CQ-representable functions/sets Operations preserving CQ-representability of sets Operations preserving CQ-representability of functions More operations preserving CQ-representability More examples of CQ-representable functions/sets Fast CQr approximations of exponent and logarithm From CQR's to K-representations of functions and sets Conic representability of convex-concave function—definition Main observation Symmetry Calculus of conic representations of convex-concave functions Illustrations More applications: Robust Linear Programming Robust Linear Programming: the paradigm Robust Linear Programming: examples Robust counterpart of uncertain LP with a CQr uncertainty set CQ-representability of the optimal value in a CQ program as a function of the data Affinely Adjustable Robust Counterpart Affinely Adjustable Robust Counterpart of LP Example: Uncertain Inventory Management Problem Does Conic Quadratic Programming exist? Proof of Theorem 2.5.1 Exercises for Lecture 2 Optimal control in discrete time linear dynamic system Around stable grasp Around randomly perturbed linear constraints Around Robust Antenna Design Semidefinite Programming Semidefinite cone and Semidefinite programs Preliminaries Dual to a semidefinite program (SDP) Conic Duality in the case of Semidefinite Programming Comments. What can be expressed via LMI's? SD-representability of functions of eigenvalues of symmetric matrices SD-representability of functions of singular values Applications of Semidefinite Programming in Engineering Dynamic Stability in Mechanics Truss Topology Design Design of chips and Boyd's time constant Lyapunov stability analysis/synthesis Uncertain dynamical systems Stability and stability certificates Lyapunov Stability Synthesis Semidefinite relaxations of intractable problems Semidefinite relaxations of combinatorial problems Combinatorial problems and their relaxations Shor's Semidefinite Relaxation scheme When the semidefinite relaxation is exact? Stability number, Shannon and Lovasz capacities of a graph The MAXCUT problem and maximizing quadratic form over a box Nesterov's 2 Theorem Shor's semidefinite relaxation revisited Semidefinite relaxation on ellitopes and its applications Ellitopes Construction and main result Application: Near-optimal linear estimation Application: Tight bounding of operator norms Matrix Cube Theorem and interval stability analysis/synthesis The Matrix Cube Theorem Application: Lyapunov Stability Analysis for an interval matrix Application: Nesterov's 2 Theorem revisited Application: Bounding robust ellitopic norms of uncertain matrix with box uncertainty S-Lemma and Approximate S-Lemma S-Lemma Inhomogeneous S-Lemma Approximate S-Lemma Application: Approximating Affinely Adjustable Robust Counterpart of Uncertain Linear Programming problem with ellitopic uncertainty Application: Robust Conic Quadratic Programming with ellitopic uncertainty Semidefinite Relaxation and Chance Constraints Chance constraints Safe tractable approximations of chance constraints Situation and goal Approximating chance constraints via Lagrangian relaxation Illustration I Modification Illustration II Extremal ellipsoids Preliminaries on ellipsoids Outer and inner ellipsoidal approximations Inner ellipsoidal approximation of a polytope Outer ellipsoidal approximation of a finite set Ellipsoidal approximations of unions/intersections of ellipsoids Inner ellipsoidal approximation of the intersection of full-dimensional ellipsoids Outer ellipsoidal approximation of the union of ellipsoids Approximating sums of ellipsoids Problem (O) Problem (I) Exercises for Lecture 3 Around positive semidefiniteness, eigenvalues and -ordering Criteria for positive semidefiniteness Variational characterization of eigenvalues Birkhoff's Theorem Semidefinite representations of functions of eigenvalues Cauchy's inequality for matrices -convexity of some matrix-valued functions SD representations of epigraphs of convex polynomials Around the Lovasz capacity number and semidefinite relaxations of combinatorial problems Around operator norms Around Lyapunov Stability Analysis Around ellipsoidal approximations More on ellipsoidal approximations of sums of ellipsoids ``Simple'' ellipsoidal approximations of sums of ellipsoids Invariant ellipsoids Greedy infinitesimal ellipsoidal approximations Around S-Lemma A straightforward proof of the standard S-Lemma S-Lemma with a multi-inequality premise Relaxed versions of S-Lemma Around Chance constraints Polynomial Time Interior Point algorithms for LP, CQP and SDP Complexity of Convex Programming Combinatorial Complexity Theory Complexity in Continuous Optimization Computational tractability of convex optimization problems What is inside Theorem 4.1.1: Black-box represented convex programs and the Ellipsoid method Proof of Theorem 4.1.2: the Ellipsoid method Difficult continuous optimization problems Interior Point Polynomial Time Methods for LP, CQP and SDP Motivation Interior Point methods The Newton method and the Interior penalty scheme But... Interior point methods for LP, CQP, and SDP: building blocks Canonical cones and canonical barriers Elementary properties of canonical barriers Primal-dual pair of problems and primal-dual central path The problem(s) The central path(s) On the central path Near the central path Tracing the central path The path-following scheme Speed of path-tracing The primal and the dual path-following methods The SDP case The path-following scheme in SDP Complexity analysis Complexity bounds for LP, CQP, SDP Complexity of LPb Complexity of CQPb Complexity of SDPb Concluding remarks Exercises for Lecture 4 Around canonical barriers Scalings of canonical cones The Dikin ellipsoid More on canonical barriers Around the primal path-following method Infeasible start path-following method Simple methods for large-scale problems Motivation: Why simple methods? Black-box-oriented methods and Information-based complexity Main results on Information-based complexity of Convex Programming The Simplest: Subgradient Descent and Euclidean Bundle Level Subgradient Descent Incorporating memory: Euclidean Bundle Level Algorithm Mirror Descent algorithm Problem and assumptions Proximal setup Standard proximal setups Ball setup Entropy setup 1/2 and Simplex setups Nuclear norm and Spectahedron setups Mirror Descent algorithm Basic Fact Standing Assumption MD: Description MD: Complexity analysis Refinement MD: Optimality Mirror Descent and Online Regret Minimization Online regret minimization: what is it? Online regret minimization via Mirror Descent, deterministic case Mirror Descent for Saddle Point problems Convex-Concave Saddle Point problem Saddle point MD algorithm Refinement Mirror Descent for Stochastic Minimization/Saddle Point problems Stochastic Minimization/Saddle Point problems Stochastic Saddle Point Mirror Descent algorithm Refinement Solving (5.3.75) via Stochastic Saddle Point Mirror Descent. Mirror Descent and Stochastic Online Regret Minimization Stochastic online regret minimization: problem's formulation Minimizing stochastic regret by MD Illustration: predicting sequences Bundle Mirror and Truncated Bundle Mirror algorithms Bundle Mirror algorithm BM: Description Convergence analysis Truncated Bundle Mirror TBM: motivation TBM: construction Convergence Analysis Implementation issues Illustration: PET Image Reconstruction by MD and TBM Alternative: PET via Krylov subspace minimization Saddle Point representations and Mirror Prox algorithm Motivation Examples of saddle point representations The Mirror Prox algorithm Refinement Typical implementation Summary on Mirror Descent and Mirror Prox Algorithms Situation Mirror Descent and Mirror Prox algorithms First Order oracles and oracle-based algorithms Mirror Descent Algorithm Mirror Prox algorithm Processing problems with convex structure by Mirror Descent and Mirror Prox algorithms Problems with convex structure Problems with convex structure: basic descriptive results Problems with convex structure: basic operational results Well-structured monotone vector fields Conic representability of monotone vector fields and monotone VI's in conic form Conic representation of a monotone vector field Conic form of conic-representable monotone VI Calculus of conic representations of monotone vector fields Raw materials Calculus rules Illustrations ``Academic'' illustration Nash Equilibrium Derivations for Section 5.7.2 Verification of ``raw materials'' Verification of calculus rules Verifying (5.7.30) and (5.7.31) Fast First Order algorithms for Smooth Convex Minimization Fast Gradient Methods for Smooth Composite minimization Problem formulation Composite prox-mapping Fast Composite Gradient minimization: Algorithm and Main Result Proof of Theorem 5.8.1 ``Universal'' Fast Gradient Methods Problem formulation Algorithm and Main Result Proof of Theorem 5.8.2 From Fast Gradient Minimization to Conditional Gradient Proximal and Linear Minimization Oracle based First Order algorithms Conditional Gradient algorithm Bridging Fast and Conditional Gradient algorithms LMO-based implementation of Fast Universal Gradient Method Appendix: Some proofs A useful technical lemma Justifying Ball setup Justifying Entropy setup Justifying 1/2 setup Proof of Theorem 5.9.1 Proof of Corollary 5.9.1 Justifying Nuclear norm setup Proof of Theorem 5.9.2 Proof of Corollary 5.9.2 Bibliography Solutions to selected exercises Exercises for Lecture 1 Around Theorem on Alternative Around cones Feasible and level sets of conic problems Exercises for Lecture 2 Optimal control in discrete time linear dynamic system Around stable grasp Exercises for Lecture 3 Around positive semidefiniteness, eigenvalues and -ordering Criteria for positive semidefiniteness Variational description of eigenvalues Cauchy's inequality for matrices -convexity of some matrix-valued functions Around Lovasz capacity number Around operator norms Around S-Lemma A straightforward proof of the standard S-Lemma S-Lemma with a multi-inequality premise Exercises for Lecture 4 Around canonical barriers Scalings of canonical cones Dikin ellipsoid More on canonical barriers Around the primal path-following method An infeasible start path-following method Prerequisites from Linear Algebra and Analysis Space Rn: algebraic structure A point in Rn Linear operations Linear subspaces Linear independence, bases, dimensions Linear mappings and matrices Determinant and rank Determinant Rank Space Rn: Euclidean structure Euclidean structure Inner product representation of linear forms on Rn Orthogonal complement Orthonormal bases Affine subspaces in Rn Affine subspaces and affine hulls Intersections of affine subspaces, affine combinations and affine hulls Affinely spanning sets, affinely independent sets, affine dimension Dual description of linear subspaces and affine subspaces Affine subspaces and systems of linear equations Structure of the simplest affine subspaces Space Rn: metric structure and topology Euclidean norm and distances Convergence Closed and open sets Local compactness of Rn Continuous functions on Rn Continuity of a function Elementary continuity-preserving operations Basic properties of continuous functions on Rn Differentiable functions on Rn The derivative Derivative and directional derivatives Representations of the derivative Existence of the derivative Calculus of derivatives Computing the derivative Higher order derivatives Calculus of Ck mappings Examples of higher-order derivatives Taylor expansion Symmetric matrices Main facts on symmetric matrices Eigenvectors and eigenvalues Eigenvalue decomposition of a symmetric matrix Vector of eigenvalues Freedom in eigenvalue decomposition ``Simultaneous'' decomposition of commuting symmetric matrices Variational characterization of eigenvalues Corollaries of the VCE Eigenvalue characterization of positive (semi)definite matrices -Monotonicity of the vector of eigenvalues Eigenvalue Interlacement Theorem Spectral norm and Lipschitz continuity of vector of eigenvalues Spectral and induced norms of matrices Lipschitz continuity of the vector of eigenvalues Functions of symmetric matrices Positive semidefinite matrices and positive semidefinite cone Positive semidefinite matrices. The positive semidefinite cone Schur Complement Lemma Convex sets in Rn Definition and basic properties A convex set Examples of convex sets Inner description of convex sets: Convex combinations and convex hull Cones Calculus of convex sets Topological properties of convex sets Main theorems on convex sets Caratheodory Theorem Radon Theorem Helley Theorem Polyhedral representations and Fourier-Motzkin Elimination General Theorem on Alternative and Linear Programming Duality Separation Theorem Polar of a convex set and Milutin-Dubovitski Lemma Extreme points and Krein-Milman Theorem Structure of polyhedral sets Convex functions Convex functions: first acquaintance Definition and Examples Elementary properties of convex functions Jensen's inequality Convexity of level sets of a convex function What is the value of a convex function outside its domain? How to detect convexity Operations preserving convexity of functions Differential criteria of convexity Gradient inequality Boundedness and Lipschitz continuity of a convex function Maxima and minima of convex functions Subgradients and Legendre transformation Proper functions and their representation Subgradients Legendre transformation Convex Programming, Lagrange Duality, Saddle Points Mathematical Programming Program Convex Programming program and Lagrange Duality Theorem Convex Theorem on Alternative Cone constrained case Lagrange Function and Lagrange Duality Lagrange function Convex Programming Duality Theorem Dual program Cone constrained forms of Lagrange Function, Lagrange Duality, and Convex Programming Duality Theorem Conic Programming and Conic Duality Theorem Optimality Conditions in Convex Programming Saddle point form of optimality conditions Karush-Kuhn-Tucker form of optimality conditions Optimality conditions in Conic Programming Duality in Linear and Convex Quadratic Programming Linear Programming Duality Quadratic Programming Duality Saddle Points Definition and Game Theory interpretation Existence of Saddle Points