Systems

A system in IBEX is a set of constraints (equalities or inequalities) with, optionnaly, a goal function to minimize and an initial domain for variables. It corresponds to the usual concept of system in mathematical programming. Here is an example of system:

Minimize \(x+y,\)

\(x \in[-1,1], y\in[-1,1]\)

such that

\(x^2+y^2\le1\)

\(y\ge x^2\).

One is usually interested in solving the system while minimizing the criterion, if any.

Class and Fields

The class for representing a system is System.

Systems fields

A system is not as simple as a collection of any constraints because each constraint must exactly relates the same set of arguments. And this set must also coincide with that of the goal function. Many algorithms of IBEX are based on this assumption. This is why they requires a system as argument (and not just an array of constraints). This makes systems a central concept in IBEX.

A system is an object of the System class. This object is made of several fields that are detailed below.

  • const int nb_var: the total number of variables or, in other words, the size of the problem. This number is basically the sum of all arguments’ components. For instance, if one declares an argument x with 10 components and an argument y with 5, the value of this field will be 15.

  • const int nb_ctr: the number of constraints.

  • Function* goal: a pointer to the goal function. If there is no goal function, this pointer is NULL.

  • Function f: the (usually vector-valued) function representing the constraints. For instance, if one defines three constraints: \(x+y\leq0,\ x-y=1\), and \(x-y\geq0\), the function f will be \((x,y)\mapsto (x+y,x-y-1,x-y)\). Note that the constraints are automatically transformed so that the right side is 0 but, however, without changing the comparison sign. It is however possible to normalize a system so that all inequalities are defined with the \(\le\) sign (see ).

  • IntervalVector box: when a system is loaded from a file, a initial box can be specified. It is contained in this field.

  • Array<NumConstraint> ctrs: the array of constraints. The Array class of IBEX can be used as a regular C array.

Auxiliary functions

(to be completed)

Creating systems (in C++)

The first alternative for creating a system is to do it programmatically, that is, directly in your C++ program. Creating a system in C++ resorts to a temporary object called a system factory. The task is done in a few simple steps:

  • declare a new system factory (an object of SystemFactory)

  • add arguments in the factory using add_var.

  • (optional) add the expression of the goal function using add_goal

  • add the constraints using add_ctr

  • create the system simply by passing the factory to the constructor of System

Here is an example:

Variable x,y;

SystemFactory fac;
fac.add_var(x);
fac.add_var(y);
fac.add_goal(x+y);
fac.add_ctr(sqr(x)+sqr(y)<=1);

System sys(fac);

If you compare the declaration of the constraint here with the examples given here, you notice that we do not list here the arguments before writing sqr(x)+sqr(y)<=1. The reason is simply that, as said above, the goal function and the constraints in a system share all the same list of arguments. This list is defined via add_var once for all.

System Transformation

We present in this section the different transformations that can be applied to a system.

Copy

The first transformation you can apply on a system is a simple copy. Of course, this is done via the copy constructor of the System class.

When calling the copy constructor, you can decide to copy everything, only the equations or only the inequalities. For this, set the second parameter of the constructor to either:

value

def

COPY

duplicate all the constraints

INEQ_ONLY

duplicate only inequalities

EQ_ONLY

duplicate only equalities

The first argument of the constructor is the system to copy of course.

	output << "original system:"         << endl;
	output << "-------------------------"<< endl;
	output << sys;
	output << "-------------------------"<< endl << endl;

	System sys2(sys,System::INEQ_ONLY);

	output << "system with only inequalities" << endl;
	output << "-------------------------"<< endl;
	output << sys2;
	output << "-------------------------"<< endl << endl;

The display is:

original system:
-------------------------
variables: 
  x, y
box: 
  ([-inf, inf] ; [-inf, inf])
goal: 
  (none)
constraints:
  ((x^2+y^2)-1)<=0
  (y-x^2)>=0
  ((y+x)-1)=0
-------------------------

system with only inequalities
-------------------------
variables: 
  x, y
box: 
  ([-inf, inf] ; [-inf, inf])
goal: 
  (none)
constraints:
  ((x^2+y^2)-1)<=0
  (y-x^2)>=0
-------------------------

Normalization

It is confortable in some situations to assume that a system is made of inequalities only, and that each inequality is under the forme \(g(x)\le0\), that is, it is a “less or equal” inequality. This is called a “normalized” system.

This need arises, e.g., in optimization methods where the calculation of Lagrange multipliers is simplified when the normalization assumption holds.

It is possible to automatically transform a system into a normalized one. The process is immediate. If a constraint is:

  • \(g(x)\le0\)

    it is already normalized so it is left unchanged.

  • \(g(x)<0\)

    it is replaced by \(g(x)\le0\) (yes, there is a little loss of precision here)

  • \(g(x)>0\) or \(g(x)\ge0\)

    it is replaced by \(-g(x)\le0\)

  • \(g(x)=0\)

    it is replaced by two constraints: \(g(x)\le0\) and \(-g(x)\le0\). It is also possible to introduce an inflation value or “thickness”, that is, to replace the equality by \(g(x)\le\varepsilon\) and \(-g(x)\le \varepsilon\) where \(\varepsilon\) can be fixed to any value.

Note: There is a special treatment for “thick equalities”, that is, equations of the form \(g(x)=[l,u]\). This kind of equations appear often in, e.g., robust parameter estimation problems. In this case, the equality is replaced by two inequalities, \(g(x)\le u\) and \(-g(x)\le-l\), and the \(\varepsilon\)-inflation is not applied unless \(|u-l|<\varepsilon\).

Normalization is done by calling the constructor of NormalizedSystem, a sub-class of System. Here is an example where sys is a system built previously:

	output << "original system:"         << endl;
	output << "-------------------------"<< endl;
	output << sys;
	output << "-------------------------"<< endl << endl;

	// normalize the system with a "thickness"
	// set to 0.1
	NormalizedSystem norm_sys(sys,0.1);

	output << "normalized system:"       << endl;
	output << "-------------------------"<< endl;
	output << norm_sys;
	output << "-------------------------"<< endl;

We get the following display:

original system:
-------------------------
variables: 
  x, y
box: 
  ([-inf, inf] ; [-inf, inf])
goal: 
  (none)
constraints:
  ((x^2+y^2)-1)<=0
  (y-x^2)>=0
  ((y+x)-1)=0
-------------------------

normalized system:
-------------------------
variables: 
  x, y
box: 
  ([-inf, inf] ; [-inf, inf])
goal: 
  (none)
constraints:
  ((x^2+y^2)-1)<=0
  (-(y-x^2))<=0
  ((y+x)+[-1.1,-1.09999])<=0
  ((-(y+x))+[0.9,0.900001])<=0
-------------------------

Extended System

An extended system is a system where the goal function is transformed into a constraint.

For instance, the extension of the system given above:

Minimize \(x+y,\)

\(x \in[-1,1], y\in[-1,1]\)

such that

\(x^2+y^2\le1\)

\(y\ge x^2\).

is the following unconstrained system of constraints:

\(x \in[-1,1], y\in[-1,1], \mbox{__goal__}\in(-\infty,\infty)\)

such that

\(x+y=\mbox{__goal__}\)

\(x^2+y^2\le1\)

\(y\ge x^2\)

Once built, an extended system is a system like any other one, but it has also some extra information:

  • the name of the goal variable which is automatically generated (it is “__goal__” in our previous example).

  • the index of the goal variable (the last (2) in our previous example)

  • the index of the “goal constraint” (the first (0) in our previous example)

For this reason, an extended system is represented by a subclass of System named ExtendedSystem.

To create an extended system just use the constructor of ExtendedSystem. We assume in the following example that the variable sys is a System previously built.

	output << "original system:"         << endl;
	output << "-------------------------"<< endl;
	output << sys;
	output << "-------------------------"<< endl;
	output << "  number of variables:"   << sys.nb_var  << endl;
	output << "  number of constraints:" << sys.nb_ctr  << endl << endl;

	ExtendedSystem ext_sys(sys);

	output << "extended system:"         << endl;
	output << "-------------------------"<< endl;
	output << ext_sys;
	output << "-------------------------"<< endl;
	output << "  number of variables:"   << ext_sys.nb_var << endl;
	output << "  number of constraints:" << ext_sys.nb_ctr << endl;
	output << "  goal name:"             << ext_sys.goal_name() << endl;
	output << "  goal variable:"         << ext_sys.goal_var() << endl;
	output << "  goal constraint:"       << ext_sys.goal_ctr() << endl;

We get the following display:

original system:
-------------------------
variables: 
  x, y
box: 
  ([-inf, inf] ; [-inf, inf])
goal: 
  (x+y)
constraints:
  ((x^2+y^2)-1)<=0
  (y-x^2)<=0
-------------------------
  number of variables:2
  number of constraints:2

extended system:
-------------------------
variables: 
  x, y, __goal__
box: 
  ([-inf, inf] ; [-inf, inf] ; [-inf, inf])
goal: 
  __goal__
constraints:
  ((x+y)-__goal__)=0
  ((x^2+y^2)-1)<=0
  (y-x^2)<=0
-------------------------
  number of variables:3
  number of constraints:3
  goal name:__goal__
  goal variable:2
  goal constraint:0

Kuhn-Tucker conditions

The generalized Kuhn-Tucker (aka kkt) conditions can be obtained from a system. This produces a new system of n+M+R+K+1 variables where

  • n is the number of basic variables (the ones of the original system)

  • M is the number of Lagrange multipliers for inequalities (i.e., the number of inequalities in the original system)

  • R is the number of Lagrange multipliers for equalities (i.e., the number of equalities in the original system)

  • K is the number of Lagrange multipliers for bounding constraints. These bounding constraints correspond to the box field of the original system which is taken into account as 2n additional inequalities.

  • The last variable is the “special coefficient” of the goal function that is equal to 0 in the case where constraint qualification (linear independency of constraints gradients) does not hold.

Generation of the KKT conditions is based on Applying a function with numerous arguments.

Example:

	output << "original system:"         << endl;
	output << "-------------------------"<< endl;
	output << sys;
	output << "-------------------------"<< endl;

	KuhnTuckerSystem kkt(sys,true);

	output << "kkt system:"       << endl;
	output << "-------------------------"<< endl;
	output << kkt << endl;
	output << "-------------------------"<< endl;
	output << "  number of variables:" << kkt.nb_var << endl;

We get the following display. The variable _u is the coefficient of the goal function. The variable _l is the multiplier of the constraint.

original system:
-------------------------
variables: 
  x, y
box: 
  ([-inf, inf] ; [-inf, inf])
goal: 
  (x+y)
constraints:
  ((x^2+y^2)-1)<=0
-------------------------
kkt system:
-------------------------
variables: 
  x, y, _u, _l
box: 
  ([-inf, inf] ; [-inf, inf] ; [0, 1] ; [0, 1])
goal: 
  (none)
constraints:
  ((_u+_l)-1)=0
  (_u+(2*(_l*x)))=0
  (_u+(2*(_l*y)))=0
  ((x^2+y^2)-1)<=0
  (_l*((x^2+y^2)-1))=0

-------------------------
  number of variables:4