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.
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.