Lecture Notes

LEC # TOPICS
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