Nonlinear Optimization Math 433/833 Spring 2009 Class Log

1. Jan 12, Mon. course overview and logistics; initial student survey; Sec 1.1: discussion of optimization for univariate differential functions; critical points
2. Jan 14, Wed. Taylor's formula with second derivative error test; proof of second derivative test; Sec 1.2: basic algebraic properties of R^n; properties of norm
3. Jan 16, Fri. distance; topology of R^n; open, closed, and compact subsets; minimizers in R^n; critical points; gradient
Jan 19, Mon. Martin Luther King day --- No class.
4. Jan 21, Wed. Taylor's formula in higher dimensions; Hessian; analogous second derivative test
5. Jan 23, Fri. quadratic forms; Sec 1.3: positive and negative definite and semidefinite matrices; principal minor test for 2x2 real symmetric matrices
6. Jan 26, Mon. principal minor test for nxn real symmetric matrices; proof of inductive step for n=3; Sec 1.5: eigenvalue characterization for (semi)definiteness
7. Jan 18, Wed. review of second derivative test; local version; example; Sec 1.4: coercive functions; example
8. Jan 30, Fri. Sec 2.1: convexity in Rn; convex combinations; intersection of convex sets; convex hull; introduction to Sage
9. Feb 2, Mon. Sec 2.3: convex functions; univariate case; implies continuity; relation to derivatives; local minimizers of convex functions on convex domains are global minimizers; multivariate definition
10. Feb 4, Wed. local minizimers of convex functions; tangent hyperplanes and convexity; Hessian and convexity; critical points of convex functions
11. Feb 6, Fri. convex functions from linear combinations and compositions of convex functions; Sec 2.4: arithmetic-geometric mean inequality; proof
12. Feb 9, Mon. example of solving constrained geometric programs using arithmetic-geometric mean inequality; unconstrained example; Sec 2.5: posynomials; unconstrained geometric programming; started development of the dual
13. Feb 11, Wed. dual geometric program; primal-dual inequality; theorem of strong duality; method of solving geometric programs
14. Feb 13, Fri. examples of solving unconstrained geometric programs; Sec 2.6: Young's inequality; Holder's inequality
15. Feb 16, Mon. p-norm is a norm; Minkowski's inequality; Sec 3.1: Newton's Method for univariate differentiable functions
16. Feb 18, Wed. Newton's Method in the multivariate case; example; Newton's Method for minimizing; derivation via second-order Taylor's Formula; example of quadratic function
17. Feb 20, Fri. examples showing rapid convergence, oscillation, and divergence; Hessian positive definite implies Newton's method moves in a descent direction; computational considerations and Cholesky decomposition.
18. Feb 23, Mon. computing the Cholesky decomposition; Sec 3.2: Method of Steepest Descent
19. Feb 25, Wed. Test #1, starting at 7:30am
20. Feb 27, Fri. example; moves in perpendicular steps; slow to converge
21. Mar 2, Mon. returned Test 1; principal minors of indefinite matrices; method of steepest descent always converges
22. Mar 4, Wed. Sec 3.3: criteria of an iterative minimization method; Wolfe thm (no proof); other choices for descent direction; modifying Hessian to guarantee positive definiteness
23. Mar 6, Fri. Sec 3.4: secant method; tensor product; Broyden's method
24. Mar 9, Mon. example; matrix norm; choice of Dk+1 in Broyden's algorithm
25. Mar 11, Wed. Sec 3.5: secant method for minimization; choice of update matrix
26. Mar 13, Fri. updated matrix is positive definite; example of BFGS method
27. Mar 23, Mon. Sec 4.1: least squares fit; derivation of normal equations; example for linear regression; informal feedback survey
28. Mar 25, Wed. discussion of informal feedback; best least squares solution for inconsistent linear systems; generalized inverse; example; Gram-Schmidt orthogonalization; QR factorization; application to least squares optimization
29. Mar 27, Fri. Sec 4.2: subspaces; orthogonal complement; basis and column space of a matrix; Thm 4.2.4, first part
30. Mar 30, Mon. example of QR factorization; Gauss, least squares, and Ceres; finished proof of Thm 4.2.4; orthogonal projection is linear transformation; not dependent on basis choice
31. Apr 1, Wed. Sec 4.3: min norm solution of underdetermined system; example Sec 4.4: H-inner product; H-norm; properties
32. Apr 3, Fri. analogous theorems for H-norm; example; Sec 5.1: convex programming; closest vector to a convex set
33. Apr 6, Mon. proof of thm characterizing closest vector in a convex set; application to subspaces; closed sets
34. Apr 8, Wed. uniqueness of closest vector for closed convex sets; separation theorem; closure of a set; closure of a convex set is convex; interior
35. Apr 10, Fri. technical lemma; support theorem for convex sets with nonempty interior; statement of theorem of subgradient for nondifferentiable convex functions
36. Apr 13, Mon. discussion of HW4; existence of subgradients for convex functions
37. Apr 15, Wed. Test #2, starting at 7:30am
38. Apr 17, Fri. Sec 5.2: convex programs; terminology; infimums; perturbation of convex program; domain and perturbation are convex
39. Apr 20, Mon. returned Test 2; MP(z) is a convex function; existence of sensitivity vector for superconsistent convex programs
40. Apr 22, Wed. interpretation of sensitivity vector; examples; relation to unconstrained programs
41. Apr 24, Fri. Lagrangian; Karush-Kuhn-Tucker thm; first part of proof; student evaluations
42. Apr 27, Mon. finished proof of KKT thm; gradient version of KKT thm; example; converting posynomials to convex functions
43. Apr 29, Wed. KKT theorem gives a sensitivity vector; Sec 5.3: extended arithmetic-geometric mean inequality; constrained geometric programs; example
44. May 1, Fri. recovering optimal t; handling multiple constraints; applying KKT to constrained geometric programs
May 5, Tue. Final Exam, 7:30am-9:30am in Oldfather Hall Room 208

    Back This page last modified .