Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that the solution to finding minimum of $f(x)=-x_{1}$ With conditions

$-\sin(x_{1})+x_{2} \leq 0$
$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.

share|improve this question
    
Kuhn, not Kuhner. –  Did Jan 7 '13 at 12:55
    
Can you write down the Kuhn-Tucker conditions for this problem? –  Mike Spivey Jan 7 '13 at 17:33
add comment

1 Answer

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$.

share|improve this answer
    
Thank you. But I stil don't undestand why such function $x_{h}$ doesn't exist. And why you take this set: $\{x | \langle x , \binom{1}{1} \rangle \geq 0 \}$? Thank you. –  user57157 Jan 13 '13 at 20:22
1  
@user57157: I have added a note above that expands on this points. –  copper.hat Jan 13 '13 at 21:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.