Given the following deterministic equivalent definition of two-stage stochastic linear problems:

\[K = \min_{x} \left\{ c^T{x} + \sum_{k=1}^{M} p_kq_k^Ty_k ~|~ Ax = b; T_kx + W_ky_k = h_k; y_k \geq 0, x \geq 0 \,\,\forall ~k=1,2, \ldots M \right\} \]

where \((T_k, W_k, h_k, y_k)\) occurs with probability \(p_k > 0 ~\forall ~k = 1,2, \ldots, M\)

Now, I want to prove the following claim:

For \(M \geq 2\),

\[K \neq p_1 \min_{x} \left\{c^{T}x + q_1^{T} y_1 ~|~ Ax = b; T_1 x + W_1 y_1 = h_1; y_1 \geq 0, x \geq 0 \right\} + \\ \ldots + p_M min_{x} \left \{c^{T}x + q_M^{T} y_M ~|~ Ax = b; T_M x + W_M y_M = h_M; y_M \geq 0, x \geq 0 \right\}\]

1st approach:

First, since \(\sum_{k=1}^{M}p_k = 1\), I planned to establish

\[min_{x} \left\{c^Tx + \sum_{k=1}^{M} p_kq_k^Ty_k ~|~ Ax = b; T_kx + W_ky_k = h_k; y_k \geq 0, x \geq 0 ~\forall ~k=1,2,\ldots M \right\} \\ > \sum_{k=1}^{M} min_{x} \left\{p_kc^Tx + p_kq_k^Ty_k ~|~ Ax = b; T_kx + W_ky_k = h_k; y_k \geq 0, x \geq 0 \right\}\]

However, such inequality seems not to always hold, as we know nothing about the signs of the coefficients of the objective function, besides the fact that the constraints form a polyhedron as a feasible region. The reverse sign is also not correct for every cases, I think. So I abandon this approach.

2nd approach:

Define optimal solutions \(x^{*}\) for K, and \(x_{1}^{*},x_{2}^{*}, \ldots, x_{M}^{*}\) for

\(\min_{x} \left\{p_kc^Tx + p_kq_k^Ty_k ~|~ Ax = b; T_kx + W_ky_k = h_k; y_k \geq 0, x \geq 0 \right\} ~\forall ~k=1,2,\ldots, K\)

By the sake of contradiction, assume

\[K = \sum_{k=1}^{M} \min_{x} \left\{p_kc^{T}x + p_kq_k^{T} y_k ~|~ Ax = b; T_{k}x + W_{k} y_k = h_k; y_k \geq 0, x \geq 0 \right\}\]

This is equivalent to: \(c^Tx^{*} = \sum_{k=1}^{M} p_{k} c^{T} x_k^{*}\).

However, note that \(Ax^{*} = Ax_{1}^{*} = Ax_{2}^{*} = \ldots = Ax_{M}^{*}\), and \(T_kx^{*} = T_kx_{1}^{*} = \ldots = T_kx_{M}^{*}\). So, does the first set of equality imply \(x^{*} = x_{1}^{*} = x_{2}^{*} = \ldots = x_{M}^{*}\), if \(A\) is an invertible matrix? But if that's the case, shouldn't this means \(\sum_{k=1}^{M} p_kc^Tx_k^{*} = c^Tx^{*} \sum_{k=1}^{M} p_k = c^Tx^{*}\) (since \(\sum_{k=1}^{M}p_k = 1\))? But this implies the claim above is wrong...

My question: Could someone please help review my attempt above, and let me know how you could arrive at the desired contradiction, or if the claim is actually false? Any other suggestions for other approaches would be really appreciated.

asked 28 Feb '18, 03:19

ghjk's gravatar image

accept rate: 0%

edited 01 Mar '18, 13:40

fbahr's gravatar image

fbahr ♦

FYI -- FAQ: Hey, How do I get that fancy math stuff? > "We have MathJax installed. Use latex between "\\[" and "\\]" for display math and "\\(" and "\\)" for inline math. Within latex, all backslashes must be doubled." (Sort of paraphrasing here...) -- Also, markdown symbols such as * have to be escaped > "\*".

(01 Mar '18, 13:22) fbahr ♦

@fbahr: Thank you so much for your help. I think the problem statement above is false. Could you give it a try?

(04 Mar '18, 00:38) ghjk
Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 28 Feb '18, 03:19

Seen: 910 times

Last updated: 04 Mar '18, 00:38

OR-Exchange! Your site for questions, answers, and announcements about operations research.