3
$\begingroup$

Consider the following optimization problem:

\begin{align} \inf_{x,y}&\quad(x-x_0)^\top A(x-x_0) + (y-y_0)^\top B(y-y_0) \\\text{s.t.}&\quad x^\top a\geq0,\\ & \quad y^\top b\geq0, \\& \quad \|x-y\|_2^2 \leq \varepsilon, \end{align}

where $x,y\in\mathbb{R}^n$ are the unknown variables, $x_0,y_0,a,b\in\mathbb{R}^n$ are known vectors, $A,B\in\mathbb{R}^{n\times n}$ are known positive definite matrices, and $\varepsilon > 0$.

I would like to find a closed-form solution to such a problem.

What I have tried:

Define the Lagrangian as

$$L(\rho,x,y) = \frac{1}{2}((x-x_0)^\top A(x-x_0) + (y-y_0)^\top B(y-y_0)) - \rho_1(x^\top a) - \rho_2(y^\top b) + \rho_3(\varepsilon - \|x - y\|^2).$$ where $\rho$ is the vectors of Lagrange multipliers having non-negative components. Then, the optimality conditions impose: \begin{equation*} \begin{cases} \frac{\partial L}{\partial x} = A(x - x_0) - \rho_1a - 2\rho_3(x-y) = 0 \\ \frac{\partial L}{\partial y} =B(y - y_0) - \rho_2b + 2\rho_3(x-y) = 0 \\ \rho_1(x^\top a) = 0 \\ \rho_2(y^\top b) = 0 \\ \rho_3(\varepsilon - \|x - y\|^2) = 0, \end{cases} \end{equation*} plus, the constraints in the primal domain must be satisfied. The main problem for me is that I cannot find a closed-form solution to the above system of equations. Any help would be very appreciated.

$\endgroup$
4
  • 5
    $\begingroup$ To the best of knowledge it is not possible to find a closed form solution in this case. Btw do you really mean strict inequalities? $\endgroup$ Aug 29 at 8:40
  • $\begingroup$ No, they are not strict. I updated the question. $\endgroup$
    – Apprentice
    Aug 29 at 8:43
  • $\begingroup$ Anyway, how difficult is to find a numerical solution? $\endgroup$
    – Apprentice
    Aug 29 at 8:43
  • 3
    $\begingroup$ It can be written as a SOCP aka conic quadratic problem. See docs.mosek.com/modeling-cookbook/index.html $\endgroup$ Aug 29 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.