Minimize a Quadratic Cost Function on the Unit Simplex

How can I compute $$ \min_{x \in \Delta_n} \frac{1}{2}\lVert Bx\rVert^2 + x^tAy$$ with $x \in \mathbb{R}^n, y \in \mathbb{R}^m, A_{m \times n}$, $B_{n \times n}$ where $\Delta_n$ is the unit simplex $$\Delta_n = \{x \in \mathbb{R}^n_+ | \sum_{i=1}^n x_i = 1\}$$ Are there standard algorithms for computing it?

Solution 1:

You can also solve this by Projected Gradient Descent since the Projection onto the Unit Simplex is known.

The Code:

vX = pinv(mA) * vB;
    
mAy = mA.' * vY;
mAA = mA.' * mA;

for ii = 1:numIterations
    stepSize = stepSizeBase / sqrt(ii);
    vG = (mAA * vX) + mAy;
    vX = vX - (stepSize * vG);
    vX = ProjectSimplex(vX, simplexRadius, stopThr);
end

objVal = (0.5 * sum((mA * vX) .^ 2)) + (vX.' * mAy);

disp([' ']);
disp(['Projected Gradient Solution Summary']);
disp(['The Optimal Value Is Given By - ', num2str(objVal)]);
disp(['The Optimal Argument Is Given By - [ ', num2str(vX.'), ' ]']);
disp([' ']);

You can even accelerate this using Nesterov / FISTA to get really fast and efficient algorithm.

You can have the Simplex Projection function from my Ball Projection GitHub Repository.