An algorithm for global optimization of Lipschitz continuous functions

An algorithm is presented which locates the global minimum or maximum of a function satisfying a Lipschitz condition. The algorithm uses lower bound functions defined on a partitioned domain to generate a sequence of lower bounds for the global minimum. Convergence is proved, and some numerical results are presented.     

A parallel stochastic method for solving linearly constrained concave global minimization problems

A parallel stochastic algorithm is presented for solving the linearly constrained concave global minimization problem. The algorithm is a multistart method and makes use of a Bayesian stopping rule to identify the global minimum with high probability. Computational results are presented for more than 200 problems on a Cray X-MP EA/464 supercomputer.     

A new global optimization approach for convex multiplicative programming

In this paper, by solving the relaxed quasiconcave programming problem in outcome space, a new global optimization algorithm for convex multiplicative programming is presented. Two kinds of techniques are employed to establish the algorithm. The first one is outer approximation technique which is applied to shrink relaxation area of quasiconcave programming problem and to compute appropriate feasible points and to raise the capacity of bounding. And the other one is branch and bound technique which is used to guarantee global optimization. Some numerical results are presented to demonstrate the effectiveness and feasibility of the proposed algorithm.     

A simulated annealing driven multi-start algorithm for bound constrained global optimization

A derivative-free simulated annealing driven multi-start algorithm for continuous global optimization is presented. We first propose a trial point generation scheme in continuous simulated annealing which eliminates the need for the gradient-based trial point generation. We then suitably embed the multi-start procedure within the simulated annealing algorithm. We modify the derivative-free pattern search method and use it as the local search in the multi-start procedure. We study the convergence properties of the algorithm and test its performance on a set of 50 problems. Numerical results are presented which show the robustness of the algorithm. Numerical comparisons with a gradient-based simulated annealing algorithm and three population-based global optimization algorithms show that the new algorithm could offer a reasonable alternative to many currently available global optimization algorithms, specially for problems requiring ‘direct search’ type algorithm.     

求解非线性互补问题的一类光滑Broyden-like方法

非线性互补问题可以等价地转换为光滑方程组来求解. 基于一种新的非单调线搜索准则, 提出了求解非线性互补问题等价光滑方程组的一类新的非单调光滑 Broyden-like 算法.在适当的假设条件下, 证明了该算法的全局收敛性与局部超线性收敛性. 数值实验表明所提出的算法是有效的.     

A deterministic algorithm for global optimization

We present an algorithm for finding the global maximum of a multimodal, multivariate function for which derivatives are available. The algorithm assumes a bound on the second derivatives of the function and uses this to construct an upper envelope. Successive function evaluations lower this envelope until the value of the global maximum is known to the required degree of accuracy. The algorithm has been implemented in RATFOR and execution times for standard test functions are presented at the end of the paper.Partially supported by NSF DMS-8718362.     

一类带约束min-max-min问题的区间算法

构造了求解一类带不等式约束的min-max-min问题的区间算法,其中目标函数和约束函数都是一阶连续可微函数,证明了方法的收敛性,给出了数值算例.该方法可以同时求出问题的最优值和全部全局最优解,是有效和可靠的.     

关于解极大相关问题P-SOR算法的收敛性

对求解极大相关问题的P-SOR方法的收敛性做了进一步研究.得到了一些新的收敛条件.为了提高收敛到全局最大解的可能性,提出了一种新的初始向量选择策略.给出了P-SOR算法的对称形式(P-SSOR).还给出了一种算法精化策略.最后,用数值例子说明新方法的有效性.     

一种基于LVI求解二次规划问题的数值算法

给出并研究了一种数值算法(简称94LVI算法),用于求解带等式和双端约束的二次规划问题. 这类带约束的二次规划问题首先被转换为线性变分不等式问题,该问题等价于分段线性投影等式.接着使用94LVI算法求解上述分段线性投影等式,从而得到QP问题的最优解. 进一步给出了94LVI算法的全局收敛性证明. 94LVI算法与经典有效集算法的对比实验结果证实了给出的94LVI算法在求解二次规划问题上的高效性与优越性.     

Wolfe步长规则下约束优化问题的共轭梯度投影算法

本文研究了约束优化问题min x∈Ωf(x).利用共轭梯度算法与GLP梯度投影思想相结合的方法,构造了一个新的共轭梯度投影算法,并在Wolfe线搜索下获得了该算法的全局收敛性结果.     

求解一类非光滑优化问题的改进变尺度方法

1 引言 近来，人们对用过剩其函数来表示信号的处理方法表现出极大的兴趣，原因是基函数类越大所表示出的函数类就越大，人们通常采用小波基和Gabor基，本文的目的是构造一个寻找优化（或最优）基函数的算法，该算法的出发点是从过剩的其函数中选择紧支撑的基向量。     

SPT: a stochastic tunneling algorithm for global optimization

A stochastic approach to solving unconstrained continuous-function global optimization problems is presented. It builds on the tunneling approach to deterministic optimization presented by Barhen and co-workers (Bahren and Protopopescu, in: State of the Art in Global Optimization, Kluwer, 1996; Barhen et al., Floudas and Pardalos (eds.), TRUST: a deterministic algorithm for global optimization, 1997) by combining a series of local descents with stochastic searches. The method uses a rejection-based stochastic procedure to locate new local minima descent regions and a fixed Lipschitz-like constant to reject unpromising regions in the search space, thereby increasing the efficiency of the tunneling process. The algorithm is easily implemented in low-dimensional problems and scales easily to large problems. It is less effective without further heuristics in these latter cases, however. Several improvements to the basic algorithm which make use of approximate estimates of the algorithms parameters for implementation in high-dimensional problems are also discussed. Benchmark results are presented, which show that the algorithm is competitive with the best previously reported global optimization techniques. A successful application of the approach to a large-scale seismology problem of substantial computational complexity using a low-dimensional approximation scheme is also reported.     

Global solution of bilevel programs with a nonconvex inner program

A bounding algorithm for the global solution of nonlinear bilevel programs involving nonconvex functions in both the inner and outer programs is presented. The algorithm is rigorous and terminates finitely to a point that satisfies ε-optimality in the inner and outer programs. For the lower bounding problem, a relaxed program, containing the constraints of the inner and outer programs augmented by a parametric upper bound to the parametric optimal solution function of the inner program, is solved to global optimality. The optional upper bounding problem is based on probing the solution obtained by the lower bounding procedure. For the case that the inner program satisfies a constraint qualification, an algorithmic heuristic for tighter lower bounds is presented based on the KKT necessary conditions of the inner program. The algorithm is extended to include branching, which is not required for convergence but has potential advantages. Two branching heuristics are described and analyzed. Convergence proofs are provided and numerical results for original test problems and for literature examples are presented.     

A filter line search algorithm based on an inexact Newton method for nonconvex equality constrained optimization

We propose an inexact Newton method with a filter line search algorithm for nonconvex equality constrained optimization. Inexact Newton’s methods are needed for large-scale applications which the iteration matrix cannot be explicitly formed or factored. We incorporate inexact Newton strategies in filter line search, yielding algorithm that can ensure global convergence. An analysis of the global behavior of the algorithm and numerical results on a collection of test problems are presented.     

约束全局整数规划问题的填充函数法

本文给出了一类新的求解箱约束全局整数规划问题的填充函数，并讨论了其填充性质．基于提出的填充函数，设计了一个求解带等式约束、不等式约束、及箱约束的全局整数规划问题的算法．初步的数值试验结果表明提出的算法是可行的。     

Nonmonotone trust region algorithm for unconstrained optimization problems

In this paper, a nonmonotone trust region algorithm for unconstrained optimization problems is presented. In the algorithm, a kind of nonmonotone technique, which is evidently different from Grippo, Lampariello and Lucidi’s approach, is used. Under mild conditions, global and local convergence results of the algorithm are established. Preliminary numerical results show that the new algorithm is efficient.     

A global cost Malmquist productivity index using data envelopment analysis

This paper proposes a global cost Malmquist productivity index, new cost Malmquist productivity index, that is circular and that gives a single measure of productivity change. The index is inspired by the global Malmquist productivity index as extended to productivity measurement. Decomposition of the proposed cost Malmquist productivity index is presented. Numerical results are presented for an example taken from the literature to illustrate the proposed algorithm.     

An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming

This paper is concerned with nonlinear, semidefinite, and second-order cone programs. A general algorithm, which includes sequential quadratic programming and sequential quadratically constrained quadratic programming methods, is presented for solving these problems. In the particular case of standard nonlinear programs, the algorithm can be interpreted as a prox-regularization of the Solodov sequential quadratically constrained quadratic programming method presented in Mathematics of Operations Research (2004). For such type of methods, the main cost of computation amounts to solve a linear cone program for which efficient solvers are available. Usually, “global convergence results” for these methods require, as for the Solodov method, the boundedness of the primal sequence generated by the algorithm. The other purpose of this paper is to establish global convergence results without boundedness assumptions on any of the iterative sequences built by the algorithm.     

Deterministic parallel global parameter estimation for a model of the budding yeast cell cycle

Two parallel deterministic direct search algorithms are combined to find improved parameters for a system of differential equations designed to simulate the cell cycle of budding yeast. Comparing the model simulation results to experimental data is difficult because most of the experimental data is qualitative rather than quantitative. An algorithm to convert simulation results to mutant phenotypes is presented. Vectors of the 143 parameters defining the differential equation model are rated by a discontinuous objective function. Parallel results on a 2200 processor supercomputer are presented for a global optimization algorithm, DIRECT, a local optimization algorithm, MADS, and a hybrid of the two.     

Global Optimization using Dynamic Search Trajectories

Two global optimization algorithms are presented. Both algorithms attempt to minimize an unconstrained objective function through the modeling of dynamic search trajectories. The first, namely the Snyman–Fatti algorithm, originated in the 1980's and still appears an effective global optimization algorithm. The second algorithm is currently under development, and is denoted the modified bouncing ball algorithm. For both algorithms, the search trajectories are modified to increase the likelihood of convergence to a low local minimum. Numerical results illustrate the effectiveness of both algorithms.