# Prove $\sum_{i=1}^{m}\lambda_i^*\leq\frac{f(\hat{x})-f^*}{\underset{i=1,\ldots,m}{\min}(-g_i(\hat{x}))}$

Consider the primal problem \begin{align}f^*=\min&\quad f(x)\\\text{s.t.}&\quad g_i(x)\le0\tag P\end{align} where $$f,g_i$$ are convex functions. Suppose there exists $$\hat{x}$$ such that $$g_i(\hat{x})<0$$ and (P) is bounded from below ($$f^*>-\infty$$).

Consider the dual problem (D) given by $$\max\{q(\lambda):\lambda\in\operatorname{dom}(q)\}$$ where $$q(\lambda)=\min_xL(x,\lambda),\quad\operatorname{dom}(q)=\{\lambda\in\mathbb{R}^m_+:q(\lambda)>-\infty\}.$$ Let $$\lambda^*$$ be an optimal solution of the dual problem. Prove
$$\sum_{i=1}^{m}\lambda_i^*\leq\frac{f(\hat{x})-f^*}{\underset{i=1,\ldots,m}{\min}(-g_i(\hat{x}))}.$$

My attempt

From the the information that $$\lambda^*$$ is optimal solution of (D) we can deduce that $$f^*\leq q(\lambda^*)=\underset{x}{\min}\{f(x)+\sum_i\lambda_i^*g_i(x)\}$$ using the non-linear extension of Farkas' lemma. Because we take the minimal $$x$$ at $$q(x^*)$$, if we take $$\hat{x}$$ we only increase the value. Therefore $$\underset{x}{\min}\{f(x)+\sum_i\lambda_i^*g_i(x)\}\leq f(\hat{x})+\sum_i\lambda_i^*g_i(\hat{x})\implies f^*\leq f(\hat{x})+\sum_i\lambda_i^*g_i(\hat{x})$$ iff $$f(\hat{x})-f^*\geq \sum_i\lambda_i^*g_i(\hat{x})\geq \underset{i=1,\ldots,m}{\min}(-g_i(\hat{x}))\sum_i\lambda_i^*.$$ Therefore we get $$f(\hat{x})-f^*\geq\underset{i=1,\ldots,m}{\min}(-g_i(\hat{x}))\sum_i\lambda_i^*$$ as desired.