2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.