Guide for Week 8
Math 408 Section A, February 25, 2013
-
Reading Assignment:
Homework Assignment:
Vocabulary Words
- 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)
- Numerical Linear Algebra
- Gaussian elimination matrices
- upper and lower triangular matrices
- LU factorization
- Cholesky Factorization
- unitary transformations
- Householder reflections
- QR Factorization
- orthogonal projections
- The Conjugate Gradient Algorithm
- Q-conjugacy
- Show Q-conjugacy implies linear independence
- conjugate direction methods
- Expanding subspace theorem
- the conjugate gradient algorithm (CGA)
- the Conjugate Gradient Theorem
- the non-quadratic CG algorithm
- the Fletcher-Reeves and Polak-Ribiere formula
- Optimality Conditions for Constrained Problems
- Tangent directions
- Basic Constrained 1st-Order Optimality Conditions
- Regularity
- the Lagrangian and Lagrange multipliers
- Constrained 1st-Order Optimality Conditions
- Karush-Huhn-Tucker (KKT) conditions
- Constrained 2nd-Order Necessary and Sufficient Conditions
- 1st-Order Necesaary and Sufficient Conditions in Convex Optimization
-
Key Concepts:
- Search Directions
- steepest descent
- Newton direction
- Newton Like Methods
- matrix secant methods
- The Conjugate Gradient Algorithm
- Q-conjugacy
- the conjugate gradient algorithm
- Optimality Conditions for Constrained Problems
-
Skills to Master:
- Checking Q-cojugacy
- write a pseudo code implementation of the CGA
- checking the KKT conditions
-
Quiz:
-
The quiz will consist of 2 questions.
The first question will be related to the vocabulary
words from the notes on
Search Direction.
In the second question you will be asked to solve a problem similar to one
of the problems on Problem Set 6.