Background 2

Question 1

Describe line search algorithms:

Answer 1

in each iteration choose a direction p_k and then search along this direction from x_k by approximately solving(to find the minimum)
min f(x_k +αp_k)

Question 2

Describe trust region methods:

Answer 2

construct a model function m_k whose behaviour near x_k is similar to the original function f.

the search for a minimizer of m_k is restricted to some region around x_k

approximate minimizer of the model in this region.

Question 3

What is steepest descent direction?

What is the characteristic of this direction ?

Answer 3

steepest descent direction is the inverse of the gradient of the function f(x_k)

direction is orthogonal to the contours of the function.

Question 4

What is steepest descent method?

what is its convergence rate?

Answer 4

is a line search method that moves along the search path which is negative of the gradient of the function f(x_k) at every step

converge at linear rate. when ill condition converge factor r close to 1.

Question 5

Advantage and disadvantage of the steepest descent method ?

Answer 5

Advantage:
-it only requires the calculation of the gradient not the second derivative.

-negative of the gradient is guaranteed to produce a decrease in f.

Disadvantage:
-the method may converge very slowly on ill-conditioned problems(scaling) it will zigzag

Question 6

What is Newton direction ?

Answer 6

it derived from the second-order Taylor series

Assuming the hessians ∇*2 f_k is positive definite

Question 7

Advantage and disadvantage of Newton method ? What is the convergence rate?

Answer 7

Advantage:
- avoid slow convergence on ill-conditioned problems
- fast rate of local convergence
Disadvantage: 
-the Hessian is expensive to compute. 

-converge quadratically rate

Question 8

What is quasi-Newton direction ?

Answer 8

Use approximation of the hessians.

use the knowledge gained from the gradient at each step.

Question 9

Advantage of quasi-Newton method ?

and its convergence rate ?

Answer 9

• do not require computation of the Hessian

- still attain a super-linear rate

Question 10

Conjugate Gradient Strategies vs steepest decent ?
search direction?
convergence rates?
advantage ?

Answer 10

• more effective than the steepest descent direction
• each new search direction only depends on data from the previous step
• do not attain the fast convergence rates of Newton or quasi- Newton methods
• advantage of not requiring storage of matrices

Question 11

Golden section search

Answer 11

?

Question 12

backtracking line search

Answer 12

?

Question 13

Trust region linear model ?

Answer 13

??

Question 14

Trust region quadratic model ?

Answer 14

??