KKT formulation

319 Views Asked by At

How to reformulate the following problem

$$min \frac{1}{2} (x_1-a_1)^2+ \frac{1}{2} (x_2-a_2)^2$$ $$s.t. \mathbf{1}^Tx=1$$ $$ ||x||_2\leq2$$

as the following system of KKT conditions: $$(1 + \mu)x = a + \lambda\mathbf{1}$$ $$\mu \geq 0$$ $$\mathbf{1}^Tx=1$$ $$ ||x||_2\leq2$$ $$ (||x||_2-2)\mu=0$$

where $$ x = (x_1, x_2)^T$$ and $$ a = (a_1, a_2)^T$$

Actually, the only thing which is not clear to me is how the first term in the KKT system is obtained, the rest is pretty straightforward.

1

There are 1 best solutions below

2
On BEST ANSWER

The first equation represents the KKT condition

$$ \nabla f_0 (x) + \sum \lambda_i\nabla g_i(x) + \sum\mu_i\nabla h_i(x) = 0 $$

You can easily verify that $\nabla f_0 = x-a$. The rest of the calculation should be straightforward; it might helpful to represent the second constraint as $||x||_2^2 = x^Tx \leq 4$.

Also, do not get tripped up if you have a $2\lambda$ instead of $\lambda$, since $\lambda$ is just a variable you can simply redefine $\lambda' = 2\lambda$, much like absorbing all extra constants into one constant of integration in calculus.