Class 04 - Q&A

[andrewrosemberg]

Thanks @joaquimg for the great presentation!

Opening this discussion forum for students to discuss the topics presented.

[klamike]

Continuing the discussion @kevinwoots @allensctong and I had after class -- how is feasibility handled in SDDP?

What I've seen most is "complete recourse", i.e. changing the formulation to guarantee feasibility of the subproblems. However, I believe there are other methods such as "feasibility cuts". Does anybody know how that works?

[klamike]

Found this post: https://or.stackexchange.com/questions/10804/how-do-you-derive-the-benders-feasibility-cuts

[joaquimg]

Feasibility cuts in SDDP are very hard. There no robust literature on the topic. There is ongoing research that I know.

The most common is just to add slack varaible to make the recourse relative complete.

[klamike]

On the "convexity" requirement; we saw in class that the value function $\alpha(x)$ is convex when the parameters appear only in the RHS (5.6.1 in https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)

In class I mentioned that this is probably not the case when the dynamics are state-dependent, since then instead of $Au+b(x)$, the subproblem constraints would read $A(x)u=b(x)$ where $A$ and $b$ are functions of the parameter $x$. I am wondering if there are some conditions on the underlying control problem that would result in $\alpha(x)$ retaining convexity even with state-dependent dynamics.

[klamike]

Joaquim mentioned that one can avoid scalability issues with multi-cut by using "single-cut" SDDP where multiple cuts are "averaged" to produce one cut. Can anybody point to how this averaging is performed and how it guarantees the validity of the generated cut?

[kevinwoots]

In multicut SDDP, a stage with multiple outcomes produces one cut per outcome. Each cut provides a valid lower bound hyperplane. Taking the probability-weighted sum (i.e. the expected value) of these valid lower bounds will result in a still valid lower bound. This results in the single inequality and the averaged/aggregate cut.

[andrewrosemberg]

From what I naively understand, (adding on the previous answer), the multicut generates a cut per scenario and that cut is a valid lower bound for that scenario (we only guarantee it being a lower bound for the scenario it was generated from at least, right?) . While the average of epigraph variables is a valid lower bound for the entire cost-to-go.

[joaquimg]

Averaging works because of Jensen's inequality. I can send more details later. Birge's book on stochastic programming certainly has a discussion on multi-cut versus average cut Benders. same results apply

[Joeyetinghan]

In SDDP implementations, the random variables are typically modeled through stage-wise independent samples or scenario trees. My question is:

• What assumptions are actually required on the distributions (e.g., finite support, stagewise independence, availability of i.i.d. samples)?
• In practice, are distributions given explicitly, or is it sufficient to provide a sampling oracle?
• How critical is the choice between specifying a parametric distribution vs. working with empirical data?

[joaquimg]

The vanilla SDDP will require:

• stagewise independence
• finite support

In a single stage, the multiple RVs can be correlated (in very non-linear ways).

Finite support can be "modelled" through discretization:

• https://optimization-online.org/wp-content/uploads/2017/09/6201.pdf
• this package contains methods for it: https://msppy.readthedocs.io/en/latest/discretize.html / https://optimization-online.org/wp-content/uploads/2019/05/7199.pdf