0
$\begingroup$

I have the following Max Min optimization problem that appears to be non convex.

link

where t p c are my variables and all others are constants. I took the eigen values of the hermetian part of the hessian matrix of the 1st constraint(keeping all the constants as 1) and it comes out to be negative(hessian is indefinite for some values of t p and c). does this mean that the problem is non convex altogether. can it be converted into convex. is there any tool for solving such non convex problems?

$\endgroup$
  • $\begingroup$ What stops us from using $c_{k,n} = P_{k,n} = \infty \forall k \notin S_l$ (assuming $h_{k,n}$ non-negative)?. Is it simply the case of a strange notation, i.e., is the sum in the simplex constraints actually over all k elements? $\endgroup$ – Johan Löfberg Oct 16 '13 at 6:48
  • $\begingroup$ Yeah yeah, the sum is indeed over all K elements. putting ck,n = Pk,n = ∞ ∀k∉Sl I don't know would it solve my problem? If I put all the constants (R,B,N,sigma,H) as 1 for simplicity I can write the 1st constraint, T- c*log(1-p)<=0 for this the hessian becomes indefinite(at p=c=t=10) problem is non convex. $\endgroup$ – cody Oct 16 '13 at 8:18
  • $\begingroup$ I don't know, if the hessian is indefinite over say few points, does the problem become non convex altogather? $\endgroup$ – cody Oct 16 '13 at 8:20
  • $\begingroup$ Unless the sums actually range over all indices, the problem is ill-posed, since it would be optimal to put those non-index variables to infinity, thus resulting in an infinite objective value. So may I thus assume that the column sums of both $c$ and $P$ are bounded from above? $\endgroup$ – Johan Löfberg Oct 16 '13 at 10:16
  • $\begingroup$ If the Hessian is indefinite for some feasible points, yes it is non convex. $\endgroup$ – Johan Löfberg Oct 16 '13 at 10:17
5
$\begingroup$

The problem is a standard nonlinear nonconvex problem, so any solver for this problem class is suitable to solve the problem.

As an example, the following code implements the problem in the MATLAB Toolbox YALMIP (disclaimer, developed by me) and solves the problem using the local nonlinear solver ipopt.

N = 3;
K = 3;
h = rand(N,K);
R = rand(K,1);
sigma = 1;
beta  = 1;
Pmax = 10;
Constraints = [];
P = sdpvar(N,K,'full');
C = sdpvar(N,K,'full');
sdpvar t
Constraints = [P>=0, C>=0, sum(sum(P)) <= Pmax,sum(C,1)<=1]
for k = 1:K
   Constraints = [Constraints, t<=(beta/(N*R(k)))*sum(C(:,k).*log2(1+P(:,k).*h(:,k)/sigma))];
end    
solvesdp(Constraints,-t,sdpsettings('solver','ipopt'))

ipopt is a local solver, so all you can hope for here is a locally optimal solution. However, it looks as if your problem actually is rather easy, as the solution often seems to be globally optimal. You can see this by solving the problem globally using the global solver available in YALMIP. It implements a b&b strategy based on linear relaxations for lower bounds and nonlinear local solvers for upper bounds. Of course, it is only applicable to small problems (unless you have a lot of time to spare...)

solvesdp(Constraints,-t,sdpsettings('solver','bmibnb'))

Finally, I would like to add that the structure of your problem actually allows you to eliminate the c-variables. It can be seen that the optimal choice of c is to have all elements in each column equal to zero, execpt the element which corresponds to the largest term in the vector of logarithmic terms. Hence, conceptually, you can solve

Constraints = [P>=0, sum(sum(P))<= Pmax]
for k = 1:K
    Constraints = [Constraints, t<=(beta/(N*R(k)))*max(log2(1+P(:,k).*h(:,k)/sigma))];
end

This leads to a mixed-integer nonlinear nonconvex program when you model it in YALMIP (binary variables are introduced to model the nonconvex use of the max operator), and it seems to be a less efficient approach than the straightforward nonlinear approach.

$\endgroup$
  • $\begingroup$ By default, solvesdp minimizes, and since I have negated the objective, it means it maximizes t. $\endgroup$ – Johan Löfberg Oct 17 '13 at 11:22
  • $\begingroup$ Sir, I am not sure about the convexity of the problem. Actually, I'm trying to implement a paper and they had this optimization formulation. its Authors have mentioned that the problem is convex. Earlier I was using CVX(for convex optimization), I was not able to formulate the problem in that so I posted a question on CVX forum.. ask.cvxr.com/question/1193/… , and someone told me that the problem is not convex. IPOPT can solve both convex and non convex, but I just wanted to know weather the authors of the paper are correct or not $\endgroup$ – cody Oct 20 '13 at 21:58
  • $\begingroup$ The model you have posted is not convex. You can easily convince your self about this by simply plotting the function and directly see that the function in the constraint is not concave (nor convex) .[C,P] = meshgrid(0:0.01:1); mesh(C.*log2(1+P)). Which paper are you trying to implement? $\endgroup$ – Johan Löfberg Oct 21 '13 at 6:28
  • $\begingroup$ First, I don't think it is line with the policy of this site to link to your own copies of copyrighted material. Looking at the first link though, equation (2) is convex, but equation (3) is definitely not obviously convex as they state. If it is, some magic occurs due to the constraints. Could there be a missing $c_{k,n}$ in the denominator inside the log? $\endgroup$ – Johan Löfberg Oct 21 '13 at 8:49
  • $\begingroup$ Well, there is either a typo somewhere or the claim is simply incorrect. You can easily construct counterexamples. A bit messy in a comment, but contact me by email and we can discuss it. $\endgroup$ – Johan Löfberg Oct 21 '13 at 11:06

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.