No label defined (Q3266142)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3148887
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3148887

      Statements

      0 references
      0 references
      0 references
      1958
      0 references
      collection of 14 research papers
      0 references
      existence theorems
      0 references
      concave programming
      0 references
      Kuhn-Tucker theorem
      0 references
      Lagrangian saddle-points
      0 references
      gradient methods
      0 references
      methods of linear and quadratic programming
      0 references
      nonlinear programming
      0 references
      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). \bigskip 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). \bigskip 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 \textit{H. W. Kuhn} and \textit{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. \bigskip 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. \bigskip 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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references