A decomposition-based crash-start for stochastic programming

In this paper we propose a crash-start technique for interior point methods applicable to multi-stage stochastic programming problems. The main idea is to generate an initial point for the interior point solver by decomposing the barrier problem associated with the deterministic equivalent at the second stage and using a concatenation of the solutions of the subproblems as a warm-starting point for the complete instance. We analyse this scheme and produce theoretical conditions under which the warm-start iterate is successful. We describe the implementation within the OOPS solver and the results of the numerical tests we performed.

We would like to thank the two anonymous referees for their helpful comments which have improved the quality of the manuscript. This research was supported by the Engineering and Physical Sciences Research Council under grant EP/E036910/1.

Authors and Affiliations

1. School of Mathematics and Maxwell Institute, The University of Edinburgh, Edinburgh, UK

   Marco Colombo & Andreas Grothey

Corresponding author

Correspondence to Andreas Grothey.

Appendix

We now give the postponed analysis of the situation of Sect. 4.2 where the crash start point is not constructed from exact μ-centers, but approximate subproblem solutions satisfying conditions (17) and (18) are used.

The following Lemma 5 gives bounds on the resulting error in the relevant components of these points compared to the exact μ-centers. Before we proceed, we need a general result stating how far the components of a point in the \(\mathcal{N}_{2}\)-neighbourhood can deviate from the exact μ-center.

Lemma 4

Let (x _μ ,y _μ ,s _μ ) be the exact μ-center for the linear programming problem

and let \((\tilde{x}_{\mu}, \tilde{y}_{\mu}, \tilde{s}_{\mu})\in\mathcal {N}_{2}(\theta)\) with average complementarity product \(\tilde{x}_{\mu}^{\top}\tilde {s}_{\mu} /n = \mu\). Then there are constants C _x ,C _s >0, only dependent on the problem data and μ, but not on θ, such that

Proof

Let \(\bar{\mu}\in \mathcal {R}^{n}_{+}\) and \((x(\bar{\mu}), y(\bar{\mu}), s(\bar{\mu}))\) be the unique solution to

then we have (x _μ ,y _μ ,s _μ )=(x(μe),y(μe),s(μe)) and there is a \(\tilde{\mu}\in \mathcal {R}^{n}_{+}\), such that

with

Differentiating (19) with respect to a component \(\bar{\mu}_{j}\) of \(\bar{\mu}\) gives

which we can solve for \(\frac{\mathrm {d}{x}(\bar{\mu})}{\mathrm {d}\bar{\mu}_{j}}, \frac{\mathrm {d}{y}(\bar{\mu})}{\mathrm {d}\bar{\mu}_{j}}, \frac{\mathrm {d}{y}(\bar{\mu })}{\mathrm {d}\bar{\mu}_{j}}\) to get

(21a)

(21b)

(21c)

For any \((x, y, s)\in\mathcal{N}_{2}(\theta)\) we have

and hence \(s_{j}^{-1} \le\frac{1}{(1-\theta)\mu}x_{j}\) which yields

Further, from [20, Theorem 3.1] we have the relations

which together with (21c) give the bound

For a bound on \(\|\frac{\mathrm {d}{s}(\bar{\mu})}{\mathrm {d}\bar{\mu}_{j}}\|_{\infty}\) we can rewrite (21b) as

and using \(s_{j}/x_{j} = s_{j}^{2}/(x_{j}s_{j})\le\frac{1}{\mu(1-\theta )}|s_{j}|^{2}\) we obtain

Finally, for a bound on \(\|\frac{\mathrm {d}{y}(\bar{\mu})}{\mathrm {d}\bar{\mu }_{j}}\|_{\infty}\) we can rewrite (21a) as

which yields

By defining

and since 1≤1/(1−θ) we have

Together with (20) we get

 □

Lemma 5

For θ∈(0,1), let \((\tilde{x}_{\mu}^{R}, \tilde{y}_{\mu}^{R},\tilde{\lambda}_{\mu }^{R},\tilde {s}_{\mu}^{R},\tilde{z}_{\mu}^{R})\in\mathcal{N}_{2}^{R}(\theta)\). Then there is a C ₃>0 independent of θ such that

Proof

This is an immediate consequence of Lemma 4. □

From the previous lemma we get that we can bound the difference in the primal–dual first-stage decisions (x,s) of the true μ-center of the full problem \((x_{\mu}(\mathcal {T}), s_{\mu}(\mathcal {T}))\) to the calculated approximate μ-center for the reduced problem \((\tilde{x}_{\mu}^{R}, \tilde{s}_{\mu}^{R})\) by

In the second step of the algorithm we will not find the exact μ-center for all subproblems \(P_{i}(\tilde{x}_{\mu}^{R})\), but rather find points

Again we need a bound on the implied error in the dual components λ _i . According to Lemma 5 there is a C ₃>0 such that

This affects the bound on ∥Δc∥ in the proof of Theorem 1. Finally we are in a position to prove Theorem 2.

Proof of Theorem 2

From (17) and (18) we have that

and therefore

(23)

As in the proof to Theorem 1 let

and consider the problem instance \(P(\tilde{d})\) obtained from \(\mathcal{P}(\mathcal {T})\) by replacing the first-stage cost c with \(\tilde{c}\). Then by construction the crash-start point \(\tilde{w}\) is primal–dual feasible for \(P(\tilde{d})\) and due to (23) satisfies

We will analyse the crash-start as a warm-start attempt for the (perturbed) problem \(P(\mathcal {T})\) starting from a point in the \(\mathcal{N}_{2}\)-neighbourhood for problem \(P(\tilde{d})\). The change in problem data is

with

Using the bounds from Lemma 3 and Lemma 5 we have

Moreover, using the bounds from Lemma 2 we get

(24)

where

Proposition 4.2 of [26] can now be applied with \(\theta_{0} = \tilde{\theta}\sqrt{|\mathcal {T}|+1}\) and \(\xi= \frac{1}{2}(\theta- \tilde{\theta}\sqrt{|\mathcal {T}|+1})\) from which we get

and therefore the conditions for a successful warmstart are

which can be combined to obtain

Combining (24) and (25) we get as the condition for a successful warmstart

which can be satisfied by keeping \(W_{1}(\mathcal {T},\mathcal{T}^{R})\) and \(\tilde{\theta}\) small enough. □

Reprints and permissions