Solve Matrix Inequality Ax ≤ b, nxn A with Solution Exists

[muzak]

Homework Statement

Ax ≤ b, assuming A is nxn and solution exists

Homework Equations

The Attempt at a Solution

I don't know of any concrete methods offhand. A grad student suggested rearranging it to:
Ax - b ≤ 0, zero vector

Then I don't know where to go from here. I was thinking of multiplying by x^{T} to get x^{T}Ax - x^{T}b ≤ 0 , 0 a scalar now. Is this a valid method? If not, I wouldn't mind any direction to theorems that say otherwise. Then I was thinking of solving for the null space of A and finding some other method to make x^{T}b ≥ 0 (would also like some literature or reference to methods involving this operation).

aye or nay, if nay, can someone suggest the general accepted methods and perhaps the name of what this kind of problem is. Thanks in advance.

 

[Ray Vickson]

Homework Statement

Ax ≤ b, assuming A is nxn and solution exists

Homework Equations

The Attempt at a Solution

I don't know of any concrete methods offhand. A grad student suggested rearranging it to:
Ax - b ≤ 0, zero vector

Then I don't know where to go from here. I was thinking of multiplying by x^{T} to get x^{T}Ax - x^{T}b ≤ 0 , 0 a scalar now. Is this a valid method? If not, I wouldn't mind any direction to theorems that say otherwise. Then I was thinking of solving for the null space of A and finding some other method to make x^{T}b ≥ 0 (would also like some literature or reference to methods involving this operation).

aye or nay, if nay, can someone suggest the general accepted methods and perhaps the name of what this kind of problem is. Thanks in advance.

This is a standard linear inequality question. Typically we first convert to an equality by adding *slack* variables: if s_1, s_2,...,s_n are slack variables, we require s_1 ≥ 0, s_2 ≥ 0, ..., s_n ≥ 0, and we can write BX = 0, where B = [A,I] (I = nxn identity matrix) and X = [x_1, x_2, ..., x_n, s_1, s_2, ...,s_n}^T. Now we need to look for feasible basic solutions; these are obtained by selecting n linearly-independent columns of the matrix B (called basic columns), and solving for the corresponding basic variables in terms of the non-basic variables, then setting the non-basic variables to zero. If all of the basic solutions are infeasible (that is, have at least one s_i < 0) the original problem is infeasible; otherwise, there exists at least one basic solution that is feasible (and maybe many such points). All of this is part of the subject of Linear Programming.

RGV