# How to prove that the subgradient of a dual function contains the equality constraint for closed and convex function?

Apologies for the fundamental question. But I am am just trying to understand the pieces.

Let us consider a minimization problem \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{subject to }\quad & Ax = b \ ,\\ \end{align} where $$f(x)$$ is closed and convex function, and $$A \in \mathbb{R}^{m \times n}$$, and $$b \in \mathbb{R}^m$$.

Now, if we write a dual problem \begin{align} \text{maximize}_{u \in \mathbb{R}^m} \ g(u) \equiv \text{maximize}_{u \in \mathbb{R}^m} -f^*(-A^T u) - b^T u \ , \end{align} where $$f^*$$ is a conjugate of $$f$$.

Question: How to prove that $$Ax-b \in \frac{\partial}{\partial u} g(u)$$?

ADD: I want to understand through the conjugate function (not through the Lagrangian $$L(x,u) = f(x) + u^T(Ax-b)$$, and then taking the derivative of $$L$$ w.r.t. $$u$$ yields the condition that $$Ax-b=0$$ (or one could equivalently explain through the KKT conditions).

Partial attempt:

The subgradient of $$\partial g(u)$$ can be shown as \begin{align} \frac{\partial}{\partial u} g(u) = A \ \frac{\partial}{\partial u} f^*(-A^T u) - b \ . \end{align}

Now how to proceed and prove that the equality constraint exist in the subgradient of $$g(u)$$?

EDIT: For closed and convex function $$f$$, I can say that $$x \in \frac{\partial}{\partial u} f^*(-A^T u)$$. So, $$Ax-b \in \frac{\partial}{\partial u} g(u)$$. Correct?

• It's quite obvious if you just write down the Lagrangian without using the conjugate and then take the inf over $u$. You get a $u^{T}(Ax-b)$ term, which has $Ax-b$ as a gradient. If $Ax \neq b$, then that inf is unbounded. – Brian Borchers Feb 13 at 15:59
• I agree with that if you form a Lagrangian $L(x,u) = f(x) + u^T(Ax-b)$, then the gradient w.r.t. $u$ yields $Ax-b=0$. However, I wanted to understand also using the Conjugate. – user550103 Feb 13 at 18:43