[Math] Minimizing the Sum of Quadratic Form with Equality Constraint

convex optimizationlinear algebraoptimizationquadratic programming

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), \; \text{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)?

Best Answer

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([' ']);
disp(['Projected Gradient Solution Summary']);
disp(['The Optimal Value Is Given By - ', num2str(objVal)]);
disp(['The Optimal Argument Is Given By - [ ', num2str(mX(:).'), ' ]']);
disp([' ']);

The full code is in my Mathematics Q2199546 GitHub Repository (Specifically in Q2199546.m).
The code is validated using CVX.

Related Question