Proving an optimal solution to an LP also is optimal for a modified one

Question

Consider the LP $\min cx $ subject to $a^i x = b_i $ $i=1,...,m$ and $x \geq0$ where $x$ is an n-vector. Let $x^*$ be an optimal solution to this LP. Let $\pi^*$ be the optimal solution to the dual. Prove that $x^*$ is also optimal to

\begin{align*} \min \; \;& (c-\pi_k^* a^k) x \\ &a^i x = b_i, i=1,...,m \\ &x \geq 0 \end{align*}

whre $\pi_k^*$ is kth component of the vector $\pi^*$

thoughts

We are given that $cx^* \leq cx $ for all $x$ feasible. By the duality theorem, we see that $\pi^* = x^*$. We need to prove that

$$ (c- \pi_k^* a^k ) x^* \leq (c- \pi_i^* a^i ) x $$

But, since $cx^* \leq cx$, then

$$ - \pi_k^* a^k x^* \leq - \pi_i^* a^i x \implies \pi_k^* a^k x^* \geq \pi_i^* a^i x$$

here I get stuck. Am I thinking about this problem correctly? or my approach leads nowhere?

is it $x>0$ or $x \ge 0$? – Siong Thye Goh Nov 06 '18 at 04:51 — Siong Thye Goh, Nov 06 '18 at 04:51
yes, it is $x \geq 0$, i just updated. – Mikey Spivak Nov 06 '18 at 11:38 — Mikey Spivak, Nov 06 '18 at 11:38

score 2 · Accepted Answer · answered Nov 06 '18 at 13:16

2

The new problem is $$\min (c^T-\pi_k^*e_k^TA)x$$

subject to $$Ax=b$$

$$x \ge 0$$

and the corresponding dual is

$$\max y^Tb$$

subject to $$y^TA \le (c^T-\pi_k^*e_k^TA)$$

At $x^*$ which is feasible in the primal, the optimal value is evaluated to be $$(c^T-\pi_k^*e_k^TA)x^*=b^T\pi^{*}-\pi_k^*e_k^Tb$$

Let's check if $y^*=\pi^*-\pi_k^*e_k$ is feasible for the new dual problem.

We have $$y^{*T}A = (\pi^*-\pi_k^*e_k)^TA \le (c^T-\pi_k^*e_k^TA),$$

$y^*$ is indeed feasible and

$$y^{*T}b = (\pi^*-\pi_k^*e_k)^Tb$$

which is equal to the primal objective value evaluated at $x^*$. Hence by strong duality, $x^*$ remains optimal.

answered Nov 06 '18 at 13:16

Siong Thye Goh

149,520
20
88
149

thanks for you reply. But, my approach is correct? Can you tell me if my attempted solution is correct? thanks – Mikey Spivak Nov 06 '18 at 13:23
Statement of duality theorem is $\pi^{T}b=c^Tx^$. Also from $a \le b$ and $c \le d$, I don't think we can conclude that $(a-c) \le (b-d)$ . – Siong Thye Goh Nov 06 '18 at 13:31
The $y$ is unrestricted right? Also, can you explain why the second inequality starting from the end is true? – Mikey Spivak Nov 06 '18 at 19:07
$y$ can take any sign. Also, since $\pi^$ is feasible in the original dual, we ahve $\pi^{T}A \le c^T$. – Siong Thye Goh Nov 07 '18 at 00:45
Why is
$$(c^T-\pi_k^e_k^TA)x^=b^T\pi^{}-\pi_k^e_k^Tb$$

true? I understand $Ax^* = b $, but how $c x^* = b \pi^* $?
– James Nov 07 '18 at 06:13
that is strong duality. – Siong Thye Goh Nov 07 '18 at 06:35
Why do you put the basis vector $e_k$? in the vector $c - \pi^*k a^k $ , isnt the $a^k = (a{k1},a_{k2},...,a_{kn})$? – James Nov 07 '18 at 07:16
It is more of a habit thing. if I see $Ax$ explicitly, I can subconsciously write down $b$ without thinking. – Siong Thye Goh Nov 07 '18 at 07:21
So, just the clarify then, the vector $c-\pi_k^a^k $ is supposed to be the n-vector for which the jth component is given by $c_j- \pi^k a{kj} $, correct? – James Nov 07 '18 at 07:22
yup, that's correct. – Siong Thye Goh Nov 07 '18 at 07:23

Proving an optimal solution to an LP also is optimal for a modified one

thoughts

1 Answers1