0
$\begingroup$

Suppose we are dealing with the following non linear programming problem: $$ \min f(x)=x_1-5x_2 \\ g_1(x)=-x_1^2+x_2\le 0 \\ g_2(x)=x_1^2-4x_2\le 0 \\ g_3(x)=x_2-1\le0 $$

We can get a visualization of the feasible region using Wolfram Alpha:

enter image description here

To solve this problem, I wanted to compute all the Fritz-John and Kuhn-Tucker points.

There are 8 possible combinations of touching a set of borders.

We can easily see that there are no FJ or KT points in the middle of the region, since the gradient of the cost function $f$ is never $0$.

We can also easily see from the drawing that there is no way of satisfying all three conditions with an equality, so we can also ignore that case.

The problem I have is with the rest of the cases.

For example, let's assume that $g_1(x)=0, g_2\ne 0 \ne g_3$.

Then to find the FJ points I have to find a multiplier $u$ such that: $$ u_0 \nabla f(x)+u_1 \nabla g_1(x)= \begin{pmatrix} 1 & -2x_1\\ -5 & 1 \end{pmatrix} \begin{pmatrix} u_0 \\ u_1 \end{pmatrix} =0 $$ where I already know that $u_2=u_3=0$.

Such a multiplier can be found iff the determinant associated to the matrix in the equation is zero. But the determinant is zero iff $x_1=\frac{1}{10}$.

Thus I have that since $g_1(x)=-x_1^2+x_2= 0$, the FJ point is $(\frac{1}{10}, \frac{1}{100})$.

We know that there are no KT points since that would require us that: $$ \nabla f(x)+u_1 \nabla g_1(x)=0 $$ which is impossible to achieve.

Similarly for the case where $g_2=0, g_1, g_3 <0$ I get that the only FJ point is $(\frac{2}{5}, \frac{1}{25})$. If I plug this into the KT equation, I get that it is a KT point!

$$ \nabla f + u_2 \nabla g_2 = \begin{pmatrix} 1+2u_2 x_1 \\ -5 - 4u_2 \end{pmatrix}=0 \implies u_2=\frac{-5}{4} \wedge x=(\frac{2}{5}, \frac{1}{25}) $$

Similarly for the case where $g_3=0, g_1, g_2 <0$ I get that there are no FJ or KT points.

Now, what is left to analyze are the cases where two border conditions are met simultaneously.

For example, let's say that we want to analyze the points where $g_1=g_2=0, g_3<0$. The only such point is $(0,0)$.

$$ \nabla f + u_1 \nabla g_1 + u_2 \nabla g_2= \begin{pmatrix} 1 & -2x_1 & 2x_1\\ -5 & 1 & -4 \end{pmatrix} \begin{pmatrix} u_0 \\ u_1 \\ u_2 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 \\ -5 & 1 & -4 \end{pmatrix} \begin{pmatrix} u_0 \\ u_1 \\ u_2 \end{pmatrix} $$

Since this system is homogeneous and underspecified, by the Roche theorem we can deduce that there are infinity valid solutions, and in particular there exists a non zero solution. So $(0,0)$ is a JF point.

Saying that this point is also KT would be equivalent to saying that $$ \begin{pmatrix} 0 & 0 \\ 1 & -4 \end{pmatrix} \begin{pmatrix} u_1 \\ u_2 \end{pmatrix}= \begin{pmatrix} -1 \\ 5 \end{pmatrix} $$ has a solution. Which it does not since the rank of the augmented matrix is greater than the rank of the coefficient matrix.

Similarly, in the case where $g_1=g_3=0, g_2<0$ we have the points $(\pm 1, 1)$.

Both points are KT since the coefficient matrix associated to the gradients of the g's is of rank 2.

Lastly we have that the points when $g_2=g_3=0, g_3<0$ are $(\pm 2, 1)$.

Following the same reasoning, since the rank of the matrix associated is 2, we get that both points are KT.

So, summing up:

  • The FJ points we have found are $(\frac{1}{10}, \frac{1}{100}), (\frac{2}{5}, \frac{1}{25}), (0,0), (\pm 1, 1), (\pm 2, 1)$
  • The KT points we have found are $(\frac{2}{5}, \frac{1}{25}), (\pm 1, 1), (\pm 2, 1)$

If I wanted the optimum, I would have to plug these points in the equation and I would get that the minimum is $(- 2, 1)$.

Questions:

  • Am I right in saying that every KT point a FJ point? In that case, what do I win by computing the KT points when I am trying to find an optimum?
  • Am I computing KT and FJ points right? Is there any shortcut I could be using?
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Let's recall first the basic optimality conditions:

$$\textbf{1. If x is a local minimum, then x is FJ.}$$

$$\textbf{2. If x is local minimum and some constraint qualification(CQ) holds at x, then x is KT.}$$

Now, to answer your question, all KT points are FJ points: just put $u_0=1$. What you win by computing KT points is that you get a smaller set of points which 'contains' the set of local minima on which suffices to verify optimality. I wrote 'contains' because there may be local minima that are not KT; of course, no CQ can hold at those points. That is the price you have to pay in order to obtain a smaller set. Typically, the set of FJ points is way larger than those of KT, so to find KT points is always desirable. However, FJ points are important too. When CQ fails at one point and it is not KT, you can still test if it satisfies the FJ condition.

Curious fact: there are nonlinear optimization problems on which the Mangasarian-Fromovitz Constraint Qualification(and hence the Linear Independence Constraint Qualification) is violated at any feasible point. Furthermore, any feasible point is FJ. This are called Mathematical Programs with Complementarity Constraints(MPCC).

As of the second question, yes, you are doing fine.

$\endgroup$
5
  • $\begingroup$ I notice I am confused. For me a FJ point is a point such that there are multipliers $u$ satisfying that $u_0 \nabla f + u_1 \nabla g_1 + ... + u_n \nabla g_n = 0$ while $u_i g_i =0$, while a KT point is a point such that there is a multiplier satisfying the same condition but also that $u_0=0$ AND that the gradients $\nabla g_i$ for which $g_i = 0$ are linearly independent. Thus in order to find the optimum I am under the impression that I have to find all the KT points AND all the FJ points where the gradients are not linearly independent. $\endgroup$ Commented Sep 7, 2017 at 9:18
  • $\begingroup$ Maybe what you are trying to tell me is that I could have know in advance that for example $(\frac{1}{10}, \frac{1}{100})$ was not an optimum because even though it is a FJ point it also satisfies the linear independence condition yet it is not a KT? And that in the other hand I would have had to still check $(0,0)$ since it does not satisfy that $\nabla g_1$ and $\nabla g_2$ are linearly independent in $(0,0)$? $\endgroup$ Commented Sep 7, 2017 at 9:21
  • 1
    $\begingroup$ Your definition of KT point is not correct. A KT point is a FJ point in which you can choose $u_0=1.$ Hence, the LICQ is not necessary. There can be KT points at which the LICQ does not hold(but other CQ may). Nevertheless, in order to find minimum it suffices to find all KT(in the right sense) and FJ at which the LICQ doesn't hold $\endgroup$ Commented Sep 7, 2017 at 9:31
  • 1
    $\begingroup$ Also, if $(\frac{1}{10},\frac{1}{100})$ is FJ and the LICQ holds, it must be KT (just divide by $u_0$) $\endgroup$ Commented Sep 7, 2017 at 9:33
  • $\begingroup$ Oops! You are right, $(\frac{1}{10},\frac{1}{100})$ is a KT point. You say that to find the optimum we need to find all the KT and FJ where LICQ doesn't hold, but this is the same as all the FJ points isn't it? Why do we have a separate concept for KT points then? $\endgroup$ Commented Sep 7, 2017 at 10:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.