INTERVAL ANALYSIS: VERIFYING FEASIBILITY

Introduction.

Constrained optimization problems are of the form

minimize ϕ(x)

subject to c_{i}(x) = 0, i = 1, …, m,
g_{j}(x) ≤ 0, j = 1, … q_{1}
\underline{x}_{i_{k}} ≤ x_{i_{k}}, k = 1, … q_{2} − μ,
x_{i_{k}} ≤ \overline{x}_{i_{k}}, k = μ + 1, … q_{2},

where ϕ : R^{n} → R, c_{i} : R^{n} → R, and g_{j} : R^{n} → R.

(1)

In interval branch and bound algorithms for finding global optima for Problem (1), a search box of the form

x = {(x_{1}, x_{2}, …, x_{n})^{T} ∈ R^{n} |  (2)
\underline{x}_{i} ≤ x_{i} ≤ \overline{x}_{i}, 1 ≤ i ≤ n\},

is generally given, where some of the sides in

(2) correspond to bound constraints of problem (1), and the other sides merely define the extent of the search region. If there are no constraints c_{i} and g_{j}, then the box x is systematically tessellated into sub-boxes. The branch and bound algorithm, in its most basic form, proceeds as follows: Over each sub-box x̃, ϕ(x̌) is computed for some x̌ ∈ x̃, and the range of ϕ over x̃ is bounded (e.g. with a straightforward interval evaluation). (See Interval analysis : Introduction, interval numbers and basic properties of interval arithmetic.) If there are no constraints c_{i} and g_{j}, then the value ϕ(x̌) represents an upper bound on the minimum of ϕ. The minimum such value \underline{ϕ} is kept as the tessellation and search proceed; if any box x̃ has a lower range bound greater than \underline{ϕ}, it is rejected as not containing a global optimum. See [1], [2], or [3] for details of such algorithms.

The situation is more complicated in the constrained case. In particular, the values ϕ(x̌) cannot be taken as upper bounds on the global optimum unless it is known that x̌ is feasible. More generally, an upper bound on the range of ϕ over a small box x̌ can be taken as an upper bound for the global optimum provided it is proven that there exists a feasible point of Problem (1) within x̌. This article outlines how this can be done.

For the fundamental concepts used throughout this article, see Interval analysis : Introduction, interval numbers and basic properties of interval arithmetic. General feasibility: the Fritz-John conditions.

An interval Newton method (see Interval analysis: Interval Newton methods) can sometimes be used to prove existence of a feasible point of Problem (1) that is a critical point of ϕ. In particular, the interval Newton method can sometimes prove existence of a solution to the Lagrange multiplier or Fritz–John system within x̌. For the Fritz–John system, it is convenient to consider the q_{2} bound constraints in the same form as the q_{1} general inequality constraints, so that there are q = q_{1} + q_{2} general inequality constraints of the from g_{j}(x) ≤ 0. With that, the Fritz–John system can be written as

\begin{matrix}F (W) = \\ ( & u_{0}∇ϕ(X) + ∑_{j=1}^{q} u_{j}∇g_{j} + ∑_{i=1}^{m} v_{i}∇c_{i}(X) ; u_{1}g_{1} ; ⋮ ; u_{q}g_{q} ; c_{1}(X) ; ⋮ ; c_{m}(X) ; (u_{0} + ∑_{j=1}^{q} u_{j} + ∑_{i=1}^{m} v_{i}^{2}) − 1 & ) \\ = 0, \end{matrix} (3)

where u_{j} ≥ 0, j = 1, …, q, the v_{i} are unconstrained, and the last equation is one of several possible normalization conditions. For details, see [1, §10.5] or [2, §5.2.5].

Interval analysis : Introduction, interval numbers and basic properties of interval arithmetic Interval analysis : Introduction, interval numbers and basic properties of interval arithmetic Interval analysis: Interval Newton methods Fritz–John

However, computational problems occur in practice with the system (3). It is more difficult to find a good approximate critical point (for an appropriate small box x̌) of the entire system (3) than it is to find a point where the inequality and equality constraints are satisfied. Furthermore, if an interval Newton method is applied to (3) over a large box, the corresponding interval Jacobi matrix or slope matrix typically contains singular matrices and hence is useless for existence verification. This is especially true if it is difficult to get good estimates for the Lagrange multipliers u_{j} and v_{i}. For this reason, the techniques outlined below are useful. Feasibility of inequality constraints.

Proving feasibility of the inequality constraints is sometimes possible by evaluating the g_{j} with interval arithmetic: If g_{j}(x̌) ≤ 0, then every point in x̌ is feasible with respect to the constraint g_{j}(x) ≤ 0; see Interval analysis: Introduction, interval numbers, and basic properties of interval arithmetic or [3]. However, if x̌ corresponds to a point at which g_{j} is active, then 0 ∈ g_{j}(x̌), and no conclusion can be reached from an interval evaluation. In such cases, feasibility can sometimes be proven by treating g_{j}(x) = 0 as one of the equality constraints, then using the techniques below. Infeasibility.

An inequality constraint g_{j} is proven infeasible over x̌ if g_{j}(x̌) > 0, and an equality constraint c_{i} is infeasible over x̌ if either c_{i}(x̌) > 0 or c_{i}(x̌) < 0. See Interval analysis: Introduction, interval numbers, and basic properties of interval arithmetic or [3]. Feasibility of equality constraints.

The equality constraints

c(x) = (c_{1}(x), …, c_{m}(x))^{T} = 0,

c : R^{n} → R^{m}, n ≥ m can be considered an underdetermined system of equations, whereas interval Newton methods generally prove existence / uniqueness for square systems. However, fixing n − m coordinates x̌_{i} ∈ x̌_{i} allows interval Newton methods to work with c̃: R^{m} → R^{m}, to prove existence of a feasible point within x̌. In principle, indices of the coordinates to be held fixed are chosen to correspond to coordinates in which c is varying least rapidly. For a set of test problems, the most successful way appears to be choosing those coordinates corresponding to the right-most columns after Gaussian elimination with complete pivoting has been applied to the rectangular matrix c′(x̌) for some x̌ ∈ x̌. The figure below illustrates the process in two dimensions.

[figure: c(x) = 0; First coordinate is held; fixed at center of box.; Second coord. varies.; This point is proven; Center of box; to exist.]

Proving that there exists a feasible point of an underdetermined constraint system

Certain complications arise. For example, if bound constraints or inequality constraints are active, then either the point x̌ must be perturbed or else the bound or inequality constraints must be treated as equality constraints. Handling this case by perturbation is discussed in [2, p. 191 ff].

For the original explanation of the Gaussian elimination-based process, see [1, §12.4]. In [2, §5.2.4], additional background, discussion, and references appear. References

[1] Hansen, E. R.: Global Optimization Using Interval Analysis, Marcel Dekker, Inc., New York, 1992.

[2] Kearfott, R. B.: Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht, Netherlands, 1996.

[3] Ratschek, H., and Rokne, J.: New Computer Methods for Global Optimization, Wiley, New York, 1988.

Lagrange multipliers Interval analysis: Introduction, interval numbers, and basic properties of interval arithmetic Interval analysis: Introduction, interval numbers, and basic properties of interval arithmetic

R. Baker Kearfott

Department of Mathematics University of Southwestern Louisiana

U.S.L. Box 4-1010, Lafayette, LA 70504-1010 USA

E-mail address: rbk@usl.edu

AMS1991SubjectClassification: 65G10, 65H20. Key words and phrases: constrained optimization, automatic result verification, interval computations, global optimization.