Separable Programming: Theory and Methods

✍ Scribed by Stefan M. Stefanov (auth.)

• Publisher: Springer US
• Year: 2001
• Tongue: English
• Leaves: 323
• Series: Applied Optimization 53
• Edition: 1
• Category: Library

✦ Synopsis

In this book, the author considers separable programming and, in particular, one of its important cases - convex separable programming. Some general results are presented, techniques of approximating the separable problem by linear programming and dynamic programming are considered.
Convex separable programs subject to inequality/ equality constraint(s) and bounds on variables are also studied and iterative algorithms of polynomial complexity are proposed.
As an application, these algorithms are used in the implementation of stochastic quasigradient methods to some separable stochastic programs. Numerical approximation with respect to I₁ and I₄ norms, as a convex separable nonsmooth unconstrained minimization problem, is considered as well.
Audience: Advanced undergraduate and graduate students, mathematical programming/ operations research specialists.

✦ Table of Contents

Front Matter....Pages i-xix
Preliminaries: Convex Analysis and Convex Programming....Pages 1-61
Front Matter....Pages 63-63
Introduction. Approximating the Separable Problem....Pages 65-77
Convex Separable Programming....Pages 79-90
Separable Programming: A Dynamic Programming Approach....Pages 91-139
Front Matter....Pages 141-141
Statement of the Main Problem. Basic Result....Pages 143-150
Version One: Linear Equality Constraints....Pages 151-158
The Algorithms....Pages 159-174
Version Two: Linear Constraint of the Form “≥”....Pages 175-180
Well-Posedness of Optimization Problems. On the Stability of the Set of Saddle Points of the Lagrangian....Pages 181-194
Extensions....Pages 195-206
Applications and Computational Experiments....Pages 207-222
Front Matter....Pages 227-227
Approximations with Respect to ℓ 1 and ℓ ∞ -Norms: An Application of Convex Separable Unconstrained Nondifferentiable Optimization....Pages 229-250
About Projections in the Implementation of Stochastic Quasigradient Methods to Some Probabilistic Inventory Control Problems. The Stochastic Problem of Best Chebyshev Approximation....Pages 251-262
Integrality of the Knapsack Polytope....Pages 263-266
Back Matter....Pages 269-316

✦ Subjects

Optimization