Are there any solvers to Chance Constrained Programming Problems

Question

I'm trying to solve a chance constrained programming (CCP) problem

$\min_x f_0(x, \xi), \text{ such that } \mathbb{P} ( f_i(x, \xi) \ge \alpha_i ) \le \epsilon_i, \text{ where } i = 1,2,\cdots, m$

Most of approaches to solve CCP problems are reformulating the chance constraint into some computationally tractable forms.

For example, the chance constraint $\mathbb{P}(\xi^\intercal x \ge b) \le \epsilon $ can be rewritten in 3 different ways (not equivalent)

1. assume $\xi$ satisfies a Gaussian distribution $\xi \sim N(\bar{\xi}, \Sigma)$, then $\mathbb{P}(\xi^\intercal x \ge b) \le \epsilon $ is equivalent with $b - \bar{\xi}^\intercal x \ge \Phi^{-1}(1-\epsilon) || \Sigma^{1/2} x ||_2 $. This is a deterministic Second Order Cone Constraint. which is convex and will not cause intractable issues. (Please refer to Stephen Boyd's lecture notes for more details)

2. Using the scenario approach in [1] Calafiore, Giuseppe C., and Marco C. Campi. "The scenario approach to robust control design." IEEE Transactions on Automatic Control 51.5 (2006): 742-753. Assume we have many samples $\xi^1, \xi^2,\cdots, \xi^N$ from unknown distribution of $\xi$. The chance constraint $\mathbb{P}(\xi^\intercal x \ge b) \le \epsilon $ is approximated by

\begin{eqnarray} (\xi^1)^\intercal x \ge b\\ (\xi^2)^\intercal x \ge b\\ \vdots\\ (\xi^N)^\intercal x \ge b \end{eqnarray} which is a set of linear (deterministic) inequalities

3. the convex approximation (Bernstein approximation) in [2] Nemirovski, Arkadi, and Alexander Shapiro. "Convex approximations of chance constrained programs." SIAM Journal on Optimization 17.4 (2006): 969-996. I will not write their solutions here since I don't want to scare you away.

All these approaches are reformulating the chance constraint into some computationally tractable forms (by which I mean current solvers like gruobi/cplex/mosek could handle).

I'm wondering are there any scripts (preferably in Matlab or Python) that could convert a chance constraint into a deterministic form using the methods listed above?

Or in the best case, are there any solvers have incorporated the methods above and are able to solve chance constrained programming problems?

Answer 1

This is not an answer. It is another perspective which may point to an answer. I have no references to provide.

Given a real valued continuous function h(x,v), where v will be restricted to D= [-1,1] for sake of illustration, consider some operators M which act on h(x,v) and return a function g(x). Examples of operators are Max, where g(x) is Max h(x,v) for given x and v ranging over D, Min which is defined similarly, Convolve in which g(x) is the integral over D of f(x,v)*w(v) dv, and others. It should be a theorem that , for the class of operators under consideration here, f being continuous implies g=Mf is also continuous.

Now with the vocabulary of operators, I see a related (if not equivalent, then hopefully sufficient) optimization problem: find the value of x that minimizes Mf subject to N_if_i greater than 0 as i ranges over the index set of constraint operators N_i. To keep things continuous I define N_i something like Max(0, (measure of set of v in which h(x,v) greater than alpha_i)- epsilon_i), and M is some operator which is or approximates the min condition of the problem.

I ask in the above that h be continuous because that is what is familiar to me. However there may be weaker conditions like Hoelder or Lipschitz continuity that may also work. If the operators M and N_i are such that the outputs are expressible functions in the language of the solver then one has the desired conversion to a standard constraint problem. Life is often not convenient, so I have suggestions for a workaround.

Approach 1 is essentially Monte Carlo: for a fixed i, to evaluate N_i f_i at a given x, choose a large sample of v_i to feed into f_i, get a large sample of outputs, and do a weighted average of this output sample for the answer.

Approach 2 is to approximate f_i by a piecewise or domainwise step function or linear function, and apply N_i to this substitute for f_I to get an approximation to N_i f_i. There are most likely some assumptions that need to be made on (or restrictions on the coding of the implementation of) N_i to make this worth trying.

Approach 3 depends on the functions being "sufficiently differentiable", which I don't really understand well enough but here is a motivating idea: if h(x,v) is such that it is likely to exceed alpha with probability greater than epsilon, and you move x in a positive direction as indicated by the gradient, then it should be even more likely that h(x',v) is greater than alpha, so you don't move in that direction if you are looking for the constrained set. This approach is inspired by my fragmented memory regarding numerical analysis of PDE's. Hopefully someone who knows what they are talking about will chime in and give a better explanation of approach 3.

All of these have the theme of solving an approximation of the problem in hopes of pointing to a solution of the actual problem. For those like me who are not adept at probability, they may prefer this operator/measure theoretic viewpoint. Of course they require that the solver software call some external routine which implements the operator version.

Gerhard "Hopes To Inspire And Inform" Paseman, 2017.06.24.