Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to transform a non-linear objective function into a linear one, in order to create a LP. How might I go about to do this (I have never taken a course in linear programming).

I have that I would like to maximize the following objective function: $\mu(\alpha)$, where $\mu(\alpha) = \min{U_i(\alpha)}$. $U_i(\alpha)$ denotes the expected utility for player $i$ in a correlated Nash equilibrium and $\alpha$ denotes the corresponding probability distribution played by the players.

The contrains I have so far are the following: $\sum_{a \in A} \alpha(a) = 1$, and $\alpha(a) \ge 0 $ for all $a \in A$. The other contraints that I have are the ones used for a standard correlated equilibrium, namely that: for each player $i$ and pairs of action $a_i^{1}$ and $a_i^{2}$, we have that: $\sum_{a \in A | a_i = a_i^{1} } [u_i(a) - u_i(a_i^{2}, a_{-i})]\alpha(a) \ge 0$.

The first 2 contraints are the ones requiring that $\alpha$ follows a proper probability distribution, and while the last sets are the ones that enforce the correlated equilibrium (by definition). How might I go about to modify this into an LP with the objective function I mentioned above. I know that it's not linear, so I need to change it somehow (and the LP ) appropriately.

Advice is appreciated :)

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

For those who are curious, I ended up realizing that I can define the non-linear objective function as a piece-wise set of linear and concave functions, then adding the appropriate constraint for each of these pieces in the original LP. The remainder of the work fell into place after that.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.