Separable programming. Theory and methods (Q5948302)

The author considers separable convex nonlinear programming problems, where the objective function and constraints consist of sums of convex functions depending on a single variable only. In most cases, it is assumed in addition that the functions are twice continuously differentiable. The first chapter of the book introduces convex analysis, i.e., convex sets and functions, directional derivatives, optimality criteria, and duality. Part I consists of three further chapters to define separable functions and linear approximations by adjacent function values over a given grid. A broader discussion of a dynamic programming approach follows together with some OR applications, particularly inventory models. In Part II, convex separable programs with bounds on variables are analyzed in more detail. Optimality conditions are derived in Chapter 5, and extensions for linear equality constraints in Chapter 6. Algorithms and convergence results for differentiable, convex and separable problems are the main topics of Chapters 7 and 8, whereas well-posedness and stability are studied in Chapter 9. Extensions and computational test results are found in Chapters 10 and 11. Part III of the book consists of three further chapters, where alternative non-smooth approximations, stochastic quasi-gradient methods and knapsack polytopes are outlined. The book covers the more classical area of convex, separable programming in a mathematically rigorous way. More modern concepts, such as interior point methods, are not treated. New topics are illustrated by detailed examples. Proofs are included, as well as a couple of applications from operations research. Algorithms and theoretical analysis are sometimes difficult to read because of complex index sets.