Help with CVX DCP rule


#1

The following unconstrained optimization problem is strictly and jointly concave in all its decision variables (q’s):

max sum_i (u_i/b_i).* q_i - (1 - sum_i ((1/b_i)* q_i)) .* log(1 - sum_j (q_j)) + log(1 - sum_j (q_j)) - sum_i (entr(q_i)./b_i)

All u_i, b_i are scalars.
q is a 1xd vector and the indices i & j represents two different q’s but when we sum over i or j basically we’re summing over the same q vector of d dimension.

The objective function has 4 terms, all are acceptable by CVX except for the second term [(1 - sum_i ((1/b_i)* q_i)) .* log(1 - sum_j (q_j))] is not due to DCP rule.

I’d appreciate any suggestion on how to handle this term to make it acceptable by CVX.


(Mark L. Stone) #2

Do you have a proof of concavity?

How are you concluding that - sum_i (entr(q_i)./b_i) is concave, unless the b_i are negative, which you neglected to tell us?

Do you claim the 2nd term concave on its own, or is it only the entire objective function which is concave? Looking just at the 1D version of this, if I haven’t misread the term, the 2nd derivative of this term changes sign at q = 1 and possibly elsewhere, so this term is neither concave nor convex, so even in 1D will never be accepted by CVX on its own (although could possibly be if part of a larger concave expression and suitably presented, although I don’t see how).


(Michael C. Grant) #3

I’m marking this with the “Nonconvex” tag not because I know for sure that it is, but because it almost certainly is covered by at least one of the sections in the FAQ. I doubt CVX will solve this. I suggest trying a smooth solver.


#4

Thanks for your reply, and I apologize for not making the problem clear.

0 < b_i <= 1 for all i Also, q_i > 0 && sum_i (q_i) < 1 (due to the property of log)

Also, I should mention that there’s a typo, there should not be a minus sign in front of the sum of entropies.

Proof of concavity:

The first term and the third are linear and logarithmic and hence concave. The fourth term is the negative entropy which is known to be concave. here is the proof of the second term’s concavity:
If we take the second derivative, we’ll get
[-1/(1 - sum_j (q_j))] . {(2/b_i) - (1 - sum_i (q_i/b_i)/(1 - sum_j (q_j)))}

Please note that the term in [.] < 0 and the term in {.} > 0 . QED


(Mark L. Stone) #5

I think you’re out of luck because of the need to rely on 0 <= q_i <= 1 for concavity. Having an expression be convex (or concave) on only a portion of its natural domain is usually not compatible with expressing it in CVX, even if you impose constraints constraining to the convex (or concave) region. See mcg’s comment above.


(Michael C. Grant) #6

As the FAQ says, if you can’t prove convexity using the DCP rules, CVX can’t handle it—even if you can prove convexity in other ways (like a derivative test).