Stationary Points

We could define a stationary point by using the first order Kuhn-Tucker condition for opti-mality. That is

0 F⁴x^?

∑

q i^D 1

λic_ix λi ^< 0 (4.2)

If Cx F 0, this generalization is the same as the unconstrained case as shown in (2.9). This is natural when realizing that for Cx F 0 the constraints have no effect. The interesting case is when Cx 0, i.e., we are at the border of the feasible regionD.

When noting that Cx is a minimax function, then we can define the generalized gradient of the constraints ∂Cx in a similar way as we did with∂Fx in (2.6), by using the first order Kuhn-Tucker conditions which yields

∂Cx^#8

∑

i^; Ac

λic⁴_ix^Y

∑

i^; Ac

λi 1λi ^< 0^N (4.3) where

Ac⁸ i c_ix^# Cx^[h (4.4)

The stationary point could, however, be defined slightly differently by using the Fritz-John stationary point condition [Man65, p. 94]. This condition holds when Fx in the nonlinear programming problem (4.1) is a smooth function. Then it holds for a stationary point that 0^$ F^4dx.

0 λ0F⁴x λc⁴_ix^Œ λ

∑

^q

i^D 1

λi λ0 λ 1 (4.5)

where the multipliersλi ^< 0 for i 0^@q. If constraint i is not violated, then c_ix F 0 which leads toλi 0. Forλ0^X 0 andλ^X 0, the stationary point condition for the Fritz-John point is

0^$ conv F⁴x∂Cx^Œ (4.6)

So, we say that the null vector should belong to the convex hull spanned by F^4dx and∂Cx . But this only hold when Fx is smooth, and Cx^B 0. There are, however, other cases to consider, and for that Merrild [Mer72] defined the map

Mx^{# R}

ST ∂Fx if Cx F 0

conv ∂Fx∂Cx if Cx^# 0

∂Cx if Cx^eX 0

(4.7) As proposed in [Mad86] we will use the Fritz-John stationary point condition in the follow-ing, because for some cases the stationary point condition based on Kuhn-Tucker in (4.2) will not suffice. This is illustrated through an example, but first we shall see that there is in fact no huge difference between the two stationary point conditions.

First, the Fritz-John stationary point condition says that

0^$¯ λf^{4 °}1⁰ λ c⁴ f^{4 $} ∂Fxc^{4 $} ∂Cx0^A λ^A 1^h (4.8) Second, the stationary point condition derived from Kuhn-Tucker in (4.2) says that

0^$% f⁴ µc⁴ f^{4 $} ∂Fx c^{4 $} ∂Cx µ< 0^N (4.9) where µ^‰1⁰ λ^G λ. We see that the two conditions are equivalent if 0^F λ^F 1. That is, if 0 belongs to the convex hull in (4.8), then 0 will also belong to the convex hull in (4.9) as seen on figure 4.1.

Figure 4.1: The convex hull for three different values of λ. Sta-tionary point condition due to (left) Kuhn-Tucker, (right) Fritz-John.

λ ⁺ 0 (dotted line) , λ ⁺ 0^‡5 (dashed line) andλ⁺ 1 (solid line).

Before we give the example, we must define what is meant by a stationary point in a con-strained minimax framework.

Definition 4.1 x^$ Dis a stationary point of the constrained minimax problem in (4.1) if 0^$ Mx

We now illustrate why the Fritz-John condition is preferred over Kuhn-Tucker in the fol-lowing example. We have the folfol-lowing problem

min_xFx x₁

subject to

c1x^#"‰0 x2 x²₁ ^A 0

c₂x^#" x₂ x²₁ ^A 0

(4.10)

An illustration of the problem is given in figure 4.2 (left). From the constraints it is seen that the feasible domainDis the point x^to 0 0^q, so the solution must be that point regardless of F. If wee used the Kuhn-Tucker stationary point condition, then the convex hull (dashed line) would not have 0 as part of its set, and hence the point would not be stationary due to the definition, which is obviously incorrect.

When the Fritz-John stationary point condition is used, the convex hull can be drawn as indicated on the figure by the solid lines, for multiple values ofλ. Here we see that 0 can be a part of the convex hull ifλ 0. So the Fritz John condition can be used to define the stationary point successfully.

PSfrag replacements

x⁶

PSfrag replacements

x⁶

Figure 4.2: The dashed line shows the convex hull due to the Kuhn-Tucker stationary point condition, forλ⁺ 1. The solid line indicate Fritz-John, forλ⁺ 0^,0^‡25^{,±‡±‡‡•,}1.

The Fritz-John conditions is, however, not without its drawbacks. If we linearize the con-straints in (4.10), then we have the situation shown in figure 4.2 (right). Here we see that the line between c1x and c2x can be a stationary point regardless of F, even when F is increasing along the line.

The last example shows that it is not possible to generalize proposition 2.1 to the constrained case, because ifλ 0 then it is not certain that F_d⁴x ^< 0 for every direction at x.

As defined in [Mad86] we introduce the feasible direction.

Definition 4.2 For d ^$ IRⁿand d^O 0, a feasible direction from x^$ D^{exits if V} ε^X 0 so that x td^$ Dfor 0^A t ^A ε.

Proposition 4.1 If Cx^# 0 and d is a feasible direction, then C_d⁴ x^eA 0.

Proof: [Mad86] pp. 53.

This means that the directional derivative for the constraints C_d⁴ x must be negative or zero when whe are at the border ofDand go in a feasible direction. This must hold since Cx is a convex function.

One way we can avoid the situation described in the last example is to assume that Cx is negative for some x. In that case the feasible domainDwould not be a point, and F would have an influence on the stationary point condition in such a case becauseλ^X 0. This leads to the following proposition that holds for stationary points.

Proposition 4.2 Let x^$ D^{. If F}_d^{4 x <} 0 for all feasible directions d from x then 0^$ Mx. On the other hand, the following holds:

0^$ Mx and^V y^$ IRⁿ: Cy ^F 0 then F_d⁴ x < 0 for all feasible directions d.

Proof: [Mad86] pp. 54

We see that the first part of the proposition is very similar to the unconstrained case. The second part of the proposition deals with the case where the unconstrained problem at x would have a negative directional derivative, so in the constrained case where Cx^B 0 we are stopped by constraints at x. An illustration of a simple case is given in figure 4.3.

PSfrag replacements

x x⁶

Fx Cx

d Figure 4.3: The point x^u indicates

a solution to the constrained prob-lem, and the feasible direction is indicated by d.

We see that when Cx^B 0 andλ^X 0 because ^V y^$ IRⁿ: Cy F 0 then the convex hull of the Fritz-John stationary point condition can be written as

0 λf^°1⁰ λ c ^Q 0 f µc µ1⁰ λ^G λ (4.11) where µ^X 0, f^$ ∂Fx and c^$ ∂Cx . We see that in this case the Fritz-John and Kuhn-Tucker stationary conditions are equivalent. Next we use the feasible direction d.

0 f^Td µc^Td (4.12)

And from proposition 4.1 we see that if d is a feasible direction, then it must hold that C_d⁴ x^nA 0 and therefore due to the definition of the directional derivative in (2.13) and µ^X 0, we have that

C_d⁴ x^eA 0 ^E µc^Td^A 0 (4.13)

which is obvious as illustrated in figure 4.3. This leads to

f^Td< 0 ^E F_d⁴ x < 0 (4.14)

In document Minimax Optimization without second order information (Sider 53-57)