What does the objective of the primal tell us about the dual?

Question

So lets say the primal of the problem is written like this:

$$\max \sum^n_{j=1}c_jx_j$$ $$\text{subject to } \sum^n_{j=1}a_{ij}x_j\le b_i\qquad i=1,2,\ldots,m$$

$$\qquad x_j\ge 0\qquad j=1,2,\ldots,n$$

If the objective function (c) is negative, what does that mean for the dual?

$\begingroup$ can you show us your attempt? $\endgroup$
– Siong Thye Goh
Oct 23, 2022 at 16:30 — Siong Thye Goh, Oct 23, 2022 at 16:30

RobPratt · Accepted Answer · 2022-10-23 16:56:42Z

1

The dual constraints are $\sum_i a_{ij} y_i \ge c_j,$ so $c_j < 0$ implies that the constant zero solution $y\equiv 0$ is dual feasible.

answered Oct 23, 2022 at 16:56

RobPratt

39.9k3 gold badges19 silver badges50 bronze badges

$\begingroup$ So the dual will always be feasible? Can it no be unbounded? Or does feasible include unboundedness? $\endgroup$
– PufferFish46
Oct 23, 2022 at 18:18
$\begingroup$ In general, feasible includes the possibility of unboundedness, $\endgroup$
– RobPratt
Oct 23, 2022 at 18:22
$\begingroup$ Ohh, I see! But I still find it a bit weird that the dual is always feasible. What if the primal has negative entries in the objective function, put the constraints make it unbounded, wont the dual be infeasible then? $\endgroup$
– PufferFish46
Oct 23, 2022 at 18:29
$\begingroup$ $\sum_i a_{ij} \cdot 0 = 0 \ge c_{ij}$, so $0$ is dual feasible. The primal cannot be unbounded here because the primal objective function to be maximized is $\sum_j c_j x_j \le 0$ since $c_j < 0$ and $x_{ij} \ge 0$. $\endgroup$
– RobPratt
Oct 23, 2022 at 18:35
1

$\begingroup$ I meant $x_j \ge 0$. $\endgroup$
– RobPratt
Oct 23, 2022 at 18:41

| Show 3 more comments

1 Answer 1