Inertia-preserving secant updates

A class of rank-two, inertia-preserving updates for symmetric matricesH _c is studied. To ensure that inertia is preserved, the updates are chosen to be of the formH ₊=FH _c F ^t, whereF=I+qr ^t, withq andr selected so that the secant equation is satisfied. A characterization is given for all such updates. Using a parameterization of this family of updates, the connection between them and the Broyden class of updates is established. Also, parameter selection criteria that can be used to choose the optimally conditioned update or the update closest to the SR1 update are discussed.The work of the first author was partially supported by AFOSR Grant 84-0326. The work of the second author was partially supported by NSF Grant EAR-82-18743.     

Convergence of quasi-Newton matrices generated by the symmetric rank one update

Quasi-Newton algorithms for unconstrained nonlinear minimization generate a sequence of matrices that can be considered as approximations of the objective function second derivatives. This paper gives conditions under which these approximations can be proved to converge globally to the true Hessian matrix, in the case where the Symmetric Rank One update formula is used. The rate of convergence is also examined and proven to be improving with the rate of convergence of the underlying iterates. The theory is confirmed by some numerical experiments that also show the convergence of the Hessian approximations to be substantially slower for other known quasi-Newton formulae.The work of this author was supported by the National Sciences and Engineering Research Council of Canada, and by the Information Technology Research Centre, which is funded by the Province of Ontario.     

Evolutionary Simulated Annealing With Application to Image Restoration

Simulated annealing is a randomized algorithm proposed for finding a global optimum in large problems where a target function may have many local extrema. This article considers a modification of the simulated annealing algorithm that turns it into a deterministic technique. Instead of carrying out a stochastic jump based on the annealing update density, the update density is used to select a fixed number of candidate parameter vectors which are all fed to the next iteration of the algorithm. The selection criterion involves not only the update density height, but also information about the origin of the candidate vector. Thus, each iteration produces a cooperative collection of parameter vectors in hope of exploring the parameter space in search of the optimum more thoroughly than the regular annealing. The technique is shown to outperform regular annealing on the problem of restoration of lattice images consisting of simple-shaped objects.     

A numerical investigation of rank-two ellipsoid algorithms for nonlinear programming

We study the performance of some rank-two ellipsoid algorithms when used to solve nonlinear programming problems. Experiments are reported which show that the rank-two algorithms studied are slightly less efficient than the usual rank-one (center-cut) algorithm. Some results are also presented concerning the growth of ellipsoid asphericity in rank-one and rank-two algorithms.     

Using imperfect advance demand information in forecasting

Email: t.tan{at}tue.nl Received on 4 January 2007. Accepted on 11 January 2008. In this paper, we consider the demand-forecasting problem ofa make-to-stock system operating in a business-to-business environmentwhere some customers provide information on their future orders,which are subject to changes in time, hence constituting imperfectadvance demand information (ADI). The demand is highly volatileand non-stationary not only because it is subject to seasonalityand changing trends but also because some individual clientdemands have significant influence on the total demand. In suchan environment, traditional forecasting methods may result inhighly inaccurate forecasts, since they are mostly developedfor the total demand based only on the demand history, not makinguse of demand information and ignoring the effects of individualorder patterns of the customers. We propose a forecasting methodologythat makes use of individual ordering pattern histories of theproduct–customer combinations and the current build upof orders. Moreover, we propose making use of limited judgementalupdates on the statistical forecasts prior to the use of ADI.     

基于技术创新的资金约束供应链融资策略分析

新兴技术进入竞争市场时,供应链成员往往存在资金约束,为了尽早占据市场份额、获得更高的利润流,上下游企业有意愿进行供应链的内外部融资。文章对上游企业存在资金约束、下游核心企业资金充裕的供应链融资策略进行决策分析。研究表明:上下游的融资策略会使上游企业得到帕累托改进,且随上游企业自有资金的增大,下游企业的利率阈值逐渐减小;存在最优融资利率使得下游企业的期望利润达到最大。在上下游企业财务不透明的前提下,存在下游企业的融资利率区间使上游企业有隐藏真实资金状况以期获得更低融资利率的动机,文章基于博弈论的信息甄别模型给出了相应的激励合同对上游企业的期望利润进行修正,诱使上游企业提供真实的资金状况。     

Modifying the forrest-Tomlin and saunders updates for linear programming problems with variable upper bounds

The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Fonest—Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted. Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS82-15361.     

Symmetric minimum-norm updates for use in gibbs free energy calculations

This paper examines a type of symmetric quasi-Newton update for use in nonlinear optimization algorithms. The updates presented here impose additional properties on the Hessian approximations that do not result if the usual quasi-Newton updating schemes are applied to certain Gibbs free energy minimization problems. The updates derived in this paper are symmetric matrices that satisfy a given matrix equation and are least squares solutions to the secant equation. A general representation for this class of updates is given. The update in this class that has the minimum weighted Frobenius norm is also presented. This work was done at Sandia National Laboratories and supported by the US Dept. of Energy under contract no. DE-AC04-76DP00789.     

Modifying the forrest-tomlin and saunders updates for linear programming problems with variable upper bounds

The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Forrest-Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS82-15361.     

Variational quasi-Newton methods for unconstrained optimization

In this paper, we propose new members of the Broyden family of quasi-Newton methods. We develop, on the basis of well-known least-change results for the BFGS and DFP updates, a measure for the Broyden family which seeks to take into account the change in both the Hessian approximation and its inverse. The proposal is then to choose the formula which gives the least value of this measure in terms of the two parameters available, and hence to produce an update which is optimal in the sense of the given measure. Several approaches to the problem of minimizing the measure are considered, from which new updates are obtained. In particular, one approach yields a new variational result for the Davidon optimally conditioned method and another yields a reasonable modification to this method. The paper is also concerned with the possibility of estimating, in a certain sense, the size of the eigenvalues of the Hessian approximation on the basis of two available scalars. This allows one to derive further modifications to the above-mentioned methods. Comparisons with the BFGS and Davidson methods are made on a set of standard test problems that show promising results for certain new methods.Part of this work was done during the author's visits at International Centre for Theoretical Physics, Trieste, Italy, at Systems Department, University of Calabria, Cosenza, Italy, and at Ajman University College of Science and Technology, Ajman, United Arab Emirates.The author expresses his gratitude to Professor L. Grandinetti for his encouragement and thanks the anonymous referees for their careful reading of an earlier draft of the paper and valuable comments, which led to a substantial improvement of the original paper.     

A simulated annealing based solution approach for the two-layered location registration and paging areas partitioning problem in cellular mobile networks

This paper presents a mathematical model and simulated annealing based solution approach for finding optimal location updates and paging area configuration for mobile communication networks. We use a two-layered zone-based location registration and paging scheme in which the costs of location updates and paging signaling traffic are reduced by introducing a two-step paging process. The location updates and paging procedures in a two-layered scheme are first described, and an approximation of the measure required for calculating the paging-related signaling volume is provided based on assumptions of cell shapes and mobile stations’ movement patterns. A simulated annealing (SA)-based solution method is devised along with a greedy heuristic, and computational experiments are conducted to illustrate the superiority of the proposed SA-based method over other solution methods.     

Computing Karmarkar projections quickly

The paper presents a numerical method for computing the projections for Karmarkar's new algorithm for linear programming. The method is simple to implement, fully exploits sparsity, and appears in limited experimentation to have good stability properties. Preliminary numerical experience indicates that the method promises advantages over methods that refactor a matrix at every iteration.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF under Grant AFOSR-86-0170. The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.This work was initiated while the author was at the Graduate School of Administration, University of California, Davis, Davis, California.     

Periodic-Review Inventory Model with Three Consecutive Delivery Modes and Forecast Updates

This paper is concerned with a periodic-review inventory system with three consecutive delivery modes (fast, medium, and slow) and demand forecast updates. At the beginning of each period, the inventory level and demand information are updated and decisions on how much to order using each of the three delivery modes are made. It is shown that there is a base-stock policy for fast and medium modes which is optimal. Furthermore, the optimal policy for the slow mode may not be a base-stock policy in general.This research was supported in part by a Faculty Research Grant from the University of Texas at Dallas, a RGC (Hong Kong) Competitive Earmarked Research Grant, a Distinguished Young Investigator Grant from the National Natural Sciences Foundation of China, and a Grant from the Hundred Talents Program of the Chinese Academy of Sciences.     

Quick response policy with Bayesian information updates

In this paper we investigate the quick response (QR) policy with different Bayesian models. Under QR policy, a retailer can collect market information from the sales of a pre-seasonal product whose demand is closely related to a seasonal product’s demand. This information is then used to update the distribution for the seasonal product’s demand by a Bayesian approach. We study two information update models: one with the revision of an unknown mean, and the other with the revision of both an unknown mean and an unknown variance. The impacts of the information updates under both models are compared and discussed. We also identify the features of the pre-seasonal product which can bring more significant profit improvement. We conclude that an effective QR policy depends on a precise information update model as well as a selection of an appropriate pre-seasonal product as the observation target.     

A Modified Rank One Update Which Converges Q-Superlinearly

Quasi-Newton methods are generally held to be the most efficient minimization methods for small to medium sized problems. From these the symmetric rank one update of Broyden (Math. Comp., vol. 21, pp. 368–381, 1967) has been disregarded for a long time because of its potential failure. The work of Conn, Gould and Toint (Math. Prog., vol. 50, pp. 177–195, 1991), Kelley and Sachs (COAP, vol. 9, pp. 43–64, 1998) and Khalfan, Byrd and Schnabel (SIOPT, vol. 3, pp. 1–24, 1993; SIOPT, vol. 6, pp. 1025–1039, 1996) has renewed the interest in this method. However the question of boundedness of the generated matrix sequence has not been resolved by this work. In the present paper it is shown that a slightly modified version of this update generates bounded updates and converges superlinearly for uniformly convex functions. Numerical results support these theoretical considerations.     

A derivative-free nonmonotone line-search technique for unconstrained optimization

A tolerant derivative–free nonmonotone line-search technique is proposed and analyzed. Several consecutive increases in the objective function and also nondescent directions are admitted for unconstrained minimization. To exemplify the power of this new line search we describe a direct search algorithm in which the directions are chosen randomly. The convergence properties of this random method rely exclusively on the line-search technique. We present numerical experiments, to illustrate the advantages of using a derivative-free nonmonotone globalization strategy, with approximated-gradient type methods and also with the inverse SR1 update that could produce nondescent directions. In all cases we use a local variation finite differences approximation to the gradient.     

Optimal matrix approximants in structural identification

Problems of model correlation and system identification are central in the design, analysis, and control of large space structures. Of the numerous methods that have been proposed, many are based on finding minimal adjustments to a model matrix sufficient to introduce some desirable quality into that matrix. In this work, several of these methods are reviewed, placed in a modern framework, and linked to other previously known ideas in computational linear algebra and optimization. This new framework provides a point of departure for a number of new methods which are introduced here. Significant among these is a method for stiffness matrix adjustment which preserves the sparsity pattern of an original matrix, requires comparatively modest computational resources, and allows robust handling of noisy modal data. Numerical examples are included to illustrate the methods presented herein.This research was partially supported by the National Science Foundation under Grant DMS-88-07483 and by NASA under Grant NAG-1-960.     

On the convergence,invariance, and related aspects of a modification of Huang's algorithm

We consider a certain generalization of the Huang family of updates and discuss, firstly, convergence, dependence on parameters, and descent property; secondly, invariance under nonlinear scaling, conjugacy of search directions, and possibility of achieving a better approximation of the inverse of the Hessian. The last three aspects are shown to be dependent on particular choices of parameters. A numerical experiment is presented comparing the performances of the usual and modified BFGS algorithms.The author is indebted to Professor D. H. Jacobson and Professor M. J. D. Powell for helpful discussions during the preparation of this paper.This work was partially supported by a grant from Control Data.     

Computational experience with known variable metric updates

Variable metric methods from the Broyden family are well known and commonly used for unconstrained minimization. These methods have good theoretical and practical convergence properties which depend on a selection of free parameters. We demonstrate, using extensive computational experiments, the influence of both the Biggs stabilization parameter and Oren scaling parameter on 12 individual variable metric updates, two of which are new. This paper focuses on a class of variable metric updates belonging to the so-called preconvex part of the Broyden family. These methods outperform the more familiar BFGS method. We also experimentally demonstrate the efficiency of the controlled scaling strategy for problems of sufficient size and sparsity.