# What does the statement “Optimality condition for convex problem” mean? KKT or other condition?

I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with slighlty different answers: one assistant would assume $L^\infty$ -smoothness immediately but the assignment does not specify anything about smoothness and other two assistant got somehow lost. Wikipedia here states:

"The necessary conditions are sufficient for optimality if the objective function and the inequality constraints are continuously differentiable convex functions and the equality constraints are affine functions."

but the problem does not specify the $L^\infty$ so I cannot use KKT. So what is the condition the assignment is looking for here? Source is here. [Update] The original statement did have the bug with "the lack of differentiability", so Lipschitz at least according to Willie Wong, so no necessary conditions found. So let's consider the corrected version. I think this was the purpose of the assignment, I wrote it in my own words below.

-

You can, and must, assume that $f$ is differentiable. Otherwise a trivial counterexample is to pick some $y$ strictly in the interior of $X$, and let $f(x) = |x - y|$. It is convex, but at the minimum (which is achieved at $x^* = y$) no partial derivatives exist.

On the other hand, without the smoothness condition, we have that a convex function is automatically Lipschitz, and so we can consider its subdifferentials. A similar statement can be made regarding subdifferentials for your problem.

Perhaps the "special" thing that the instructor is looking at is that $X$ is a box and so the form of the KKT multipliers simplify?

-
The last sentence is just a random guess. I was merely commenting on the geometry of the box, for which "boundary versus not-boundary" can be easily decided and written down explicitly. I have no actual idea what your instructor is looking for when he/she said "special". Why not just ask the instructor? –  Willie Wong Oct 23 '12 at 16:23
Hang on, so what is special about the problem is that "it is not answerable (or even false) as stated"? –  Willie Wong Oct 24 '12 at 10:59
Yes that is my understanding. My instructor was not very specific. My assistant from CA Berkeley did not notice the issue, he made an impression that it was supposed to be some easy thing with KKT but did not address the differentiability -issue. Perhaps it was just a human-mistake, I don't really know but I should still learn things... –  hhh Oct 24 '12 at 13:24
@WillieWong Excuse me but I also had some KKT questions for which I received no answers: math.stackexchange.com/questions/216963/… math.stackexchange.com/questions/216963/… I will be happy if you have at least some comments. –  Seyhmus Güngören Oct 26 '12 at 9:54

Here is my attempt at the solution:

The Lagrangian of the given objective function is

$$L = f(x) +\sum_{i=1}^n \lambda_i (\alpha_i -x_i) + \sum_{i=1}^n\gamma_i(x_i-\beta_i)$$

where $\lambda_i, \gamma_i\ge 0$ are lagrange multipliers. The optimality condition is $\dfrac{\partial L} {\partial x^*_i}=0$ and the K.K.T. conditions are, $\forall i$ $$\alpha_i-x_i \le 0, \\ x_i-\beta_i \le 0, \\ \lambda_i \ge 0, \\ \gamma_i\ge 0, \\ \lambda_i(\alpha_i -x_i) = 0, \\ \gamma_i(x_i-\beta_i) = 0$$

The optimal point $x^*$ satisfies KKT conditions and, $$\dfrac{\partial L} {\partial x^*_i}=0 \\ \implies \dfrac{\partial f}{\partial x^*_i} - \lambda_i + \gamma_i = 0$$

when $x^*_i=\alpha_i$, then $(x^*_i - \beta_i) \ne 0$ therefore by KKT conditions, $\gamma_i = 0$ and $\dfrac{\partial f}{\partial x^*_i} = \lambda_i \ge 0$. Similarly the other conditions can be derived.

-