Convex optimization problem with similarity constraint between variables

Question

Let $x_i,y_i\in\mathbb{R}$, $a_i\in[0,1]$, with $y_1>y_2$ and $y_3>y_4$. We also have $(y_1-y_3)^2 + (y_2 -y_4)^2 <\varepsilon $. I need to solve the following constrained optimization problem

$$\min_{x_1,x_2,x_3,x_4}\sum_{i = 1}^4 a_i(x_i-y_i)^2/2$$ $$\text{subject to } x_2\geq x_1,$$ $$ \quad \quad \quad \; x_4 \geq x_3$$ $$ \quad \quad \quad \;\quad \quad \quad \;\quad \quad \quad \; (x_1-x_3)^2 + (x_2-x_4)^2\leq \varepsilon$$

Attempted solution:

$L(\lambda,x) = \sum_{i = 1}^4 a_i(x_i-y_i)^2/2 + \lambda_1(x_1-x_2)+ \lambda_2(x_3-x_4) + \lambda_3( (x_1-x_3)^2 + (x_2-x_4)^2-\varepsilon)$

Differentiating and assuming binding constraints ($x_1 = x_2$, $x_3 = x_4$, $\varepsilon = (x_1-x_3)^2 + (x_2-x_4)^2)$ we get

$$x_k = \frac{\sum_i{a_i y_i}\mp \sqrt{\varepsilon/2}}{\sum_i a_i }, \text{ for } k = 1,2$$ and $$x_k = \frac{\sum_i{a_i y_i}\pm \sqrt{\varepsilon/2}}{\sum_i a_i }, \text{ for } k = 3,4$$

Is the procedure correct? Thanks!

Answer 1

That is the right approach, but you have a few errors:

1. The last term of $L(\lambda,x)$ should instead be $\lambda_3((x_1-x_3)^2 + (x_2-x_4)^2 - \varepsilon)$
2. You have used the index $i$ in two different ways ($x_i$ and $\sum_i$) in the same formula.
3. Your last formula has $i=1,2$, but you meant $i=3,4$.