2
$\begingroup$

I am new to the math stack exchange community and I am in desperate need of help with some computation in a research paper. I am reading Glasserman's and Broadie's research paper detailing pricing of American options with a stochastic mesh. The full paper can be found here: https://www0.gsb.columbia.edu/faculty/pglasserman/Other/bgh.pdf

My confusion comes from page 40 - 41 of the paper when the authors introduce maximum entropy weights. The following is an excerpt of the paper:


For a fixed node i, the entropy criterion is $L_0 = -\sum_{j=1}^N w_{ij}log(w_{ij})$ This objective is maximized (subject to the sum constraint $\sum_{j=1}^N w_{ij} = 1$) by the uniform distribution, i.e. $w_{ij} = 1/N$. However, to obtain "good" weights we impose further constraints, such as matching the 1st order and higher order moments for the underlying processes. The maximum entropy solution then corresponds to the "most uniform" distribution satisfying the constraints. For a different application of entropy weights in pricing derivative securities, see Avellaneda et al. [2]. As an illustration of the types of constraints we use, consider, for example, the case of a single underlying asset with value $S_{t}(k)$ on path k at time t. Suppose $E[S_{t+\vartriangle t}|St] = e^{r\vartriangle t}S_t$. Then we might impose the constraint that the $w_{kj}$ satisfy$$S_t(k) = e^{-r\vartriangle t}\sum_{j=1}^N w_{kj}S_{t+\vartriangle t}(j)$$ which is the sum taken over all nodes at time $t + \Delta t$. This ensures that the weights $w_{kj}$ correctly "price" the underlying asset itself at node k. Observe that in this example the constraint is linear in the weights. Suppose more generally that at each node i there are K linear constraints given by $$\sum_{j=1}^N B_{kj}w_{ij} = b_k$ for $k = 1...K$$ where B is a K x N matrix and b a K-dimensional vector. (The matrix B and vector b will in general depend on the node i). We incorporate these constraints in the optimization criterion at node i by setting $$L = L_{0} + \lambda_{0}(\sum_{j} w_{ij} - 1) + \sum_{k,j} \lambda_{k} (B_{k,j} - b_{k})w_{i,j} $$ where the $\lambda_k$ are Lagrange multipliers. Notice that we have also imposed $\sum_{j=1}^N w_{ij} = 1$ as a constraint. By explicitly solving the following equations $$\frac{\partial L}{\partial w_{ij}} = 0$$ $$\frac{\partial L}{\partial \lambda_0} = 0$$ we obtain $w_{ij}$ in terms of the Lagrange multipliers and parameters for the constraints as $$w_{ij} = \frac{exp(\sum_k \lambda_k(B_{k,j} - b_k))}{\sum_l exp(\sum_k \lambda_k(B_{k,l} - b_k) }$$ Solving the rest of the constraints given by $\sum_{j=1}^N B_{kj}w_{ij} = b_k$ for $k = 1...K$, therefore, amounts to minimizing the following function with respect to $\lambda$'s ([8]): $$log(\sum_l exp(\sum_k \lambda_k(B_{k,l} - b_k)))$$ We use the Newton-Raphson method to obtain the Lagrange multipliers that minimize this function and solve for the weights. The number of constraints is usually much smaller than the number of weights N and thus the numerical optimization is viable. It should be clear from the presence of the logarithm in (7) that the maximum entropy weights are always positive.


I understand the optimization theory behind the method, but I am stuck on the math. I don't think I quite understand how they are taking derivatives. This is basic stuff I know, but bear with me. How did they derive the equation for $w_{ij}$. I tried for an entire day to derive it given their information but I could not get it to come out as they did. I also do not understand where the index "l" came from in the summation. Furthermore, why does the problem reduce to minimizing $$log(\sum_l exp(\sum_k \lambda_k(B_{k,l} - b_k)))$$

If someone could please help me with this then I would really appreciate it. I am trying to write my own implementation of a stochastic mesh in python but I want to understand all of the math that goes behind it first.

$\endgroup$
2
$\begingroup$

All there is to understand is this: if you have a sum of the form $\sum_i f(x_i)$, the partial derivative with respect to an $x_j$ is $f'(x_j)$ because for an $i\neq j$ the variables are independent. So only the term $j$ has a non-zero derivative. All the rest follows from there. The partial derivative of $L$ with respect to $w_{ij}$ is therefore

$$-\log(w_{ij})-1 + \lambda_0 + \sum_k \lambda_k (B_{k,j}-b_k)$$

Requiring this to be equal to zero (stationarity condition) and rearranging we get

$$w_{ij} = \exp\left(-1 + \lambda_0 + \sum_k \lambda_k (B_{k,j}-b_k)\right)$$

Imposing the condition $\sum_j w_{ij} = 1$ we can show that

$$\exp(1 - \lambda_0) = \sum_j\exp\left(\sum_k \lambda_k (B_{k,j}-b_k)\right)$$

hence the numerator in the formula for $w_{ij}$. The only reason they use $l$ instead of $j$ in the summation is to avoid confusion between the "free" index $j$ in $w_{ij}$ and the index $l$ over which you sum, which is a "dummy" index.

$\endgroup$
1
  • $\begingroup$ Thank you! I made the mistake of changing the index of the derivative along with the summation instead of taking it with respect to some stationary $w_{ij}$. Silly me. $\endgroup$ – glawley Jul 17 '19 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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