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.     

Long steps in an O(n 3 L) algorithm for linear programming

We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein—Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n ³ L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous primal-only initialization actually reduces the complexity to less than O(m ^1.5 n ^1.5 L).     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

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.     

Multilevel least-change Newton-like methods for equality constrained optimization problems

This paper deals with the application of multilevel least-change Newton-like methods for solving twice continuously differentiable equality constrained optimization problems. We define multilevel partial-inverse least-change updates, multilevel least-change Newton-like methods without derivatives and multilevel projections of fragments of the matrix for Newton-like methods without derivatives. Local andq-superlinear convergence of these methods is proved. The theorems here also imply local andq-superlinear convergence of many standard Newton-like methods for nonconstrained and equality constraine optimization problems.     

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.     

Engineering graph-based models for dynamic timetable information systems

In the last years we have witnessed remarkable progress in providing efficient algorithmic solutions to the problem of computing best journeys (or routes) in schedule-based public transportation systems. We have now models to represent timetables that allow us to answer queries for optimal journeys in a few milliseconds, also at a very large scale. Such models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. Array-based models have been shown to be very effective in terms of query time, while graph-based ones usually answer queries by computing shortest paths, and hence they are suitable to be combined with the speed-up techniques developed for road networks.In this paper, we study the behavior of graph-based models in the prominent case of dynamic scenarios, i.e., when delays might occur to the original timetable. In particular, we make the following contributions. First, we consider the graph-based reduced time-expanded model and give a simplified and optimized routine for handling delays, and a re-engineered and fine-tuned query algorithm. Second, we propose a new graph-based model, namely the dynamic timetable model, natively tailored to efficiently incorporate dynamic updates, along with a query algorithm and a routine for handling delays. Third, we show how to adapt the ALT algorithm to such graph-based models. We have chosen this speed-up technique since it supports dynamic changes, and a careful implementation of it can significantly boost its performance. Finally, we provide an experimental study to assess the effectiveness of all proposed models and algorithms, and to compare them with the array-based state of the art solution for the dynamic case. We evaluate both new and existing approaches by implementing and testing them on real-world timetables subject to synthetic delays.Our experimental results show that: (i) the dynamic timetable model is the best model for handling delays; (ii) graph-based models are competitive to array-based models with respect to query time in the dynamic case; (iii) the dynamic timetable model compares favorably with both the original and the reduced time-expanded model regarding space; (iv) combining the graph-based models with speed-up techniques designed for road networks, such as ALT, is a very promising approach.     

Opinion Dynamics and Unifying Principles: A Global Unifying Frame

I review and extend the set of unifying principles that allow comparing all models of opinion dynamics within one single frame. Within the Global Unifying Frame (GUF), any specific update rule chosen to study opinion dynamics for discrete individual choices is recast into a probabilistic update formula. The associated dynamics is deployed using a general probabilistic sequential process, which is iterated via the repeated reshuffling of agents between successive rounds of local updates. The related driving attractors and tipping points are obtained with non-conservative regimes featuring both threshold and threshold-less dynamics. Most stationary states are symmetry broken, but fifty–fifty coexistence may also occur. A practical procedure is exhibited for several versions of Galam and Sznajd models when restricted to the use of three agents for the local updates. Comparing these various models, some are found to be identical within the GUF. Possible discrepancies with numerical simulations are discussed together with the difference between the GUF procedure and a mean field approach.     

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

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

A two-step superlinearly convergent projected structured BFGS method for constrained nonlinear least squares

We present an exact penalty approach for solving constrained non-linear least-squares problems, when the projected structured Hessian is approximated by a projected version of the structured BFGS formula and prove its local two-step Q-superlinear convergence. The numerical results obtained in an extensive comparative testing experiment confirm the approach to be reliable and efficient.