Jump to content

How to Solve this optimization problem?


Senjuti

Recommended Posts

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.

Link to comment
Share on other sites

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 by Kreutzer
Link to comment
Share on other sites

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

Link to comment
Share on other sites

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 by Kreutzer
Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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 ...

?

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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 by Kreutzer
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

This website uses cookies to ensure you get the best experience on our website. See our Privacy Policy and Terms of Use