Guide for Week 4
Math 408 Section A, January 29, 2013
-
Reading Assignment:
Homework Assignment:
Vocabulary Words
- Optimality Conditions for Unconstrained Problems
- Weierstrass extreme value theorem
- coercive functions
- The coercivity and compactness theorem (proof not required)
- The coercivity and existence theorem (proof required)
- The Basic first-order optimality result (proof not required)
- The first-order necessary conditions for optimality
- the second-order necessary and sufficient conditions for optimality
- convex functions and sets (and strict convex functions)
- the epi-graph and essential domain of a function
- existence of directional derivatives for convex functions
- the convexity and optimality theorem (proof not required)
- first- and second-order conditions for convexity checking
- gradients and hessians of linear least squares functions and general
quadratic functions
- the unitary diagonalization of symmetric matrices
- positive semi-definite and positive definite matrices
- Choleky factorization of a symmetric positive definite matrix
- matrix square roots
- Line Search Methods
- search direction
- descent direction
- direction of strict descent
- direction of steepest descent
- the Cauchy direction
- The Newton direction
- step length , step size
- Curry step length
- Armijo-Goldstein inequality
- backtracking line search
- The Basic Backtracking Algorithm
- Convergence Theorem for the backtracking line search
- the weak Wolfe conditions
- the strong Wolfe conditions
- the Goldstein conditions
- The Bisection Method for the Weak Wolf Conditions
- Search Directions
- Steepest Descent direction
- Newton's method for solving equations
- Newton-Like methods
- Q-convergence rates
- linear, superlinear, and quadratic convergence
- Newton's method for minimization
- The rate of convergence of Newton's method
- Matrix secant equation
- Broyden's method (both direct and inverse updates)
- the BFGS update (both direct and inverse updates)
-
Key Concepts:
- Optimality Conditions for Unconstrained Problems
- Coercivity and existence
- first- and second-order optimality conditions
- convexity and optimality
- Coercivity and existence
- first- and second-order optimality conditions
- convexity and optimality
- Line Search Methods
- Goldstein conditions
- Wolfe conditions
- Basic Backtracking line search
- Bisection method for the weak Wolfe conditions
- Search Directions
- Steepest descent
- Newton's method for equations and minimization
- Broyden's method
- BFGS
-
Skills to Master:
- locating and classifying critical points
- checking coercivity
- checking convexity
- executing the backtracking and bisection line searches.
- Implementing Newton's method
- Implementing Broyden and BFGS in Matlab
-
Quiz:
-
The quiz will consist of 2 questions.
The first question will be related to the vocabulary
words from, or preceding, the notes on
Optimality Conditions for Unconstrained Problems
(except the material on the Cholesky factorizaton and matrix square roots).
The second question
will be computational. It will either be identical to or very similar to
one of the exercises
from Problem Set 3 or problems 1-5
on Problem Set 4.