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

Question

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?

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.