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
    $\begingroup$ Given the presence of the term $s_{\kappa}\exp\left(\frac{{s_{\kappa}}^2}{2}\right)$, you'd likely need something like the $W$-Lambert function, or, more likely, you won't have a closed form expression for $s_{\kappa}$. As an alternative to obtaining an explicit dual objective, you could just form the Wolfe Dual. $\endgroup$ – nathan.j.mcdougall Jan 15 at 0:49
  • $\begingroup$ An alternative to that term is to introduce a constraint of the form $$ s^2_\kappa \leq \alpha, \ \forall \kappa$$ and then the $\eta_\kappa$ term becomes $\eta_\kappa r_\kappa \exp(r_\kappa s_\kappa)$. The problem here is then that there would be a new lagrange multiplier $\mu_\kappa$ associated with each of these constraints. Would something like this be more ameanable? $\endgroup$ – NeedsToKnowMoreMaths Jan 15 at 1:53
  • $\begingroup$ I'm afraid I don't really follow you. If you introduce those constraints into the primal, you now need to solve $$\frac{1}{2}\eta_{\kappa}\left[r_{\kappa}\exp(r_{\kappa}s_{\kappa})+s_{\kappa}\exp\left(\frac{{s_{\kappa}}^2}{2}\right)\right]+\frac{1}{2}\lambda\exp\left(\frac{s_{\kappa}}{2}\right)+2s_{\kappa}\mu_{\kappa}=0$$ for $s_{\kappa}$ in terms of both $\lambda$ and $\mu_{\kappa}$, which seems more difficult rather than easier. I don't see how the $\eta_{\kappa}$ term changes. $\endgroup$ – nathan.j.mcdougall Jan 15 at 2:11
  • $\begingroup$ Sorry, I meant that I could change the objective to $$\min \sum_\kappa \eta_\kappa \exp(r_\kappa s_\kappa)$$ by adding in the additional constraints. The $s^2_\kappa$ term came from trying to regularize to avoid the need for the constraints. $\endgroup$ – NeedsToKnowMoreMaths Jan 15 at 15:05

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.


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.