Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms

We investigate subdivision strategies that can improve the convergence and efficiency of some branch and bound algorithms of global optimization. In particular, a general class of so called weakly exhaustive simplicial subdivision processes is introduced that subsumes all previously known radial exhaustive processes. This result provides the basis for constructing flexible subdivision strategies that can be adapted to take advantage of various problem conditions.     

Convergence Rate of The Trust Region Method for Nonlinear Equations Under Local Error Bound Condition

In this paper, we present the new trust region method for nonlinear equations with the trust region converging to zero. The new method preserves the global convergence of the traditional trust region methods in which the trust region radius will be larger than a positive constant. We study the convergence rate of the new method under the local error bound condition which is weaker than the nonsingularity. An example given by Y.X. Yuan shows that the convergence rate can not be quadratic. Finally, some numerical results are given. This work is supported by Chinese NSFC grants 10401023 and 10371076, Research Grants for Young Teachers of Shanghai Jiao Tong University, and E-Institute of Computational Sciences of Shanghai Universities. An erratum to this article is available at .     

Packing into the smallest square: Worst-case analysis of lower bounds

We address the problem of packing a given set of rectangles into the minimum size square. We consider three versions of the problem, arising when the rectangles (i) are squares; (ii) have a fixed orientation; (iii) can be rotated by 90. For each case we study lower bounds, and analyze their worst-case performance ratio. In addition, we evaluate through computational experiments their average performance on instances from the literature.     

大规模界约束优化的子空间截断牛顿法

给出了大规模界约束优化的一个子空间截断牛顿法。利用截断牛顿法修正非有效约束所对应的变量，用投影梯度法修正有效约束所对应的变量，文中证明了方法的整体收敛性，并对方法进行了数值试验，且与子空间有限内存拟牛顿法进行了数值比较。     

On error bounds for lower semicontinuous functions

We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f. Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002     

搜索三个目标

本文通过建立简洁而有效的搜索方法 ,证明了对于无穷多个n来说 ,三个目标的最优搜索问题的最小试验次数等于信息论下界 .同时也研究了上述问题的修正情形 ,证明了对于所有整数n来说 ,对应的最小试验次数或者等于信息论下界或者超过信息论下界 1次并且对于无穷多个区间 ,信息论下界均是可以达到的 .     

Periodic solutions of a second order forced sublinear differential equation with delay

In this paper, existence criteria are established for the existence of periodic solutions of a second order sublinear differential equation with delay and forcing function. Our method is based on careful a priori estimation and continuation theorems, and our sublinear condition is an improvement of the boundedness condition in some recent results.     

n维氢原子的散射态

研究了n维氢原子的散射态性质．给出了精确的按“k/2π标度”归一化的散射态的精确解波函数及相移表达式，讨论了相移的解析性质，获得了束缚-连续跃迁矩阵元的解析计算公式．普通氢原子(n=3)散射态的有关结果作为特例包含在本文的一般结论之中． 关键词： n维氢原子 散射态 精确解 相移 束缚-连续跃迁矩阵元     

Branch and win: OR tree search algorithms for solving combinatorial optimisation problems

Currently, most combinatorial optimisation problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. We propose Branch and Win, a general formulation for understanding and synthesising the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. Several general ideas are also presented, whose application allows designing new hybrid search algorithms, in order to implement the procedure.