1
$\begingroup$

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.

enter image description here

2 Answers 2

1

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?

  • 0
    @WillieWong Excuse me but I also had some KKT questions for which I received no answers: http://math.stackexchange.com/questions/216963/optimality-conditions-for-non-linear-equations http://math.stackexchange.com/questions/216963/optimality-conditions-for-non-linear-equations I will be happy if you have at least some comments.2012-10-26
0

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.