Formulating the dual of an exponential cone optimization problem

566 Views Asked by At

I have an optimization problem that is written \begin{align} \min_{\{s_\kappa\} }& \frac{1}{2}\sum_{\kappa} \eta_\kappa \left( \exp(r_\kappa s_\kappa) + \exp\left( \frac{s^2_\kappa}{2} \right) \right) \\ \text{s.t.} & \sum_{\kappa} \exp\left( \frac{s_\kappa}{2} \right) \leq C \end{align} where $r_\kappa < 0$, $C> 0$ and $\{ s_\kappa\}$ is a finite set of decision variables.

I believe then that the Lagrangian is given by \begin{align} \mathcal{L}(s_\kappa,\lambda) = \frac{1}{2}\sum_{\kappa} \eta_\kappa \left( \exp(r_\kappa s_\kappa) + \exp\left( \frac{s^2_\kappa}{2} \right) \right) + \lambda\left( \sum_{\kappa} exp\left( \frac{s_\kappa}{2} \right) - C\right) \end{align} and the KKT conditions then give $\lambda \geq 0$ (dual feasibility), $0 = \lambda \left( \sum_{\kappa} exp\left( \frac{s_\kappa}{2} \right) - C \right)$ (complimentary slackness), and \begin{align} 0 &= \frac{1}{2} \eta_\kappa \left( r_\kappa \exp(r_\kappa s_\kappa) + s_\kappa \exp\left(\frac{s^2_\kappa}{2}\right) \right) + \frac{\lambda \exp(\frac{s_\kappa}{2})}{2},\ \forall \kappa \end{align}

I would like to write the dual problem for this, which should be $g(\lambda) = \inf_{\{s_\kappa\} } \mathcal{L}(s_\kappa,\lambda)$. I would like to this because I have from other sources some properties on $\lambda$ which I would like to translate into properties on the optimal objective.

My problem is that though I can write $\lambda$ in terms of $s_\kappa$ for a given $s_\kappa$ \begin{align} \lambda = - \eta_\kappa \left( r_\kappa \exp(r_\kappa s_\kappa) + s_\kappa \exp\left( \frac{s^2_\kappa}{2} \right) \right) \end{align} I am struggling to write $s_\kappa$ in terms of $\lambda$ in order to substitute back into the Lagrangian to get the dual objective function. Any suggestions?

1

There are 1 best solutions below

0
On

After making the modifications you've allowed in the comments, the optimization problem becomes

$$\begin{align*} \min_{\{s_{\kappa}\}}\quad&\sum_{\kappa}\eta_{\kappa}\exp(r_{\kappa}s_{\kappa})\\ \text{s.t.}\quad&\sum_{\kappa}\exp\left(\frac{1}{2}s_{\kappa}\right)\leq C\\ &s_{\kappa}^2\leq \alpha. \end{align*}$$ We can make the transformation $x_{\kappa}=\exp(\frac{1}{2}s_{\kappa})$ to render this more linear. Especially, we can change the $s_{\kappa}^2\leq \alpha$ constriants into pairs of linear constraints $x_{\kappa}\leq \exp(\sqrt{\alpha})$, and $x_{\kappa}\geq \exp(-\sqrt{\alpha})$. This gives a new problem $$\begin{align*} \min_{\{x_{\kappa}\}}\quad&\sum_{\kappa}\eta_{\kappa}(x_{\kappa})^{2r_{\kappa}}\\ \text{s.t.}\quad&\sum_{\kappa}x_{\kappa}\leq C\\ &x_{\kappa}\leq \exp(\sqrt{\alpha})\\ &x_{\kappa}\geq \exp(-\sqrt{\alpha})\\ \end{align*}$$

The KKT stationary-point constraint for the transformed problem is given by $$2\eta_{\kappa}r_{\kappa}(x_{\kappa})^{2r_{\kappa}-1}+\lambda+\mu_{\kappa}-\nu_{\kappa}=0.$$

Then, it is a simple rearrangement for $x_{\kappa}$ to give $$x_{\kappa}^*=\left[\frac{\lambda+\mu_{\kappa}-\nu_{\kappa}}{2\eta_{\kappa}(-r_{\kappa})}\right]^{\frac{1}{2r_{\kappa}-1}}.$$

The Lagrangian for the transformed problem is then $$\mathcal{L}(x_{\kappa},\lambda,\mu,\nu)=\sum_{\kappa}\eta_{\kappa}(x_{\kappa})^{2r_{\kappa}}+\lambda\left[\sum_{\kappa}x_{\kappa}-C\right]+\sum_{\kappa}\mu_{k}[x_{\kappa}-\exp(\sqrt{\alpha})]-\sum_{\kappa}\nu_{k}[x_{\kappa}-\exp(-\sqrt{\alpha})].$$

I will leave the cumbersome exercise of substituing $x_{\kappa}^*$ into the Lagrangian, but hopefully this approach will help you progress.