# Minimizing the Sum of Quadratic Form with Equality Constraint

In a problem I need to minimize sum of $K$ quadratic costs as follows:

$\min_{\mathrm x_1,...,\mathrm x_K} \sum_{i=1}^{K}( \mathrm x_i^TA_i\mathrm x_i+\lambda\mathrm c_i^T\mathrm x_i)$ , s.t. $\sum_{i=1}^{K}\mathrm x_i=e$

where $\mathrm x_i \in \Bbb{R}^n,i=1,...,K$, each $A_i$ is a symmetric real matrix, and $e$ is an all-ones vector.

Using the Lagrange function and Lagrange multipliers, the solution of above optimization problem can be obtained by solving a linear system of equations. However, for large $n$ and large $K$ this leads to very large linear system. So my question is can I solve this problem more efficiently.

In fact, can I do this minimization by minimizing each of the quadratic cost separately (with no constraint) and then normalizing the solutions to make them sum up to one (according to the constraint)?

• What are the $A_i$'s? – uniquesolution Mar 23 '17 at 9:03
• If you were to solve each quadratic minimization separately, what constraint would you put on each subproblem? – Brian Borchers Mar 23 '17 at 14:07
• I solve each quadratic sub-problem with no constraint and then normalize the solution of all sub-problems according to the constraint of main problem. However, I do not know whether I am doing the right thing or not. – M Nejati Mar 23 '17 at 18:29
• Are your $A_{i}$ matrices positive semidefinite? indefinite? negative semidefinite? – Brian Borchers Mar 26 '17 at 18:01
• The matrices $A_i$'s are symmetric positive semidefinite. – M Nejati Mar 27 '17 at 20:13

I would use Accelerated Gradient Descent Method.
This means you'll stay only with Matrix Multiplication (And exploiting ${A}_{i}$ being Symmetric can help with that).

But you actually need to use "Projected Sub Gradient", namely to calculate the projection of the solution onto the Domain.

## The Projection onto The Constrain

Let's define a vector $z = \left[ {{x}_{1}}^{T}, {{x}_{2}}^{T}, \ldots, {{x}_{K}}^{T} \right]^{T}$.
The constrains is equivalent of:

$$S * z = \boldsymbol{1}_{n}, \; S = \underset{\times K}{\left [ \underbrace{{I}_{n}, {I}_{n}, \ldots, {I}_{n}} \right ]}$$

Basically the matrix $S$ sum over the $i$ -th element of all $x$ vectors.

Now, given a vector $y \in \mathbb{R}^{nk}$, its projection onto the set $\mathcal{S} = \left\{ x \mid S * x = \boldsymbol{1}_{n} \right\}$ is given by:

$$\arg \min_{x \in \mathcal{S}} \frac{1}{2} \left\| x - y \right\|_{2}^{2} = y - {S}^{T} \left( S {S}^{T} \right)^{-1} \left( S y - \boldsymbol{1}_{n} \right)$$

Due to the special structure of $S$ one could see it is equivalent to:

$${x}_{i} - \frac{\sum_{i = 1}^{K} {x}_{i} - \boldsymbol{1}_{n}}{K}, \: i = 1, 2, \ldots, k$$

Namely spread the deviation equally on all elements.

Here is the code:

%% Solution by Projected Gradient Descent

mX = zeros([numRows, numCols]);

for ii = 1:numIterations
for jj = 1:numCols
mX(:, jj) = mX(:, jj) - (stepSize * ((2 * tA(:, :, jj) * mX(:, jj)) + (paramLambda * mC(:, jj))));
end
mX = hProjEquality(mX);
end

objVal = 0;
for ii = 1:numCols
objVal = objVal + (mX(:, ii).' * tA(:, :, ii) * mX(:, ii)) + (paramLambda * mC(:, ii).' * mX(:, ii));
end

disp([' ']);