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
IllustrationsAcademic'' 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.1Universal'' 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