3.1 Exact Step Length在线视频

Hi, everyone.

Welcome to modern optimization methods.

Today we will introduce the third chapter of this class.

Now, chapter three, line search methods.

This is the outline of chapter three.

We will first introduce the exact step length,

and then we go on to introduce the inexact line search,

including the Wolfe conditions,

the Goldstein conditions and backtracking conditions.

Finally,

we will discuss the convergence of line search methods

as well as convergence rate.

Now, let's come to the first part,

the exact line search.

Now we will introduce the update

of line search methods,

mainly focusing on the step length.

Then we will talk about the exact line search.

Recall that the update for line search methods

takes the following form.

So we stand at the current iterate xk

and we choose the direction pk

which is a descent direction.

Then we choose a step length αk

and then we move to the next iteration.

So this is the update for the line search method.

Now here the pk is the search direction,

which needs to satisfy the descent conditions.

Here we need pk transpose the gradient

to be strictly negative.

And αk to be the step length,

which we will discuss later.

Now let's focus on the step length.

The step length is determined by looking for

a minimizer along this direction.

So the minimizer along this direction is denoted

as a function Φ with respect to α.

Now this Φ(α) is defined as function value f at xk+αpk.

Here xk and the direction pk are all fixed.

And the only choice we need to make

is how big this step length α is.

Now there are two ways of choosing the step length.

One is we use the exact line search.

The exact line search means that

this αk must reach the global minimizer

along these directions.

So this is called the exact line search.

And for the inexact line search,

we only require that αk achieves adequate reduction

in function f along this direction.

The difference of the two line search strategies

actually means that sometimes you want to

get the exact minimizer along this direction,

Sometimes you only want

this α achieves adequate reduction in function values.

Let's take a look at this figure

which illustrates the exact line search and inexact line search.

Now we plot out the function Φ about α in this figure.

Obviously,

you can see that this is a nonconvex function.

So if you want to find the exact line search step,

this α lies here.

So we need to find that.

However, because it is a nonconvex function,

we may need a lot of computational cost

and a lot of techniques to find this global minimizer α.

If we just want to get some adequate reduction

in function values,

then any point α below Φ(0),

they are okay.

For example,

the first stationary point here

satisfies our adequate reduction condition.

And also the first local minimizer here

is also our candidate for the choice of αk.

So you can see that for inexact line search,

we may save some computational cost.

Now let's take a look at a special case

to calculate the exact line search.

We consider the quadratic function f(x)

where the Hessian matrix Q is positive semidefinite.

Now let's fix iteration xk and we fix the search direction pk.

Then we look for the global minimizer

of the step length,

which means that we search for the minimizer of Φ(α).

So recall that the Φ(α) defines for the function value f

at xk+αpk, and we fix xk and fix pk,

then we get Φ(α) like this.

And we write Φ(α) in terms of α.

So Φ(α) is a quadratic function in terms of α.

The coefficient of α^2 is here.

And this is the coefficient for linear term.

Now by taking gradient to be zero,

we can easily find the explicit form of this step length.

In other words, for quadratic function values,

we can find the exact line search αk in an explicit form.

We just calculate them following this formula,

which is a special case.

However, for other complicated form of functions,

we may not have such good explicit form.

You may design numerical algorithms

to find the exact line search.

Now we have some comments about the exact line search.

Although for quadratic functions,

the exact line search returns us an explicit form.

However, in general case,

if we want to do the exact line search,

we may need a lot of computational cost.

All right, which actually result in more cputime.

And for inexact line search,

this is based on the observation that

exact line search may have some difficulties to reach.

So we tend to inexact line search

we want to get some adequate reduction.

Meanwhile, we want to save a lot of computational cost.

So the main idea for inexact line search is that

we try out some function values

or even use some information for gradient.

And we try to find some candidates for the step length,

then we accept one of those candidates

when some adequate or sufficient reduction conditions

are satisfied.

So in other words, for inexact line search,

we can put it into two phases.

In the first phase,

we find some intervals where the candidates of α lie.

Then within this interval,

we try to do bisection or interpolation

in order to pick up one particular choice

for the step length of αk,

such choice should give a sufficient decrease

in the function values.

So you have to be careful to make sure

some sufficient reduction condition must be satisfied.

Below I give an example to show that

sufficient reduction is important in choosing a step length.

For example,

here we choose function values fk

like the sequence 1/k here.

So each time the function value takes 1/k such evaluations.

And we can see that for this fk

we do have reductions in function values.

Because this is strictly decreasing sequence.

However,

as we can see in this figure that

the minimum of this function f is reached at -1 here,

which is below 0.

However, if we use this function sequence 1/k.

The limit of this sequence is zero.

In other words,

although we can get function reduction in each iteration,

such reduction cannot guarantee us

to get the minimum of this function values.

So in other words,

we have to emphasize some sufficient reduction conditions

on the choice of step length.

We will discuss this in more details in the next part.

So for the inexact line search,

there are mainly three types.

For the first type is the Wolfe condition.

The second one is the Goldstein condition

and the third one is the backtracking approach.

We will discuss this later in the next part.

Now in this part, let's make a brief summary.

We mainly introduce the step length,

including the exact step length and inexact step length.

In the next part,

we will discuss more details for different strategies

of inexact step length.

So we stop here and see you next time.