Let $x^*$ be a feasible solution of the following convex optimization problem \begin{align}\min&\quad f_0(x)\\\text{s.t.}&\quad f_i(x)\leq0,i=1,\ldots,m\end{align} where $f_0$ is $C^1$ and convex and $f_i$ are $C^1$ and strictly convex functions. Suppose the following condition is satisfied:

  • there exist $y_i\geq0$ for $i\in\{0\}\cup I(x^*)$ where $I(x^*)=\{i:f_i(x^*)=0\}$ which are not all zeroes such that $y_0\nabla f_0(x^*)+\sum\limits_{i\in I(x^*)}y_i\nabla f_i(x^*)=0$.

Prove that $x^*$ is an optimal solution.

I've tried to set $S(x)=y_0f_0(x^*)+\sum\limits_{i\in I(x^*)}y_if_i(x^*)$. Then $S$ is a convex function as it is a sum of convex functions and $x^*$ is minimizer of $S$ because $\nabla S(x^*)=0$ and $$f(x^*)=y_0f_0(x^*)+\sum_{i\in I(x^*)}y_if_i(x^*)=S(x^*).$$ Using the gradient inequality we get $0=y_0\nabla f_0(x^*)+\sum_{i\in I(x^*)}y_i\nabla f_i(x^*)$ if and only if $$0=\left(y_0\nabla f_0(x^*)+\sum_{i\in I(x^*)}y_i\nabla f_i(x^*)\right)^\top(y-x)<S(y)-S(x^*)$$ which implies that $S(y)>S(x^*)$. This is the same as $$y_0f_0(y)+\sum_{i\in I(x^*)}y_if_i(y)>y_0f_0(x^*)+\sum_{i\in I(x^*)}y_if_i(x^*)=y_0f_0(x^*)$$ and $y_0f_0(y)+\sum_\limits{i\in I(x^*)}y_if_i(y)\leq y_0f_0(y)$ because $y_i\geq0$ and $f_i(y)\leq0$. Thus $$y_0f_0(y)>y_0f_0(x^*)\iff f_0(y)>f_0(x^*)$$ which is the desired result. The strong inequality is because $f_i$ are strictly convex. Where $y_0\neq0$
Now I need to solve the case when $y_0=0$ any hint?


1 Answer 1


Note that by assumption, there must be some $i \in I(x^*) \cup \{0\}$ with $y_i \ne 0$. Let $\mathcal I = \{i \in I(x^*) \cup \{0\} \mid y_i \ne 0\}$ be the set of such indices.

Let $u$ be any unit vector of the same dimension as $x^*$. We wish to show that $x^* + tu$ is either not feasible or has weakly worse objective for any positive scalar $t$. To show this, choose an index $i$ from the set $\mathcal I$ such that $\nabla f_i(x^*) \cdot u \geq 0$, which is possible because the following sum cannot have all negative terms. $$ \sum_{i \in \mathcal I} y_i(\nabla f_i(x^*) \cdot u) = \left(\sum_{i \in \mathcal I} y_i\nabla f_i(x^*)\right) \cdot u = 0. $$ Note that the sum above is just the original expression with all terms where $y_i = 0$ removed and the $i = 0$ term included into the sum if $y_0$ is nonzero.

However it now follows from $\nabla f_i(x^*) \cdot u \geq 0$ that $f_i$ is non-decreasing in the direction $u$.

If $i = 0$, it follows by weak convexity that $f_0(x^* + ut) \geq f_0(x^*)$ for every positive $t$. Thus $x^*$ is optimal in this direction.

If $i \ne 0$, it follows from strong convexity that $f_i(x^* + ut) > f_i(x^*) = 0$ for every positive $t$. Thus $x^*$ is the only feasible solution in this direction.

It now follows that all other solutions are either infeasible or have $f_0(y) \geq f_0(x^*)$. Thus $x^*$ is optimal.

Note that if you assume that $y_0 = 0$ as in your question, the above argument concludes that $x^*$ is the only feasible solution.

  • $\begingroup$ Very nice :) now I see why we need the strict convexity .Thanks $\endgroup$
    – convxy
    Commented Dec 23, 2020 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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