7.4 Constraint Qualifications在线视频

Hi, everyone,

welcome to modern optimization methods.

Today we will introduce the fourth part of chapter seven,

the constraint qualifications.

We will basically introduce the following definitions

to derive the constraint qualifications.

One is tangent cone

and another one is linearized feasible direction.

And finally

is the linearly independent constraint qualification.

Now let's start with a brief talk about constraint qualifications

as we analyzed in the previous parts

for the first order optimality condition,

we have derived the first order optimality condition

by using some sort of linear expansion.

And then we get the mathematical form

for first order optimality condition.

However,

a question is whether such linear approximation works

or whether it is sound,

so we have to provide some theoretical investigation to prove this.

And this theoretical tool is just the constraint qualification.

In other words,

the constraint qualification actually shows that

under what condition we can do linear expansion

to the constraints as well as to the function values.

Now let's first take a look at the tangent cone.

We start with the definition

about a feasible sequence approaching a point x.

Assume that Ω is a closed convex set.

Given a feasible point x,

then we call a sequence zk

a feasible sequence approaching point x

if the following conditions hold.

For sufficiently large k,

the sequence zk will be inside of Ω,

and the second condition is that the limit of zk must be x,

so this will be a feasible sequence approaching x.

And with this feasible sequence approaching to x

then we can give the tangent direction.

What is tangent direction?

It is defined as follows.

We make this vector d to be a tangent

or tangent vector to a set Ω at point x

if the following conditions hold.

The first condition is that

we can find a feasible sequence zk approaching this point x.

The second condition is that

there is a sequence of positive scalars tk

with tk approaching to zero,

such that the following condition holds,

meaning that the limit of this ratio is exactly the direction d.

Then we will call that

this d is a tangent vector to the set Ω at point x.

And all the tangent vectors,

they will make up the tangent cone to set Ω at point x.

This is the definition for tangent cone.

In other words,

the tangent vector is defined as a limiting direction,

which is approaching to x.

If we take a look at this limit,

then it actually means that

we got a feasible sequence approaching x,

this is the first one.

Secondly,

we also got a sequence of scalar tk approaching zero

to make this limit exist,

and the limit will be the tangent vector.

We give an example in the next page.

Now in this page,

we actually have the feasible region as a circle.

And we consider

the tangent cone at the nonoptimal point (-√2,0)

Here,

let's construct two sequences to derive the tangent vector,

so one sequence is the zk like this.

We take it from downward to x,

and it moves along the direction of zk here

and approaching to the point x in this way.

So as k goes to infinity,

zk will approach x.

And we make the scalar tk as the distance between zk and x.

By taking the limit,

then we can get the limit direction d as (0, -1) this direction.

Because we are approaching this x from downward.

Similarly,

if we approach x from upward,

then we can similarly get another direction - tangent direction

as (0, 1).

Now the tangent cone

will make up by the two vectors here,

so the first component is zero

and the second one is actually both negative or positive,

or zero.

This means that the second component here

is actually free to move along any direction.

Now,

having given the tangent cone,

you can see that actually the tangent cone

is not easy to calculate.

Giving you a nonoptimal point,

calculating the tangent cone may be very difficult.

And to that end,

we need to use some alternative way

to represent this tangent cone.

The alternative way

is actually called the linearized feasible direction,

which we actually used in previous parts.

Now let's recall our constraint is some equality one

and inequality one.

And also we have definitions for the active set,

which actually means those constraints

that make strictly equality constraints at some point x.

Now,

having the constraint and active set,

we can define the linearized feasible direction

in the following way.

It says that f at the point x is made up of those directions,

so such directions have to satisfy two conditions.

The first one is for all equality constraints,

this direction must be orthogonal to the gradient

of these constraints.

And for the inequality constraints,

and also active constraints,

the inner product of the direction

with the gradient of constraints must be greater than

or equal to zero.

Which means that,

in this set,

we actually contain some linearized feasible directions.

And also notice that in this linearized feasible direction,

this set is also a cone.

Because if you multiply by a positive scalar,

it is still a feasible point in this set.

Now let's take a look at

how we calculate the linearized feasible direction,

still for the constraint here.

At the point here,

let's calculate the linearized feasible direction.

Recall that the definition for this case is that

we only require the direction

is orthogonal to the gradient of equality constraints,

so if we take the gradient of equality constraints,

then we can get the following condition.

By taking it to be zero,

we can see that it actually means that d1 is zero.

In other words,

the linearized feasible direction also takes the form

as the first component to be zero

and the second one is free.

Compared to the tangent cone

as we analyzed before,

you can see that the two sets are actually the same.

In other words,

sometimes or under some conditions,

the linearized feasible direction

is exactly the tangent cone at the same point,

so you may ask,

under what condition,

the conclusion will hold.

This actually brings the constraint qualifications.

Now let's give a very special class of constraint qualifications,

which is LICQ.

It actually means that

the linearly independent constraint qualification,

the definition is like this.

Assume that we have a point x

and we got the corresponding active set for some constraints.

Then we say that

the linear independent constraint qualification holds

if for all the active constraint gradients,

they are linearly independent.

If this condition is satisfied,

then we say that LICQ holds.

Now we have some remarks about the LICQ property.

As we mentioned before,

that the tangent cone

and the linearized feasible direction may sometimes coincide

with each other,

so under what condition they will coincide?

We need some constraint qualifications.

We can see that or we can prove that,

under LICQ condition,

then the linearized feasible direction does coincide

with the tangent cone,

so this is a very helpful property.

Therefore,

in our following optimality condition analysis,

we will always use LICQ.

Actually,

there are also other constraint qualifications,

like the Mangasarian-Fromovitz constraint qualifications

or other different types of constraint qualifications,

under which we can also get different characterizations

about linearized feasible direction and the tangent cone.

Also LICQ is actually a very special constraint qualification,

under which we do have that the two sets,

they are the same.

This is the main conclusion of this part.

Now let's make a brief summary about this part.

We basically introduce the constraint qualification,

which actually plays an important role

in analyzing the relations of linearized feasible direction

as well as tangent cone.

We stop here and see you next time.