10
$\begingroup$

When reading various papers about two-stage (or multi-stage) stochastic programs with recourse, a common representation of the non-anticipativity constraints is: $$ \sum_{i}H_ix_i=h, $$ where $i$ indexes the scenarios, and the matrices $H_i$ and vector $h$ are typically not specified (see, e.g., this paper by Carøe and Schultz).

Question: What are some common choices of $H_i$ and $h$ used to enforce non-anticipativity? What advantages and disadvantages do these choices have when used algorithmically (in decomposition approaches, etc.)?

$\endgroup$
2
$\begingroup$

Edit: If one define $H_i$ as an operator, not necessarily a matrix, I can think of what happens in progressive hedging and go for something like: $H_i(x_i)=I(x_i−x^*)+1/2(x_i−x^*)^TI(x_i−x^*)$. If in the matrix format: $H_i=1/rIx_i$ and $h=x^*$.

| improve this answer | |
$\endgroup$
1
$\begingroup$

Suppose there are three scenarios $i$ in the second stage and two time steps $t$. With $$ x_1 = \begin{pmatrix} x_{11} \\ x_{12} \\ \end{pmatrix},\quad x_2 = \begin{pmatrix} x_{21} \\ x_{22} \\ \end{pmatrix},\quad x_3 = \begin{pmatrix} x_{31} \\ x_{32} \\ \end{pmatrix}, $$ one obvious choice would be $$ H_1 = \begin{pmatrix} 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{pmatrix},\quad H_2 = \begin{pmatrix} -1 & 0 \\ 1 & 0 \\ 0 & -1 \\ 0 & 1 \\ \end{pmatrix},\quad H_3 = \begin{pmatrix} 0 & 0 \\ -1 & 0 \\ 0 & 0 \\ 0 & -1 \\ \end{pmatrix}. $$ Another possibility:

$$ H_1 = \begin{pmatrix} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ \end{pmatrix},\quad H_2 = \begin{pmatrix} -1 & 0 \\ 0 & 0 \\ 0 & -1 \\ 0 & 0 \\ \end{pmatrix},\quad H_3 = \begin{pmatrix} 0 & 0 \\ -1 & 0 \\ 0 & 0 \\ 0 & -1 \\ \end{pmatrix}. $$ Both with $h = 0$.

Visually, the block structure is more obvious in the latter formulation. I don't see any major advantages or disadvantages by using one or the other.

| improve this answer | |
$\endgroup$

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.