Constrained Optimization Closed Form Solution Using KKT Gives Wrong Values

Question

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 full matlab code to simulate and test different values of $n$, $m$, and $\gamma^{\text{priority}}_j$ can be found here.
• The link to goodnotes pdf notes for the full solution of the problem can be found here.

Answer 1

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.