# Unbounded Values in Lagrangian Relaxation

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.

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$.
• 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. – Flogo Aug 10 '18 at 9:35