Class 1, C&O 367

1. Functions of one variable:
   1. (calculus) Taylor's Theorem, Law of Mean
   2. Definitions: (strict) global/local minimizers/maximizers, critical points
   3. local optimizer and critical points (Fermat Theorem)
   4. second derivative tests for minimizer/maximizer/saddle points
   5. examples

Class 2, C&O 367

1. Review of basic calculus and linear algebra/ Functions on Rⁿ
   1. extension of definitions from R to Rⁿ (global and local min, critical point)
   2. chain rule, directional derivative, Taylor theorems
   3. extension of tests for optimality,
   4. quadratic forms
   5. example of identifying critical points

Class 3, C&O 367

1. positive and negative definite matrices (relation to optimization on Rⁿ)
   1. leading principal minor tests for positive definite matrices (Be aware that the book has the wrong definition for principal minors, i.e. their definition should be called leading principal minors.)
   2. sufficient optimality conditions (tests) for local minima
   3. min f(x) is equivalent to -max-f(x)
   4. examples on quadratic functions
   5. examples of saddle points

Class 4, C&O 367

1. Coercive functions and global minimizers
   1. definitions and examples
2. Eigenvalues and Positive Definite matrices
   1. definitions and examples
3. Convex Sets and Convex Functions
   1. Convex Sets: definitions, examples, convex combinations

Class 5, C&O 367

1. Convex Sets and Convex Functions
   1. Convex Sets: convex combinations, convex hull, Theorem 2.1.4 with proof,
   2. Convex Functions: definitions, examples, properties (comparison between convex -- concave; positive semidefinite --- negative semidefinite; maximization -- minimization)

Class 6, C&O 367

1. Convex Sets and Convex Functions
   1. Convex Functions on D a convex subset of Rⁿ
      1. properties, characterizations, examples
      2. Theorem 2.3.3 and proof (convex combinations);
         Theorem 2.3.4 and proof (local and global minima);
         Theorem 2.3.5 and proof (tangent hyperplane characterization)
         Theorem 2.3.7 and proof (psd Hessian characterization)

Class 7, C&O 367

1. Description of convex functions as a cone
2. Arithmetic-Geometric Mean Inequality (AGM)
   1. examples and applications to solving optimization problems

Class 8, C&O 367

1. Geometric Programming
   1. primal and dual programs, Theorem 2.5.2
2. Iterative Methods for Unconstrained Optimization (Chap. 3)
   1. Newton's method for solving a nonlinear system of equations (derivation, example)

Class 9, C&O 367

1. Iterative Methods for Unconstrained Optimization (Chap. 3)
   1. Newton's method for minimization

Class 10, C&O 367

1. Newton's method for minimization cont...
   1. quadratic model, descent direction property, examples, quadratic convergence rate, using Cholesky
2. Steepest Descent method for minimization
   1. derivation, directional derivative, Theorem 3.2.3 and proof (moving in perpendicular directions), Theorems 3.2.4 and 3.2.5 and their proofs.

Class 11, C&O 367

1. Beyond Steepest Descent ....
   1. combine good properties of steepest descent and Newton's method
   2. Wolfe line search (with backtracking)
2. Least Squares
   1. best least squares solutions

Class 12, C&O 367

1. Convex Programming and KKT Conditions
   1. Definition of a convex program
   2. Separation and Support Theorems for convex sets
   3. Theorem 5.1.1 and the equivalent results using polar cones
   4. Pshenichnyi optimality conditions (geometric optimality conditions)

Class 13, C&O 367

1. Optimality Conditions for Convex Programs
   1. More on Pshenichnyi optimality condition
   2. lemma: K is a closed convex cone if and only if K=K⁺⁺

Class 14, C&O 367

1. Optimality Conditions for Convex Programs cont...
   1. Linearizing cone
   2. Cone of gradients
   3. constraint qualification, Farkas' Lemma

Class 15, C&O 367

1. Optimality Conditions for Convex Programs cont...
   1. Lemma: K is a ccc iff K=K⁺⁺ and proof using hyperplane separation theorem
   2. Farkas' Lemma and proof using the above Lemma
   3. KKT conditions for a convex program (sufficient, necessary with Slater's constraint qualification) with proof using relation between tangent and linearizing cones
   4. examples where KKT holds/fails
   5. Accessibility Lemma, Supporting Hyperplane Theorem,

Class 16, C&O 367

1. Optimality Conditions for Convex Programs cont...
   1. Recall convex set separation theorem proved on assignment, i.e. problem 3 on Pg 212.
   2. Lagrange multiplier theorem and proof using the above separation theorem

Class 17, C&O 367

1. Optimality Conditions for Convex Programs cont...
   1. Examples of solving convex programs using the KKT conditions (comparisons with the Pshenichnyi condition)
   2. Using the KKT conditions to derive eigenvalues and (orthonormal) eigenvectors for A=A^T

Class 18, C&O 367

1. Duality for Convex Programs
   1. Derive the dual using a game theory approach
   2. Examples of duals for linear programming, quadratic programming

Class 19, C&O 367

1. Duality for Convex Programs
   1. Strong duality for convex programs - theorem with proof
   2. Duffin's example of a duality gap
   3. strengthened KKT for the TRS (i.e. including convexity of the Lagrangian - see e.g. the book by R. Fletcher, "Practical Methods of Optimization" Chapter 5. This includes the TR algorithm that I could not finish in class)

Class 20, C&O 367

1. Penalty Function Methods
   1. Examples of quadratic and absolute value penalty functions

Class 21, C&O 367

1. Penalty Function Methods
   1. Geometry, connections with Lagrange Multipliers