Class 1

1. Review of: basic calculus, linear algebra, geometry
   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
      6. application: minimize time from A to B given running and swimming times.

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
      • comparisons 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
   2. MATLAB file (with output) to minimize the least square error.

Class 8, C&O 367

1. Geometric Programming
   1. primal and dual programs;
      skip Section 2.5 other than the definition of a posynomial.
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. Steepest Descent cont....
   1. Theorem 3.2.3 and proof (moving in perpendicular directions), Theorems 3.2.4 and 3.2.5 and their proofs.
2. Beyond Steepest Descent ....
   1. combine good properties of steepest descent and Newton's method
   2. Wolfe line search (with backtracking)
3. Least Squares
   1. best least squares solutions

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. Least Squares cont....
   1. generalized inverse, QR factorization, SVD
2. Convex Programming and KKT Conditions (Sects 5.1, 5.2, 5.3)
   1. Definition of a convex program (objective function and constraint functions are convex on the convex domain set, C)
   2. Separation and Support Theorems for convex sets
   3. Theorem 5.1.1 and the equivalent results using polar cones
   4. Pshenichnyi-Rockafellar optimality conditions (geometric optimality conditions) using the polar of the tangent cone.

Class 13, C&O 367

1. Optimality Conditions for Convex Programs, cont...
   1. More on Pshenichnyi-Rockafellar optimality condition
   2. lemma: K is a closed convex cone if and only if K=K⁺⁺ (polar of the polar) and the proof using the hyperplane separation theorem.

Class 14, C&O 367

1. Optimality Conditions for Convex Programs cont...
   1. Linearizing cone, tangent cone, Cone of gradients
   2. (weakest) constraint qualification
   3. Farkas' Lemma (with proof using the Lemma: K is a closest convex cone if and only if K equals its second polar)

Class 15, C&O 367

1. Optimality Conditions for Convex Programs cont...
   1. Review of Lemma: K is a ccc iff K=K⁺⁺ and proof using hyperplane separation theorem
   2. Review of 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 (see also Theorems 5.2.13 and 5.2.14)
   4. examples where KKT holds/fails
   5. Accessibility Lemma, Supporting Hyperplane Theorem 5.1.9. (Theorem 5.1.10 but without proof)

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 reviewed

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 17a, C&O 367

1. Optimality Conditions for Convex Programs cont...
   1. Deriving the KKT using Convex Analysis (Separation Theorems)
      1. Separation and Support Theorem
      2. epigraph and subdifferentials of convex functions

Class 18, C&O 367

1. Optimality Conditions for Convex Programming (Sects 5.1, 5.2, 5.3)
   1. Sufficiency always holds, i.e. KKT at x^* implies x^* optimal.
   2. Necessity requires a constraint qualification, CQ, e.g. generalized Slater condition (strict feasibility: g(x)<0, h(x)=0, at some x). If a constraint qualification holds, then KKT holds at the optimum.
   3. Examples of finding optimal solutions using the KKT conditions.

Class 19, C&O 367

1. Duality for Convex Programs (Sect. 5.4, pgs 199-210)
   1. Weak and Strong duality for convex programs, (i.e. min-max and max-min type of formulation).
   2. linear and quadratic program examples
   3. Duffin's example of a duality gap