Pseudo-Cut Strategies for Global Optimization

Pseudo-Cut Strategies for Global Optimization

Fred Glover (OptTek Systems, Inc., USA), Leon Lasdon (The University of Texas at Austin, USA), John Plummer (Texas State University, USA), Abraham Duarte (Universidad Rey Juan Carlos, Spain), Rafael Marti (Universidad de Valencia, Spain), Manuel Laguna (University of Colorado, USA) and Cesar Rego (University of Mississippi, USA)
Copyright: © 2011 |Pages: 12
DOI: 10.4018/jamc.2011100101
OnDemand PDF Download:
$37.50

Abstract

Motivated by the successful use of a pseudo-cut strategy within the setting of constrained nonlinear and nonconvex optimization in Lasdon et al. (2010), we propose a framework for general pseudo-cut strategies in global optimization that provides a broader and more comprehensive range of methods. The fundamental idea is to introduce linear cutting planes that provide temporary, possibly invalid, restrictions on the space of feasible solutions, as proposed in the setting of the tabu search metaheuristic in Glover (1989), in order to guide a solution process toward a global optimum, where the cutting planes can be discarded and replaced by others as the process continues. These strategies can be used separately or in combination, and can also be used to supplement other approaches to nonlinear global optimization. Our strategies also provide mechanisms for generating trial solutions that can be used with or without the temporary enforcement of the pseudo-cuts.
Article Preview

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 xo 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)

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing