Minimum of sum of squares over sums

Question

I am trying to minimize $\phi(\alpha)$, where $\alpha \in \mathbb{R}^K$.

$\phi(\alpha) = \frac{R^2 + G^2 \gamma \sum_{i=0}^{K} A_i \alpha_i^2}{\sum_{i=0}^{K} A_i \alpha_i} $

Where, $A_i = \gamma \beta^i (K+1-i)$. $K, \beta, \gamma$ are constants. $K$ is a positive integer, $\beta \in (0,1)$, $\gamma = 1 - \beta$.

I am trying to obtain a sequence $\alpha_i$ which will minimize $\phi(\alpha)$. I am proceeding the standard way of differentiating $\phi(\alpha)$ with respect to each $\alpha_i$ and setting it to zero. Further, I know $\phi(\alpha)$ is a convex function. My final objective is to obtain a solution in closed form, however it is turning out to be a nightmare.

I am actually solving a generalization of a problem. The special case being when $A_i$ are constants. In which case it is easy to argue that $\phi(\alpha)$ is a symmetric convex function and the solution should the one in which $\alpha_i$ are constants.

Am I proceeding in the correct direction? Please suggest.

Answer 1

I seeked a numerical solution to this problem. This problem being a {convex}./{linear} cannot be directly solved with CVX for example. Epi-graph trick and bisection give a way to solve this problem numerically.

Thus this problem can be transformed to,

$\underset{\alpha_0,\cdots,\alpha_K}{ minimize }\ t \\ subject\ to\ \ \ numerator \leq t \times denominator $

Which in turn can be solved by bi-section. Here is the code with matlab/CVX. Repeat this code with various t, which can be initially chosen as average of an upper bound and an lower bound and updating the upper bound or lower bound based on if the problem is feasible or not.

cvx_begin 
variable alphaS(K)
minimize 1
subject to
( R^2 + G^2 * sum_square( diag(b) * alphaS ) ) - t * (2*sum(alphaS) ) <= 0
alphaS >= 0
cvx_end

Entire matlab script,

b = zeros(K,1);
for p=1:K
    b(p) = 1-beta^p;
end

maxSubDivisions = 20;

% epigraph trick / bisection
upper = 2;
lower = 0;

loopCount=0;
while( 1 )
    loopCount = loopCount + 1;

    t=(upper+lower)/2;
    cvx_begin quiet
    variable alphaS(K)
    minimize 1
    subject to
    ( R^2 + G^2 * sum_square( diag(b) * alphaS ) ) - t * (2*sum(alphaS) ) <= 0
    alphaS >= 0
    cvx_end

    display( sprintf( '#%d : %s', loopCount, cvx_status ) );
    if( strcmp( cvx_status, 'Infeasible' ) == 1 )
        lower = t;
    end


    if( strcmp( cvx_status, 'Failed' ) == 1 )
        break;
    end

    len = length(strfind( cvx_status, 'Solved' ));
    if( ( len == 1) )
        upper = t;
        optArg = alphaS;
        optFVal = t;


        if( length(strfind( cvx_status, 'Inaccurate' )) == 1 )
            break;
        end
        if( loopCount > maxSubDivisions )
            break;
        end

    end


end