The HullConsistency, Simp2B and HullIConsistency procedures

The idea underlying this simplification procedure (known in the community of constraint programming as the hull-consistency or 2B-consistency) is to rewrite the equation and check if it is consistent at each time. For example imagine that one of the equation is $x^2-2x+1=0$. The procedure will introduce a new variable $X$ such that $X=2x-1$ and compute its interval evaluation. As $X$ should be equal to $x^2$ if $X$ has a negative upper bound the simplification procedure will return -1, which indicate to the solving algorithm that it may discard the current input interval. If the upper bound $U$ of $X$ is positive the procedure will check if $x$ lie in $[-\sqrt{U},\sqrt{U}]$ and update the interval for $x$ if this is not the case.

In a second step the procedure will introduce another new variable $Y$ such that $Y=(x^2+1)/2$ and compute its interval evaluation. As $Y$ should be equal to $x$ the procedure will check if the interval value for $Y$ is consistent with the interval value for $x$ and if not update the interval for $x$ accordingly.

The HullConsistency and HullIConsistency procedures of ALIAS-Maple partly implements this principle respectively for equalities and inequalities. They may be used if any of the equation has linear or square terms in the unknown (e.g. $x*y, x^2*y$). The procedure will isolate the linear and square terms of each unknown and produce the C++ code that will check is their interval evaluation is consistent.

The syntax of the HullConsistency procedure is:

 
HullConsistency([x^2+y^2-1,x*y-1],[x,y],"Simp");

The first argument is a list of equations, the second a list of variable names and the third argument is the name of a file. In the above example the procedure will create the C++ program Simp.C that may be later be given to a solving procedure.

Until version 2.4 was a HullConsistencyStrong procedure available, that has been contributed by G. Chabert. The procedure was intended to deal with terms that were different from linear and square terms that are managed by HullConsistency. Its drawback was that it was based on a semantic tree of the expression and was not able to decrease the dependency problem. For example if the expression is

$$x^2+x*y+x$$

and the final node is $x^2$, then the 2B will be implemented using

$$x^2 = -x*y-x$$

while HullConsistency will use

$$x^2= -x*(y-1)$$

which is more efficient. For example in the equation

$$\sin(x_1+x_2)\cos(x_1^2)*x_2+x_1=0$$

we will use

$$\sin(x_1+x_2)=\frac{-x_1}{\cos(x_1^2)*x_2}   x_2=\frac{-x_1}{\sin(x_1+x_2)*\cos(x_1^2)}    x_1=-\sin(x_1+x_2)\cos(x_1^2)*x_2$$

to update successively the range for $(x_1, x_2),(x_2),(x_1)$. Note that there is not an extensive check of the possibility of interval evaluating the right hand side term of these new equations and thus the simplification procedure may lead to an error during this evaluation. The syntax of Simp2B is similar to the one of Hullconsistency.

The new procedure Simp2B manages in a better way the dependency problem but is less complete than HullConsistencyStrong, which is no more available for Maple 9.5, as it manages only the following expressions

$$\sin, \cos, \tan, \log, exp, x^n (n being an integer)$$

It is also usually more computer intensive than the HullConsistencyStrong procedure. Note that you have some control over the simplification rule that will be used. Consider for example the equation

$$x^2+ e^z y+1=0$$

By default Simp2B will use the following equalities: $x^2 = -1 -e^z y$, $e^z = (-1-x^2)/y$, $y= (-1-x^2)/e^z$ to reduce the range respectively for $x, z,y$. But if you specify in the list ALIAS_FORBIDDEN_TERMS:

 
ALIAS_FORBIDDEN_TERM:=[e^z]:

then only the first and third rule will be used.

The syntax of the HullIConsistency procedure is:

 
HullIConsistency([x^2+y^2-1<=0,x*y-1<=0],[x,y],0,"Simp");

Here the third argument is an integer which should be either 0 or 1. It 1 it indicates that the derivatives of the left side of the inequalities are used for their interval evaluation.

There is an optional last argument to these procedures which is a floating point number $f$. If during the simplification there is change in the interval for a variable such that the width of the new range is lower by more than $f$ from the width of the initial range, then the simplification process will be repeated until either the procedure detect that there is no solution to the system or that no change occur in the variable or that the amplitude of the change is lower than $f$.

If you have numerous equations that have such terms the C++ procedure may be quite large. To reduce this size you may choose to look only at the linear term or only at the square term by setting the flag `ALIAS/hullC` to 1 or 2 (its default value is 0). Note that this option is not valid for the HullConsistencyStrong and HullIConsistency procedures.

A typical use of this procedure is given below, assuming that you have a list of equations EQ and a list of variable VAR:

 
HullConsistency(EQ,VAR,"SS"):
HessianSolve(EQ,VAR,Init,"SS");

Here the procedure generate the C++ procedure SS (which will be written in the file SS.C) and the solving algorithm HessianSolve will use this procedure during the computation.

The efficiency of the hull consistency approach is usually quite good but decreases quite quickly after the first improvements. Hence it is in general not a good idea to repeat the procedure when only small improvements on the range are obtained.

A test to determine if an expression involved in the equations and inequalities can be interval-valuated may be performed if the Verify_Problem_Expression procedure has been called before the call to HullConsistency or HullIConsistency (see section 2.1.5). If different calls to the consistency procedures are made with different set of expressions it is necessary to specify a different string `ALIAS/ID` string before each call to Verify_Problem_Expression. For example

 
 `ALIAS/ID`:="Simp1":
 Verify_Problem_Expression(EQ1,VAR):
 HullIConsistency(EQ1,VAR,"Simp1"):
 `ALIAS/ID`:="Simp2":
 Verify_Problem_Expression(EQ2,VAR):
 HullConsistency(EQ2,VAR,"Simp2"):
 `ALIAS/ID`:="Simp3":
 Verify_Problem_Expression(EQ2,VAR):
 HullConsistencyStrong(EQ3,VAR,"Simp3"):
 `ALIAS/ID`:="other":

is valid.

A special key-word may be used for the procedures HullConsistency and HullIConsistency in the case of an optimization problem. In that case the ALIAS-C++ variable ALIAS_Optimize is set to -1 (minimum problem) or 1 (maximum problem), the flag ALIAS_Has_Optimum is set to 1 as soon as an estimation of the optimum is found while the interval ALIAS_Optimum is set to the estimation of the optimum. If an equation or an inequality has the key-word "Optimum" in it and if ALIAS_Has_Optimum is 1, then "Optimum" will be substituted by Sup(ALIAS_Optimum) (minimum problem) or Inf(ALIAS_Optimum) (maximum problem).

For example assume that you deal with a problem involving the minimum of $x\sin(x)+y\cos(y)$: you may then use the following call

 
HullIConsistency([x*sin(x)+y*cos(y)-Optimum<=0],[x,y],0,"Simp");

to create a simplification procedure that may reduce the current box. See another example in section 5.2