|
Show that the solution to finding minimum of $f(x)=-x_{1}$ With conditions $-\sin(x_{1})+x_{2} \leq 0$ is point $(0,0)$, but the Kuhn-Tucker condition is not satisfied in this point. First part is easy (without optimization theory), but I dont know how to show second part. |
|||||
|
|
Let $g_1(x) = -\sin x_1 + x_2, g_2(x) = x_1-x_2$ and $\hat{x} = (0,0)^T$. Now let $\hat{g}_\mu = \nabla f(\hat{x})+\sum_i\mu_i \nabla g_i(\hat{x})$. Evaluating the gradients gives $\hat{g}_\mu = \binom{-1}{0}+\mu_1 \binom{-1}{1} + \mu_2 \binom{1}{-1}=\binom{-(1+\mu_1-\mu_2)}{\mu_1-\mu_2}$. It is easy to see that for any $\mu$, $\hat{g}_\mu \in \{\binom{-1}{0}\}+\text{sp} \{ \binom{1}{-1}\}$ which is a hyperplane that does not pass through zero. Hence $\hat{g}_\mu \neq 0$ for all $\mu$. Hence the KT conditions cannot be satisfied at a solution. To see why this is so, remember that the KT conditions need a first order constraint qualification to hold so that Farka's lemma (or variant) can be applied. The conditions boil down to showing that for every feasible direction $h \in \{\eta | \langle \nabla g_i(\hat{x}), \eta \rangle \leq 0 , \ \ i =1,2\}$ at a solution $\hat{x}$ (note that both constraints are active at the solution), there exists a (one-sided) differentiable function $x_h: [0,\epsilon) \to \mathbb{R}^2$ such that $x_h(0) = \hat{x}$ and $x_h'(0) = h$. In this example, the set of feasible directions is $\text{sp} \{ \binom{1}{1}\}$, and there is no $x_h$ that works for $h=\binom{1}{1}$ (since $\{x|g_i(x) \leq 0, \ i = 1,2 \} \cap \{x | \langle x , \binom{1}{1} \rangle \geq 0 \} = \{0 \}$). Note to answer question below: (A picture helps a lot here; draw one.) The set of feasible directions is $\text{sp} \{ \binom{1}{1}\}$, so we need see if we can find a suitable $x_\binom{1}{1}$ and $x_{-\binom{1}{1}}$. The function $x_{-\binom{1}{1}}(t) = -t\binom{1}{1}$ satisfies the required conditions, however there is no function that satisfies the conditions for $h=\binom{1}{1}$. To see this, we proceed by contradiction. Suppose such a $x_\binom{1}{1}$ exists, and consider the function $\phi(t) = \langle \binom{1}{1} , x_\binom{1}{1} \rangle$. Note that $\phi'(0) = 2 > 0$, hence $\phi(t) >0$ for small $t$. In particular, this says that $\phi(t) \in \{x | \langle x , \binom{1}{1} \rangle \geq 0 \}$ for such $t$. However, we also require that $\phi(t)$ be feasible, that is $\phi(t) \in \{x | x_2 \leq \sin x_1, \ x_1 \leq x_2 \}$. In particular, this means $\phi(t) \in Q = \{x | \langle x , \binom{1}{1} \rangle \geq 0 \} \cap \{x | x_2 \leq \sin x_1, \ x_1 \leq x_2 \}$. If I can show that $Q = \{0\}$, this gives a contradiction as this implies $\phi(t) = 0$ for small $t$. Clearly $0 \in Q$. Now suppose $x \in Q$. Then $x_1+x_2 \geq 0 $ and $x_2\geq x_1$ imply $x_2 \geq |x_1|$. Furthermore, we have $\sin x_1 \geq x_2 \geq |x_1|$. However, the only solution to $ \sin x \geq |x|$ is $x=0$, hence we have $x_1 = 0$, and hence $x_2 =0$. |
|||||||
|
