3
$\begingroup$

The following is my derivation in the Conjugacy relation in the primal and dual problem. I am shaky in it; so hope for some advices.

Consider the following problem, $f(x),g(x)$ are convex functions:

$p(u)=\underset{x\in \mathcal{X},\ \ g(x)\leq u}{\text{inf}}f(x),\ \ \ u\in R^r, \ \ \ f: \mathcal{X} \mapsto R$

Therefore, $p(u)$ can be viewed as the following problem:

\begin{equation} \begin{aligned} &\underset{x\in \mathcal{X}}{\text{min}} & & f(x)\\ & \text{s.t.} & & g(x) \leq u \\ \end{aligned} \end{equation}

  1. Form the dual function: \begin{align*} q_1(\mu) &= \underset{x}{\text{inf}}\{f(x)+\mu^T(g-u)\}\\ &= \underset{x}{\text{inf}}\{f(x)+\mu^Tg\}-\mu^Tu \\ &= q(\mu)-\mu^Tu\end{align*} Here $\ \ \ q(\mu)=\underset{x}{\text{inf}}\{f(x)+\mu^Tg\}$.

  2. Form the conjugate function:
    \begin{align*} p(u) &= \underset{\mu \geq 0}{\text{sup}}\{q(\mu)-\mu^Tu\}\\ &= \underset{\mu \geq 0}{\text{sup}}\{(-u)^T\mu-(-q(\mu))\} \\ &= -q^*(-u)\end{align*}

The result shows a relation of the primal function $p$ and the dual function $q$, which is conjugacy relation.

My problem is:

  1. The original problem is that we have to find the optimal value over $x$ given $u$. This type problem is a little bit difficult for me since there is another variable $u$, not just $x$. Does my whole derivation make sense?

  2. Is the way to form the conjugate function in the second step correct? I mean the change of sign.

Hope I can learn more from this problem.

$\endgroup$

1 Answer 1

3
$\begingroup$

It's good you're learning Fenchel-Rockefellar duality by doing-it-yourself.

Question: Does my whole derivation make sense ? Answer: Yes!

Qestion: Is the way to form the conjugate function in the second step correct? Answer: Almost there...

Indeed, let me recover your results from first principles (without assuming any knowledge of the concept of "dual", etc.). However, recall the notions of indicator functions of convex sets, and convex conjugates (aka Fenchel-Legendre transform) of convex functions. Now, observe that \begin{eqnarray} \underset{\mu \ge 0}{\text{sup }}\mu^T(g(x) - u) = \begin{cases}0, &\mbox{ if }g(x) \le u,\\+\infty, &\mbox{ otherwise.}\end{cases} \end{eqnarray} Thus \begin{eqnarray} \begin{split} p(u) := \underset{x:g(x) \le u}{\text{inf }}f(x) &= \underset{\mu \ge 0}{\text{inf }}f(x) + \underset{\mu \ge 0}{\text{sup }}\mu^T(g(x) - u)\\ &= \underset{\mu \ge 0}{\text{sup }}\underbrace{\underset{x}{\text{inf }}f(x) + \mu^Tg(x)}_{q(u)} - \mu^Tu\\ &= \underset{\mu \ge 0}{\text{sup }}q(\mu) - \mu^Tu\\ &=\underset{\mu}{\text{sup }}\mu^T(-u) - \underbrace{(i_{\mathbb{R}_+^r} - q)}_{\tilde{q}}(\mu) =: \tilde{q}^*(-u), \end{split} \end{eqnarray} which is your result, except that you implicitly assumed $-q$ was supported (in the convex sense) on the nonnegative orthant $\mathbb{R}_+^r$.

Bonus: Depending on the nature of $f$ and $g$, it might be conceptually easier to optimize $\tilde{q}^*$ than $p$.

$\endgroup$
2
  • $\begingroup$ I cannot get the idea of the last step, i.e., $(i-q)(\mu)$. What happen there? $\endgroup$ Commented Aug 17, 2015 at 10:11
  • 1
    $\begingroup$ Principle: "$\text{sup }r(x)\text{ subject to }x \in C$" is equivalent to "$\text{sup }r(x) - i_C(x)$" and "$\text{inf }r(x)\text{ subject to }x \in C$" is equivalent to "$\text{inf }r(x) + i_C(x)$", where $i_C$ is the indicator function of $C$. $\endgroup$
    – dohmatob
    Commented Aug 17, 2015 at 13:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .