Graphics Reference
In-Depth Information
interval list function
ConstrainedMinimization (
inclusion function
G,
inclusion function
H,
inclusion function
F,
interval
A)
{ G is the inclusion function for a constraint function g. H is the inclusion function
for an solution acceptance set constraint function.
F is the inclusion function for the function f we want to minimize. }
begin
interval list
S;
{ the solutions }
interval priority queue
Q;
real
u;
{ upper bound }
interval
B, B
1
, B
2
;
integer
i;
point
p
;
S :=
f
;
Q := CreateQueue ( A );
u := +•;
while not
(Empty (Q))
do
begin
B := DeQueue (Q);
if
H (B) = [1,1]
then
Insert (B,S);
else
begin
Subdivide (B,B
1
,B
2
);
{ Subdivides the interval B }
for
i:=1
to
2
do
if
(G (B
i
) π [0,0]) and (lb (F (B
i
)) £ u)
then
begin
EnQueue (B
i
,Q); { based on lb (F (B
i
)) }
if
HasIdentifiableFeasablePt (B
i
,
p
)
then
u := min (u , f (
p
))
else if
HasUnIdentifiableFeasablePt (B
i
)
then
u := min (u , ub (F (B
i
)));
end
end
end
;
return
S;
end
;
Algorithm 18.6.1.
The constrained minimization algorithm.