Complementary Slackness: Quadratic objective with linear constraint

Question

Let \begin{align*} \mathcal{P} : &\min_{x}~& (x + a)^2 \\ & s.t. & x + b \leq 0 \end{align*}

where $ a, b \in \mathbb{R} $. I would like to find $ x $.

My attempt: The Lagrangian is $ L_\pi = |x + a|^2 + \pi (x + b) $.

Stationarity: $ x + a + \pi = 0 $

Complementary slackness: $ \pi (x + b) = 0 $

• Replacing $ x = -\pi - a $ in $ \pi (x + b) = 0 $, we obtain that $ \pi (-\pi - a + b) = 0 $.

This is the point where I am not able to continue. I get two roots por $ \pi $ but I am unable to realize which one I should use to get $ x $.

Answer 1

No need for big words and complicated methods.

Clearly, the minimum of $(x+a)^2$ with no conditions is reached at $x=-a$, since $(-a+a)^2=0$, and $(x+a)^2\geq 0$.

Now, simply separate two cases. One where $-a+b\leq 0$, and another where $-a+b>0$.

Case $1$: If $a\geq b$, then $x_0=-a$ satisfies the condition $x+b\leq 0$, and the minimum is $0$.

Case $2$: If $a<b$, then $(x+a)^2$ is a strictly decreasing function on $(-\infty, -b]$ (i.e., where $x+b\leq 0$), which means that the minimum is reached at $x_0=-b$.

Answer 2

Probably the purpose of this problem is to practice using the KKT conditions, but we should first mention the visual way to solve it.

Solution 1: We want $x$ to be as close to $-a$ as possible, but we have a constraint that $x \leq -b$. If $-a \leq -b$, then the solution is $x = -a$. Otherwise, the solution is $x = -b$.

Solution 2 (using the KKT conditions):

The Lagrangian is $L(x, \lambda) = (x + a)^2 + \lambda(x + b)$. The KKT conditions tell us that $x$ is primal optimal if and only if there exists a Lagrange multiplier $\lambda$ such that

1. $x + b \leq 0$.
2. $2(x + a) + \lambda = 0$, or equivalently $\lambda = -2(x + a)$.
3. $\lambda \geq 0$.
4. Either $\lambda = 0$ or $x + b = 0$.

Combining conditions 2 and 4, we see that either $x = -a$ or $x = -b$. Note that $x = -a$ only works as a solution if $-a \leq -b$. Otherwise, the solution is $x = -b$.