"Partial" Lagrangian Dual in LP

Question

Consider the optimization problem \begin{align}\label{opt-lp}\tag{Primal} \begin{array}{cl} \underset{x \in \mathbb{R}^n}{\text{minimize}} & c^\top x \\ \text{subject to} & Ax = a \\ & Bx = b \end{array} \end{align} where $A \in \mathbb{R}^{m \times n}, a \in \mathbb{R}^m, B \in \mathbb{R}^{q \times n}, b \in \mathbb{R}^q$ are the problem data, and the problem has a nonempty feasible set.

I would like to introduce a partial Lagrange relaxation to only $Ax = a$ constrains, so that the partial Lagrange function is $$L(x, \lambda) =c^\top x + \lambda^\top ( Ax - a).$$ As this is a "partial" Lagrange relaxation, I define the Lagrange dual function as $$ g(\lambda) = \underset{x : Bx = b}\inf L(x, \lambda)$$ that is, I add the constraint of $Bx = b$ already. It is clear that $g(\lambda)$ lower bounds \eqref{opt-lp}.

I think the Lagrange dual problem becomes: \begin{align}\label{dual}\tag{Dual} \sup_\lambda \inf_{x : Bx =b} c^\top x + \lambda^\top (Ax - a). \end{align} My question is whether what I am doing here has a name and whether I can simply say strong duality holds between problems \eqref{opt-lp} and \eqref{dual} in a paper without going much in detail.

Answer 1

Based on the mentioned references, suppose the primal problem is: \begin{align} \begin{array}{cl} \underset{}{\text{minimize}} & c x \\ \text{subject to} & Ax = a \\ & Dx \leq e \\ & x \geq \text{0} \end{array} \end{align}

The idea behind Lagrangian relaxation is to relax the complicating constraints to produce an easier problem by adding this constraint into the objective function with a penalty so-called Lagrange multipliers. The Lagrangian subproblem is:

\begin{align} \begin{array}{cl} \underset{}{\text{minimize}} & cx \ + \ \lambda(b \ - \ Ax)\\ \text{subject to} & Dx \leq e \\ & x \geq \text{0} \end{array} \end{align}

Solving the Lagrangian subproblem can produce a lower bound on the optimal objective value of the primal problem. Let $Z^*$ be the optimal objective value of primal and let $Z_{LR}(\lambda)$ be the optimal objective value of The Lagrangian subproblem. Then we have the following result:

For any $\lambda \in \mathbb{R}^m$ ($m$ be the number of rows in $A$) $$Z_{LR}(\lambda) \leq Z^*$$

Since primal is a minimization problem, we want lower bounds that are as large as possible; these are the most accurate and useful bounds. Different values of $\lambda$ will give different values of $Z_{LR}(\lambda)$, and hence different bounds. We’d like to find $\lambda$ that gives the largest possible bounds. That is, we want to solve:

\begin{align} \begin{array}{cl} \underset{\lambda}{\text{maximize}} & Z_{LR}(\lambda)\\ \end{array} \end{align}

According to the primal-dual relation: $Z_{LP} \leq Z_{LR}$.

$$\begin{aligned} z_{\mathrm{LR}} &\geq \max _{\lambda}\left\{\min _{x} c x+\lambda(b-A x) \mid D x \leq e, x \geq 0\right\} \\ &=\max _{\lambda}\left\{\min _{x}(c-\lambda A) x+\lambda b \mid D x \leq e, x \geq 0\right\} \\ &=\max _{\lambda}\left\{\max _{\mu} \mu e+\lambda b \mid \mu D \leq c-\lambda A, \mu \leq 0\right\} \\ &=\max _{\lambda, \mu}\{\mu e+\lambda b \mid \mu D \leq c-\lambda A, \mu \leq 0\} \\ &=\max _{\lambda, \mu}\{\mu e+\lambda b \mid \mu D+\lambda A \leq c, \mu \leq 0\} \\ &=\min _{y}\{c y \mid A y=b, D y \leq e, y \geq 0\} \\ &=z_{\mathrm{L} P} \end{aligned}$$

where the last one is LP dual of the entire problem.

---

References:

• Fundamentals of Supply Chain Theory
• LARGE SCALE LINEAR AND INTEGER OPTIMIZATION: A UNIFIED APPROACH

Answer 2

This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.