Senjuti Posted January 27, 2010 Share Posted January 27, 2010 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 More sharing options...

Kreutzer Posted January 27, 2010 Share Posted January 27, 2010 What are the values of "Pij" here ? Link to comment Share on other sites More sharing options...

hubris Posted January 27, 2010 Share Posted January 27, 2010 Perhaps I am overlooking something, but this seems to be just an integer programming problem. Link to comment Share on other sites More sharing options...

Senjuti Posted January 27, 2010 Author Share Posted January 27, 2010 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? Link to comment Share on other sites More sharing options...

Senjuti Posted January 27, 2010 Author Share Posted January 27, 2010 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? Link to comment Share on other sites More sharing options...

Kreutzer Posted January 27, 2010 Share Posted January 27, 2010 (edited) 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 Link to comment Share on other sites More sharing options...

Senjuti Posted January 27, 2010 Author Share Posted January 27, 2010 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 More sharing options...

Kreutzer Posted January 27, 2010 Share Posted January 27, 2010 (edited) 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 Link to comment Share on other sites More sharing options...

Senjuti Posted January 27, 2010 Author Share Posted January 27, 2010 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 More sharing options...

Kreutzer Posted January 28, 2010 Share Posted January 28, 2010 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 More sharing options...

Senjuti Posted January 28, 2010 Author Share Posted January 28, 2010 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 More sharing options...

Kreutzer Posted January 28, 2010 Share Posted January 28, 2010 (edited) 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 Link to comment Share on other sites More sharing options...

## Recommended Posts

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