9.2 Exact Penalty Function在线视频

Hi, everyone.

Welcome to optimization methods.

Today we will introduce the second part

of chapter nine,

the exact penalty method.

So recall that in this chapter

we are trying to solve the constrained problem

with equality constraints and inequality constraints.

We try to use the way that

we transfer the constraint

into the unconstrained problem.

So in the previous part,

we introduce that we transfer the constraints

in terms of quadratic penalty method,

and we solve the resulting unconstrained problem.

So there is another way

that we transfer the constraint

in terms of penalty function by absolute values.

So let's take a look at the nonsmooth

penalty method,

which is also referred to as l1 penalty method.

In l1 penalty method,

we just penalize the constraints

in the absolute value here.

So for equality constraints,

we just put the absolute value here

and do the summation.

For inequality constraints,

we take the max of zero

and the nonnegative part of

inequality constraints,

then we put them directly into the objective function.

This will become the l1 penalty function here.

So in other words,

we replace the l2

penalty function by l1 penalty function.

And then we get the l1 penalty problem.

So we have some remarks

about the exact penalty method.

Actually, for exact penalty method,

why we call it exact,

because it has a nice property,

meaning the exact recovery property

that is by choosing a proper penalty parameter μ.

The resulting

penalty problem have the same solution

as the original problem.

So recall that in quadratic penalty method,

we have to drive the parameter σ

to be infinity in order to get the original solution

for the problem.

Now here that we have no need to drive this

penalty parameter μ to infinity.

So we just choose a proper one,

then we can get the exact solution

of the original problem.

Now,

let's take a look at the example here.

We get a very simple example in one-dimensional space,

where we try to minimize x

and we have a nonnegative constraint

that x must be greater than or equal to one.

To see the constraint and the objective,

we can easily find that the optimal solution

is achieved at x* =1.

And if we take a further look at the l1 penalty function,

it actually takes the following form

that we multiply the violation of the inequalities

by a penalty parameter μ,

and since this is an absolute value of max,

according to different cases,

we can write the l1 penalty function into two parts.

If x is smaller than or equal to one,

then this will be a violation,

and we add the penalty term here.

So the objective becomes the term like this.

And if x satisfies the condition,

meaning that at x is greater than or equal to one,

then the function value takes the original one,

which is x.

So in other words,

for the one-dimensional example here,

we can actually plot the figure of this

l1 penalty function.

And by taking the minimization

of the l1 penalty function,

we can find the minimizer.

So below,

we demonstrate the figure of the penalty function.

As we can see that,

this is the kind of penalty function.

So the left hand side is just

a penalty one because in this case,

x violates the constraints.

When x is greater than one,

then this is the original function.

And for this case,

you can see that if μ is greater than one,

then we have the figure like this,

where the optimal solution is achieved

exactly at one.

However,

if we choose penalty parameter μ

strictly smaller than one,

then the penalty function take the shape like this,

where x=1

is not the minimizer of the problem.

Because for the part here,

we can actually see that this problem is unbounded.

Therefore,

for l1 penalty function,

the parameter μ has to be chosen carefully.

It has no need to turn to infinity.

Now let's take a look at

how we do the exact penalty method.

So the framework of the algorithm

is demonstrated here,

where it is very similar

to the quadratic penalty method, actually.

So in the initial point

or the starting point,

we still choose the penalty parameter μ0,

and tolerance τ

as well as a starting point xs0.

Then we start the loop

in the following way.

So in each iteration,

we find an approximate minimizer

about this l1 penalty function

with a starting point at xsk,

and if the measurement of violation

is smaller than or equal to τ,

then we will stop the inner iteration.

And then we return the current iteration xk.

Now we check whether we need to

stop the outer loop.

If the stopping criteria is satisfied,

then we stop with the out loop.

Otherwise,

we need to choose the next new

penalty parameter to be greater

than the current one.

And then we choose a new starting point

for the next loop.

And the iteration goes on until

the final stopping criterion is satisfied.

Now let's make a brief summary about

the exact penalty method.

The exact penalty method basically means that

we take the penalty function as the l1 penalty function

to do the optimization process.

There is a good property

about the exact penalty function.

However,

when we try to solve the inner problem,

we actually may get some difficulty

because the objective function is nonsmooth.

Anyway,

we will leave this problem to the future,

which we will discuss

how we solve nonsmooth problems.

We stop this part here and see you next time.