Cutting angle method - a tool for constrained global optimization

Cutting angle method (CAM) is a deterministic global optimization technique applicable to Lipschitz functions f: Rn → R. The method builds a sequence of piecewise linear lower approximations to the objective function f. The sequence of solutions to these relaxed problems converges to the global minimum of f. This article adapts CAM to the case of linear constraints on the feasible domain. We show how the relaxed problems are modified, and how the numerical efficiency of solving these problems can be preserved. A number of numerical experiments confirms the improved numerical efficiency.

Construction of aggregation operators for automated decision making via optimal interpolation and global optimization

This paper examines methods of point wise construction of aggregation operators via optimal interpolation. It is shown that several types of application-specific requirements lead to interpolatory type constraints on the aggregation function. These constraints are translated into global optimization problems, which are the focus of this paper. We present several methods of reduction of the number of variables, and formulate suitable numerical algorithms based on Lipschitz optimization.

Extended cutting angle method of global optimization

Methods of Lipschitz optimization allow one to find and confirm the global minimum of multivariate Lipschitz functions using a finite number of function evaluations. This paper extends the Cutting Angle method, in which the optimization problem is solved by building a sequence of piecewise linear underestimates of the objective function. We use a more flexible set of support functions, which yields a better underestimate of a Lipschitz objective function. An efficient algorithm for enumeration of all local minima of the underestimate is presented, along with the results of numerical experiments. One dimensional Pijavski-Shubert method arises as a special case of the proposed approach.

Geometry and combinatorics of the cutting angle method

Lower approximation of Lipschitz functions plays an important role in deterministic global optimization. This article examines in detail the lower piecewise linear approximation which arises in the cutting angle method. All its local minima can be explicitly enumerated, and a special data structure was designed to process them very efficiently, improving previous results by several orders of magnitude. Further, some geometrical properties of the lower approximation have been studied, and regions on which this function is linear have been identified explicitly. Connection to a special distance function and Voronoi diagrams was established. An application of these results is a black-box multivariate random number generator, based on acceptance-rejection approach.

Bounded lower subdifferentiability optimization techniques : applications

In this article we develop a global optimization algorithm for quasiconvex programming where the objective function is a Lipschitz function which may have "flat parts". We adapt the Extended Cutting Angle method to quasiconvex functions, which reduces significantly the number of iterations and objective function evaluations, and consequently the total computing time. Applications of such an algorithm to mathematical programming problems inwhich the objective function is derived from economic systems and location problems are described. Computational results are presented.

Nonsmooth continuous-time optimization problems: Necessary conditions

We consider Lipschitz continuous-time nonlinear optimization problems and provide first-order necessary optimality conditions of both Fritz John and Karush-Kuhn-Tucker types. (C) 2001 Elsevier B.V. Ltd. All rights reserved.

The generation of virtual prototypes for performance optimization

I am suspicious of tools without a purpose - tools that are not developed in response to a clearly defined problem. Of course tools without a purpose can still be useful. However the development of first generation CAD was seriously impeded because the solution came before the problem. We are in danger of repeating this mistake if we do not clarify the nature of the problem that we are trying to solve with the next generation of tools. Back in the 1980s I used to add a postscript slide at the end of CAD conference presentations and the applause would invariably turn to concern. The slide simple asked: can anyone remember what it was about design that needed aiding before we had computer aided design?