Combining a path method and parametric linear programming for the computation of competitive equilibria

A path-following philosophy (continuation method, global Newton method) is used to compute equilibria for piecewise linear economies while taking advantage of the linear structure of the model. The existence of a path leading through certain faces of a polyhedral set to an equilibrium point is demonstrated. Computational experience is reported which indicates that this method is promising for models dealing with many commodities and relatively few consumers.Most of this paper has been extracted from the author's doctoral dissertation for the Department of Operations Research at Stanford University; the author would like to express indebtedness to his advisor, R. Wilson. Major revisions were made while the author was at Bell Laboratories in Whippany, New Jersey.     

The value of the stochastic solution in stochastic linear programs with fixed recourse

Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem.This paper is an extension of part of the author's dissertation in the Department of Operations Research, Stanford University, Stanford, California. The research was supported at Stanford by the Department of Energy under Contract DE-AC03-76SF00326, PA#DE-AT03-76ER72018, Office of Naval Research under Contract N00014-75-C-0267 and the National Science Foundation under Grants MCS76-81259, MCS-7926009 and ECS-8012974 (formerly ENG77-06761).     

Diagonalized multiplier methods and quasi-Newton methods for constrained optimization

Two approaches to quasi-Newton methods for constrained optimization problems inR ⁿ are presented. These approaches are based on a class of Lagrange multiplier approximation formulas used by the author in his previous work on Newton's method for constrained problems. The first approach is set in the framework of a diagonalized multiplier method. From this point of view, a new update rule for the Lagrange multipliers which depends on the particular quasi-Newton method employed is given. This update rule, in contrast to most other update rules, does not require exact minimization of the intermediate unconstrained problem. In fact, the optimal convergence rate is attained in the extreme case when only one step of a quasi-Newton method is taken on this intermediate problem. The second approach transforms the constrained optimization problem into an unconstrained problem of the same dimension.The author would like to thank J. Moré and M. J. D. Powell for comments related to the material in Section 13. He also thanks J. Nocedal for the computer results in Tables 1–3 and M. Wright for the results in Table 4, which were obtained via one of her general programs. Discussions with M. R. Hestenes and A. Miele regarding their contributions to this area were very helpful. Many individuals, including J. E. Dennis, made useful general comments at various stages of this paper. Finally, the author is particularly thankful to R. Byrd, M. Heath, and R. McCord for reading the paper in detail and suggesting many improvements.This work was supported by the Energy Research and Development Administration, Contract No. E-(40-1)-5046, and was performed in part while the author was visiting the Department of Operations Research, Stanford University, Stanford, California.     

Path problems in skew-symmetric graphs

We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the skew-symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.This research was done while the first author was at Stanford University Computer Science Department, supported in part by ONR Office of Naval Research Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation.This research was done while the second author was visiting Stanford University Computer Science Department and supported by the above mentioned NSF and Powell Foundation Grants.     

Pivoting for Size and Sparsity in Linear Programming Inversion Routes

^* Present address: The Operations Research Department, Stanford University, Stanford, California 94305, U.S.A. This note reports some experimental results on the inversionof real linear programming bases, with particular emphasis onthe compromise between minimum density and maximum numericalstability. The general features of a linear programming inversionroutine are outlined and the special structure of linear programsconsidered. The main result is a suitable and apparently safe"pivot tolerance" level, together with more general data onthe nature and behaviour of the problems.     

Optimization of unconstrained functions with sparse Hessian matrices—Quasi-Newton methods

Newton-type methods and quasi-Newton methods have proven to be very successful in solving dense unconstrained optimization problems. Recently there has been considerable interest in extending these methods to solving large problems when the Hessian matrix has a known a priori sparsity pattern. This paper treats sparse quasi-Newton methods in a uniform fashion and shows the effect of loss of positive-definiteness in generating updates. These sparse quasi-Newton methods coupled with a modified Cholesky factorization to take into account the loss of positive-definiteness when solving the linear systems associated with these methods were tested on a large set of problems. The overall conclusions are that these methods perform poorly in general—the Hessian matrix becomes indefinite even close to the solution and superlinear convergence is not observed in practice. Research for this paper was performed at the Department of Operations Research, Stanford, CA 94305. The research was partially supported by the Department of Energy Contract AM03-76SF00326. PA# DE-AT03-76ER72018: Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS-7681259, MCS-7926009 and ECS-8012974.     

Sensitivity analysis in posynomial geometric programming

Sensitivity analysis results for general parametric posynomial geometric programs are obtained by utilizing recent results from nonlinear programming. Duality theory of geometric programming is exploited to relate the sensitivity results derived for primal and dual geometric programs. The computational aspects of sensitivity calculations are also considered.This work was part of the doctoral dissertation completed in the Department of Operations Research, George Washington University, Washington, DC. The author would like to express his gratitude to the thesis advisor, Prof. A. V. Fiacco, for overall guidance and stimulating discussions which inspired the development of this research work.     

Shift-invariant bi-inner product functionals are inner products

Bi-inner product functionals generated by a pair of Bessel sequences of L² functions are introduced. It is shown that these functionals are constant multiples of the inner products of L² and l², if and only if they are shift-invariant both in space (or time) and in phase. This result is then applied to characterize dual frames and bi-orthogonal Riesz bases of L². The research of this author was supported by NSF Grant # DMS-95-05460 and ARO Contract #DAAH-04-95-10193, This author is currently visiting the Department of statistics, Stanford University, Stanford, CA 94305. The research of this author was supported by the Texas Coordinating Board of Higher Education under Grant # 999903-109.     

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.     

On theoretical and numerical aspects of the bang-bang-principle

Summary In the first part of this paper we are dealing with theoretical statements and conditions which finally lead to bang-bang-principles. A careful analysis of these theorems is used for the development of a numerical method. This method consists of two stages: During the first iterations the number and approximate location of the switching points of the optimal control are determined. In the second phase a rapidly convergent algorithm determines the exact location. We apply this method successfully to a parabolic boundary control problem and give an extensive discussion of numerical results.The work of the second author on this paper was partially done during his stay at North Carolina State University, Graduate Program in Operations Research and Department of Mathematics, Raleigh, USA     

Mathematical Models for Studying the Value of Motivational Leadership in Teams

Mathematical models are presented for studying the value of leadership in a team where the members interact with each other. The models are based on a leader’s role of motivating each team member to perform closer to his/her maximum ability. These models include controllable parameters whose values reflect the amount of task interdependence among the workers as well as the motivational skill and variability in the skill of the leader. Confirming results—such as the fact that the skill level of the leader is a critical factor in the expected performance of the team—establish credibility in the models. Mathematical analysis and computer simulations are used to provide new managerial insights into the value of the leader—such as the fact that the skill of the leader can be more important than controlling the amount of interdependence among the team members and that having a choice of multiple leaders with no particular motivating skill is beneficial to the performance of small teams but not to large teams.Daniel Solow received a B.S. in Mathematics from Carnegie-Mellon, an M.S. in Operations Research from the University of California at Berkeley, and a Ph. D. in Operations Research from Stanford University. He has been a professor at Case Western Reserve University since 1978. His research interests include complex systems, discrete, linear, and nonlinear optimization. He has also developed systematic methods for teaching mathematical proofs, computer programming, and operations research.Sandy Kristin Piderit is an assistant professor of organizational behavior at the Weatherhead School of Management at Case Western Reserve University, and earned her Ph.D. from the University of Michigan. She studies the roles of relationships among coworkers on their performance and satisfaction with their work environments, and has published studies in the Academy of Management Review, the Journal of Management Studies, and Management Science.Apostolos Burnetas received a Diploma in Electrical Engineering from National Technical University in Athens, Greece, and an M.B.A. and Ph.D. in Operations Research from Rutgers University. He has been at the Department of Operations at Case Western Reserve University and is currently an Associate Professor at the Department of Mathematics at the University of Athens. His research interests include stochastic models and optimization, complex systems, and applications in queueing systems, supply chain and the interface of operations with finance.Chartchai Leenawong received a B.S. in Mathematics from Chulalongkorn University in Bangkok, an M.S. in Computer Science from the Asian Institute of Technology in Bangkok, and a Ph.D. in Operations Research from Case Western Reserve University. His research interests include mathematical modeling of complex systems as applied to business organizations. He has been a professor at King Mongkut’s Institute of Technology Ladkrabang, Bangkok, Thailand since 2002.     

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.     

On the core and nucleolus of minimum cost spanning tree games

We develop two efficient procedures for generating cost allocation vectors in the core of a minimum cost spanning tree (m.c.s.t.) game. The first procedure requires O(n ²) elementary operations to obtain each additional point in the core, wheren is the number of users. The efficiency of the second procedure, which is a natural strengthening of the first procedure, stems from the special structure of minimum excess coalitions in the core of an m.c.s.t. game. This special structure is later used (i) to ease the computational difficulty in computing the nucleolus of an m.c.s.t. game, and (ii) to provide a geometric characterization for the nucleolus of an m.c.s.t. game. This geometric characterization implies that in an m.c.s.t. game the nucleolus is the unique point in the intersection of the core and the kernel. We further develop an efficient procedure for generating fair cost allocations which, in some instances, coincide with the nucleolus. Finally, we show that by employing Sterns' transfer scheme we can generate a sequence of cost vectors which converges to the nucleolus. Part of this research was done while the author was visiting the Department of Operations Research at Stanford University. This research was partially supported by Natural Sciences and Engineering Research Council Canada Grant A-4181.     

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.     

Low order polynomial bounds on the expected performance of local improvement algorithms

We present a general abstract model of local improvement, applicable to such diverse cases as principal pivoting methods for the linear complementarity problem and hill climbing in artificial intelligence. The model accurately predicts the behavior of the algorithms, and allows for a variety of probabilistic assumptions that permit degeneracy. Simulation indicates an approximately linear average number of iterations under a variety of probability assumptions. We derive theoretical bounds of 2en logn and en ² for different distributions, respectively, as well as polynomial bounds for a broad class of probability distributions. We conclude with a discussion of the applications of the model to LCP and linear programming.The author was supported by the New Faculty Research Development Program of the Georgia Institute of Technology. This work is based on the author's Ph.D. thesis, performed under George Dantzig at Stanford 1978–81, at the Systems Optimization Laboratory. While at Stanford, research was supported in part by Department of Energy Contract AM03-76SF00326, PA #DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS76-81259, MCS-7926009 and ECS-8012974; and Army Research Office Contract DAA29-79-C-0110. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

A dual extremum principle for a population equation

A dual extremum principle for the Verhulst-Pearl population equation is constructed using a complementary variational technique. The dual formulation utilizes a minimum principle recently developed by Leitmann to convert the functional optimization problem into a parameter optimization problem.This research was supported in part by NASA Grant No. NGR-36-010-024. The first author would like to thank Dr. W. Stadler, Department of Mechanical Engineering, University of California, Berkeley, for his valuable suggestions.     

Total dual integrality of the linear complementarity problem

Annals of Operations Research - In this paper, we introduce total dual integrality of the linear complementarity problem (LCP) by analogy with the linear programming problem. The main idea of...     

Shortest paths algorithms: Theory and experimental evaluation

We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the NSF and Powell Foundation grants mentioned below. Andrew V. Goldberg was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation. Corresponding author. This work was done while Tomasz Radzik was a Postdoctoral Fellow at SORIE, Cornell University, and supported by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550, and by the Packard Fellowship of éva Tardos.     

A note on computational approaches for the antibandwidth problem

Central European Journal of Operations Research - In this note, we consider the antibandwidth problem, also known as dual bandwidth problem, separation problem and maximum differential coloring...