Finding Robust Solutions Using Local Search

This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature. This revised version was published online in August 2006 with corrections to the Cover Date.     

Proper Efficiency in Vector Optimization on Real Linear Spaces

In this paper, we use an algebraic type of closure, which is called vector closure, and through it we introduce some adaptations to the proper efficiency in the sense of Hurwicz, Benson, and Borwein in real linear spaces without any particular topology. Scalarization, multiplier rules, and saddle-point theorems are obtained in order to characterize the proper efficiency in vector optimization with and without constraints. The usual convexlikeness concepts used in such theorems are weakened through the vector closure.     

Simultaneous Pseudo-Timestepping for PDE-Model Based Optimization Problems

In this paper we present a new method for the solution of optimization problems with PDE constraints. It is based on simultaneous pseudo-time stepping for evolution equations. The new method can be viewed as a continuous reduced SQP method in the sense that it uses a preconditioner derived from that method. The reduced Hessian in the preconditioner is approximated by a pseudo-differential operator, whose symbol can be investigated analytically. We apply our method to a boundary control model problem. The new optimization method needs 3.2-times the overall computational effort of the solution of simulation problem alone.     

A Finite Algorithm for Global Minimization of Separable Concave Programs

Researchers first examined the problem of separable concave programming more than thirty years ago, making it one of the earliest branches of nonlinear programming to be explored. This paper proposes a new algorithm that finds the exact global minimum of this problem in a finite number of iterations. In addition to proving that our algorithm terminates finitely, the paper extends a guarantee of finiteness to all branch-and-bound algorithms for concave programming that (1) partition exhaustively using rectangular subdivisions and (2) branch on the incumbent solution when possible. The algorithm uses domain reduction techniques to accelerate convergence; it solves problems with as many as 100 nonlinear variables, 400 linear variables and 50 constraints in about five minutes on an IBM RS/6000 Power PC. An industrial application with 152 nonlinear variables, 593 linear variables, and 417 constraints is also solved in about ten minutes.     

Characteristics in optimization of CGH for array generator

A method of simulated annealing in optimization of a computer generated holo-gram(CGH)is presented.The characteristics of energy in annealing curve are analyzed.Thecooling schedule such as giving an initial temperature,the temperature function,the numberof interactions and stopping criterion are discussed.As an example,an optimization of phaserelief kinoform,a CGH with multiple phase levels,is implemented.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Preparation of Papers

We motivate the study of a vector variational inequality by a practical flow equilibrium problem on a network, namely a generalization of the well-known Wardrop equilibrium principle. Both weak and strong forms of the vector variational inequality are discussed and their relationships to a vector optimization problem are established under various convexity assumptions.     

灰色模型的最优化及其参数的直接求法

基于灰色模型的内涵表达式和白化方程响应式均为等比级数的观点,提出了一种不用求ago值、均值,不涉及灰色微分方程,白化微分方程概念,直接求灰色模型参数a,c的方法,通过此方法建立的新模型不仅从理论上可保证是在满足给定评价标准为模拟绝对误差平方和最小(或模拟相对误差平方和最小)、给定精度条件下的最优化模型,从而结束了灰色模型只有更优,没有最优的历史.并从理论上证明了新模型具有白化指数律重合性、白化系数律重合性,伸缩变换一致性.最后通过实例编程验证该方法具有可操作性,且预测精度高,效果好.     

CONE-DIRECTED CONTINGENT DERIVATIVES AND GENERALIZED PREINVEX SET-VALUED OPTIMIZATION

By using cone-directed contingent derivatives, the unified necessary and suffi-cient optimality conditions are given for weakly and strongly minimal elements respectively in generalized preinvex set valued optimization.     

The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs

We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002