×

Studies in linear and non-linear programming. (English) Zbl 0091.16002

Stanford Mathematical Studies in the Social Sciences. 2. Stanford, CA: Stanford University Press. 229 p. (1958).
Contents:
Chap. 1. Kenneth J. Arrow and Hirofumi Uzawa, Introduction. Part. I. Existence theorems.
Chap. 2. Hirofumi Uzawa, A theorem on convex polyhedral cones (p. 23).
Chap. 3. Hirofumi Uzawa, The Kuhn-Tucker theorem in concave programming (p. 32).
Chap. 4. Leonid Hurwicz, Programming in linear spaces (p. 38).
Chap. 5. Leonid Hurwicz and Hirofumi Uzawa, A note on the Lagrangian saddle-points (p. 103).


Part II. Gradient method.
Chap. 6. Kenneth J. Arrow and Leonid Hurwicz, Gradient method for concave programming. I: Local results (p. 117).
Chap. 7. Hirofumi Uzawa, Gradient method for con-cave programming. II: Global stability in the strictly concave case (p. 127).
Chap. 8. Kenneth J. Arrow and Leonid Hurwicz, Gradient method for concave programming. III: Further global results and applications to resource allocation (p. 133).
Chap. 9. Thomas Marschak, An example of a modified gradient method for linear programming (p. 146).
Chap. 10. Hirofumi Uzawa, Iterative methods for concave programming (p. 154).
Chap. 11. Kenneth J. Arrow and Robert M. Solow, Gradient methods for constrained maxima, with weakened assumptions (p. 166).


Part III. Methods of linear and quadratic programming.
Chap. 12. Hirofumi Uzawa: An elementary method for linear programming (p. 179).
Chap. 13. Kenneth J. Arrow and Samuel Karlin: Price speculation under certainty (p. 189).
Chap. 14. Kenneth J. Arrow and Selmer M. Johnson: A feasibility algorithm for one-way substitution on process analysis (p. 198).
Chap. 15. Hollis B. Chenery and Hirofumi Uzawa: Non-linear programming in economic development (p. 203).
This integrated collection of 14 research papers contains three Parts, preceded by an introductory chapter. The latter gives an account of the background to and of the contents of the various papers and this review will be mainly based on it.
Part I consists of Chapters 2 to 5. It is known that a convex polyhedral cone can be defined either as the intersection of a finite number of half-spaces, or equivalently as the set of all linear combinations, with non-negative coefficients, of a finite number of vectors.
In Chapter 2 H. Uzawa gives an explicit formula for those vectors which span a convex polyhedral cone, given as the intersection of half-spaces. This is then used for constructive proofs of some known theorems. In the remaining chapters modifications and generalizations of the Kuhn-Tucker Theorem (see H. W. Kuhn and A. W. Tucker [Nonlinear programming. Proc. Berkeley Symp. Math. Stat. Probab., California 1950, 481–492 (1951; Zbl 0044.05903)]) are presented, of which the following, from Chapter 4, is a very general case: Let \(\mathcal H\) and \(\mathcal Z\) be linear spaces, \(P_x\) and \(P_z\) closed convex cones in \(\mathcal H\) and \(\mathcal Z\) respectively, \(f\) a concave functional on \(P_x\), and \(g\) a concave function on \(P_x\) into \(\mathcal Z\); let there also exist a point \(x^0\) such that \(x^0\) in \(\mathcal H\) and \(g(x^0)\) is in the interior of \(P_z\). Then \(\bar x\in\mathcal H\) maximizes \(f(x)\) subject to \(x\ge 0\) in \(\mathcal H\) and \(g(x)\ge 0\) in \(\mathcal Z\) if and only if there exists \(\bar z^*\in\mathcal Z\) such that \((\bar x, \bar z^*)\) is a non-negative saddle point of the Lagrangian \(f(x) + (z^*, g(x))\). The condition that \(g(x^0)\) be in the interior of \(P_x\) for some \(x^0\ge 0\) can be replaced by a set of other conditions.


Part II consists of Chapters 6 to 11. They deal with the use of what is here called the gradient method to solve programming problems. The following results will give an idea of the approach. If \(\psi(u,v)\) is convex in \(v\) for each \(u\) (special case: linear in \(v)\) and if \(\Vert \partial^2\psi/\partial u_h\partial u_k\Vert\) is negative definite at the saddle point \((\bar u, \bar v)\), then the solution of the gradient process, i. e. \(du_i/dt = 0\) if \(u_i = 0\), \(\partial \psi/ \partial u_i < 0\); \(= \partial \psi/\partial u_i\) otherwise, and \(dv_j/dt = 0\) if \(v_j = 0\), \(\partial\psi/\partial u_j > 0\); and \(= - \partial\psi/\partial v_j\) otherwise, has for \(t\to\infty\) the limit \(\bar u_i, \bar v_j\) provided the starting point is sufficiently close to the saddle point.
Let \(f(x)\) and \(g_j(x)\) be concave and let \(\rho_j(u)\) for each \(j\) be a strictly increasing strictly concave function with \(\rho_j(0) = 0\). Then the gradient method applied to the Lagrangian \(f(x) + \sum_j y_j\rho_j[g_j(x)]\) converges to a limit \((\hat u, \hat v)\), where \(\hat x\) is the constrained maximum of \(f(x)\) subject to \(g_j(x)\ge 0\). This supplies an algorithm for all concave programming problems.
Computational problems of stability are discussed, concerning the approximation of the differential equation above by a suitable difference equation, and a number of ways are mentioned in which the gradient method can be applied to Linear Programming problems.


In the four chapters of Part III certain kinds of linear and nonlinear problems are solved, some by methods outlined above, and others by specially adapted arguments. They are aimed at showing the usefulness of programming techniques in applied economics problems, such as price speculation, allocation of processes to different types of machines, and inter-industry programming. In Chapter 12 the results of Chapter 2 are applied to the solution of Linear Programming problems. This algorithm is useful when the number of variables and constraints is small; otherwise it is less efficient than the Simplex Method.
Reviewer: Steven Vajda

MSC:

90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90-06 Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming
00B15 Collections of articles of miscellaneous specific interest
90C05 Linear programming
90C20 Quadratic programming
90C30 Nonlinear programming

Citations:

Zbl 0044.05903