Equality constraints with $x \geq 0$ – What algorithm

linear programmingmaxima-minimaoptimization

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.

Best Answer

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$.

Related Question