Calendar

LEC # TOPICS
1 Convex and Nonconvex Optimization Problems

Why is Convexity Important in Optimization

Lagrange Multipliers and Duality

Min Common / Max Crossing Duality
2 Convex Sets and Functions

Epigraphs

Closed Convex Functions

Recognizing Convex Functions
3 Differentiable Convex Functions

Convex and Affine Bulls

Caratheodory's Theorem

Closure, Relative Interior, Continuity
4 Review of Relative Interior

Algebra of Relative Interiors and Closures

Continuity of Convex Functions

Recession Cones
5 Global and Local Minima

Weierstrass' Theorem

The Projection Theorem

Recession Cones of Convex Functions

Existence of Optimal Solutions
6 Nonemptiness of Closed Set Intersections

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

Hyperplanes

Hyperplane Separation

Nonvertical Hyperplanes

Min Common and Max Crossing Problems
8 Min Common / Max Crossing Problems

Weak Duality

Strong Duality

Existence of Optimal Solutions

Minimax Problems
9 Min-Max Problems

Saddle Points

Min Common / Max Crossing for Min-Max
10 Polar Cones and Polar Cone Theorem

Polyhedral and Finitely Generated Cones

Farkas Lemma, Minkowski-Weyl Theorem

Polyhedral Sets and Functions
11 Extreme Points

Extreme Points of Polyhedral Sets

Extreme Points and Linear / Integer Programming
12 Polyhedral Aspects of Duality

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

Directional Derivatives of Multi-Dimensional Convex Functions

Subgradients and Subdifferentials

Properties of Subgradients
14 Conical Approximations

Cone of Feasible Directions

Tangent and Normal Cones

Conditions for Optimality
15 Introduction to Lagrange Multipliers

Enhanced Fritz John Theory
16 Enhanced Fritz John Conditions

Pseudonormality

Constraint Qualifications
17 Sensitivity Issues

Exact Penalty Functions

Extended Representations
18 Convexity, Geometric Multipliers, and Duality

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

Conditions for Existence of Geometric Multipliers

Conditions for Strong Duality
20 The Primal Function

Conditions for Strong Duality

Sensitivity

Fritz John Conditions for Convex Programming
21 Fenchel Duality

Conjugate Convex Functions

Relation of Primal and Dual Functions

Fenchel Duality Theorems
22 Fenchel Duality

Fenchel Duality Theorems

Cone Programming

Semidefinite Programming
23 Overview of Dual Methods

Nondifferentiable Optimization
24 Subgradient Methods

Stepsize Rules and Convergence Analysis
25 Incremental Subgradient Methods

Convergence Rate Analysis and Randomized Methods
26 Additional Dual Methods

Cutting Plane Methods

Decomposition