Constrained Optimization Closed Form Solution Using KKT Gives Wrong Values

I have a (I guess) simple constrained optimization problem that I'm hoping to find a closed-form solution for using Lagrangian analysis and KKT conditions. I figured out the solution but there is one Lagrangian multiplier that I can't find a solution for.

The vector of decision variables that I have is denoted by $$\boldsymbol{\gamma}$$ where $$|\boldsymbol{\gamma}| = m$$.

\begin{align}\min_{\gamma_j}&\quad\sum_{j=0}^m(\gamma_j - \frac{n}{m}\gamma_j^{\text{priority}})^2&\qquad(1\text{a}) \\\text{s.t.} \\&\quad0 < \sum_{j=0}^m\gamma_j\leq n&\qquad(1\text{b})\end{align}

Where $$n$$ and $$\gamma^{\text{priority}}_j\; \forall j \in \boldsymbol{\gamma}$$ are constants.

Here is the full Lagrangian analysis solution:

I start the solution by deriving the Lagrangian function: \begin{align} \mathcal{L}(\boldsymbol{\gamma}, \lambda^{(1)}, \lambda^{(2)}) = \sum^m_{j=1} (\gamma_j - \frac{n}{m}\gamma^{\text{priority}}_j)^2 + \lambda^{(1)}\left(\sum^m_{j=1}\gamma_j\right) - \lambda^{(1)}n - \lambda^{(2)}\sum^m_{j=1}\gamma_j\qquad(2)\end{align} Then I derive the partial derivatives with respect to the decision variables and the Lagrangian multipliers: \begin{align} \frac{\partial \mathcal{L}}{\partial \gamma_j} &= 2(\gamma_j - \frac{n}{m}\gamma^{\text{prioirty}}_j) + \lambda^{(1)} - \lambda^{(2)} &= 0\qquad (3)\\ \frac{\partial\mathcal{L}}{\partial \lambda^{(1)}} &= \sum^m_{j=1}\gamma_j = n\qquad(4)\\ \frac{\partial \mathcal{L}}{\partial \lambda^{(2)}} &= -\sum^m_{j=1}\gamma_j \qquad (5) \end{align}

KKT conditions: \begin{align} \lambda^{(1)}\sum^m_{j=1}\gamma_j &= \lambda^{(1)}n\qquad(6)\\ \lambda^{(2)}\sum^m_{j=1}\gamma_j&=0\qquad (7) \end{align} From (3) we can conclude that: \begin{align} \gamma_j = \frac{n}{m}\gamma^{\text{priority}}_j + \frac{\lambda^{(1)} - \lambda^{(2)}}{2} \qquad(8) \end{align} From (7) we conclude that $$\lambda^{(2)} = 0$$ because the term $$\sum^m_{j=1}\gamma_j$$ will never equal to zero. Thus we have: \begin{align} \gamma_j = \frac{n}{m}\gamma^{\text{priority}}_j + \frac{\lambda^{(1)}}{2} \qquad(9) \end{align}

Now plugging (9) in (4) we get: \begin{align} \lambda^{(1)} = \frac{2n}{m}\left(1 - \frac{1}{m}\sum^m_{j=1}\gamma^{\text{priority}}_j\right)\qquad(10) \end{align}

According to the previous steps, the closed-form solution is attainable but, when I try different values of $$n$$, $$m$$, and $$\gamma^{\text{priority}}_j$$ sometimes I get values for $$\gamma_j$$ that violate constraint (1b) ,i.e., the summation of all $$\gamma_j$$ can sometimes exceeds the value of $$n$$. For instance, when $$n=85$$, and $$m=42$$, the term $$\sum_{j=0}^m\gamma_j$$ evaluates to $$166$$.

Have I done something wrong?

• The KKT conditions don't hold for strict inequality constraints like $0 < \sum_{j=1}^{m} \gamma_j$.
– joni
Commented Nov 19, 2022 at 9:48
• @joni If you're sure that the sum of the $\gamma_j$ is positive, you can just drop the lower bound. Ibrahim: I get the same value for $\lambda$. Can you share the full model/the code? Commented Nov 19, 2022 at 18:08
• @joni You are right. But I guess in this case it doesn't matter because the way a problem is solved using strict inequality constraints is the same, we just need to drop the strict constraint and make it $0 \leq \sum^m_{j=1} \gamma_j$. Commented Nov 19, 2022 at 21:49
• @cvanaret Thank you for your reply. Is it Okay to share the full solution with you via an iPad-written pdf solution document? Commented Nov 19, 2022 at 21:50
• @cvanaret I have shared the full matlab code and the full notes for the solution. Commented Nov 19, 2022 at 22:22

For convenience, let $$x_j = \gamma_j / n$$, $$c_j = \gamma_j^\mathrm{priority} / m$$, then the problem is \begin{align*} \min_{x_j} \quad&\sum_{j=0}^m(x_j - c_j)^2\\ \mathrm{s.t.} \quad&0\leq\sum_{j=0}^m x_j \leq 1 \end{align*} The Lagrangian function is $$\mathcal{L}(x, \lambda^{(1)}, \lambda^{(2)}) = \sum (x_j - c_j)^2 + \lambda^{(1)}(\sum x_j - 1) - \lambda^{(2)}\sum x_j$$ The gradient is $$\frac{\partial \mathcal{L}}{\partial x_j} = 2(x_j - c_j) + \lambda^{(1)} - \lambda^{(2)} = 0, \forall j$$ So $$x_j = c_j + \frac {\lambda^{(2)} - \lambda^{(1)}} {2}$$

Complenmentary slackness $$\lambda^{(1)}(\sum x_j - 1) = 0\\ \lambda^{(2)}\sum x_j = 0$$

Case 1: $$\lambda^{(1)} = \lambda^{(2)} = 0$$, then $$x_j = c_j$$. The primal feasibility condition is $$\sum x_j = \sum c_j \in [0, 1]$$

Case 2: $$\lambda^{(1)} = 0, \lambda^{(2)} \neq 0$$, then $$\sum x_j = 0$$, $$\lambda^{(2)} = -2\bar{c}$$ where $$\bar{c} = \sum c_j / m$$. The dual feasibility condition is $$\sum c_j \leq 0$$

Case 3: $$\lambda^{(2)} = 0, \lambda^{(1)} \neq 0$$, then $$\sum x_j = 1$$, $$\lambda^{(1)} = 2 \bar{c} - \frac {2}{m}$$ The dual feasibility condition is $$\sum c_j \geq 1$$.

Case 4: $$\lambda^{(1)}\lambda^{(2)}\neq 0$$, then $$\sum x_j=0$$ and $$\sum x_j=1$$, which is not possible.

To summarize, there might be one or two KKT points depending on the value of $$\sum c_j$$. When $$\sum c_j = 0$$ or $$1$$, there are two KKT points, but they are always identical: $$x_j = c_j$$. Other than that, the KKT point is always unique, therefore optimal. So the solution is as follows.

1. $$\sum c_j < 0$$, then $$x_j = c_j - \bar c$$.
2. $$\sum c_j \in [0,1]$$, then $$x_j = c_j$$.
3. $$\sum c_j > 1$$, then $$x_j = c_j - \bar c + \frac {1} {m}$$.

When $$\sum c_j \leq 0$$, the above solution gives $$\sum x_j = 0$$. If the actual feasible region is $$\sum x_j > 0$$, then there is no optimal solution for the problem.

• Thank you for the detailed answer! I'm new to the world of mathematical optimization, so, I have two questions. 1. How did you obtain the primal and dual feasibility conditions when you listed the cases? For instance, $\sum c_j \leq 0$. 2. Can this problem have a closed-form solution if we added the constraint $0 \leq \gamma_j$? Commented Nov 22, 2022 at 18:58