# Using max/min operators in linear programming.

I'm currently implementing a Markov Decision Process using the solver GLPK, I'm following the lecture by Vincent Conitzer, and there is a step I don't understand between the theoretical problem and its implementation.

More precisely, I have a set of states $\Sigma$ and a set of actions $A$, such that given two states $s$ and $s'$, $P(s, a, s')$ denotes the probability of going from the state $s$ to the state $s'$ with the action $a$. Moreover, for each state $s$ and each action $a$, $R(s, a)$ denotes the immediate reward of executing the action $a$ from the state $s$.

A policy is a function $\delta : \Sigma \to A$, which decides which action to perform in each state, and the value of a policy $\delta$ for a given state $s$ is given by

$$V^\delta(s) = R(s, \delta(s)) + \beta \sum_{s'} P(s, \delta(s), s') \cdot V^\delta(s')$$ where $\beta$ is a discount factor between 0 and 1. The goal is to find to optimal policy $\delta^*$ which maximises the value for each state. In other words, the problem we are trying to solve is to calculate the function $V^*$ (corresponding to the value of $\delta^*$ such that: $$V^*(s) = \max_{a} \,\,[R(s, a) + \beta \sum_{s'} P(s, a, s') \cdot V^*(s')]$$ Up to this point, I have no problem, but then when I look at how to solve this using linear programming, I find the following (PDF, page 5):

As in the game theory example above, we are confronted with the diﬃculty that we cannot use the max operator in a linear program. The solution is similar. We use the following linear program:

minimize $\sum_{s} V^*(s)$

subject to $\forall s, a \,\, V^*(s) \geq R(s, a) + \beta \sum_{s'} P(s, a, s') \cdot V^*(s')$

The argument about game theory is the following one (page 6 of the previous PDF):

There is an interesting trick in this linear program. We would like to write $u = max_i \sum^n_{j=1} p_j u_1(i, j)$, but this is not linear because of the max operator. So, instead, the linear program requires that $u$ is at least $\sum^n_{j=1} p_j u_1(i, j)$ for every i, thereby forcing it to be at least $max_i \sum^n_{j=1} p_j u_1(i, j)$. Then, in the optimal solution, u will be set exactly to $max_i \sum^n_{j=1} p_j u_1(i, j)$, because we try to minimize u.

My first problem is that I don't see why we using the max operator make the program non linear, and secondly, although this solution works, I am not sure to exactly understand why.

-
Disclaimer: I haven't really studied linear programming formally, so the answer might be obvious. –  userxxxxx Aug 17 '12 at 12:47

For your first question, consider the function $z = \max(x_1,x_2)$. Fix $x_2=1$ and let $x_1$ range over $[0,2]$. Then it is easy to see that $z$ is non-linear, for it is constant for $x_1 \in [0,1]$, but increasing for $x_2 \in [1,2]$.
As to getting around this problem, when you introduce the dummy variable $u$ with the conditions $u \geq \mathbf p_j^T \cdot \mathbf u \;$, notice that these are the only conditions in which $u$ appears. In other words, if $u$ is greater than all such linear combinations, there is nothing preventing it from being smaller. Therefore, in any optimal solution, $u$ must take on the value of one of the $\mathbf p_j^T \cdot \mathbf u \;$ (specifically, the one with the greatest value). Think of $u$ as a ceiling that drops down and settles on the highest point.
My pleasure. The definition of linearity is the same as the one in your link. Fixing $x_2=1$ effectively turns the function in my example into a function of one variable, $f(x_1)=\max(x_1,1)$. If f were linear, then we would have $f(a+b)=f(a)+f(b)$ for all $a,b$; however, $1 = f(0+1) \neq f(0)+f(1) = 1 +1$. –  Théophile Aug 18 '12 at 17:19
The reason for taking the sum of the $v^*$ in the Markov decision problem is that you have multiple $\max$ operators. The goal is to choose a set of actions that will minimize the total cost for all states, in other words, the sum of the $v_s^*$, each of which is the maximum of several values. –  Théophile Aug 18 '12 at 17:28
Thanks, I didn't think of instantiating one argument for the max function, it makes sense now. As for the sum of $v^*$, I guess my confusion comes from the fact that there might several combinations of $v^*$ that could minimize the sum, but then I realize that if you can minimize independently each $v^*$, then this is necessarily the only way to obtain the minimal sum. –  userxxxxx Aug 20 '12 at 9:43