2
$\begingroup$

In Example 5.5 of the book Convex Optimization, the authors derived the dual problem for the optimization problem

$$ \begin{aligned} & \text{min} && \log \sum_i^m \exp y_i\\ & \text{s.t.} && Ax + b = y \end{aligned} $$

where $A \in \mathbb R^{m \times n}, x \in \mathbb R^n, b, y \in \mathbb R^m$, using the conjugate function of log-sum-exp. (The derivation can be found here at page 268)

My question is, is it possible for us to derive the dual problem without using the conjugate function?

The following is my current attempt:

The Lagrangian is

$$L(x, y, v) = \log \sum_i^m \exp y_i + v^T(Ax + b - y)$$

where $v \in \mathbb R^m$ is the Lagrange multiplier.

$$\frac{\partial L}{\partial x} = A^Tv = 0$$

$$\frac{\partial L}{\partial y} = \frac{1}{\sum_i^m \exp y_i} \left(\begin{array}{c} \exp y_1 \\ \exp y_2 \\ . \\ . \\ . \\ \exp y_m \end{array}\right) - v = 0$$

So we have

$$A^T v = 0$$

$$\frac{\exp y_i}{\sum_j^m \exp y_j} = v_i \ \ \forall i$$

I've also noticed that the second equation implies that $\textbf 1^T v = 1$ and $v \succeq 0$.

Here's where I get stuck. I don't know how to continue to express the dual function.

$\endgroup$
  • $\begingroup$ So far, you've found a bunch of implicit constraints on the dual variables (the inf of L(x,y,v) will be unbounded unless $1^{T}v=1$, $v\geq 0$, and $A^{T}v=0$. These will end up as dual constraints. Assuming they're satisfied, what is the inf? $\endgroup$ – Brian Borchers Nov 16 '17 at 17:25
  • $\begingroup$ @BrianBorchers yes I realized that these constraints are dual constraints, but I don’t know how to express the $\inf$ because I can’t solve for $y$ :(. Mind giving me more hint? $\endgroup$ – hklel Nov 16 '17 at 17:47
  • $\begingroup$ The hint here is that you don't have to solve for $y$. Rather, you need to find the value of $-v^{T}y+v^{T}b+\log(\sum e^{y_{i}})$ in terms of $v$ at a value of $y$ that satisfies the constraints. $\endgroup$ – Brian Borchers Nov 16 '17 at 18:55
  • 2
    $\begingroup$ Here's the thing: you say you're not using the conjugate function, but in fact you're effectively doing the same computations you would use to derive the conjugate. $\endgroup$ – Michael Grant Nov 16 '17 at 19:16
0
$\begingroup$

Thanks to the hints and guidance given by @BrianBorchers and @MichaelGrant, I've figured out the answer. I am posting it here so it might help others.

From

$$\frac{\exp y_i}{\sum_j^m \exp y_j} = v_i \ \ \forall i$$

we can easily express $y_i$ as

$$y_i = \log v_i \sum_j^m \exp y_j$$

Substitute this and $A^Tv = 0$ into the Lagrangian, we have

$$\begin{aligned} && L(y, v) &= \log\sum_i^m \exp y_i + b^Tv - \sum_i^mv_i( \log v_i \sum_j^m \exp y_j)\\ &&& = \log\sum_i^m \exp y_i + b^Tv - \sum_i^mv_i( \log v_i + \log\sum_j^m \exp y_j)\\ &&& = \log\sum_i^m \exp y_i + b^Tv - \sum_i^mv_i \log v_i - \log\sum_j^m \exp y_j\sum_i^m v_i\\ && & = b^Tv- \sum_i^mv_i\log v_i \\ &&& = g(v) \end{aligned}$$

With the dual function in place we can proceed to write out the dual problem:

$$\begin{aligned} & \text{max} && b^Tv - \sum_i^m v_i \log v_i\\ & \text{s.t.} && A^Tv = 0\\ &&& \textbf 1^Tv = 1\\ &&& v \succeq 0 \end{aligned}$$

As @MichaelGrant pointed out, the steps above are effectively deriving the conjugate function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.