$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$

$$f_i : \text{convex};\quad x : \text{variable}$$

It is also considered that $g(y)$ is the optimal value of the problem and $\lambda^*$ is the optimal dual variable.

Then, it is claimed that $$g(z) \ge g(y) - \sum_{i=1}^m \lambda^*_i * (z_i - y_i)\tag{1}$$

Hence $- \lambda^*$ is a subgradient of $g$ at $y$.

Though the material I am reading from (Basic Rules for Subgradient Calculus, slide at 51:40 mins) claims the proof of (1) is straightforward, still I can't figure out how to derive that. Can anybody help ?

My Approach:

Assuming $z_i = f_i(x)$, I get the Lagrangian dual function as $g(z) = f_0(x) + \sum_{i=1}^{m}\lambda_i (z_i-y_i)$. Since $g(y)$ is the optimal value of the problem and $\lambda^*$ is the optimal dual variable, I can write

$$g(y)=f_0(x) + \sum_{i=1}^{m}\lambda^*_i(z_i-y_i)$$ or may be $$g(y)=f_0(x)$$ since $z_i = y_i$. But then I can't figure out how should I use the $\lambda^*$ in the eq (1) which is to be derived.

The unconstrained problem is $$g(y) = \inf_z g(z).$$ Based on problem definition, it is also true that $g(y) \le g(z)$. But how can (1) be derived from these relations? Or, I am doing something wrong assumptions here?

• I'm confused. What is $g(y)$? The value of $f_0$ at its minimum within the admissible region parameterized by $y$, right? If so, what does it mean to equate $g(y)$ with its infimum? Dec 31 '12 at 1:34
• $g(y)$ is considered as the optimal value of the primal problem. Yes, I think $g$ is the unconstrained optimization problem parameterized with variable $y$, the resource variable in $m$ inequality constraints. Though when I looked at literature, I find that generally the Lagrangian parameters (e.g. $\lambda, \nu$) are considered as dual variables. I am not sure why $y$ is the parameter in this case. Again, since we are trying to find the pointwise infimum of $g(z)$ and $g(y)$ is the optimal value, $y$ should be the minimizer. The Lagrangian part in $g(y)$ is minimized when $z_i = y_i$. Dec 31 '12 at 1:45
• @user7530: For a particular $x$, $f_0(x)$ is the fixed part and unvariant with parameter $y$. That's my understanding from the video lecture slide. What it tells in the lecture is that this problems falls into the category of convex minimization problems with minimal resource allocation, like for $m$ resources corresponding to $m$ inequality constraints. Dec 31 '12 at 1:52
• This is called sensitivity analysis. You will find an answer to your question in almost any book on convex optimization (e.g., stanford.edu/~boyd/cvxbook). First you need to convince yourself that $g$ is a convex function. Secondly (under Slater's qualification condition), $-\lambda^*$ is a subgradient of $g$. Jan 30 '13 at 13:36

I'm a bit surprised there's no full answer for this question (and it may be far too late to provide one). Anyway.

I'm using $\langle a,b\rangle=\sum_i a_i b_i$.

Lagrangian:

$$L(x,\lambda; y) = f_0(x) + \langle \lambda, f(x)-y\rangle$$

where $f$ is the vector value function with entries $f_1,\dots,f_m$. The dual of that Lagrangian is

$$H(\lambda; y) = \min_{x} L(x,\lambda;y) \le f_0 (x) + \langle \lambda , f(x)-y\rangle$$

for every $x$. To relate with the original problem $g(y)=H(\lambda^\star;y)$ if $\lambda^\star$ is the optimal dual variable.

This means that:

$$g(y) = H(\lambda^\star;y) \le f_0(x) + \langle \lambda^\star,f(x)-y\rangle$$

for every $x$. Now let's take $x$ such that $f(x)\le z$ then $z-f(x)\ge 0$ and since the dual variable is non-negative,

$$g(y) \le f_0 (x) + \langle \lambda^\star,f(x)-y\rangle + \langle \lambda^\star,z-f(x)\rangle$$

now take $x^\sharp$ a minimizer such that $g(z) = f_0(x^\sharp)$ (and, still, $f(x^\sharp)\le z$ of course) then, rearranging:

$$g(y) \le g(z) + \langle \lambda^\star, z-y\rangle$$

rearranging once more concludes the proof.