-1
$\begingroup$

I am wondering to know how it is possible to prove that the second-stage value function in a two-stage stochastic program is convex on $x$ and $\xi$? A two-stage stochastic program can be defined as \begin{align}\min&\quad c^\top x+\mathcal{Q}(x)\\\text{s.t.}&\quad Ax=b\\&\quad x \ge 0\end{align} where \begin{align}\mathcal{Q}(x)&= E_{\xi}[Q(x,\xi)] \\Q(x,\xi)&= \min d(\xi)^\top y\\Wy&=h(\xi)-T(\xi)x\end{align}

How is it possible to prove that $Q(x,\xi)$ is convex on both $x$ and $\xi$? For example, when $Q(x,\xi)$ is defined as follows, how to prove the convexity?

\begin{align}\min&\quad\xi_1 y_1+y_2 \\\text{s.t.}&\quad2y_1+3y_2 \ge 1- 2x_1 \\&\quad y_2 \ge \xi_2-x_1-2x_2 \\&\quad y_1,y_2 \ge 0\end{align}

$\endgroup$
2
  • $\begingroup$ Are there any assumptions on the functions $h(\cdot), T(\cdot)$? In your example $T(\xi)$ did not depend on $\xi$ and $h(\xi)$ was just linear. Is that the special case you are interested in? $\endgroup$ – batwing Mar 2 at 5:39
  • $\begingroup$ Those are just linear. Yeah, in my example, $T(.)$ does not depend on $\xi$. But, I wanted to know how to prove it for the general case and if possible, for this example. $\endgroup$ – Katatonia Mar 2 at 5:47
2
$\begingroup$

Standard assumption: we write a general second-stage problem as $Q(x,\xi)=\min_y\{q^\top y\mid Wy=h-Tx\}$ and $\xi=(q,W,T,h)$. In your example $W$ and $T$ are fixed (not stochastic) while $q=(\xi_1,1)$ and $h=(1,\xi_2)$ are stochastic.

Now, $Q(x,\xi)$ is convex in $h$, $T$ and $x$ but is concave in $q$. So, saying that $Q(x,\xi)$ is, in general, convex in $x$ and $\xi$ is wrong, except if $q$ is fixed. $Q(x)$ is the expectation of a convex function and, as such, is convex. In your specific case, the second-stage problem is convex in $x$ and $\xi_2$, and is concave in $\xi_1$

To see that $Q(x,\xi)$ is convex in $h$, $T$ and $x$, simply observe that they appear in the right-hand-side of the problem. Now, a minimization linear program is always convex in its right-hand-side. To prove that an LP is convex in its RHS let $t=h-Tx$. Consider $t_1$ and $t_2$ and $t^{\alpha}=\alpha t_1+(1-\alpha)t_2$ with $\alpha\in[0,1]$. Let $y_1$ and $y_2$ be the optimal solution to $f(t)=\min_y\{q^\top y\mid Wy=t\}$ for $t=t_1$ and $t=t_2$, respectively. It is easy to see that $y^{\alpha}= \alpha y_1+(1-\alpha)y_2$ is feasible for $f(t^{\alpha})=\min_y\{q^\top y\mid Wy=t^{\alpha}\}$ (it satisfies the constraints). However, it is not necessarily optimal. Let $y^{\alpha*}$ be the optimal solution to $f(t^{\alpha})$. We can write \begin{align*}f(t^{\alpha})&=q^\top y^{\alpha*}\leq q^\top y^{\alpha}\\ &=q^\top(\alpha y_1+(1-\alpha)y_2)=\alpha (q^\top y_1)+(1-\alpha)(q^\top y_2)\\ &=\alpha f(t_1)+(1-\alpha)f(t_2)\end{align*} Which proves convexity. To make the proof more rigorous one must specify how the RHS vectors are chosen. This article clarifies that the set of RHSs which make the problem feasible is a polyhedral cone. However, this should suffice for now.

To see that is its concave in $q$ observe that $q$ shows up in the right-hand-side of the dual of $Q(x,\xi)$, which is a maximization linear program. A maximization LP is always concave in its right-hand-side. The proof proceeds with the same steps used to prove convexity above.

$\endgroup$
2
  • $\begingroup$ Thanks for your comment. But, how to prove that " minimization linear program is always convex in its right-hand-side". Another difference with my example is that $\xi_1$ is in the objective function. $\endgroup$ – Katatonia Mar 2 at 17:38
  • 1
    $\begingroup$ A good proof of that statement is given, for example, in R. Wets PROGRAMMING UNDER UNCERTAINTY: THE EQUIVALENT CONVEX PROGRAM 1966 in an appendix. Your $\xi_1$ in the objective function coincides with a component of $q$ in the standard formulation. You have $q=(\xi_1,1)$. $\endgroup$ – k88074 Mar 2 at 20:47

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.