Let $ (a_{ij}) $ and $ (b_{ij}) $ be two sequences of real numbers. I'm trying to solve the quadratic program
$$
\min_{(a_{ij})} \sum_i \Big(\sum_j a_{ij} \Big)^2 \quad \text{s.t.} \quad \sum_i\sum_j a_{ij}b_{ij} = 1
$$
using Lagrange multipliers, but can't seem to get anywhere. Does anyone know any references for these types of programs?
Edit: With $ a = (a_{ij}) $, the Lagrangian is
$$
\mathcal{L}(a, \lambda) = \sum_i \Big(\sum_j a_{ij} \Big)^2 – \lambda \sum_i\sum_j a_{ij}b_{ij}
$$
and its partial derivatives are
$$
\frac{\partial}{\partial a_{ij}}\mathcal{L}(a, \lambda) = 2\sum_{j'} a_{ij'} – \lambda b_{ij}.
$$
Best Answer
I am not sure whether $a$ and $b$ are intended to be finite or infinite arrays. If they are allowed to be infinite, then the problem may not have any minimizer at all. For instance let $b_{ij}=1$ for all $i,j\ge 1$. Now Fix $N$ and let $a^N_{ij}=\delta_{j=1}\delta_{i\leq N}/N$. That is, $a^N_{ij}=1/N$ if $j=1$ and $i\leq N$, and 0 otherwise. Then it is easy to check that $a^N_{ij}$ satisfies the constraint and the value of the objective at $a_{ij}^N$ is $1/N$. Thus, the objective attains values arbitrarily close to 0. On the other hand, it can never be equal to 0, since this would imply that $\sum_{j} a_{ij}=0$ for each $i$, but this is impossible because the constraint implies that $\sum_i \sum_j a_{ij}=1$.
Thus, I will assume $a$ and $b$ are finite arrays.Let $n$ denote the number of rows of $a$.
We first write the equation you derived for the critical points in the terser form $2A\textbf{1}\textbf{1}^t=\lambda B$. The first thing to note is that $A\textbf{1}\textbf{1}^t$ is a rank 1 matrix. In fact it is a special kind of rank 1 matrix of the form $v\textbf{1}^t$. Therefore we consider two cases:
Case 1 $B$ is not of the form $v \textbf{1}^t$ for some $v$
In this case, we must have $\lambda=0$, since otherwise we would have $B=(2A\textbf{1}/\lambda)\textbf{1}^t$. This implies that $A\textbf{1}=0$.
It remains to check that we can find a matrix $A$ satisfying the constraints $A\textbf{1}=\textbf{0}$ and $Tr(AB^t)=1$. To do this, we first note that there must exists a non-constant row of $b$ (this is another way of stating the hypothesis on $B$). By reordering the indices if necessary, we can assume WLOG that $b_{11}\ne b_{12}$. Then we will construct the array $A$ by setting $a_{ij}=0$ unless $(i,j)=(1,1)$ or $(1,2)$. To satisfy the constraints, we just have to ensure that $a_{11}+a_{12}=0$ and $a_{11}b_{11}+a_{12}b_{12}=1$. The determinant of the corresponding linear system is $b_{12}-b_{11}\ne 0$ so there is indeed a solution for $A$. It follows that the minimum value of the objective is 0 in this case.
Case 2 $B=v\textbf{1}^t$,$v\ne 0$
The crucial difference from the previous case is that that in this case, there is no solution with $\lambda=0$. Indeed, such a solution would have $A\textbf{1}=0$ and $Tr(AB^t)=1$. But $Tr(AB^t)=Tr(A\textbf{1}v^t)=Tr(v^t A\textbf{1})=Tr(v^t\textbf{0})=0$, a contradiction.
Consider the critical point equation $2A\textbf{1}\textbf{1}^t=\lambda v\textbf{1}^t$. This implies that $2A\textbf{1}=\lambda v$.
On the other hand, $Tr(AB^t)=1$ so $1=Tr(A\textbf{1}v^t)=(\lambda/2)Tr(v^tv)=\lambda |v|^2/2$, thus we have $A\textbf{1}=v/|v|^2$ for any critical point $A$. Conversely, any such matrix $A$ satisfies the constraint $Tr(AB^t)=1$ and is a critical point. The value of the objective at any such $A$ is $|A\textbf{1}|^2=1/|v|^2$, so this is the minimal value in this case.