Separable programming. Theory and methods

Publication date 5 November 2001

Published in Applied Optimization (Search for Journal in Brave)

algorithms convergence results convex analysis convex nonlinear programming problems convex separable programs convex sets directional derivatives duality dynamic programming inventory models knapsack polytopes linear approximations linear equality constraints non-smooth approximations optimality criteria separable functions stability stochastic quasi-gradient methods well-posedness

Mathematics Subject Classification ID

Convex functions and convex programs in convex geometry (52A41) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Convex programming (90C25) Nonlinear programming (90C30) Dynamic programming (90C39) Approximation methods and heuristics in mathematical programming (90C59)

Review text

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.

Recommendations

Cited in

(14)

This page was built for publication: Separable programming. Theory and methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5948302)