| Overview Lecture: A New Look at Convex Analysis and Optimization (PDF) |
| 1 | Cover Page of Lecture Notes (PDF)
Convex and Nonconvex Optimization Problems (PDF)
Why is Convexity Important in Optimization
Lagrange Multipliers and Duality
Min Common/Max Crossing Duality |
| 2 | Convex Sets and Functions (PDF)
Epigraphs
Closed Convex Functions
Recognizing Convex Functions |
| 3 | Differentiable Convex Functions (PDF)
Convex and Affine Bulls
Caratheodory's Theorem
Closure, Relative Interior, Continuity |
| 4 | Review of Relative Interior (PDF)
Algebra of Relative Interiors and Closures
Continuity of Convex Functions
Recession Cones |
| 5 | Global and Local Minima (PDF)
Weierstrass' Theorem
The Projection Theorem
Recession Cones of Convex Functions
Existence of Optimal Solutions |
| 6 | Nonemptiness of Closed Set Intersections (PDF)
Existence of Optimal Solutions
Special Cases: Linear and Quadric Programs
Preservation of Closure under Linear Transformation and Partial Minimization |
| 7 | Preservation of Closure under Partial Minimization (PDF)
Hyperplanes
Hyperplane Separation
Nonvertical Hyperplanes
Min Common and Max Crossing Problems |
| 8 | Min Common / Max Crossing Problems (PDF)
Weak Duality
Strong Duality
Existence of Optimal Solutions
Minimax Problems |
| 9 | Min-Max Problems (PDF)
Saddle Points
Min Common / Max Crossing for Min-Max |
| 10 | Polar Cones and Polar Cone Theorem (PDF)
Polyhedral and Finitely Generated Cones
Farkas Lemma, Minkowski-Weyl Theorem
Polyhedral Sets and Functions |
| 11 | Extreme Points (PDF)
Extreme Points of Polyhedral Sets
Extreme Points and Linear / Integer Programming |
| 12 | Polyhedral Aspects of Duality (PDF)
Hyperplane Proper Polyhedral Separation
Min Common / Max Crossing Theorem under Polyhedral Assumptions
Nonlinear Farkas Lemma
Application to Convex Programming |
| 13 | Directional Derivatives of One-Dimensional Convex Functions (PDF)
Directional Derivatives of Multi-Dimensional Convex Functions
Subgradients and Subdifferentials
Properties of Subgradients |
| 14 | Conical Approximations (PDF)
Cone of Feasible Directions
Tangent and Normal Cones
Conditions for Optimality |
| 15 | Introduction to Lagrange Multipliers (PDF)
Enhanced Fritz John Theory |
| 16 | Enhanced Fritz John Conditions (PDF)
Pseudonormality
Constraint Qualifications |
| 17 | Sensitivity Issues (PDF)
Exact Penalty Functions
Extended Representations |
| 18 | Convexity, Geometric Multipliers, and Duality (PDF)
Relation of Geometric and Lagrange Multipliers
The Dual Function and the Dual Problem
Weak and Strong Duality
Duality and Geometric Multipliers |
| 19 | Linear and Quadric Programming Duality (PDF)
Conditions for Existence of Geometric Multipliers
Conditions for Strong Duality |
| 20 | The Primal Function (PDF)
Conditions for Strong Duality
Sensitivity
Fritz John Conditions for Convex Programming |
| 21 | Fenchel Duality (PDF)
Conjugate Convex Functions
Relation of Primal and Dual Functions
Fenchel Duality Theorems |
| 22 | Fenchel Duality (PDF)
Fenchel Duality Theorems
Cone Programming
Semidefinite Programming |
| 23 | Overview of Dual Methods (PDF)
Nondifferentiable Optimization |
| 24 | Subgradient Methods (PDF)
Stepsize Rules and Convergence Analysis |
| 25 | Incremental Subgradient Methods (PDF)
Convergence Rate Analysis and Randomized Methods |
| 26 | Additional Dual Methods (PDF)
Cutting Plane Methods
Decomposition |