1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Feb 13 at 15:59
  • $\begingroup$ 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. $\endgroup$ – user550103 Feb 13 at 18:43

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.