Optimization problem: smallest euclidean distance with positive entries constraints

Question

Suppose there is the simple function:

\begin{align} f(x,y,z) &= (x-a)^2 + (y-b)^2 + (z-c)^2 + (x+y-S-z - d)^2 \end{align}

where $a,b,c,d$ are nonnegative constants, and $S$ is an integer. I want to find $x^*=(x,y,z, x+y-S-z))$ with the smallest distance from $(a,b,c,d)$, such that the entries in $x^*$ are greater or equal to zero. This motivates the following optimization problem:

\begin{align} \min & \qquad f(x,y,z) \\ \text{subject to} & \qquad -x \leq 0 \\ & \qquad -y \leq0 \\ & \qquad -z \leq0 \\ & \qquad -(x+y-S-z) \leq 0 \end{align} Now, I want to rewrite the problem in an equivalent form where I can eliminate the inequality constraints. First attempt, Try computing the lagrangian we get: \begin{align} L(x,y,z\lambda_1,\lambda_2, \lambda_3, \lambda_4) = f(x,y,z) - \lambda_1 x - \lambda_2 y - \lambda_3 z - \lambda_4(x+y-S-z) \end{align} I cannot see another formulation of this where I can rewrite this optimization problem in an equivalent form where I can get rid of the Lagrange multipliers? Is this possible?

Answer 1

In general, it's not possible getting rid of the inequalities, or the Lagrange multipliers. In other words, there isn't a system of equations you can solve.

If you wanna do this so badly, you can always compute a zero of the gradient, and if it doesn't satisfy the inequalities, try to find the minimum in your boundary.

Answer 2

As I said in the comments, I would suggest you should not insist on finding a closed-form solution to problems like this. There is nothing wrong with the notion that a model is only solvable numerically. Indeed, few actually interesting models are!

It looks to me like you've already tried to simplify this, again unnecessarily, before you even posted about it. This seems like the intended model: \begin{array}{ll} \text{minimize} & (x-a)^2+(y-b)^2+(z-c)^2+(w-d)^2 \\ \text{subject to} & x + y + z + w = S \\ & x, y, z, w \geq 0 \end{array} You gain nothing by expressing your model in a manner that is less clear!

But hey, let's see how far we can go with this. To simplify, I'm going to write it this way: \begin{array}{ll} \text{minimize} & \tfrac{1}{2} \|x-v\|_2^2 = \tfrac{1}{2} (x-v)^T(x-v)\\ \text{subject to} & \vec{1}^T x = S \\ & x \geq 0 \end{array} where $x$ is now a 4-vector and $v=(a,b,c,d)$. I hope you don't mind the $\tfrac{1}{2}$ in the objective; it doesn't change the optimal $x$, but it does simplify some things. The Lagrangian is $$L(x,\lambda,z) = \tfrac{1}{2} (x-v)^T(x-v) - \lambda ( \vec{1}^T x - S ) - z^T x$$ where the Lagrange multipliers are a $\lambda$ and a nonnegative 4-vector $z$. This leads to the KKT conditions $$x=v+\lambda\vec{1}+z\qquad \vec{1}^Tx=S \qquad x,z\geq 0\qquad x_iz_i=0,~i=1,2,3,4$$ Combining the first and third conditions leads to these assertions about $x$: $$x_i \geq 0, ~ x_i \geq v_i+\lambda \quad\Longrightarrow\quad x_i \geq \max\{v_i+\lambda,0\}, \quad i=1,2,\dots, 4.$$ But the complementarity conditions tell us that we cannot have both $x_i>0$ and $z_i>0$, which means that if $v_i+\lambda>0$, it must be the case that $z_i=0$ and $x_i=v_i+\lambda$. So combining the first, third, and fourth conditions leads us to this: $$ \begin{gathered} x_i = \max\{v_i+\lambda,0\} \quad \\ z_i = x_i - v_i - \lambda = \max\{-v_i-\lambda,0\} \qquad (*) \end{gathered} $$ Now we're getting somewhere! Here's how we can solve this. First, knock out the easy cases:

1. Compute $s \triangleq \vec{1}^T v = a+b+c+d$.
2. If $s=0$, STOP; $(x,\lambda,v)=(v,0,0)$ is the trivial KKT solution.
3. Otherwise, let $\lambda_0 = \tfrac{1}{4}(S-q)$.
4. If $v+\lambda_0\vec{1}>0$, then STOP; $(x,\lambda,z)=(v+\lambda_0 \vec{1},\lambda_0,z)$ is a KKT solution.

If we're still going, that means that at least one of the inequality constraints $x_i\geq 0$ is active, and $\lambda$ must lie in the interval $(\lambda_0,0)$. We need to find it! Without loss of generality, assume that $a\leq b\leq c\leq d$; i.e., $v_1\leq v_2\leq v_3\leq v_4$. Then we do this:

5. Let k = 1.
6. Let $\lambda_k = \tfrac{1}{4-k} (S- \sum_{i=k+1}^4 v_i)$.
7. If $\lambda_k\in(\lambda_0,0)$ and $v-\lambda_k\vec{1}>0$, STOP. $(x,\lambda)=(v+\lambda_k\vec{1},\lambda_k)$, and $z$ calculated according to the formula $(*)$ above, is the KKT solution.
8. Set $k\rightarrow k+1$ and repeat steps 6-8.

I know I haven't proven this rigorously, but it fits my intuition and experience. $\lambda$ is controlling how far $x$ deviates from its ideal value, $(a,b,c,d)$. We want $\lambda$ to be as close as possible to $\lambda_0$, which is the value required by the equality constraints alone. By setting values of $x_i$ to zero from smallest to largest, we ensure that we're "moving" $\lambda$ by the smallest amount.

It's not a closed form solution, but at $O(n)$ it's hard to beat.