A simplex algorithm for piecewise-linear programming. I: Derivation and proof

From MaRDI portal





The paper develops a direct extended-simplex approach to the minimization of a convex separable piecewise-linear function under linear constraints of the form \(Ax=b\). The starting observation is that any convex piecewise-linear function \(f_ k\) of one variable \(x_ k\) can be specified up to an additive constant by the increasing sequence of its breakpoints \(\gamma^ h_ k\) \((h=1,2...)\) along with the increasing sequence of its slopes \(c^ h_ k\) \((h=1,2...)\) on the intervals \([\gamma^ h_ k\), \(\gamma_ k^{h+1}]\), while the conjugate of \(f_ k\) is defined (also up to an additive constant) simply by interchanging the roles of breakpoints and slopes in the definition of \(f_ k\). This suggests the concise notation \([c/\gamma]_ kx_ k\) and \([\gamma \setminus c]_ k\xi_ k\) for \(f_ k\) and its conjugate, and \[ [c,\gamma]x=\sum^{n}_{k=1}[c/\gamma]_ kx_ k,\quad [\gamma \setminus c]\xi =\sum^{n}_{k=1}[\gamma \setminus c]_ k\xi_ k \] for a convex separable piecewise-linear function f(x) and its dual \(f^*(\xi)\). With this notation, several important propositions can be formulated and proven in an elegant way. To extend the bounded-variable simplex algorithm to convex separable piecewise-linear programs, a basis matrix B is defined by m independent columns of the constraint matrix A (just as for bounded-variable linear programs) while a basic solution is defined by fixing each nonbasic variable at one of its breakpoints in the objective function. The criteria for the choice of the entering and the leaving variable differ, but not much, from corresponding criteria in the bounded-variable case. At each iteration, the entering variable is pushed away (either up or down) from its current breakpoint value, until some variable (the leaving one) reaches another breakpoint. Derivation and proof of the algorithm are given under convenient assumptions which will be removed or relaxed, as the author announces, in a subsequent paper.




Cited in
(46)








This page was built for publication: A simplex algorithm for piecewise-linear programming. I: Derivation and proof

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