Solving a constrained optimization problem I have the following problem to optimize:
\begin{align}
\begin{split}
\hat{\mathbf{x}}, \hat{\delta} = \underset{\mathbf{x}, \,\delta}{argmin} \, \sum_{i=1}^l \, \sum_{j=1}^m \, a_{i,j}\left(x_i + \delta \right)^2
\\
s.t. \, \, \, \, 1 - x_i \leq 0 \, \, \forall \, i
\\
\text{and} \,\, \delta \leq 0
\end{split}
\end{align}
where $a_{i,j}$ is just a variable that doesn't depend of $x_i$.
I am thinking to solve this problem by minimizing the following Lagrangian function:
\begin{align}
\underset{\mathbf{x}, \, \delta}{argmin} \, L\left(\mathbf{x}, \, \delta, \, \lambda_1, \, \lambda_2\right) = \sum_{j=1}^m \, \sum_{i=1}^l \, a_{i,j}\left(x_i + \delta \right)^2 + \lambda_1 \left(1 - x_i\right) +\lambda_2 \, \delta
\end{align}
and then find the derive =0.
I am sure I am wrong. Can someone provide me with brief mathematical details about how this problem can be solved?
Any help will be very appreciated.
 A: I assume that $a_{ij}$ are nonnegative. Define $q_i = \sum_j a_{ij}$, $p_i = q_i / \sum_i q_i$ and $c = -\delta$, then the problem is:
$$\min_{x,c} \left\{ \sum_i p_i(x_i - c)^2 : x_i \geq 1, c \geq 0 \right\}$$
You recognize the formula for the variance in the objective function. Let me write the problem as:
$$\min_x \min_c \left\{ \sum_i p_i(x_i - c)^2 : x_i \geq 1, c \geq 0 \right\},$$
For fixed $x$, the inner problem is $\min_c \left\{ \sum_i p_i(x_i - c)^2 : c \geq 0 \right\}$. This is the minimum of a convex quadratic function with a nonnegativity constraint. The unconstrained minimum of the quadratic function is at $c=\sum_i p_i x_i$. This solution happens to satisfy the constraint $c\geq 0$ (because $x_i \geq 0$), so this solution is also optimal to the constrained problem.
Now you can write the original problem as:
$$\min_x \left\{ \sum_i p_i(x_i - \sum_j p_j x_j)^2 : x_i \geq 1\right\},$$
or as
$$\min_x \left\{ x^T(\textrm{Diag}(p) - pp^T)x : x_i \geq 1\right\},$$
where $\textrm{Diag}(p)$ is a matrix with $p$ on the diagonal and zeros elsewhere.
If all $x_i$ are equal, the objective value is $0$. It is clear that you cannot get a value less than $0$, so $0$ is optimal.
