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.
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.
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
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.
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.
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!
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
!