Problem in formulating my problem in CVX


#1

I had Posted a question yesterday But I don’t know if I had written it correctly. I want to formulate the following problem in CVX
Find p(k), W(k) to

Minimize ∑(over k) W

S.T;

W(k)*(B/N) * log(1 + ((p(k)*H(k)/W(k)*(S^2))) > = r(k);

∑ over k p(k) < = pmax;

p(k) > = 0;

W(k) > = 0 for all K;

Where H(k), r(k), N, B are variables…

I have written the following CVK code but it is not accepting it…PLEASE HELP ME!!

variables w(k) p(k) b(k);

minimize sum(w);

subject to

for i = 1:k,

log(w(i)*square(S) + p(i)*H(i)) - log(w(i)*square(s))
          >= r(i)*N*inv_pos(w(i)*B)
 p(i)>=0;
   w(i)>=0;


end
sum(p)<=pmax;

cvx_end;

In the first constraint it says that both the terms are concave… I dont know what to do…plz help!!


(Mark L. Stone) #2

I’m afraid we’re basically back to where we were on your previous thread I have a constraint, that I am unable to write in CVX acceptable syntax. Help! .

Consider the special case in which all MATLAB variables other than those declared to be variables in CVX have the value 1. Then ignoring the index i for simplicity of exposition, your first constraint can be put in the form 1/w-log(1+p/w) <= 0. Even though you have declared p to be a CVX variable, if we fix p for the moment at 1, then this is exactly the same constraint which was analyzed in the aforementioned thread, and it is convex, but per mcg’s answer there, it is (apparently) not representable in CVX. Unfortunately, when we allow p to be a non-negative CVX variable, 1/w-log(1+p/w) <= 0 need not even be convex, as evidenced by the 2nd derivative of the LHS w.r.t w being -0.0055 at p=10, w=10.

As a minor footnote, your parentheses placement w.r.t. S^2 is inconsistent between your model statement and your CVX code, but that does not affect my conclusions above, since I set S equal to 1.


#3

Thanks a lot sir!!
I have not taken a course in convex optimization. My friend says you can not apply KKT conditions in this formulation(he says that in the >= constraint, the RHS can not be a constant, it should be > 0). is that so? I have read a paper with similar formulation that have…ctd


#4

applied KKT conditions and found an expression for for the variable. I wanted to ask you that can KKT conditions be applied in the above formulation. I have no background what so ever in convex optimization.


#5

can you please suggest me if there is something else apart form KKT condition, using which I can solve my problem.


(Mark L. Stone) #6

You may not want to hear this, but it sounds like you don’t know much about optimization in general, not just the convex variety. Therefore, I suggest you seek in-person help in model formulation and solution from someone who does.


(Mark L. Stone) #7

When the problem is not convex, KKT is not sufficient for a global optimum, and is only necessary when a constraint qualification holds, which I don’t whether it does here (your model doesn’t satisfy the easy to check condition of having only linear constraints).


(Linmumuzf) #8

Hello, how can I solve the convex optimization problem with KKT condition, can you share the relevant matlab code with me, thank you very much。


(Mark L. Stone) #9

@linmumuzf
The KKT conditions for constrained problems are always non-convex due to the complementarity condition. However,if the KKT conditions are otherwise convex, it may be possible to address the complementarity conditions in CVX using binary variables, using CVX’s MIDCP capability. Anyhow, CVX is ill-suited for use as a way of solving KKT conditions.

If you have a convex optimization problem which can be formulated in accordance with CVX’s rules, then you don’t need to formulate the KKT conditions - you can let CVX call a solver to numerically solve the problem.

If you are looking for general help in formulating and using KKT conditions, then apart from studying textbooks, your best option might be requesting help on https://math.stackexchange.com/ , because such help is out of scope of the CVX forum. if you do request additional help, you need to make a much more specific and focused request.


(Linmumuzf) #10

Thank you very much for your answer, I have a convex optimization problem. I saw in the textbooks and others’ papers that the KKT conditional solution was used when the problem had proved to be a convex optimization problem. If I let CVX call a solver to numerically solve the problem,how can i know call which solver and do I need to mention the KKT conditional solution in my paper? It’s not appropriate to say that using cvx to get the answer,right?In addition, my English is not very good, I hope you can understand what I said.Thank you。


(Mark L. Stone) #11

The solver can be specified using the cvx_solver command http://cvxr.com/cvx/doc/solver.html#selecting-a-solver

As for what’s appropriate in a paper, that is a matter to be determined by author, editor, referee, publication entity, professor, school, employer, etc,. and the readers. The only value of a KKT solution is likely to be if that enables you to get a closed form (analytical) solution or other problem insight into the solution.

There are many papers published in refereed journals which use CVX to numerically solve convex optimization problems. if you do so, the CVX developer encourages you to publish your complete CVX program so that it will be reproducible by readers. There have been many instances on this forum in which a reader of a published article has not been able to figure out how some optimization problem can be entered into CVX, despite the author’s claiming to have done so, but not providing the details; and in some of those cases, no one on this forum, including the CVX developer, could figure out what the article author did.

See http://cvxr.com/cvx/doc/citing.html for how to cite CVX iin a publication.


(Linmumuzf) #12

Very bad, I just let CVX call a solver to numerically solve the problem, but the display does not conform to the cvx’s rules.The error is “错误使用 + (line 83)
Disciplined convex programming error:
Illegal operation: {concave} + {log-affine}”. How can I change the expression of the target function or maybe i should use the KKT condition to solve it? I think the cvx’s rules are so demanding.
Thank you for your patience.


(Mark L. Stone) #13

Please show a mathematical representation of your problem and your CVX code, preferably complete with input data.

Have you proved that your optimization problem is convex? Why isn't CVX accepting my model? READ THIS FIRST!


(Linmumuzf) #14

I checked the objective function and found that I ignored a very important detail that caused the objective function to be non-convex. Now I have solved it. Thank you


(Linmumuzf) #15

Hello, what is the role of geo_mean() in the objective function in the cvx rules?


(Mark L. Stone) #16

help geo_mean

geo_mean Geometric mean.
Y=geo_mean(X), where X is a vector, computes the geometrix mean of X. If any
of the elements of X are negative, then Y=-Inf. Otherwise, it is equivalent
to Y=PROD(X).^(1/LENGTH(X)). All elements must be real.

For matrices, geo_mean(X) is a row vector containing the geometric means of
the columns. For N-D arrays, geo_mean(X) is an array of the geometric means
taken along the first non-singleton dimension of X.

geo_mean(X,DIM) takes the geometric mean along the dimension DIM of X.

geo_mean(X,DIM,W), where W is a vector of nonnegative integers, computes a
weighted geometric mean Y = PROD(X.^W)^(1/SUM(W)). This is more efficient
than replicating the values of X W times. Note that W must be a vector,
even if X is a matrix, and its length must be the same as SIZE(X,DIM).

Disciplined convex programming information:
    geo_mean is concave  and nondecreasing; therefore, when used in CVX
    specifications, its argument must be concave.

You can search this forum for geo_mean for examples of its use in CVX.


(Linmumuzf) #17

Thank you very much!