A variable-metric method for function minimization derived from invariancy to nonlinear scaling

The effect of nonlinearly scaling the objective function on the variable-metric method is investigated, and Broyden's update is modified so that a property of invariancy to the scaling is satisfied. A new three-parameter class of updates is generated, and criteria for an optimal choice of the parameters are given. Numerical experiments compare the performance of a number of algorithms of the resulting class.The author is indebted to Professor S. S. Oren, Economic Engineering Department, Stanford University, Stanford, California, for stimulating discussions during the development of this paper. He also recognizes the financial support by the National Research Council of Italy (CNR) for his stay at Stanford University.     

A geometric method in nonlinear programming

A differential geometric approach to the constrained function maximization problem is presented. The continuous analogue of the Newton-Raphson method due to Branin for solving a system of nonlinear equations is extended to the case where the system is under-determined. The method is combined with the continuous analogue of the gradient-projection method to obtain a constrained maximization method with enforced constraint restoration. Detailed analysis of the global behavior of both methods is provided. It is shown that the conjugate-gradient algorithm can take advantage of the sparse structure of the problem in the computation of a vector field, which constitutes the main computational task in the methods.This is part of a paper issued as Stanford University, Computer Science Department Report No. STAN-CS-77-643 (Ref. 45), which was presented at the Gatlinburg VII Conference, Asilomar, California, 1977. This work was supported in part by NSF Grant No. NAT BUR OF ECON RES/PO No. 4369 and by Department of Energy Contract No. EY-76-C-02-0016.The main part of this work was presented at the Japan-France Seminar on Functional Analysis and Numerical Analysis, Tokyo, Japan, 1976. The paper was prepared in part while the author was a visitor at the Department of Mathematics, North Carolina State University, Raleigh, North Carolina, 1976–77, and was completed while he was a visitor at the Computer Science Department, Stanford University, Stanford, California, 1977. He acknowledges the hospitality and stimulating environment provided by Professor G. H. Golub, Stanford University, and Professors N. J. Rose and C. D. Meyer, North Carolina State University.     

A generalization of Ehrenfeucht’s game and some applications

The concept of α, β-elementary equivalence of two relational structures is defined. Sufficient and necessary conditions are given for this notion by generalizing Ehrenfeucht’s game in algebraic terms. Some results, in a first order language with generalized quantifier, are obtained. This paper is part of the author’s doctoral dissertation which was prepared under the supervision of Professor Azriel Levy at the Hebrew University of Jerusalem. The author wishes to thank Professor Levy for his kind assistance.     

Multi-excited random walks on integers

We introduce a class of nearest-neighbor integer random walks in random and non-random media, which includes excited random walks considered in the literature. At each site the random walker has a drift to the right, the strength of which depends on the environment at that site and on how often the walker has visited that site before. We give exact criteria for recurrence and transience and consider the speed of the walk.Most of this work was done while the author was Szegö Assistant Professor at Stanford University.     

An infeasible method of large-system optimization by direct coordination of subsystem inputs

An infeasible method of large-system optimization is proposed. The dual gap is resolved by use of the generalized Lagrangian as in the previous methods due to Stephanopouloset al. and Watanabeet al. The values of subsystem inputs are, however, coordinated in the second level, instead of being adjusted in the first level, as in previous methods. As a result, in contrast with previous methods, the subproblems in the first level include a small number of variables to be adjusted; in addition, the generalized Lagrangian is decomposable in a simple manner. Further, the decomposition is not subject to any restriction, which is often encountered in feasible methods.The authors would like to acknowledge the valuable comments given by Professor D. G. Luenberger of Stanford University, Stanford, California.     

Characterization of nondominated controls in terms of solutions of weighting problems

The problem of continuously dynamic multiobjective optimization, or multiobjective control, is discussed. The concepts of nondominated controls and viable controls are introduced. For a class of nonlinear dynamic systems, the convexity of their controlled Carathéodory trajectories is proved. Based on this convexity, sufficient conditions are given for the solution of a multiobjective control problem to be obtained in terms of solutions of weighting problems.This work was partly done at the Huazhong University of Science and Technology, Wuhan, China. The author is indebted to Professor Chen Ting for his advice. The author wishes to thank Professor G. Leitmann for his favorable comments. The author is also grateful to Ms. Mary S. Linn at the University of Kansas, who helped him improve the English presentation of this paper.     

Modeling and Analyzing Cultural Influences on Project Team Performance

Research on international joint ventures (IJV) finds managers experience difficulties in working with cross-cultural teams. Our research aims to understand how cultural differences between Japanese and American firms in IJV projects effect team performance through computational experimentation. We characterize culture and cultural differences using two dimensions: practices and values.Practices refer to each cultures typical organization style, such as centralization of authority, formalization of communication, and depth of organizational hierarchy. Values refer to workers preferences in making task execution and coordination decisions. These preferences drive specific micro-level behavior patterns for individual workers. Previous research has documented distinctive organization styles and micro-level behavior patterns for different nations. We use a computational experimental design that sets task complexityat four levels and team experience independently at three levels, yielding twelve organizational contexts. We then simulate the four possible combinations of USvs.Japanese organization style and individual behavior in each context to predict work volume, cost, schedule andprocess quality outcomes. Simulation results predict that: (1) both Japanese and American teams show better performance across all contexts when each works with its familiar organization style; (2) the Japanese organization style performs better under high task complexity, with low team experience; and (3) process quality risk is not significantly affected by organization styles. In addition, culturally driven behavior patterns have less impact on project outcomes than organization styles. Our simulation results are qualitatively consistent with both organizational and cultural contingency theory, and with limited observations of US-Japanese IJV project teams.This paper won the best Ph.D. student paper award at NAACSOS 2004, Pittsburgh PA. NAACSOS is the main conference of the North American Association for Computational Social and Organizational Science.Tamaki Horii is a Ph.D. candidate in the Civil and Environmental Engineering Department at Stanford University. His research focuses on various aspects of cultural and institutional influences on team performance. He is currently developing new models to capture and distinguish the cultural factors that emerging in global projects. He received a MS in Architecture at the Science University of Tokyo and a MS in Civil and Environmental Engineering at Stanford University.Yan Jin is an Associate Professor of Mechanical Engineering at University of Southern California and Director of USC IMPACT Laboratory , and a visiting Professor of Civil Engineering Department at Stanford University. He received his Ph.D. degree in Naval Engineering from the University of Tokyo in 1988. Prior to joining USC faculty in the Fall of 1996, Dr. Jin was a Senior Research Scientist at Stanford University. His current research interests include design methodology, agent-based collaborative engineering, and computational organization modeling. Dr. Jin is a recipient of National Science Foundation CAREER Award (1998), TRW Excellence in Teaching Award (2001), Best Paper in Human Information Systems (5th World Multi-Conference on Systemic, Cybernetics and Informatics, 2001), and Xerox Best Paper Award (ASME International Conference on Design Theory and Methodology, 2002).Raymond E. Levitt is a Professor of Civil Engineering Department at Stanford University, a Professor, by Courtesy, Medical Informatics, an Academic director of Stanford Advanced Project Management Executive Program, and a Director of Collaboratory for Research on Global Projects (CRGP) . His Virtual Design Team (VDT) research group has developed new organization theory, methodology and computer simulation tools to design organizations that can optimally execute complex, fast-track, projects and programs. VDT is currently being extended to model and simulate service/maintenancework processes such as health care delivery and offshore platform maintenance. Ongoing research by Professor Levitts Virtual Design Team research group attempts to model and simulate the significant institutional costs that can arise in global projects due to substantial differences in goals, values and cultural norms among project stakeholders.     

Neighboring extremals of dynamic optimization problems with path equality constraints

Neighboring extremals of dynamic optimization problems with path equality constraints and with an unknown parameter vector are considered in this paper. With some simplifications, the problem is reduced to solving a linear, time-varying two-point boundary-value problem with integral path equality constraints. A modified backward sweep method is used to solve this problem. Two example problems are solved to illustrate the validity and usefulness of the solution technique. This research was supported in part by the National Aeronautics and Space Administration under NASA Grant No. NCC-2-106. The author is indebted to Professor A. E. Bryson, Jr., Department of Aeronautics and Astronautics, Stanford University, for many stimulating discussions.     

The fundamental theorem of algebra for monosplines satisfying boundary conditions

The existence and uniqueness of monosplines satisfying certain boundary conditions with a maximal prescribed number of zeros is established. This results is of value in characterizing optimal quadrature formulas and in problems of best approximations involving free knots. Supported in part by Office of Naval Research, Contract NOOO14-67-A-0112-0015 at Stanford University, Stanford, California.     

Asymptotic bias of the least squares estimator for multivariate autoregressive models

Summary The asymptotic bias of the least squares estimator for the multivariate autoregressive models is derived. The formulas for the low order univariate autoregressive models are given in terms of the simple functions of parameters. Our results are useful to the bias correction method of the least squares estimation. This work was supported by National Science Foundation Grant SES79-13976 at the Institute for Mathematical Studies in the Social Sciences, Stanford University. This paper is a revision of Discussion Paper No. 504, The Center for Mathematical Studies in Economics and Management Science, Northwestern University, October 1981.     

The block decomposition of a vandermonde matrix and its applications

This paper presents a new algorithm for the solution of linear equations with a Vandermonde coefficient matrix. The algorithm can also be used to solve the dual problem. Since the algorithm uses a block decomposition of the matrix, it is especially suitable for parallel computation. A variation of the block decomposition leads to the efficient solution of the interpolation problem with complex-conjugate interpolation points where the coefficients of the interpolating polynomial are real. In addition the algorithm can be used to solve some kinds of confluent Vandermonde systems.W. P. Tang is a graduate student in the Computer Science Department at Stanford University, on leave from the Institute of Computing Technology of the Chinese Academy of Science in Peking.The work of Professor Golub was in part supported by NSF Grant No. MCS78-11985.     

Quasiconcavity and nondominated solutions in multiobjective programming

In the multiobjective programming literature, the concavity of the objectives is usually assumed to be a sufficient condition in seeking Pareto-optimal solutions. This paper investigates nondominated solutions associated with dominance cones via the assumption of the quasiconcavity of the objectives. Necessary as well as sufficient conditions for such quasiconcave multiobjective programming problems are obtained.The author is indebted to one of the referees for detailed constructive comments and suggestions. Thanks are also due to the late Professor Abraham Charnes, University of Texas at Austin, and Professor Zhimin Huang, Adelphi University.     

Performance Variability and Project Dynamics

We present a dynamical model of complex cooperative projects such as large engineering design or software development efforts, comprised of concurrent and interrelated tasks. The model contains a stochastic component to account for temporal fluctuations both in task performance and in the interactions between related tasks. We show that as the system size increases, so does the average completion time. Also, for fixed system size, the dynamics of individual project realizations can exhibit large deviations from the average when fluctuations increase past a threshold, causing long delays in completion times. These effects are in agreement with empirical observation. We also show that the negative effects of both large groups and long delays caused by fluctuations may be mitigated by arranging projects in a hierarchical or modular structure. Our model is applicable to any arrangement of interdependent tasks, providing an analytical prediction for the average completion time as well as a numerical threshold for the fluctuation strength beyond which long delays are likely. In conjunction with previous modeling techniques, it thus provides managers with a predictive tool to be used in the design of a project's architecture. Bernardo A. Huberman is a Senior HP Fellow and Director of the Information Dynamics Laboratory. He is also a Consulting Professor of Physics at Stanford University. For the past ten years he has concentrated on understanding distributed processes and on the design of mechanisms for information aggregation and the protection of privacy as well as market-based distributed resource allocation systems. Dennis Wilkinson is a recent graduate of Stanford University with a doctorate in Physics, and has accepted a position in the Department of Defense. His research interests include dynamics of social networks and other stochastic systems, information extraction from large, complex networks, and techniques in distributed computing.     

New Sufficiency for Global Optimality and Duality of Mathematical Programming Problems via Underestimators

We present new conditions for a Karush-Kuhn-Tucker point to be a global minimizer of a mathematical programming problem which may have many local minimizers that are not global. The new conditions make use of underestimators of the Lagrangian at the Karush-Kuhn-Tucker point. We establish that a Karush-Kuhn-Tucker point is a global minimizer if the Lagrangian admits an underestimator, which is convex or, more generally, has the property that every stationary point is a global minimizer. In particular, we obtain sufficient conditions by using the fact that the biconjugate function of the Lagrangian is a convex underestimator at a point whenever it coincides with the Lagrangian at that point. We present also sufficient conditions for weak and strong duality results in terms of underestimators. The authors are grateful to Professor Gue Myung Lee, Pukyong National University, Korea, and the referees for their comments and suggestions which have contributed to the final preparation of the paper. The work was partially supported by the Australian Research Council Discovery Project Grant.     

Sufficient conditions for the optimal control of a class of systems with continuous lags

Sufficient conditions in the form of a maximum principle are obtained for the optimal control of a system described by integro-differential equations and subject to some specified path constraints. The conditions are relaxed to allow for jumps in the adjoint variables at the junction points, provided a certain convexity hypothesis is satisfied for the constraint set at these points.This research was partially supported at Stanford University by the Office of Naval Research, Contract No. N-00014-67-A-0112-0011, by the National Science Foundation, Grant No. GP-31393, and by the US Atomic Energy Commission, Contract No. AT(04-3)-326-PA-18. It was also supported by the Department of Economics at Rice University.     

The connection between normalizable and spectral operators

A necessary and sufficient condition for an operator to be normalizable is given in terms of Dunford’s spectral theory. This paper is a part of the author’s Ph.D. thesis to be submitted to the Hebrew University. The author wishes to express his indebtedness to Professor S. R. Foguel for his guidance and kind encouragement.     

An extension of the frank and Wolfe method of feasible directions

The Frank and Wolfe method of feasible directions is shown to be a case of the more general computational approach of inner linearization followed by restriction. An extension is proposed based on this observation. The extended procedure converges, and under certain conditions the asymptotic convergence rate is geometric. Limited computational experience comparing the two procedures is reported.The author is grateful to Mr. Peter Friesen for help with the computational work and to the Graduate School of Business, Stanford University for their support of this research.     

Duality in inexact fractional programming with set-inclusive constraints

This paper extends the fractional programming problem with set-inclusive constraints studied earlier by replacing every coefficient vector in the objective function with a convex set. A dual is formulated, and well-known duality results are established. A numerical example illustrates the dual strategy to obtain the value of the initial problem.The research of the first author was conducted while he was on sabbatical at the Department of Operations Research, Stanford University, Stanford, California. The financial assistance of the International Council for Exchange of Scholars is gratefully acknowledged. The author is grateful to the Department of Operations Research at Stanford for the use of its research facilities.     

In Short

Abstract

The California Idea: 1850 to the 1960 Master Plan: by John Aubrey Douglas. Stanford, CA: Stanford University Press, 2000, 460 pp., $55.