Pseudo-Cut Strategies for Global Optimization

Top

2. Pseudo-Cut Form And Representation

Our pseudo-cut strategy is based on generating hyperplanes that are orthogonal to selected rays (half-lines) originating at a point x′ and passing through a second point x″, so that the hyperplane intersects the ray at a point x^o determined by requiring that it lies on the ray at a selected distance d from x′. The half-space that forms the pseudo-cut is then produced by the associated inequality that excludes x′ from the admissible half-space. We define the distance d by reference to the Euclidean (L2) norm, but other norms can also be used.

To identify the pseudo-cut as a function of x′, x″ and d, we represent the ray that originates at x′ and passes through x″ by

x = x′ + λ(x″ – x′), λ ≥ 0. (1) (Hence x′ and x″ lie on the ray at the points determined by λ = 0 and 1, respectively.)

A hyperplane orthogonal to this line may then be expressed as.ax = b (2.1) where

a = (x″ – x′) (2.2) b = an arbitrary constant (2.3)