Guide for Week 3
Math 408 Section A, January 21, 2013
-
Reading Assignment:
Homework Assignment:
- Finish all of the problems in
Problem Set 2.
Due Friday, January 18.
-
Do all of the problems in
Problem Set 3.
Due Wednesday, January 25.
Vocabulary Words
- Language and Notation of Nonlinear Optimization
- linear function
- convex polyhedron
- quadratic function
- objective function
- feasible or constraint region
- Convex set and function
- linear and quadratic programming
- the linear least squares problem
- global solution and strict global solution
- local solution and strict local solution
- first-order optimality condition for unconstrained problems
- critical points and stationary points
- Optimality Conditions for Unconstrained Problems
- Weierstrass extreme value theorem
- 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
-
Key Concepts:
- Language and notation
- Convexity
- local and global (strict) extrema
- first-order optimality conditions
- critical points and stationary points
- 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
-
Skills to Master:
- locating and classifying critical points
- checking coercivity
- checking convexity
- executing the backtracking and bisection line searches.
-
Quiz:
-
The quiz will consist of 2 questions.
The first question will be related to the vocabulary
words from all of the notes up to and including those on
Optimality Conditions for Unconstrained Problems.
In the second question you will be given two functions.
For each function you will be asked to
determine and verify whether the function
is coercive and/or convex, then compute and classify their critical
points if they exist.