multiplication of nonzero scalar in a constraint of the primal

Question

Suppose we have primal and its dual in standard form, that is

\begin{align*} (P) \max z = cx \\ st \; \; Ax = b \\ \; \; \; x \geq 0 \\ \end{align*}

\begin{align*} (D) \min z = by \\ st \; \; yA \geq c \\ \; \; \; y \; \; \; free \\ \end{align*}

Where $A$ is an $m $ by $n$ matrix an $x$ is an n vector and $y$ is an m vector.

Suppose we multiply one of the constraints of the primal by some number $\alpha > 0$. Does this affect the solution of the dual?

Thoughts:

Since a constraint is of the form $a_{ij} \cdot x $, take one of the $i's$, say we multiply

$$ a_{i1}x_1 + a_{i2} x_2 + ... + a_{in} x_n $$

by $\alpha $

Once we set up our tableau, once we divide this row by $\alpha$, then in the LFH, we would have

$$ \frac{ b_i}{\alpha} $$

the ith component of the vector $b$. Doesnt it change the solution in the primal tableau? Since solutions are the same for primal and dual???

score 2 · Accepted Answer · answered Nov 02 '18 at 07:33

2

Multiplication by a non-zero scalar is equivalent to multiplication of an elementary matrix, $E$.

\begin{align*} (P') \max z = c^Tx \\ st \; \; (EA)x = (Eb) \\ \; \; \; x \geq 0 \\ \end{align*}

The dual is \begin{align*} (D') \min z = (Eb)^Ty \\ st \; \; y^T(EA) \geq c \\ \; \; \; y \; \; \; free \\ \end{align*}

Suppose $w$ is the original dual solution, then $y=E^{-T}w.$

For the operation of multiplication by a scalar, we have $E^T=E$.

Hence $y=E^{-1}w$. That is if we multiply $\alpha$ to the $i$-th constraint, now for the dual solution, we would divide $w_i$ by $\alpha$ and we can keep the rest to be the same.

answered Nov 02 '18 at 07:33

Siong Thye Goh

149,520
20
88
149

Can you help me with this related problem: https://math.stackexchange.com/questions/2989440/changes-in-the-primal-and-dual-that-modify-the-solutions?noredirect=1#comment6169741_2989440 – Mikey Spivak Nov 08 '18 at 15:11
at first glance, it seems that doing that operation might cause the primal problem to become infeasible. – Siong Thye Goh Nov 08 '18 at 15:24
But isnt it doing the same operations as the previous case but this time to the dual? – Mikey Spivak Nov 08 '18 at 18:06
the duality is in inequality form, multiplying an inequality and adding it to another one might change the feasible set. Also, if you multiply by a negative number, the inequality get flipped. – Siong Thye Goh Nov 08 '18 at 18:09
You are right :/ – Mikey Spivak Nov 08 '18 at 18:23
Sorry for asking too much, but how would you conclude so fast that the new problem must be infeasible ?? – Mikey Spivak Nov 08 '18 at 18:33
I wouldn't say it must be infeasible, but there are such cases. We can see that $b$ is in the cone generated by columns of $A$ for the original problem. We are changing the problem without changing $b$, and $b$ need not reside in the cone in the new columns. – Siong Thye Goh Nov 08 '18 at 18:38
but, the primal solutions stays the same unchanged because it is standard form. So, the only problem is in the dual – Mikey Spivak Nov 08 '18 at 20:19
Let us continue this discussion in chat. – Siong Thye Goh Nov 09 '18 at 01:41

multiplication of nonzero scalar in a constraint of the primal

Thoughts:

1 Answers1

Linked