Next: Our Technique Up: An Iterative Method for Previous: Introduction
Next: Our
Technique Up: An
Iterative Method for Previous: Introduction
The idea is that we randomly generate a point in the search region, which is specified by the bound constraints and search limits. We then check if the point is an approximate feasible point within a given error tolerance. We can repeat this process until we find a feasible point. Alternately, we can repeat the process for a fixed number of times and locate the approximate feasible point with minimum objective function value, if there are any such points. The algorithm used here follows the second pattern.
Algorithm 1 (Random search)
DO for I=1 to Ntries
1. Randomly generate a point in the search region.
2. Check if the point in step 1 is an approximate feasible point.
END DO
End Algorithm 1
By analyzing the probability of finding an approximate feasible point
in the search region, we can see that this technique is too expensive to
be practical in most cases where there are equality constraints. To simplify
the analysis, let's assume each dimension of the search region has length
L, i.e. 
.
The volume of the search region is then 
.
Normally, the feasible region for the equality and inequality constraints
consists of manifolds of dimension n-p. Let the error tolerance
for the approximate feasible points be 
.
Then the volume of the approximate feasible region is 
.
Figure 1 illustrates this situation, where 
.
Thus, the probability of finding an approximate feasible point in the
search region is 
.
This implies the need to generate
random points, on average, to find one approximate feasible point. In most
cases, this is too expensive to be practical. For example, problem wolfe3
in §6 is a simple problem, where 
.
Assuming a coefficient of 1 in (2),we
would need to generate approximately 
random points to find one approximate feasible point. As seen in Table
1 in §6, processing of 
randomly generated points needs 6846.16 STU (Standard Times Units; see
§5). Also, according to our tests the processing time for a particular
problem is proportional to the number of random points generated. Thus,
we would need to spend
to find one approximate feasible point for the problem wolfe3. For
problems containing more equality constraints, the situation could be much
worse.
If a problem contains only inequality constraints, random search could work better than cases in which equality constraints are involved, since the volume of the approximate feasible region could be of the same order of magnitude as that of the search region. (See test results in §6.)