# Convex optimization problem with similarity constraint between variables

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!

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$$.
• Corrected, Thanks! Do you think the result is correct? Should I consider the other cases? $\lambda_1 \neq 0$, $\lambda_2 = 0$ and vice-versa? May 30, 2021 at 21:18