一族新的共轭梯度法的全局收敛性

共轭梯度法是求解无约束优化问题的一种重要的方法,尤其适用于大规模优化问题的求解。本文提出一族新的共轭梯度法,证明了其在推广的Wolfe非精确线搜索条件下具有全局收敛性。最后对算法进行了数值试验,试验结果验证了该算法的有效性。     

Acceleration of conjugate gradient algorithms for unconstrained optimization

Conjugate gradient methods are important for large-scale unconstrained optimization. This paper proposes an acceleration of these methods using a modification of steplength. The idea is to modify in a multiplicative manner the steplength α_k, computed by Wolfe line search conditions, by means of a positive parameter η_k, in such a way to improve the behavior of the classical conjugate gradient algorithms. It is shown that for uniformly convex functions the convergence of the accelerated algorithm is still linear, but the reduction in function values is significantly improved. Numerical comparisons with some conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that the accelerated computational scheme outperform the corresponding conjugate gradient algorithms.     

CONVERGENCE ANALYSIS ON A CLASS OF CONJUGATE GRADIENT METHODS WITHOUTSUFFICIENT DECREASE CONDITION

1IntroductionOurproblemistominimizeafllnctionofnvariables,wheref:R"~R',fECZalldgdenotesthegradientoff.Problem(1)isoftellsolvedbyvaxiouscolljugategradientmethodsofthefornl:wherePhisascalar,andAhisastepsizechosenbymeansofolle-dimentiollalsearcllrules.VariousconjugategradientInethodsarecharacterizedbydifferentchoiceofPh,thebestkllowllforlllulaeforPharecalledtheFletcher-Reeves(FR),Polak-Ribiere(PR),alldHestenes-Stiefel(HS)forlrmlar,andarerespectivelygivenbyThecolljugategradientlllethodcor…     

一种改进的共轭梯度法及全局收敛性

本文在DY共轭梯度法的基础上对解决无约束最优化问题提出一种改进的共轭梯度法.该方法在Wolfe线搜索下能够保证充分下降性,并在目标函数可微的条件下,证明了算法的全局收敛性.大量数值试验表明,该方法是很有效的.     

Lower and upper bounds for a two-stage capacitated facility location problem with handling costs

We study in this paper multi-product facility location problem in a two-stage supply chain in which plants have production limitation, potential depots have limited storage capacity and customer demands must be satisfied by plants via depots. In the paper, handling cost for batch process in depots is considered in a realistic way by a set of capacitated handling modules. Each module can be regards as alliance of equipment and manpower. The problem is to locate depots, choose appropriate handling modules and to determine the product flows from the plants, opened depots to customers with the objective to minimize total location, handling and transportation costs. For the problem, we developed a hybrid method. The initial lower and upper bounds are provided by applying a Lagrangean based on local search heuristic. Then a weighted Dantzig–Wolfe decomposition and path-relinking combined method are proposed to improve obtained bounds. Numerical experiments on 350 randomly generated instances demonstrate our method can provide high quality solution with gaps below 2%.     

两种有效的非线性共轭梯度算法

根据CG-DESCENT算法[1]的结构和Powell在综述文献[11]中的建议,给出了两种新的求解无约束优化问题的非线性共轭梯度算法. 它们在任意线搜索下都具有充分下降性质, 并在标准Wolfe线搜索下对一般函数能够保证全局收敛性. 通过对CUTEr函数库中部分著名的函数进行试验, 并借助著名的Dolan & Moré[2]评价方法, 展示了新算法的有效性.     

Goal programming in the context of the assignment problem and a computationally effective solution method

This paper develops the goal programming technique to solve the multiple objective assignment problem. The required model is formulated and an appropriate solution method is presented. The proposed method, which is a decomposition method, exploits the total unimodularity feature of the assignment problem and effectively reduces the computational efforts. Some issues related to the efficiency of a GP solution are stated and some specialized techniques for detecting and restoring efficiency are proposed.     

Set Intersection Theorems and Existence of Optimal Solutions

The question of nonemptiness of the intersection of a nested sequence of closed sets is fundamental in a number of important optimization topics, including the existence of optimal solutions, the validity of the minimax inequality in zero sum games, and the absence of a duality gap in constrained optimization. We consider asymptotic directions of a sequence of closed sets, and introduce associated notions of retractive, horizon, and critical directions, based on which we provide new conditions that guarantee the nonemptiness of the corresponding intersection. We show how these conditions can be used to obtain simple and unified proofs of some known results on existence of optimal solutions, and to derive some new results, including a new extension of the Frank–Wolfe Theorem for (nonconvex) quadratic programming.     

A Study of the Dennis-Wolkowicz Method on Convex Functions

In this paper, we analyze the global convergence of the least-change secant method proposed by Dennis and Wolkowicz, when applied to convex objective functions. One of the most distinguished features of this method is that the Dennis-Wolkowicz update doesn't necessarily belong to the Broyden convex family and can be close to the DFP update, but it still has the self-correcting property. We prove that, for convex objective functions, this method with the commonly used Wolfe line search is globally convergent. We also provide some numerical results.     

Modeling and Solving an Airline Schedule Generation Problem

Since opening a new flight connection or closing an existing flight has a great impact on the revenues of an airline, the generation of the flight schedule is one of the fundamental problems in airline planning processes.In this paper we concentrate on a special case of the problem which arises at charter companies. In contrast to airlines operating on regular schedules, the market for charter airlines is well-known and the schedule is allowed to change completely from period to period. Thus, precise adjustments to the demands of the market have a great potential for minimizing operating costs.We present a capacitated network design model and propose a combined branch-and-cut approach to solve this airline schedule generation problem. To tighten the linear relaxation bound, we add cutting planes which adjust the number of aircraft and the spill of passengers to the demand on each itinerary.For real-world problems from a large European charter airline we obtain solutions within a very few percent of optimality with running times in the order of minutes on a customary personal computer for most of the data sets.