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
. The procedure will introduce a new variable
such
that
and compute its interval evaluation. As
should be
equal to
if
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
of
is positive the procedure will check if
lie in
and update the interval for
if this is not
the case.
In a second step the procedure will introduce another new variable
such that
and compute its interval evaluation. As
should be equal to
the procedure will check if the interval value
for
is consistent with the interval value for
and if not
update the interval for
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. ).
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
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
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 . 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
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
.
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
: 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