Least Squares with Inequality Constraints

Question

I want to use Least Squares to minimize $Ax-b$ (overdetermined system), subject to $x_1+x_2+x_3=1$ and $\forall x_i, 0 \leq x_i \leq 1$. As per my understanding, I need to set up the Lagrange function and then check KKT conditions. How do I set up this problem in matrix notation and what would KKT conditions be in this case? My linear algebra is rudimentary and I can set this problem up and solve it in "regular" notation (up to inequality constraints). But I need to implement it in Python so I want to understand how it's done in matrix notation.

Answer 1

You have two sets of constraints:

$x_1 + x_2 + x_3 = 1$

$x_i \in [0,1]\;\forall i$

In matrix notation you'd get something like this:

$\min \;\;(Ax-b)^T(Ax-b)$

$s.t.$

$1^Tx=1$

$x \geq 0$

$x \leq 1$

So you'd add your slack vectors $s,t$ and multipliers $\lambda$ (scalar) and $\phi,\mu$ (vectors) to get:

$$L(x,\lambda, \phi)= (Ax-b)^T(Ax-b) -\lambda(1^Tx-1) - \phi^T(x-s) + \mu^T(x+t) $$

KKT are per usual:

1. $\nabla L = \mathbf{0}$
2. All constraints satisfied
3. Either $\phi_i=0$ or $s_i = 0$ but not both (complementary slackness)