0
$\begingroup$

For a linear system of equations constrained by inequalities, is $ Ax \le b => y^TAx \le y^Tb $ acceptable? Or does that not generally hold.

($ y^T $ being the transpose of $y$).

  • 0
    Sorry, I meant 'implies'. Edited.2012-10-05

1 Answers 1

2

Assuming that $\mathbf x$ and $\mathbf y$ are column vectors, and that the entries of $\mathbf y$ are non-negative, then yes, $A\mathbf x \leq b$ implies $\mathbf y^TA\mathbf x \leq \mathbf y^Tb$.

This amounts to taking a linear combination of inequalities where the weights are non-negative. Incidentally, this can be used to prove the "Weak Duality Theorem", i.e., that the value of the objective function of a maximization problem is bounded above by the value of the corresponding objective function of the dual minimization problem.