Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
minimizing sum{x(i)*log(x(i))}

Subject: minimizing sum{x(i)*log(x(i))}

From: Ming

Date: 22 Dec, 2008 01:18:03

Message: 1 of 6

Hi,

I have the following minimization problem,

min x(1)*log(x(1)/0.7) + x(2)*log(x(2)/0.3)
s.t. x(1) + x(2) = 1;
                x(1) >= 0;
                x(2) >= 0;
Here is the Matlab code:

*****************************************************
x0 = [0.5 0.5];
lb = [0 0];
options = optimset('LargeScale','on', 'GradObj', 'on', 'Hessian', 'off', 'MaxIter', 20000, 'MaxFunEvals', 20000000, 'TolX', 1e-6, 'TolFun',1e-6,'Display','iter');

[x, fval] = fmincon(@obj,x0,[],[],[],[],lb,[],@constr,options);
*****************************************************

After first iteration, the line search algorithm picks x(1) = 1 and x(2) = 0 making the objective function, derivative and first order optimality measures all NaN. This is because log(0) = -inf and 0*-inf = NaN while mathematically x*log(x) = 0 when x takes on zero.

Mathematically, the optimization problem has bounded solutions. Interesting thing is when I take off the lower bound, the algorithm can quickly find the global minimum with x(1) = 0.7, x(2) = 0.3. However I do need the lower bound constraints because x(1) and x(2) represents probabilities.

Please let me know if you ran into similar situation before or you know how to work around this kind of numerical problem. Thank you very much!

Ming
 

Subject: minimizing sum{x(i)*log(x(i))}

From: Roger Stafford

Date: 22 Dec, 2008 02:05:04

Message: 2 of 6

"Ming " <mingsu@u.washington.edu> wrote in message <gimpsb$ogc$1@fred.mathworks.com>...
> ......
> I have the following minimization problem,
>
> min x(1)*log(x(1)/0.7) + x(2)*log(x(2)/0.3)
> s.t. x(1) + x(2) = 1;
> x(1) >= 0;
> x(2) >= 0;
> Here is the Matlab code:
>
> *****************************************************
> x0 = [0.5 0.5];
> lb = [0 0];
> options = optimset('LargeScale','on', 'GradObj', 'on', 'Hessian', 'off', 'MaxIter', 20000, 'MaxFunEvals', 20000000, 'TolX', 1e-6, 'TolFun',1e-6,'Display','iter');
>
> [x, fval] = fmincon(@obj,x0,[],[],[],[],lb,[],@constr,options);
> *****************************************************
>
> After first iteration, the line search algorithm picks x(1) = 1 and x(2) = 0 making the objective function, derivative and first order optimality measures all NaN. This is because log(0) = -inf and 0*-inf = NaN while mathematically x*log(x) = 0 when x takes on zero.
>
> Mathematically, the optimization problem has bounded solutions. Interesting thing is when I take off the lower bound, the algorithm can quickly find the global minimum with x(1) = 0.7, x(2) = 0.3. However I do need the lower bound constraints because x(1) and x(2) represents probabilities.
>
> Please let me know if you ran into similar situation before or you know how to work around this kind of numerical problem. Thank you very much!
>
> Ming

  You may be using 'fmincon' in order to become familiar with it. However, for the problem you show, there is a much easier approach. Call x(1) = x and x(2) = 1-x. Then you want to find the minimum value of

 f(x) = x*log(x/.7) + (1-x)*log((1-x)/.3)

subject to 0 <= x <= 1. The minimum must occur either at a point where the derivative is zero or at one of the two bounding values. The derivative is

 f'(x) = log(x/.7) + 1 - log((1-x)/.3) - 1 = log(x/(1-x)*.3/.7)

which is zero when

 x/(1-x)*.3/.7 = 1

or

 .3*x = .7*(1-x)
 x = .7

Hence the minimum occurs at either x = 0, x = .7, or x = 1. It is easily checked (via l'Hopital's rule) that there is a minimum of zero at x =.7.

  If you have a problem that actually needs to deal with x*log(x) at x = 0, you would need to define a special function which substitutes zero at x = 0 in order for it to be used as a successful function handle.

Roger Stafford

Subject: minimizing sum{x(i)*log(x(i))}

From: Ming

Date: 22 Dec, 2008 02:44:03

Message: 3 of 6

Hi Roger,

Thanks for your analysis.

I tried a redefined x*log(x) function and it worked. This really helps. My only concern is that whether this will create any instability for the algorithm. But I think it is very unlikely coz numerically x*log(x) approaches 0 as x approaches 0. So it is consistent with the original function except at 0.

thanks again,
Ming
 

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gimskg$egm$1@fred.mathworks.com>...
> "Ming " <mingsu@u.washington.edu> wrote in message <gimpsb$ogc$1@fred.mathworks.com>...
> > ......
> > I have the following minimization problem,
> >
> > min x(1)*log(x(1)/0.7) + x(2)*log(x(2)/0.3)
> > s.t. x(1) + x(2) = 1;
> > x(1) >= 0;
> > x(2) >= 0;
> > Here is the Matlab code:
> >
> > *****************************************************
> > x0 = [0.5 0.5];
> > lb = [0 0];
> > options = optimset('LargeScale','on', 'GradObj', 'on', 'Hessian', 'off', 'MaxIter', 20000, 'MaxFunEvals', 20000000, 'TolX', 1e-6, 'TolFun',1e-6,'Display','iter');
> >
> > [x, fval] = fmincon(@obj,x0,[],[],[],[],lb,[],@constr,options);
> > *****************************************************
> >
> > After first iteration, the line search algorithm picks x(1) = 1 and x(2) = 0 making the objective function, derivative and first order optimality measures all NaN. This is because log(0) = -inf and 0*-inf = NaN while mathematically x*log(x) = 0 when x takes on zero.
> >
> > Mathematically, the optimization problem has bounded solutions. Interesting thing is when I take off the lower bound, the algorithm can quickly find the global minimum with x(1) = 0.7, x(2) = 0.3. However I do need the lower bound constraints because x(1) and x(2) represents probabilities.
> >
> > Please let me know if you ran into similar situation before or you know how to work around this kind of numerical problem. Thank you very much!
> >
> > Ming
>
> You may be using 'fmincon' in order to become familiar with it. However, for the problem you show, there is a much easier approach. Call x(1) = x and x(2) = 1-x. Then you want to find the minimum value of
>
> f(x) = x*log(x/.7) + (1-x)*log((1-x)/.3)
>
> subject to 0 <= x <= 1. The minimum must occur either at a point where the derivative is zero or at one of the two bounding values. The derivative is
>
> f'(x) = log(x/.7) + 1 - log((1-x)/.3) - 1 = log(x/(1-x)*.3/.7)
>
> which is zero when
>
> x/(1-x)*.3/.7 = 1
>
> or
>
> .3*x = .7*(1-x)
> x = .7
>
> Hence the minimum occurs at either x = 0, x = .7, or x = 1. It is easily checked (via l'Hopital's rule) that there is a minimum of zero at x =.7.
>
> If you have a problem that actually needs to deal with x*log(x) at x = 0, you would need to define a special function which substitutes zero at x = 0 in order for it to be used as a successful function handle.
>
> Roger Stafford
>

Subject: minimizing sum{x(i)*log(x(i))}

From: Walter Roberson

Date: 22 Dec, 2008 02:54:16

Message: 4 of 6

Ming wrote:
> This is because log(0) = -inf and 0*-inf = NaN while mathematically x*log(x) = 0 when x
> takes on zero.

No, mathematically x*log(x) is indeterminate when x takes on 0, and if your
code requires 0 * infinity to be any particular real number, the code is
mathematically broken.

One argument sometimes given is:

Let c be any real number. Then limit c/x as x approaches infinity is 0.
Now consider limit c/x * x as x approaches infinity. Do the usual "cancellation"
of the numerator and denominator, to find that limit c/x * x as x approaches infinity
"must be" c. But c was any arbitrary real constant, so 0 * infinity must be simultaneously
equal to all real constants, and therefore the answer to 0 * infinity is indeterminate.

--
.signature note: I am now avoiding replying to unclear or ambiguous postings.
Please review questions before posting them. Be specific. Use examples of what you mean,
of what you don't mean. Specify boundary conditions, and data classes and value
relationships -- what if we scrambled your data or used -Inf, NaN, or complex(rand,rand)?

Subject: minimizing sum{x(i)*log(x(i))}

From: Ming

Date: 22 Dec, 2008 03:34:02

Message: 5 of 6

Hi Walter,

I don't know what you meant by "indeterminate". If we define f(x) = x*log(x) and f(0) = lim{x->0} x*log(x), then f(0) = 0. This way, f(x) is continuous from right at 0.

In your argument, you made a mistake. limit{f(x)*g(x)} does not equal to limit{f(x)}*limit{g(x)}. But the point, 0*inf is indeterminate, is correct. We don't know what value it should take unless we know at what rate 0 and inf are approached.

thanks,
Ming



Walter Roberson <roberson@hushmail.com> wrote in message <2jD3l.8328$cL7.952@newsfe22.iad>...
> Ming wrote:
> > This is because log(0) = -inf and 0*-inf = NaN while mathematically x*log(x) = 0 when x
> > takes on zero.
>
> No, mathematically x*log(x) is indeterminate when x takes on 0, and if your
> code requires 0 * infinity to be any particular real number, the code is
> mathematically broken.
>
> One argument sometimes given is:
>
> Let c be any real number. Then limit c/x as x approaches infinity is 0.
> Now consider limit c/x * x as x approaches infinity. Do the usual "cancellation"
> of the numerator and denominator, to find that limit c/x * x as x approaches infinity
> "must be" c. But c was any arbitrary real constant, so 0 * infinity must be simultaneously
> equal to all real constants, and therefore the answer to 0 * infinity is indeterminate.
>
> --
> .signature note: I am now avoiding replying to unclear or ambiguous postings.
> Please review questions before posting them. Be specific. Use examples of what you mean,
> of what you don't mean. Specify boundary conditions, and data classes and value
> relationships -- what if we scrambled your data or used -Inf, NaN, or complex(rand,rand)?

Subject: minimizing sum{x(i)*log(x(i))}

From: Roger Stafford

Date: 22 Dec, 2008 05:16:01

Message: 6 of 6

Walter Roberson <roberson@hushmail.com> wrote in message <2jD3l.8328$cL7.952@newsfe22.iad>...
> Ming wrote:
> > This is because log(0) = -inf and 0*-inf = NaN while mathematically x*log(x) = 0 when x takes on zero.
>
> No, mathematically x*log(x) is indeterminate when x takes on 0, and if your
> code requires 0 * infinity to be any particular real number, the code is
> mathematically broken.
>
> One argument sometimes given is:
>
> Let c be any real number. Then limit c/x as x approaches infinity is 0.
> Now consider limit c/x * x as x approaches infinity. Do the usual "cancellation"
> of the numerator and denominator, to find that limit c/x * x as x approaches infinity
> "must be" c. But c was any arbitrary real constant, so 0 * infinity must be simultaneously
> equal to all real constants, and therefore the answer to 0 * infinity is indeterminate.

  Walter, I think your response was not entirely to the point. When Ming made the statement you quoted from the original article I believe he was referring to the computational difficulties encountered by 'fmincon' when it assigned x the value 0. When he stated ".... while mathematically x*log(x) = 0 when x takes on zero" it seems clear to me that his meaning, (though inaccurately stated,) was that x*log(x) approaches zero so that it is appropriate to define it as being zero at that point. I do not think he was advocating the fallacious line of reasoning concerning zero times infinity that you were apparently ascribing to him. In any case he made his meaning very clear by the time of his second article.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us