in introduction to linear optimization ($\text{p. 142}$), they take the standard form problem:

minimize $c'x$, s.t. $Ax = b$, $x\geq 0$

they relax the constraints and define:

$g(p) = \min_{x\geq 0}[c'x + p'(b-Ax)] = p'b + \min_{x\geq 0}[(c - p'A)x]$

and then they try to maximize it, with respect to p.

now they note that when $c-p'A<0$ then $\min_{x\geq 0}[(c - p'A)x]=-\infty$, so to refrain from these p values they phrase the dual problem as:

maximize $p'b$, s.t. $p'A\leq c'$

my question: why is it necessary to put the constraints? why do we care that $\min_{x\geq 0}[(c - p'A)x] = -\infty$ for some values of p? why can't we just maximize $p'b$, and obviously we won't get the maximum for these $-\infty$ p values?

  • $\begingroup$ So you’re proposing that the dual problem is just $\max\ p’b$ with no constraints? $\endgroup$
    – David M.
    Feb 2, 2019 at 18:56
  • $\begingroup$ @david - yes. I know that this is wrong, but I don't understand why $\endgroup$
    – ihadanny
    Feb 2, 2019 at 22:26
  • 1
    $\begingroup$ The dual function is not the linear function $g(p)=p’b$, it’s $g(p)=\begin{cases}p’b,&p’A\leq{c},\\-\infty,&\text{else}.\end{cases}$. Easier to optimize the linear function over a polyhedron, than to optimize the non-linear function over all of $\mathbb{R}^m$. $\endgroup$
    – David M.
    Feb 3, 2019 at 15:30

1 Answer 1


It is not necessary to formulate them as constraints, you can just write the dual problem as: $\max_p p'b + \min_{x\geq 0}[(c - p'A)x]$.

However, solving a nested problem is difficult. The maximum cannot occur when $A^T p > c$, so you can restrict your search for a maximizer to the set where $A^T p \leq c$. If you define $S = \{ p : A^T p \leq c \}$ you seem to propose solving $\max_{p \in S} p'b$. That is a correct statement of the dual problem.

We still prefer the equivalent formulation $\max_{p \in \mathbb{R}^m} \{ p'b : A^Tp\leq c\}$, since it is a linear optimization problem.

  • $\begingroup$ thanks, but I'm missing the point: you're just showing an alternative formulation for the same problem. I'm asking why is it necessary to restrict the search to the set $S$, why can't we just search all over, and take for granted that the maximum won't be outside of S. $\endgroup$
    – ihadanny
    Feb 3, 2019 at 9:59
  • $\begingroup$ @ihadanny it is not necessary at all, like I say in my first sentence you can write the dual problem as one that still has $\min_{x\geq 0}$. $\endgroup$
    – LinAlg
    Feb 3, 2019 at 13:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .