CCOpt

CCOpt is an open-source nonlinear programming solver for mathematical programs with complementarity constraints (MPCCs). It is built on top of MadNLP,

Design

CCOpt's problem structure

CCOpt solves MPCCs formulated as

\[ \begin{aligned} \min_{x} \; & f(x) \\ \text{subject to} \quad & g_\ell \leq g(x) \leq g_u \\ & x_0^\flat \leq x_0 \leq x_0^\sharp \\ & x_1^\flat \leq x_1 \perp x_2 \geq x_2^\flat \end{aligned}\]

where $x = (x_0, x_1, x_2) \in \mathbb{R}^n$ is the decision variable, $f: \mathbb{R}^n \to \mathbb{R}$ the objective function, and $g: \mathbb{R}^n \to \mathbb{R}^m$ the nonlinear constraints.

Info

CCOpt assumes that the complementarity constraints port only on a subset of the optimization variables $(x_1, x_2)$.

Warning

For the problem to be well-specified, the variables $x_1$ and $x_2$ should be lower-bounded, with no upper-bound. The variable $x_0$ can be anything.

Algorithms

CCOpt implements several solution algorithms for MPCCs, all based on the interior-point method. The two main algorithms are:

  • CCOpt.RelaxationSolver: implements the relaxation method of Raghunathan & Biegler with proper safeguards.
  • CCOpt.PenaltySolver: implements the $\ell_1$-penalty method of Leyffer & al, with refinements.

In addition, CCOpt implements the crossover described in this article to identify a B-stationarity point with guarantees.

Input format

CCOpt takes as input a MPCC formulated using the package MPCCModels which is built on top of NLPModels. The user has to pass explicitly the indices for the left-hand complementarity variable $x_1$ and the right-hand complementarity variable $x_2$. The problem is specified as

using MPCCModels
mpcc = MPCCModel(nlp, ind_x1, ind_x2)

You can build nlp using your favorite modeler, including:

In addition, CCOpt supports complementarity problems formulated using MathOptComplements, a JuMP extension built for MPCCs.

Linear solvers

CCOpt supports all the sparse linear solvers wrapped inside MadNLP. We recommend using the HSL solvers for fastest performance.