$ f(x)+ \sum \lambda_ig_i(x) \geq f(\bar x), \forall x \in \mathbb{R}^n.$

Question

Suppose that $f,g_i : \mathbb{R}^n \to \mathbb{R}$ $(i=1,\ldots,m)$ are convex functions and $\exists x$ such that

$$g_i(x)<0 , \qquad i=1,\ldots,m.$$

Show $\bar x$ is optimized solution of

$$\min f(x)$$

$$\text{s.t. }g_i(x) \leq 0, \qquad i=1,\ldots,m$$

iff $\exists\lambda \geq 0$ such that

$$ f(x)+ \sum_{i=1}^m \lambda_ig_i(x) \geq f(\bar x), \qquad \forall x \in \mathbb{R}^n.$$

Answer 1

Quick answer: Just use the following two facts:

1. If $\bar x$ and $\lambda^\star$ together satisfy the KKT conditions, then $\bar x$ is primal optimal (and $\lambda^\star$ is dual optimal).
2. Suppose that Slater's condition is satisfied. Then there exists a dual optimal vector $\lambda^\star$, and if $\bar x$ is primal optimal then $\bar x$ and $\lambda^\star$ together satisfy the KKT conditions.

I'll write a more detailed answer below.

---

Terminology: The problem of minimizing $f(x)$ subject to the constraints that $g_i(x) \leq 0$ for $i = 1, \ldots, m$ will be called the "primal problem".

The Lagrangian is $$ L(x,\lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x). $$ Here $\lambda_i$ is the $i$th component of the vector $\lambda$.

The dual function is $$ h(\lambda) = \inf_{x \in \mathbb R^n} L(x,\lambda). $$ The dual problem is to maximize $h(\lambda)$ subject to the constraint that $\lambda \geq 0$.

I'll say that a vector $x \in \mathbb R^n$ is "feasible for the primal problem" if $x$ satisfies $g_i(x) \leq 0$ for $i = 1, \ldots, m$.

---

Solution: Let's start with the easier direction. Suppose that there exists a vector $\lambda^\star \geq 0$ such that $$ f(x) + \sum_{i=1}^m \lambda_i^\star g_i(x) \geq f(\bar x) \quad \text{for all } x \in \mathbb R^n. $$ If $x$ is feasible for the primal problem, then $\lambda_i^\star g_i(x) \leq 0$ for $i = 1, \ldots, m$, and so $$ f(x) \geq f(x) + \sum_{i=1}^m \lambda_i^\star g_i(x) \geq f(\bar x) \quad \text{for all } x \in \mathbb R^n. $$ If we additionally assume that $\bar x$ is feasible for the primal problem, then we can conclude that $\bar x$ is primal optimal.

[Note that you did not give us this additional assumption in your question, but I think we need it.]

---

Conversely, suppose that $\bar x$ is primal optimal. Here is a key fact: Because Slater's condition is satisfied, it follows that strong duality holds and there exists a dual optimal vector $\lambda^\star$. (A fairly simple visual proof of this fact is given in Boyd and Vandenberghe.)

Thus, $$ f(\bar x) = h(\lambda^\star) = \inf_{x \in \mathbb R^n} f(x) + \sum_{i=1}^n \lambda_i^\star g_i(x). $$ So we see that $f(\bar x) \leq f(x) + \sum_{i=1}^m \lambda_i^\star g_i(x) \quad \text{for all} x \in \mathbb R^n. $

(The reason I said that this direction is more difficult is that we had to invoke the key fact about Slater's condition.)