0
$\begingroup$

The author of the book was explaining the following question:
Consider the following problem:
$min -x_{1}$
subject to $ x_{2} -(1-x_{1})^3 \leq 0$
$-x_{2} \leq 0$

Show that$x^{*}$ = $\begin{pmatrix} 1 \\ 0\end{pmatrix}$ it is a minimizer, but the KKT conditions are not met.

The book's solution:
We will determine if the point meets the KKT conditions. Restriction functions are:
$g_{1} = x_{2} - (1-x_{1})^3$
$g_{2} = -x_{2}$
The gradients of the objective functions and constraints are:
$\nabla f(x) = \begin{pmatrix} -1 \\ 0\end{pmatrix}$, $\nabla g_{1}(x) = \begin{pmatrix} 3(x_{1-1})^3 \\ -1\end{pmatrix}$ e $\nabla g_{2}(x) = \begin{pmatrix} 0 \\ -1\end{pmatrix}$
The gradient of the Lagrange function is:
$\nabla L(1,0,\lambda_{1}, \lambda_{2}) = \nabla f\begin{pmatrix} 1 \\ 0\end{pmatrix} + \lambda_{1}\nabla g_{1}\begin{pmatrix} 1 \\ 0\end{pmatrix}+ \lambda_{1}\nabla g_{2}\begin{pmatrix} 1 \\ 0\end{pmatrix} = \begin{pmatrix} -1 \\ 0\end{pmatrix} + \lambda_{1}\begin{pmatrix} 0 \\ 1\end{pmatrix}+\lambda_{2}\begin{pmatrix} 0 \\ -1\end{pmatrix} = \begin{pmatrix} -1 \\ \lambda_{1}-\lambda_{2}\end{pmatrix} = \begin{pmatrix} 0 \\ 0\end{pmatrix}$
The first equation cannot be satisfied with any value of the multipliers$\lambda_{1}$ e $\lambda_{2}$.
Note that the gradient gradients applied at the point$x^{*}$ são:
$\nabla g_{1}\begin{pmatrix} 1 \\ 0\end{pmatrix} = \begin{pmatrix} 0 \\ 1\end{pmatrix}$ e $\nabla g_{2}\begin{pmatrix} 1 \\ 0\end{pmatrix} = \begin{pmatrix} 0 \\ -1\end{pmatrix}$
isto é, $\nabla g_{1}\begin{pmatrix} 1 \\ 0\end{pmatrix} =-\nabla g_{2}\begin{pmatrix} 1 \\ 0\end{pmatrix}$. Gradients are linearly dependent, so the optimum does not have to satisfy KKT conditions.

My question is, why does the point not meet the KKT conditions? what does linear dependency have to do with KKT? Sorry for the writing, because English is not my mother tongue.

$\endgroup$

1 Answer 1

1
$\begingroup$

My question is, why does the point not meet the KKT conditions?

Because one of the KKT conditions is the stationarity condition, and as you pointed out, the first equation cannot be satisfied with any value of the multipliers.

what does linear dependency have to do with KKT?

There are a few conditions under which the KKT conditions are necessary. You might recognize the Slater condition, but another condition is the linear independence constraint qualification.

$\endgroup$
2
  • $\begingroup$ And to show that $x^{*}$ is minimizer ? would have to replace in f ? $\endgroup$ Oct 16, 2020 at 23:39
  • $\begingroup$ @Amissadaiferreira you can plot the feasible region, the minimizer has to be at an extreme point $\endgroup$
    – LinAlg
    Oct 17, 2020 at 1:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .