How to use log_sum_exp

(Basem El Halawany) #1

I need to write the following expression in a constraint using log_sum_exp function:

ln [ const1+Sum(const2*exp(x_i) ]

Also, how to write : Sum(exp(x_i))
I tried norm(exp(x),1) but does not work

thanks

(Mark L. Stone) #2

ln [ const1+Sum(const2*exp(x_i) ] is not the log of sum of exponentials, and can not be expressed using log_sum_exp. In fact, it’s not even necessarily convex.

As for Sum(exp(x_i)), you can write it as sum(exp(x)) if x is a vector variable.

How to handle log[exp(exp(x))-1]
(Basem El Halawany) #3

I have tried some mathematical manipulation for it:
const1+Sum(const2*exp(x_i) = exp(ln(const1)) + sum(exp(ln(const2) +x_i))

let z = [ln(const1) , ln(const2) +x_1 , …,ln(const2) +x_N)]

log_sum_exp(z) is accepted by cvx

(Mark L. Stone) #4

How is log_sum_exp(z) equal to your original expression? As I wrote before, ln [ const1+Sum(const2*exp(x_i) ] is not necessarily even convex. You have produced an expression which CVX will accept, but it is not equal to your original expression.

If you think I’m wrong, assign (non-trivial) numerical values to all your variables, including constants, as MATLAB (not CVX) variables, and compute your original expression and your version with log_sum_exp. Show us a reproducible example with complete MATLAB code which does this. Note I am not saying there are no input values in which your expressions come out with the same numerical value.

(Basem El Halawany) #5

Kindly check the following code:
clc;clear all;
N = 1e3;
i_ctr =3;
%% c1,c2, and elements of x_i in my case is greater than zero
c1 = 0.01 + (10-0.01).*rand(1,N);
c2 = 0.01 + (10-0.01).*rand(1,N);
x_i= 0.01 + (10-0.01).*rand(i_ctr,N);

expression1=zeros(1,N);
expression2=zeros(1,N);
for ctr = 1:N
expression1(ctr) = log(c1(ctr)+sum(c2(ctr)*exp(x_i(:,(ctr)))));
%% Expression2
temp =[log(c1(ctr)) ];
for m=1:i_ctr
temp= [temp log(c2(ctr))+x_i(m,ctr)];
end

expression2(ctr)  = log_sum_exp(temp);

end
cheking=[expression1;expression2;expression1-expression2];
%% I noticed some rounding , which appears in somecases
error = sum((round(expression1)-round(expression2))>0)

===============
I assumed i want to convert the constant values to equivalent exponential terms . I assumed:
c2 =exp(newterm2)
by taking ln of both sides, we get:
newterm2= ln(c2)
which I merged (multiplied) with individual elements in x_i
The same applied with c1

Let me know your feedback
Thanks for the discussions

(Mark L. Stone) #6

I am kind of confused by what you’re doing. Maybe we are solving different problems.

Consider the function
f1(x) = log(2-3*exp(x))
which is a one dimensional case of your original expression ln [ const1+Sum(const2*exp(x_i) ] .
The 2nd derivative of f1(x) is negative everywhere, so it is concave.

Now consider
f2(x) = log(2+3*exp(x))
Its 2nd derivative is positive everywhere, so it is convex.

So even in one dimension, your original expression is not necessarily convex, depending on the values of the constants. Am I misunderstanding what expression you want to use in CVX?

(Basem El Halawany) #7

yes you understand it right
but
I mentioned as a comment in my code that within my problem, C1,C2, and all elements of x is non-negative.
So this is similar to your second assumption which is true a convex.

however, if it is a general expression with the parameters can take any value, i agree with you that this will not work.
Sorry , I am just beginning to use cvx and I am really appreciate this forum and your discussions.
:slight_smile:
The DCP rule sets are still confusing me

(Mark L. Stone) #8

Because any log_sum_exp which CVX accepts is convex, then if your original expression can be converted into log_sum_exp which CVX accepts, it must necessarily be convex. Conversely, if your original expression is not convex, it can not be converted into a log_sum_exp which CVX accepts. So ln [ const1+Sum(const2*exp(x_i) ] can not be converted into a log_sum_exp which CVX will accept for a general const1 and const2. Is your transformation somehow only valid for const1 and const2 > 0 because you take log of const?

The bottom line is that if you have produced code which CVX accepts, then the question is whether that CVX code represents the problem you are trying to solve. You need to decide whether that CVX code (using log_sum_exp) represents the problem you want to solve.

I think I got confused (mistaken) on my post before my previous post by inadvertently not taking a log at the end.

(Michael C. Grant) #9

Yes, if C1 and C2 are nonnegative, then this is convex. It violates the DCP rules, however, because it’s relying on undocumented capabilities intended to help support the geometric programming capability of CVX.

The DCP rules really aren’t that difficult. They’re very simple, in fact. But they can be frustrating if you’re not using CVX properly. For instance, trying to get CVX to solve a non-convex problem, or even a convex problem that cannot be expressed using the DCP ruleset, can be frustrating. Even just trying to see “how far you can go” with CVX is challenging.

Some application areas don’t really lend themselves to effective use of CVX for one or more of these reasons.

(ya) #10

Hi,
I have this problem in which objective is convex function but constraint is

log_sum_exp(concave)-Constant<=0.

I am trying to write constraint in convex form. Could you help me in writing it in cvx.
thanks

(Mark L. Stone) #11

help log_sum_exp

log_sum_exp log(sum(exp(x))).
log_sum_exp(X) = LOG(SUM(EXP(X)).

When used in a CVX model, log_sum_exp(X) causes CVX's successive
approximation method to be invoked, producing results exact to within
the tolerance of the solver. This is in contrast to LOGSUMEXP_SDP,
which uses a single SDP-representable global approximation.

If X is a matrix, LOGSUMEXP_SDP(X) will perform its computations
along each column of X. If X is an N-D array, LOGSUMEXP_SDP(X)
will perform its computations along the first dimension of size
other than 1. LOGSUMEXP_SDP(X,DIM) will perform its computations
along dimension DIM.

Disciplined convex programming information:
    log_sum_exp(X) is convex and nondecreasing in X; therefore, X
    must be convex (or affine).

Note that -concave is convex, so you should be able to enter your constraint as written, presuming your -concave expression satisfies CVX’s DCP rules.

(Mark L. Stone) #13

Now that you have edited your post to pertain to log_sum_exp(concave)-Constant <= 0. rather than log_sum_exp(-concave)-Constant <= 0, the constraint is non-convex; so it can not be handled by CVX.

Please read Why isn't CVX accepting my model? READ THIS FIRST!

(ya) #14

Thank you for your answer. I also wanna know I used this function log_sum_exp in fmincon and it worked. Can you comment about this according to my understanding it is cvx library function. Thanks for your help.

(Mark L. Stone) #15

log_sum_exp , as well as many other CVX library functions, can take either numerical or CVX expressions as arguments . There are actually separate versions called depending on the argument type. FMINCON.was calling the numerical version, for which the DCP rules do not apply. Presumably FMINCON was used with finite difference gradient option if you didn’t supply gradient.

FMINCON is a local optimizer. Therefore it does not necessarily find the global minimum when applied to non-convex problems.

(ya) #16

Hi, I am still struggling with the log sum exponent.

I have sum of exp(concave) functions, which is not convex as we agreed about but the following link says it is convex in the form given,

Also,

Let f(x)=e(−x^2) which is example of exp(- convex) is convex if 4x^2-2 is positive function is convex other wise concave. And if it is right then how can I make CVX accept my constraint f(x)-constant <=0. Is it only due to cvx limitation or this function f(x) is not convex for 4x^2-2 >0.

Thanks in advance

(Mark L. Stone) #17

I don;t know what those people are smoking over on that other thread., Put out of your mind everything you see over there. -exp((x) is of that form, and is concave, not convex. With non-affine concave (negative of convex) arguments, it may be neither convex nor concave.

Here is what you need to know. As shown n the help log_sum_exp in one of my previous answers in this thread, the vector argument x of log_sum_exp must be convex (affine is o.k. because it is a special case of convex). If x is convex, you may use log)sum_exp(x) in CVX, otherwise you may not. You are free to use log_sum_exp on any numerical argument, for instance in a user function called by FMINCON.

log_sum_exp(x) is not accepted by CVX if x is concave (unless it affine).

It is unclear to me what constraint you are interested in. Note that log_sum_exp(x) is the log of sum of exponentials. ff the argument is a scalar, then log_sum_exp(x) = x, so thee is no no need to use log_sum_exp.

log_sum_exp(-x^2) = -x^2, which is concave. exp(-x^2) is neither convex nor concave.

(ya) #18

Thanks for your detail response.

Okay I have problem with linear objective
max x
s.th., exp(-a_1 x^2)+exp(-a_2 x^2 ) >= 0.3,
where a_1=0.4 and a_2=2 also x>0.

Now we can write constraint as log_sum_exp( A x^2) >= log(0.3), where A=[-a_1 -a_2]’.

So CVX doesn’t support this constraint but over all the problem is concave and I can use any other optimizer to find a unique solution to this problem.

Is it right? or is there any way (transformation) to write this problem in cvx.

(Mark L. Stone) #19

Your formulation with log_sum_exp is incorrect and hopeless for use in CVX.
exp(-0.4*x^2) + exp(-2*x^2) is neither convex nor concave, and for x > 0, switches from concave below 0.558394 to convex above it. Therefore it can not possibly be formulated in tems of CVX’s log_sum_exp.

The constraint is non-convex. So if that is the problem you want to solve, you will have to use something other than CVX.

(Mark L. Stone) #20

That said, with these values of a_1 and a_2, your inequality simplifies to
0 <= x <= 1.74054065
or if you wanted to allow negative values of x,
-1.74054065 <= x <= 1.74054065
which are accepted by CVX.

if you maximize x only subject to these constraints, the argmax and optimal objective value are 1.74054065. All in all, a rather boring problem, unless there are other constraints.

(ya) #21

Thank.

I tried to write it in cvx for it did not work. How did you code it to work in cvx. Can you please share the peice of code.

Thanks again