TITLE: Inequalities with matrices
QUESTION [0 upvotes]: 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$).

REPLY [2 votes]: 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.
{"set_name": "stack_exchange", "score": 0, "question_id": 207556}