# Prove that $x^*$ is an optimal solution where $f_0$ is $C^1$ and convex and $f_i$ are $C^1$ and strictly convex functions

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) 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?

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.

• Very nice :) now I see why we need the strict convexity .Thanks Dec 23, 2020 at 15:13