Equality constraints with $x \geq 0$ - What algorithm?

Question

Consider a linear problem

$$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & A x = b\\ & x \in \mathbb{R}^n {\geq 0}\end{array}$$

If the subject was $Ax \geq b $, I could use Dual Simplex method to minimize this. But this time it's a equality constrained problem.

What algorithm do you think I can use to minimize this?

Can I use ordinary least squares here? I mean if I solve the constraints like this:

$$ x = (A^TA)^{-1}A^Tb $$ And $x \geq 0$, then it exist a solution, else not? And if their is a solution, it going to be only optimal solution for the objective function? Right?

Practical problem:

Assume that we want to minimize

$$\begin{array}{ll} \text{minimize} & \frac{1}{2}x^\top Q x + c^\top x\\ \text{subject to} & A x \leq b\\ & x \in \mathbb{R}^n {\geq 0}\end{array}$$

Yes, I know that is a quadratic problem. But we are going to solve it as it was a linear problem.

First we take an example:

$$Q = \begin{bmatrix} 2 &0 \\ 0 & 8 \end{bmatrix} $$ $$ c^T = \begin{bmatrix} -8\\ -16 \end{bmatrix} $$ $$ A = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} $$

$$ b = \begin{bmatrix} 5\\ 3 \end{bmatrix} $$

We use KKT conditions and now we have this linear programming problem instead.

$$A = \begin{bmatrix} 2x_1 & 0x_2 & 1u_1 & 1u_2 & -1y_1 & 0y_2 & 0v_1 & 0v_2 & 1a_1 & 0a_2 & 0a_3 & 0a_4 \\ 0x_1 & 8x_2 & 1u_1 & 0u_2 & 0y_1 & -1y_2 & 0v_1 & 0v_2 & 0a_1 & 1a_2 & 0a_3 & 0a_4 \\ 1x_1 & 1x_2 & 0u_1 & 0u_2 & 0y_1 & 0y_2 & 1v_1 & 0v_2 & 0a_1 & 0a_2 & 1a_3 & 0a_4 \\ 1x_1 & 0x_2 & 0u_1 & 0u_2 & 0y_1 & 0y_2 & 0v_1 & 1v_2 & 0a_1 & 0a_2 & 0a_3 & 1a_4 \end{bmatrix}$$

$$b = \begin{bmatrix} 8\\ 16\\ 5\\ 3 \end{bmatrix} $$

And our objective function:

$$c^Tx = 0x_1 + 0x_2 + 0u_1 + 0u_2 + 0y_1 + 0y_2 + 0v_1 + 0v_2 + a_1 + a_2 + a_3 + a_4$$

Now we want to minimize

$$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & A x = b\\ & x \in \mathbb{R}^n {\geq 0}\end{array}$$

One problem is that there are more columns than rows in $A$ matrix. And this cannot be solved...i think.

Answer 1

Dual simplex can directly handle equality constraints.

Regarding least squares, if there is a feasible solution to $Ax=b$, least squares would find one, but it will not necessarily be $\ge 0$. Also, if there are multiple feasible solutions (which is typically the case in linear programming), the least-squares solution will not necessarily minimize your linear objective function $c^T x$.

Answer 2

The single equality constraint $Ax=b$ is equivalent to two inequality constraints, $$ Ax\ge b $$ and $$ -b \le -Ax $$ and you can then use whatever LP algorithm you want.