0
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ What are the $A_i$'s? $\endgroup$ – uniquesolution Mar 23 '17 at 9:03
  • $\begingroup$ If you were to solve each quadratic minimization separately, what constraint would you put on each subproblem? $\endgroup$ – Brian Borchers Mar 23 '17 at 14:07
  • $\begingroup$ 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. $\endgroup$ – M Nejati Mar 23 '17 at 18:29
  • $\begingroup$ Are your $A_{i}$ matrices positive semidefinite? indefinite? negative semidefinite? $\endgroup$ – Brian Borchers Mar 26 '17 at 18:01
  • $\begingroup$ The matrices $A_i$'s are symmetric positive semidefinite. $\endgroup$ – M Nejati Mar 27 '17 at 20:13
0
$\begingroup$

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 Q2375760 GitHub Repository (Specifically in Q2199546.m).
The code is validated using CVX.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.