An Algorithm of Global Optimization for Rational Functions with Rational Constraints

To solve a system of nonlinear equations, Wu wen-tsun introduced a new formative elimination method. Based on Wu's method and the theory of nonlinear programming, we here propose a global optimization algorithm for nonlinear programming with rational objective function and rational constraints. The algorithm is already programmed and the test results are satisfactory with respect to precision and reliability.     

Minimum Inter-Particle Distance at Global Minimizers of Lennard-Jones Clusters

In computer simulations of molecular conformation and protein folding, a significant part of computing time is spent in the evaluation of potential energy functions and force fields. Therefore many algorithms for fast evaluation of potential energy functions and force fields are proposed in the literature. However, most of these algorithms assume that the particles are uniformly distributed in order to guarantee good performance. In this paper, we prove that the minimum inter-particle distance at any global minimizer of Lennard-Jones clusters is bounded away from zero by a positive constant which is independent of the number of particles. As a by-product, we also prove that the global minimum of an n particle Lennard-Jones cluster is bounded between two linear functions. Our first result is useful in the design of fast algorithms for potential function and force field evaluation. Our second result can be used to decide how good a local minimizer is.     

Existence of Minimizers for Nonconvex Variational Problems with Slow Growth

Consider the minimization problem

Test Functions with Variable Attraction Regions for Global Optimization Problems

Functions with local minima and size of their region of attraction known a priori, are often needed for testing the performance of algorithms that solve global optimization problems. In this paper we investigate a technique for constructing test functions for global optimization problems for which we fix a priori: (i) the problem dimension, (ii) the number of local minima, (iii) the local minima points, (iv) the function values of the local minima. Further, the size of the region of attraction of each local minimum may be made large or small. The technique consists of first constructing a convex quadratic function and then systematically distorting selected parts of this function so as to introduce local minima.     

Rational Functions with Prescribed Critical Points

A rational function is the ratio of two complex polynomials in one variable without common roots. Its degree is the maximum of the degrees of the numerator and the denominator. Rational functions belong to the same class if one turns into the other by postcomposition with a linear-fractional transformation. We give an explicit formula for the number of classes having a given degree d and given multiplicities m₁,..., m_n of given n critical points, for generic positions of the critical points. This number is the multiplicity of the irreducible sl₂ representation with highest weight in the tensor product of the irreducible sl₂ representations with highest weights The classes are labeled by the orbits of critical points of a remarkable symmetric function which first appeared in the XIX century in studies of Fuchsian differential equations, and then in the XX century in the theory of KZ equations.     

Approximation of Transfer Functions of Unstable Infinite Dimensional Control Systems by Rational Interpolants with Prescribed Poles

Rational interpolants, some of the poles of which are left free, are used to approximate the transfer functions of a large class of possibly unstable infinite-dimensional control systems. The free poles are used to detect the singularities of the transfer function which are responsible for the instability of the system.     

Bernstein-Type Inequalities for Rational Functions with Prescribed Poles

We establish Bernstein-type inequalities for rational functionswith prescribed poles in the Chebyshev norm on the unit circlein the complex plane. Generalizations of polynomial inequalitiesof Erds-Lax and Turán are also obtained for such rational functions with restricted zeros.     

Local Optimization Method with Global Multidimensional Search

This paper presents a new method for solving global optimization problems. We use a local technique based on the notion of discrete gradients for finding a cone of descent directions and then we use a global cutting angle algorithm for finding global minimum within the intersection of the cone and the feasible region. We present results of numerical experiments with well-known test problems and with the so-called cluster function. These results confirm that the proposed algorithms allows one to find a global minimizer or at least a deep local minimizer of a function with a huge amount of shallow local minima.     

Global and Local Quadratic Minimization

We present a method which when applied to certain non-convex QP will locatethe globalminimum, all isolated local minima and some of the non-isolated localminima. The method proceeds by formulating a (multi) parametric convex QP interms ofthe data of the given non-convex QP. Based on the solution of the parametricQP,an unconstrained minimization problem is formulated. This problem ispiece-wisequadratic. A key result is that the isolated local minimizers (including theglobalminimizer) of the original non-convex problem are in one-to-one correspondencewiththose of the derived unconstrained problem.The theory is illustrated with several numerical examples. A numericalprocedure isdeveloped for a special class of non-convex QP's. It is applied to a problemfrom theliterature and verifies a known global optimum and in addition, locates apreviously unknown local minimum.     

函数空间中总极值的R-收敛有限维逼近

应用测度序列R-收敛的新概念来描述函数空间中总极值问题解的有限维逼近,并利用变差积分途径来寻找这样的解.针对有约束问题,运用罚变差积分算法把所给问题转化为无约束问题,且给出一个非凸状态约束最优控制问题的数值例子以说明该算法的有效性.     

Generating Sum-of-Ratios Test Problems in Global Optimization

A method is presented for the construction of test problems involving the minimization over convex sets of sums of ratios of affine functions. Given a nonempty, compact convex set, the method determines a function that is the sum of linear fractional functions and attains a global minimum over the set at a point that can be found by convex programming and univariate search. Generally, the function will have also local minima over the set that are not global minima.     

M—可加细函数的局部和整体线性无关性

讨论具有紧支集M的可加细函数的局部线性无关性和整体线性无关性的等价关系。     

总体优化一类双参数填充函数算法的改进

求解无约束总体优化问题的一类双参数填充函数算法需要假设该问题的局部极小解的个数只有有限个,而且填充函数中参数的选取与局部极小解的谷域的半径有关．该文对其填充函数作了适当改进,使得新的填充函数算法不仅无需对问题的局部极小解的个数作假设,而且填充函数中参数的选取与局部极小解的谷域的半径无关．数值试验表明算法是有效的．     

New Classes of Globally Convexized Filled Functions for Global Optimization

We propose new classes of globally convexized filled functions. Unlike the globally convexized filled functions previously proposed in literature, the ones proposed in this paper are continuously differentiable and, under suitable assumptions, their unconstrained minimization allows to escape from any local minima of the original objective function. Moreover we show that the properties of the proposed functions can be extended to the case of box constrained minimization problems. We also report the results of a preliminary numerical experience.     

Construction of Continuous Functions with Prescribed Local Regularity

In this paper we investigate from both a theoretical and a practical point of view the following problem: Let s be a function from [0;1] to [0;1] . Under which conditions does there exist a continuous function f from [0;1] to R such that the regularity of f at x , measured in terms of H?lder exponent, is exactly s(x) , for all x ∈ [0;1] ? We obtain a necessary and sufficient condition on s and give three constructions of the associated function f . We also examine some extensions regarding, for instance, the box or Tricot dimension or the multifractal spectrum. Finally, we present a result on the ``size' of the set of functions with prescribed local regularity. November 30, 1995. Date revised: September 30, 1996.     

Some Dual Conditions for Global Weak Sharp Minimality of Nonconvex Functions

Weak sharp minimality is a notion emerged in optimization whose utility is largely recognized in the convergence analysis of algorithms for solving extremum problems as well as in the study of the perturbation behavior of such problems. In this article, some dual constructions of nonsmooth analysis, mainly related to quasidifferential calculus and its recent developments, are employed in formulating sufficient conditions for global weak sharp minimality. They extend to nonconvex functions a condition, which is known to be valid in the convex case. A feature distinguishing the results here proposed is that they avoid to assume the Asplund property on the underlying space.     

A Combined Global & Local Search (CGLS) Approach to Global Optimization

This paper presents a general approach that combines global search strategies with local search and attempts to find a global minimum of a real valued function of n variables. It assumes that derivative information is unreliable; consequently, it deals with derivative free algorithms, but derivative information can be easily incorporated. This paper presents a nonmonotone derivative free algorithm and shows numerically that it may converge to a better minimum starting from a local nonglobal minimum. This property is then incorporated into a random population to globalize the algorithm. Convergence to a zero order stationary point is established for nonsmooth convex functions, and convergence to a first order stationary point is established for strictly differentiable functions. Preliminary numerical results are encouraging. A Java implementation that can be run directly from the Web allows the interested reader to get a better insight of the performance of the algorithm on several standard functions. The general framework proposed here, allows the user to incorporate variants of well known global search strategies. Research done under the cooperation agreement between Universidade de Vigo and Universidad Simón Bolívar.     

Global Interval Methods for Local Nonsmooth Optimization

An interval method for determining local solutions of nonsmooth unconstrained optimization problems is discussed. The objective function is assumed to be locally Lipschitz and to have appropriate interval inclusions. The method consists of two parts, a local search and a global continuation and termination. The local search consists of a globally convergent descent algorithm showing similarities to -bundle methods. While -bundle methods use polytopes as inner approximations of the -subdifferentials, which are the main tools of almost all bundle concepts, our method uses axes parallel boxes as outer approximations of the -subdifferentials. The boxes are determined almost automatically with inclusion techniques of interval arithmetic. The dimension of the boxes is equal to the dimension of the problem and remains constant during the whole computation. The application of boxes does not suffer from the necessity to invest methodical and computational efforts to adapt the polytopes to the latest state of the computation as well as to simplify them when the number of vertices becomes too large, as is the case with the polytopes. The second part of the method applies interval techniques of global optimization to the approximative local solution obtained from the search of the first part in order to determine guaranteed error bounds or to improve the solution if necessary. We present prototype algorithms for both parts of the method as well as a complete convergence theory for them and demonstrate how outer approximations can be obtained.     

Interval Branch and Bound with Local Sampling for Constrained Global Optimization

In this article, we introduce a global optimization algorithm that integrates the basic idea of interval branch and bound, and new local sampling strategies along with an efficient data structure. Also included in the algorithm are procedures that handle constraints. The algorithm is shown to be able to find all the global optimal solutions under mild conditions. It can be used to solve various optimization problems. The local sampling (even if done stochastically) is used only to speed up the convergence and does not affect the fact that a complete search is done. Results on several examples of various dimensions ranging from 1 to 100 are also presented to illustrate numerical performance of the algorithm along with comparison with another interval method without the new local sampling and several noninterval methods. The new algorithm is seen as the best performer among those tested for solving multi-dimensional problems.     

A Multivariate Global Optimization Using Linear Bounding Functions

Recently linear bounding functions (LBFs) were proposed and used to find -global minima. This paper presents an LBF-based algorithm for multivariate global optimization problems. The algorithm consists of three phases. In the global phase, big subregions not containing a solution are quickly eliminated and those which possibly contain the solution are detected. An efficient scheme for the local phase is developed using our previous local minimization algorithm, which is globally convergent with superlinear/quadratic rate and does not require evaluation of gradients and Hessian matrices. To ensure that the found minimizers are indeed the global solutions or save computation effort, a third phase called the verification phase is often needed. Under adequate conditions the algorithm finds the -global solution(s) within finite steps. Numerical testing results illustrate how the algorithm works, and demonstrate its potential and feasibility.