How to Solve this optimization problem?

[Senjuti]

I need to solve this multi variable optimization problem of the following form

Objective function:

Maximize

Sum(j=1...z)[Mult(i=..m)[ai*Pij + (1-ai)(1-Pij)]]

here (a1, a2,...,am) are m boolean variables, can have values only 0 or 1.

Can anyone please help?

I need to know which method can be used to solve this optimization. I will also have a set of constraints which I am not writing down there.

Finally, since this objective function seems to have a very high degree in m, which (numerical)approximation method could be used to solve such a function approximately?

Appreciate your help.

[Kreutzer]

What are the values of "Pij" here ?

[hubris]

Perhaps I am overlooking something, but this seems to be just an integer programming problem.

[Senjuti]

What are the values of "Pij" here ?

thanks Pijs are probabilities...

0<Pij<1

I wonder which method to use to solve this.. since the objective function is horrendous...

Also is there any approximation possible for such functions?

[Senjuti]

Perhaps I am overlooking something, but this seems to be just an integer programming problem.

thanks,

the objective function is horrendous.. How to solve this efficiently?

[Kreutzer]

I don't see any problem here given constraints for P(j).

The maximum of the given function is equal to "z" (number of terms in the sum), isn't it?

For instance, just set all a(i)=P(i,j) = 1 and you will obtain this supremum.

Edited January 27, 2010 by Kreutzer

[Senjuti]

I don't see any problem here given constraints for P(j).

The maximum of the given function is equal to "z" (number of terms in the sum), isn't it?

For instance, just set all a(i)=P(i,j) = 1 and you will obtain this supremum.

Thanks... However, here is the problem:

first of all pij's can not be 1 considering my application.

But let's say, I consider this kind of constraints. such as,

if pij > 1/2 , ai = 1.

This is also not possible, cause the outer loop (sum) runs from j= 1..., z, and it would be infeasible to consider constraints like this:

if

p11 > 1/2 , a1 = 1

p12 > 1/2 , a1 = 1

..

p1z > 1/2, a1 = 1

[Kreutzer]

Your problem formulation is still quite obfuscating, cannot understand what the real problem is.

Can you reformulate it more precisely?

e.g.

first of all pij's can not be 1 considering my application.

Why not? What is your "application"? Is it still math or programming problem?

Edited January 27, 2010 by Kreutzer

[Senjuti]

Your problem formulation is still quite obfuscating, cannot understand what the real problem is.

Can you reformulate it more precisely?

e.g.

Why not? What is your "application"? Is it still math or programming problem?

It is a computer science problem.. More precisely this is what the problem wants to do:

Naive Bayes Classifier is a probabilistic classifier which is based on Bayes Theorem and work under the assumption of independence between the variables.

Without going into too much details of the actual problem ( since it is a database related problem and I have to use lots of jargon

We want to maximize this objective function which is based on Naive Bayes Classifier:

sum(j=1..z) [P(Tj | a1, a2......,am) ]

Applying Bayes Theorem

P(Tj | a1, a2......,am) = P(j) * mult(i=1..m)[P(ai | j)]

Therefore, the objective function is :

sum(j=1..z)[P(j) * mult(i=1..m)[P(ai | j)]]

Now, a1, a2,...,am are m boolean variables and can have values 0 or 1.

Now, let pij1 = P(ai=1 | j)

and pij0 = P(ai=0 | j)

also, pij1 + pij0 = 1

Therefore,

I rewrite the objective function as follows:

Maximize,

sum(j=1..z)[P(j) * mult(i=1..m)[ai * pij1 + (1-ai)*(pij0)]]

=sum(j=1..z)[P(j) * mult(i=1..m)[ai * pij1 + (1-ai)*(1-pij1)]]

objective function,

Maximize,

sum(j=1..z)[P(j) * mult(i=1..m)[ai * pij + (1-ai)*(1-pij)]] (just replacing pij1 with pij)

we can not consider constraints like,

a1 = 1, if p11 >1/2,

a1 = 1, if p12>1/2,

.

.

.

.

a1= 1, if p1z>1/2.

If there was no outer loop (the sum loop, which runs from 1..z), I could add constraints as you suggested and could solve the problem easily.

appreciate your time.. Thanks!

[Kreutzer]

Sorry, but I'm totally confused now.

You say:

"sum(j=1..z) [P(Tj | a1, a2......,am) ]"

What is "Tj" here? Is there any difference in your notation between P(Tj) and P(j)?? Also, if P is the probability measure, then "a1, a2 ..." must be EVENTS, while as I see here they are random discrete variables, aren't they?

Let's make it straight, can you rewrite it like optimization problem in form:

Maximize ... subject to constraints ...

?

[Senjuti]

Sorry, but I'm totally confused now.

You say:

"sum(j=1..z) [P(Tj | a1, a2......,am) ]"

What is "Tj" here? Is there any difference in your notation between P(Tj) and P(j)?? Also, if P is the probability measure, then "a1, a2 ..." must be EVENTS, while as I see here they are random discrete variables, aren't they?

Let's make it straight, can you rewrite it like optimization problem in form:

Maximize ... subject to constraints ...

?

My Bad...

I used one more notation :

P(Tj) = P(j) (hope that clears up your confusion)

Maximize,

sum(j=1..z)[P(j) * mult(i=1..m)[ai * pij + (1-ai)*(1-pij)]]

s.t.

there would be given values for pijs and P(j)s

thanks

[Kreutzer]

If both P(j) and p(i,j) are constants from the [0; 1] interval, then you have the simplex points as the terms of the product.

Just set:

a(i) = 1 if p(i,j)>1/2

a(i) = 0 if p(i,j)<1/2

which will maximize your expression.

Edited January 28, 2010 by Kreutzer