Complementarity Problems

Complementarity problems

Complementarity relations arise in a variety of engineering and economics applications, most commonly to express an equilibrium of quantities such as forces or prices. One standard application in engineering arises in contact mechanics, where complementarity expresses the fact that friction occurs only when two bodies are in contact. Other applications are found in structural mechanics, structural design, traffic equilibrium and optimal control.

Economic models

Interest among economists in solving complementarity problems is due in part to increased use of computational general equilibrium models, where for instance complementarity is used to express Walras’ Law, and in part to the equivalence of various games to complementarity problems.

Nonlinear optimization

Some generalizations of nonlinear programming, such as multi-level optimization-in which auxiliary objectives are to be minimized-may be reformulated as problems with complementarity conditions. Also, by formulating the Kuhn-Tucker conditions of a nonlinear optimization model one obtains a complementarity problem, which could be solved by a complementarity solver. In the latter case, however, one requires second-order derivative information of all constraints in the original optimization model.

Complementarity conditions

Complementarity problems are, in general, systems of nonlinear constraints where variables in the system are linked to constraints in the form of complementarity conditions. There are two forms of complementarity conditions, the classical complementarity condition, and its generalization, the mixed complementarity condition.

Classical complementarity conditions

The classical form of a complementarity condition involves a nonnegative variable \(x_i\) and an associated function \(f_i(x)\). It requires that

\[\begin{split}\begin{align} x_i = 0 &\quad\text{and}\quad f_i(x) \geq 0, \text{ or}\\ x_i > 0 &\quad\text{and}\quad f_i(x) = 0. \end{align}\end{split}\]

This condition states that of both inequalities, at least one must reach its bound. Alternatively, one can formulate this complementarity condition as \(x_i \geq 0\), \(f_i(x) \geq 0\) and \(x_i\cdot f_i(x) = 0\).

Mixed complementarity condition

The mixed form of a complementarity condition involves a bounded variable \(l_i\leq x_i\leq u_i\) with an associated function \(f_i(x)\). It requires that

\[\begin{split}\begin{align} x_i = l_i &\quad\text{and}\quad f_i(x) \geq 0, \text{ or}\\ x_i = u_i &\quad\text{and}\quad f_i(x) \leq 0, \text{ or}\\ l_i < x_i < u_i &\quad\text{and}\quad f_i(x) = 0. \end{align}\end{split}\]

This condition states that either \(x_i\) must reach one of its bounds, or the function \(f_i(x)\) must be zero. A mixed complementarity condition can be split into two classical complementarity conditions (albeit by introducing auxiliary variables). The classical complementarity condition, on the other hand, is a special case of the mixed complementarity condition by choosing \(l_i = 0\) and \(u_i = \infty\).

Special cases

By choosing \(l_i = -\infty\) and \(u_i = \infty\), the mixed complementarity condition reduces to the special case

\[x_i \text{ is ``free''}\quad \text{and}\quad f_i(x) = 0.\]

Another special case is obtained when \(l_i = u_i\). The mixed complementarity condition then reduces to

\[x_i = l_i \quad \text{and}\quad f_i(x) \text{ is ``free''}\]

Supported complementarity conditions in AIMMS

All complementarity conditions described above can be represented by associating a variable with a single constraint, which will form the basis for representing complementarity conditions in AIMMS. Consider the inequalities

\[l_{x_i} \leq x_i \leq u_{x_i} \quad\text{and}\quad l_{f_i} \leq f_i(x) \leq u_{f_i}\]

where \(f_i(x)\) is a nonlinear expression, and exactly two of the constants \(l_{x_i}\), \(u_{x_i}\), \(l_{f_i}\) and \(u_{f_i}\) are finite. The six possible cases are enumerated in this table, and are discussed below.

Table 60 Six allowed cases with exactly two finite bounds

Case	\(l_{x_i}\)	\(u_{x_i}\)	\(l_{f_i}\)	\(u_{f_i}\)
1	finite	finite	\(-\infty\)	\(\infty\)
2	finite	\(\infty\)	finite	\(\infty\)
3	finite	\(\infty\)	\(-\infty\)	finite
4	\(-\infty\)	finite	finite	\(\infty\)
5	\(-\infty\)	finite	\(-\infty\)	finite
6	\(-\infty\)	\(\infty\)	finite	finite

Case 1

The case \(l_{x_i} \leq x_i \leq u_{x_i}\) and \(-\infty \leq f_i(x) \leq \infty\) corresponds to the mixed complementarity condition already discussed above:

\[\begin{split}\begin{align} x_i = l_{x_i} &\quad\text{and}\quad f_i(x) \geq 0, \text{ or}\\ x_i = u_{x_i} &\quad\text{and}\quad f_i(x) \leq 0, \text{ or}\\ l_{x_i} < x_i < u_{x_i} &\quad\text{and}\quad f_i(x) = 0. \end{align}\end{split}\]

Case 2

The case \(l_{x_i} \leq x_i \leq \infty\) and \(l_{f_i} \leq f_i(x) \leq \infty\) corresponds to the classical complementarity condition

\[\begin{split}\begin{align} \hat{x}_i = 0 &\quad\text{and}\quad \hat{f}_i(x) \geq 0, \text{ or}\\ \hat{x}_i > 0 &\quad\text{and}\quad \hat{f}_i(x) = 0. \end{align}\end{split}\]

where \(\hat{x}_i = x_i - l_{x_i}\) and \(\hat{f}_i(x) = f_i(x) - l_{f_i}\).

Case 3

The case \(l_{x_i} \leq x_i \leq \infty\) and \(-\infty \leq f_i(x) \leq u_{f_i}\) corresponds to the classical complementarity condition

\[\begin{split}\begin{align} \hat{x}_i = 0 &\quad\text{and}\quad \hat{f}_i(x) \geq 0, \text{ or}\\ \hat{x}_i > 0 &\quad\text{and}\quad \hat{f}_i(x) = 0. \end{align}\end{split}\]

where \(\hat{x}_i = x_i - l_{x_i}\) and \(\hat{f}_i(x) = u_{f_i} - f_i(x)\).

Case 4

The case \(-\infty \leq x_i \leq u_{x_i}\) and \(l_{f_i} \leq f_i(x) \leq \infty\) corresponds to the classical complementarity condition

\[\begin{split}\begin{align} \hat{x}_i = 0 &\quad\text{and}\quad \hat{f}_i(x) \geq 0, \text{ or}\\ \hat{x}_i > 0 &\quad\text{and}\quad \hat{f}_i(x) = 0. \end{align}\end{split}\]

where \(\hat{x}_i = u_{x_i} - x_i\) and \(\hat{f}_i(x) = f_i(x) - l_{f_i}\).

Case 5

The case \(-\infty \leq x_i \leq u_{x_i}\) and \(-\infty \leq f_i(x) \leq u_{f_i}\) corresponds to the classical complementarity condition

\[\begin{split}\begin{align} \hat{x}_i = 0 &\quad\text{and}\quad \hat{f}_i(x) \geq 0, \text{ or}\\ \hat{x}_i > 0 &\quad\text{and}\quad \hat{f}_i(x) = 0. \end{align}\end{split}\]

where \(\hat{x}_i = u_{x_i} - x_i\) and \(\hat{f}_i(x) = u_{f_i} - f_i(x)\).

Case 6:

The case \(-\infty \leq x_i \leq \infty\) and \(l_{f_i} \leq f_i(x) \leq u_{f_i}\) with \(l_{f_i} = u_{f_i}\) corresponds to the first special case of the mixed complementarity condition

\[x_i \text{ is ``free''}\quad \text{and}\quad \hat{f}_i(x) = 0.\]

where \(\hat{f}(x) = f_i(x) - l_{f_i}\).

Case 6:

After the introduction of variables \(x_i^+, x_i^- \geq 0\) and functions

\[\begin{split}\begin{align} f_i^x(x) &= x_i - x_i^+ - x_i^-\\ f_i^+(x) &= f_i(x) - l_{f_i}\\ f_i^-(x) &= u_{f_i} - f_i(x) \end{align}\end{split}\]

the case \(-\infty \leq x_i \leq \infty\) and \(l_{f_i} \leq f_i(x) \leq u_{f_i}\) with \(l_{f_i} < u_{f_i}\) corresponds to a system of three simultaneous complementarity conditions

\[\begin{split}\begin{align} x_i \text{ is ``free''}&\quad \text{and}\quad f_i^x(x) = 0\\ & \\ x_i^+ = 0 &\quad\text{and}\quad f_i^+(x) \geq 0, \text{ or}\\ x_i^+ > 0 &\quad\text{and}\quad f_i^+(x) = 0 \\ & \\ x_i^- = 0 &\quad\text{and}\quad f_i^-(x) \geq 0, \text{ or}\\ x_i^- > 0 &\quad\text{and}\quad f_i^-(x) = 0. \end{align}\end{split}\]

AIMMS support

AIMMS supports the variable-constraint couples with two finite bounds, as discussed above, through the special ComplementaryVariable data type. The declaration and attributes of this data type are discussed in the next section, while Declaration of Mixed Complementarity Models describes the declaration of mixed complementarity models through the common MathematicalProgram declaration.

Well-behaved systems

Like with nonlinear optimization models, not all mixed complementarity systems that can be formulated are well-behaved. For instance, a variable \(x \geq 0\) with an associated constraint \(1-x\geq 0\), only admits the solutions 0 and 1, which would destroy the continuous character of complementarity problems. For systems of complementarity conditions that are not well-behaved, the solution process may produce no, or unexpected results.