# Fenchel Duality in Prof. Bertsekas' lecture

For convenience, the relevant part is shown as:

I am confused in two things:

1. The conjugacy relation between the primal function $p$ and the dual function $q$.

2. How to derive (1.47)

Note: $Q(\mu) = \underset{u\in R^r}{u^T\mu - P(u)} = P^*(\mu)$

My work:

1. The derivation is in this link. It seems we cannot say $p(u)=q^*(u)$
2. To (1.47), my derivation is:

a. The left-hand side of (1.47) can be written as (Fenchel duality framework)

\begin{aligned} &{\text{min}} & & p(u)+P(Iu)\\ & \text{s.t.} & & u \in R^r \\ \end{aligned} b. It is equivalent to
\begin{aligned} &{\text{min}} & & p(u_1)+P(u_2)\\ & \text{s.t.} & & u_1, u_2 \in R^r \\ & & & u_2=Iu_1 \\ \end{aligned} c. Form the dual function:
\begin{align*} &\ \ \ \ \underset{u_1,u_2}{\text{inf}}\{p(u_1)+P(u_2)+\mu^T(u_2-u_1)\}\\ &= \underset{u_1}{\text{inf}}\{p(u_1)-\mu^T u_1\} + \underset{u_2}{\text{inf}}\{P(u_2)+\mu^T u_2\}\\ &= -\underset{u_1}{\text{sup}}\{\mu^T u_1-p(u_1)\} - \underset{u_2}{\text{inf}}\{(-\mu)^T u_2 - P(u_2)\} \\ &= -p^*(\mu) - P^*(-\mu)\end{align*}
d. Form the dual problem:
\begin{align*} & \underset{\mu}{\text{sup}} \{-p^*(\mu) - P^*(-\mu)\} \end{align*}

I do not know the following steps to obtain the right-hand side of (1.47).

• This question is a disguissed version of at least two other questions here on SE, one of which is math.stackexchange.com/a/1399049/168758 ;) It'd be nice if you could stick to one thread. Commented Aug 19, 2015 at 7:30