# Conjugacy relation in the primal and dual problem

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{aligned} &\underset{x\in \mathcal{X}}{\text{min}} & & f(x)\\ & \text{s.t.} & & g(x) \leq u \\ \end{aligned}

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.

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$.
• I cannot get the idea of the last step, i.e., $(i-q)(\mu)$. What happen there? Commented Aug 17, 2015 at 10:11
• 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$. Commented Aug 17, 2015 at 13:47