1
$\begingroup$

I'm trying to learn about Lagrangian relaxation from Korte and Vygen (2018) and found a case where I don't know how to proceed. When optimizing $\max \{c^\top x : A'x \le b', x \in Q\}$ the book defines $LR(\lambda) := \max \{c^\top x + \lambda^\top (b' - A'x) : x \in Q\}$ and uses subgradient optimization to minimize $LR(\lambda)$.

The first step of subgradient optimization is to find an optimal solution for $LR(\lambda^{(0)})$ for any initial multiplier $\lambda^{(0)} \ge 0$. I don't know how to proceed if $LR(\lambda^{(0)})$ is unbounded. The same situation can occur later on after the multipliers are updated. Is there any general method of how to deal with this? Or is the algorithm just incomplete in these cases?

Example: Consider the problem $\max\{-x_1 : 1 \le x_2, x_1 \ge x_2\}$ where we relax $x_1 \ge x_2$. Then $LR(\lambda) := \max \{-x_1 + \lambda (x_1 - x_2) : 1 \le x_2\}$. Staring with $\lambda^{(0)} := 3$ gives us $LR(3) = \max \{2x_1 - 3x_2 : 1 \le x_2\}$ which is unbounded. Likewise, if we start with $\lambda^{(0)} := 0.5$, we get an optimal solution of $(0, 1)$, a subgradient of $g=-1$, and with a step size of $t:=2.5$ the next multiplier would be $\lambda^{(1)} = \lambda^{(0)} - tg = 3$ with the same problem.

$\endgroup$
1
$\begingroup$

This is quite common in Lagrangian duality. When the subproblem can be unbounded, it means that there are implicit restrictions on the dual variables. In practice, we usually work to make these dual constraints explicit and then solve the dual problem with the explicit constraints.

In your simple example, the $LR(\lambda)$ subproblem will be unbounded whenever $\lambda > 1$. Thus you need to include the implied constraint $\lambda \leq 1$ in your dual problem and only consider Lagrange multipliers $\lambda$ that are less than or equal to 1.

In the more general problem considered in your textbook, $LR(\lambda)$ will be unbounded unless $A^{T}\lambda=c$. Thus the dual problem will include the linear equality constraints $A^{T}\lambda=c$.

There is a good discussion of this issue (with somewhat different notation and min/max reversed) in the (freely available pdf) textbook

Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2005.

$\endgroup$
  • $\begingroup$ Thanks for the reference, it helped to clear things up a little. I'm still not sure how to handle this case in the subgradient descent algorithm. With the additional constraints $LR(3)$ is infeasible instead of unbounded and there is still no way to get a subgradient from it. I can ask this as a separate question, though. $\endgroup$ – Flogo Aug 10 '18 at 9:35
  • $\begingroup$ I posted my follow-up question here: math.stackexchange.com/questions/2878195/… If you have another pointer for that it would be greatly appreciated. $\endgroup$ – Flogo Aug 10 '18 at 10:02
  • $\begingroup$ Some notes on Lagrangian duality in integer programming that you might find helpful at people.brunel.ac.uk/~mastjjb/jeb/natcor_ip_rest.pdf $\endgroup$ – Brian Borchers Aug 10 '18 at 14:40
  • $\begingroup$ Projected (sub) gradient (descent or ascent) methods can be used to solve the Lagrangian dual if you can reasonably compute a projection onto the convex feasible set. $\endgroup$ – Brian Borchers Aug 10 '18 at 14:59

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.