Minimize log(1+1/x) where 0<x<inf

#1

Hi

I am regenerating the results of a paper published in IEEE transactions in wireless communications where they used CVX to solve a convex optimization problem. They are minimizing the following function

Minimize

log_2 (1+\frac{\alpha}{b^H X b +1})+ \lambda. tr(X)
S.T.:
X is a postive semi-definite matrix (covariance matrix).

where \alpha and \lambda are constant scalars. and b is a constant vector.

The above problem is convex. Since X is positive semi-definite, therefore b^H X b > 0.

I tried many ways to formulate this problem using CVX. However, none of them succeeded. e.g.

cvx_begin
variable X(N,N) complex semidefinite
expression summation
summation=summation+log(1+alphainv_pos(b’Xb+1))/log(2)
minimize(summation+lmda
trace(X) )
cvx_end

But I obtain the following error

Error using cvx/log (line 64)
Disciplined convex programming error:
Illegal operation: log( {convex} ).

The authors mentioned that they used CVX to solve this problem. So, I am sure it can be implemented using CVX. Can someone help?

Thanks

(Mark L. Stone) #2

Can you reformulate in terms of minimizing

-log(concave function)

for some concave function? Note that to follow CVX’s rules, the argument of log must be a concave function. Then the log will be a concave function.

Note that your title question is easily handled as
minimize(-log(x))

#3

Thank you Mark for your quick response.

I tried a lot to formulate it in the form of -log (concave fn.) but unfortunately I couldn’t.

The authors must have found some work around to make CVX accept the formulation and that’s what I am trying to figure out.

Sorry for the title. It should have been log (1+1/x). I have updated that.

(Dinh) #4

May be you should try to minimize -log(x/(1+x))

(Mark L. Stone) #5

@Marc , I don’t see you to get -log(x/(1+x)) accepted by CVX. Specifically, x/(1+x) is indeed concave for x > 0, but I don’t see how to get it accepted.

@mohamedmarzban ,log(1+1/x) is convex for x > 0, but I don’'t know how it can be entered in CVX, and suspect it can not. Perhaps you can email the article authors and inquire how they used CVX.

#6

Thanks again Mark for your reply.

Actually, I emailed the first author but he did not answer. Maybe I will email the second author.

Thanks.

(Michael C. Grant) #7

You should reach out to the authors to find out how they formulated their problem in CVX.

(Michael C. Grant) #8

Oops, sorry, I didn’t scroll down enough. I see you’ve already reached out to them.

Frankly, while I greatly appreciate all of the citations for CVX in academic papers, I find that this kind of situation happens quite often—authors do not publish the models they use, so there’s no way to reproduce their work.

(Dinh) #9

Sorry for the late answer. May be you can rewrite your problem in the following form

minimize y
such that log(1 + 1/x) \leq y

which is equivalent to

minimize y
such that exp(-y) + exp(-y-log(x)) \leq 1

The following code is working at least

cvx_begin
variables x y
minimize( y )
exp(-y) + exp(-y - log(x) ) <= 1
cvx_end

Log{convex} log(1+1/(1+x))
(Dexin Wang) #10

This should work
log(1+1/x) = log((1+x)/x) = -log(x/(1+x)) = -log(1 - 1/(1+x)) = -log(1 - inv_pos(1+x))

(Mark L. Stone) #11

Indeed, @Dexin_Wang’s solution works. I then reformulated to use rel_entr , per CVXQUAD: How to use CVXQUAD’s Pade Approximant instead of CVX’s unreliable Successive Approximation for GP mode, log, exp, entr, rel_entr, kl_div, log_det, det_rootn, exponential cone. CVXQUAD’s Quantum (Matrix) Entropy & Matrix Log related functions so as to invoke CVXQUAD, and received the following error, in CVX 2.1, which seems like a bug to me

cvx_begin
variable x
rel_entr(1,1 - inv_pos(1+x))
=====================================
Using Pade approximation for exponential
cone with parameters m=3, k=3
=====================================
Error using cvxprob/newcnstr (line 192)
Disciplined convex programming error:
Invalid constraint: {concave} == {real affine}

Error in cvxprob/newcnstr (line 72)
newcnstr( prob, x{k}, y{k}, op );

Error in  ==  (line 3)
b = newcnstr( evalin( 'caller', 'cvx_problem', '[]' ), x, y, '==' );

Error in cvx/rel_entr (line 80)
{ -q, xt, yt } == exponential( sz ); %#ok

(Mark L. Stone) #12

However, in Writing x*log(1+x/y) ,the wizard of conic reformulation,@Michal_Adamaszek
produced the result
x*log(1+x/y) = rel_entr(x+y,y) + rel_entr(y,x+y)

Setting x = 1, then Interchanging the roles of x and y so as to match the problem in this thread, results in
log(1 + 1/x) = rel_entr(x,x+1) + rel_entr(x+1,x)
The RHS is accepted by CVX, and as a bonus, is already in a form needed by CVXQUAD. It executes without error.

And you can see how to formulate the matrix analog using CVXQUAD’s quantum_rel_entr at Perspective of log det function, and CVX formulations of related log det problems using Quantum Relative Entropy from CVXQUAD .