1
$\begingroup$

Following are some corollaries regarding the weak duality theorem.

  1. Consider a constrained problem, $\min_{x \in X} f(x),$ subject to $g(x) \leq 0$ and $h(x) =0$.

    Its dual problem is $\sup_{u \geq 0, v} \theta(u,v)$, where the dual Lagrangian function is defined as $\theta(u,v):= \inf_{x \in X} \, f(x) + u^T g(x) + v^T h(x)$.

    In Bazarra's Nonlinear Programming, on P264:

    Corollary 3 If $\inf \{ f(x): x \in X, g(x) \leq 0, h(x) = 0 \} = -\infty$, then the Lagrangian dual function $\theta(u, v) = -\infty$ for each $u \geq 0$.

    Corollary 4 If $\sup \{\theta(u, v): u \geq 0\} = \infty$, then the primal problem has no feasible solution.

  2. For a linear programming problem, $\min_{x \geq 0} c^T x$ subject to $Ax=b$, its dual problem is $\max_{p} p^Tb$ subject to $p^T A \leq c^T$. In Bertskas's Introduction to Linear Optimization, on P147:

    Corollary 4.1

    (a) If the optimal cost in the primal is $-\infty$, then the dual problem must be infeasible.

    (b) If the optimal cost in the dual is $\infty$, then the primal problem must be infeasible.

My questions:

  1. In Corollary 4 in Bazarra's and Corollary 4.1 in Bertsekas', why when one problem's optimal cost is unbounded, the other one is infeasible, i.e. has empty feasible set, instead of also having the same unbounded optimal cost?
  2. Does Corollary 3 in Bazarra's book say that if the optimal cost in primal problem is $-\infty$, then the optimal cost in the dual must also be $-\infty$?
  3. In the linear programming case, is Corollary 3 in Bazarra's book not consistent with Corollary 4.1(a) in Bertsekas' book, in that the former implies that when the optimal cost in the primal is $-\infty$, then the dual problem has a non-empty feasible set (and has $-\infty$ optimal cost)?

Thanks! Also feel free to suggest to improve this post, e.g., to make it concise and clear.

  • 0
    @PEV: I think so. On Bertsekas's p 146, the first sentence on the same section it says the section is talking about the standard form of the primal problem, which is a minimization problem as written in p141 and p145 example 4.3.2011-04-02

1 Answers 1

1

From Theorem 2.7.3(b) of Bazarra, the following holds: $P$ is unbounded $\implies$ $D$ is infeasible and $D$ is unbounded $\implies$ $P$ is infeasible.

From Corollary 1 on page 85 we have: $D$ is infeasible $\implies$ $P$ is unbounded or infeasible and $P$ infeasible $\implies$ $D$ is unbounded or infeasible.

  • 0
    Thanks! I was wondering if, in Bazaraa's, Corollary 3 on p264 and Theorem 2.7.3(b) are contrary to each other? How to understand the former? Thanks!2011-04-03