Non-Convex fractional quadratic optimization

Nonconvex
1

Hello. The problem is as blew:
$$\mathop {\max}\limits_{x,\Delta,t\ge 0}\quad t \
Tr(R\Delta)\ge t*Tr(Q\Delta)+t ,\
Tr(P_i\Delta)\ge 1 , ;; i=1,\cdots , 1 ,\
\Delta\ge x x^T , ; x\ge 0$$
Where $P_i$s , R and Q are constant matrices.
My code:

P1=[0.1425 -0.2353  -0.4085 -0.2949;-0.2353 0.3884 0.6745 0.4869;-0.4085 0.6745 1.1714 0.8455;-0.2949 0.4869 0.8455 0.6102];
P2=[0.0875 -0.2364 0.0389 -0.1683;-0.2364 0.6385 -0.1051 0.4546;0.0389 -0.1051 0.0173 -0.0748;-0.1683 0.4546 -0.0748 0.3237];
P3=[2.1760 -1.3879 -0.5751 1.2121;-1.3879 0.8853 0.3668 -0.7731;-0.5751 0.3668 0.1520 -0.3204;1.2121 -0.7731 -0.3204 0.6752];
P4=[0.0548 0.2322 -0.0206 0.0622;0.2322 0.9842 -0.0873 0.2635;-0.0206 -0.0873 0.0077 -0.0234;0.0622 0.2635 -0.0234 0.0705];
R=[0.1232 0.2604 0.3334 0.1820;0.2604 0.5506 0.7049 0.3849;0.3334 0.7049 0.9023 0.4927;0.1820 0.3849 0.4927 0.2690];
Q=[2.0837 -1.4547 0.6404 1.4238;-1.4547 1.0156 -0.4471 -0.9940;0.6404 -0.4471 0.1968 0.4376;1.4238 -0.9940 0.4376 0.9729];

cvx_begin
    variables t x(n) X(n,n);
    subject to
        t*trace(Q'*X)+t-trace(R'*X)<=0;
        trace(P1'*X)<=1;
        trace(P2'*X)<=1;
        trace(P3'*X)<=1;
        trace(P4'*X)<=1;
        X==semidefinite(n);
        [X x; x' 1]==semidefinite(n+1);
        x>=zeros(n,1);
cvx_end

But matlab gives error:

Disciplined convex programming error:
    Invalid quadratic form(s): not a square.
2
3

Your problem does look like it may be quasiconvex, so try using quaisconvex optimization methods. See, for instance, Section 4.2.5 of Boyd & Vandenberghe.

4

Thank you, Mr. Grant. As you said, in Boyd’s Convex Optimization Book there is an algorithm which is Bisection method for quasi-convex optimization.
In an article, author used the problem above (main post) to solve non-convex fraction quadratic optimization.
So i want to solve convex feasibility problem mentioned in the algorithm using Matlab CVX, but i get above error. The problem seems be in first constraint. but why?

Please help me.
Best Regards

5

If you are truly solving the feasibility problem then t should not be declared as a variable, because it is a constant fixed by the bisection process.

6

If you have further issues then you need to speak with the article’s author. They should be making it more clear how they solved the problems they have written about.

7

thank you, it worked :wink: !

8

Hi, could you please show your final code solving the problem?

I have a similar problem, and could anyone give me some hint?

maximize x‘Px / x’Qx, st. Ax = b, where P and Q are both positive semi-definite. Thank you!

9

This code maybe help you:

clc
clear all
n=4;
% Define bisection parameters
M_LL = 0;
M_UL = 2;
bisec_tol = 1.1;

P1=[0.1425 -0.2353  -0.4085 -0.2949;-0.2353 0.3884 0.6745 0.4869;-0.4085 0.6745 1.1714 0.8455;-0.2949 0.4869 0.8455 0.6102];
P2=[0.0875 -0.2364 0.0389 -0.1683;-0.2364 0.6385 -0.1051 0.4546;0.0389 -0.1051 0.0173 -0.0748;-0.1683 0.4546 -0.0748 0.3237];
P3=[2.1760 -1.3879 -0.5751 1.2121;-1.3879 0.8853 0.3668 -0.7731;-0.5751 0.3668 0.1520 -0.3204;1.2121 -0.7731 -0.3204 0.6752];
P4=[0.0548 0.2322 -0.0206 0.0622;0.2322 0.9842 -0.0873 0.2635;-0.0206 -0.0873 0.0077 -0.0234;0.0622 0.2635 -0.0234 0.0705];
R=[0.1232 0.2604 0.3334 0.1820;0.2604 0.5506 0.7049 0.3849;0.3334 0.7049 0.9023 0.4927;0.1820 0.3849 0.4927 0.2690];
Q=[2.0837 -1.4547 0.6404 1.4238;-1.4547 1.0156 -0.4471 -0.9940;0.6404 -0.4471 0.1968 0.4376;1.4238 -0.9940 0.4376 0.9729];

while (M_UL - M_LL >= bisec_tol)
    t = round((M_UL+M_LL)./2);

    cvx_begin quiet
        variables x(n) X(n,n);
        subject to
            trace(R'*X)>=t*trace(Q'*X)+t;
            trace(P1'*X)<=1;
            trace(P2'*X)<=1;
            trace(P3'*X)<=1;
            trace(P4'*X)<=1;
            X==semidefinite(n);
            [X x; x' 1]==semidefinite(n+1);
            x>=zeros(n,1);
    cvx_end

    if (strcmp(cvx_status,'Solved'))
        M_UL = t;
    else
        M_LL = t;
    end
end