Solution methods and parameters

Standard reformulation

Consider the chance constraint

\[P\left(\sum_{i=1}^k \left(c_i^Tx +d_i\right)z_i \leq b\right) \geq 1-\epsilon\]

where \(z \sim \mathcal{N}(\mu,\Sigma)\) is a vector in \(\mathbb{R}^n\) of jointly normal random variables with mean \(\mu\) and covariance matrix \(\Sigma\). JuMPChance currently only supports a diagonal covariance matrix \(\Sigma\), i.e., all variables are independent, but we present the more general case here. For simplicity, we can introduce a new set of variables \(y_i = c_i^Tx + d_i\) and reduce the constraint to:

\[P\left(y^Tz \leq b\right) \geq 1-\epsilon\]

Recall that \(y^Tz\) is normally distributed with mean \(y^T\mu\) and variance \(y^T\Sigma y\). Then

\[ \begin{align}\begin{aligned}P\left(y^Tz \leq b\right) = P\left(y^Tz - y^T\mu \leq b - y^T\mu\right) = P\left( \frac{y^Tz - \mu^Tz}{\sqrt{y^T\Sigma y}} \leq \frac{b - y^T\mu}{\sqrt{y^T\Sigma y}}\right)\\ = \Phi\left(\frac{b - y^T\mu}{\sqrt{y^T\Sigma y}}\right)\end{aligned}\end{align} \]

where \(\Phi\) is the standard normal cumulative distribution function.

Therefore the chance constraint is satisfied if and only if

\[\Phi\left(\frac{b - y^T\mu}{\sqrt{y^T\Sigma y}}\right) \geq 1- \epsilon\]

or, since \(\Phi^{-1}\) is monotonic increasing,

\[\frac{b - y^T\mu}{\sqrt{y^T\Sigma y}} \geq \Phi^{-1}(1-\epsilon)\]

which is

\[y^T\mu + \Phi^{-1}(1-\epsilon)\sqrt{y^T\Sigma y} \leq b.\]

For \(\epsilon \leq 0\), \(\Phi^{-1}(1-\epsilon) > 0\), so the above constraint is convex and equivalent to

\[||\Sigma^{\frac{1}{2}}y|| \leq (b-\mu^Ty)/\Phi^{-1}(1-\epsilon)\]

which is a second-order conic constraint, where \(\Sigma^{\frac{1}{2}}\) is the square root of \(\Sigma\).

Methods for distributionally robust constraints

Following the notation in the quick start guide, a distributionally robust chance constraint can be formulated as

\[||\Sigma^{\frac{1}{2}}y|| \leq (b-\mu^Ty)/\Phi^{-1}(1-\epsilon)\quad \forall\, \mu \in M, \Sigma \in V\]

This is a convex constraint because it is the intersection of a large (possibly infinite) set of convex constraints. These are challenging to reformulate into an explicit conic form. Instead, we approximate the constraint by a sequence of linear tangents, i.e., given a point \(y\), we detect if the constraint is violated for any choice of \(\mu\) or \(\Sigma\), and if so we add a separating hyperplane which is simple to compute.

solve parameters

The solve method has the following optional keyword parameters when invoked on a JuMPChance model:

  • method::Symbol, either :Reformulate to use the second-order conic formulation or :Cuts to approximate the constraints by a sequence of linear outer-approximations. Defaults to :Reformulate.
  • linearize_objective::Bool, either true or false indicating whether to provide a convex quadratic objective directly to the solver or to use linear outer approximations. Defaults to false.
  • probability_tolerance::Float64, chance constraints are considered satisfied if they actually hold with probability \(1-\epsilon\) minus the given tolerance. Defaults to 0.001.
  • debug::Bool, enables debugging output for the outer approximation algorithm. Defaults to false.
  • iteration_limit::Int, limits the number of iterations performed by the outer approximation algorithm. (In each iteration, a single linearization is added for each violated constraint.) Defaults to 60.
  • objective_linearization_tolerance::Float64, absolute term-wise tolerance used when linearizing quadratic objectives. Defaults to 1e-6.
  • reformulate_quadobj_to_conic::Bool, if true, automatically reformulates a quadratic objective into second-order conic form. This is necessary for some solvers like Mosek or ECOS which don’t support mixing quadratic and conic constraints. Defaults to false except if the solver is ECOS.
  • lazy_constraints::Bool, if true and method==:Cuts, use lazy constraints instead of re-solving the mixed-integer relaxation in a loop. This option is experimental and not yet implemented for distributionally robust problems. Defaults to false.