A simplex algorithm for piecewise-linear programming. I: Derivation and proof
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.
- A simplex algorithm for piecewise-linear programming. III: Computational analysis and applications
- scientific article; zbMATH DE number 776091
- A Dual Simplex Algorithm for Piecewise-Linear Programming
- A simplex algorithm for piecewise-linear programming. II: Finiteness, feasibility and degeneracy
- Piecewise-linear programming: The compact (CPLP) algorithm
- A linear programming approach to the chemical equilibrium problem
- A penalty linear programming method using reduced-gradient basis-exchange techniques
- A simplex algorithm for piecewise-linear programming. I: Derivation and proof
- A simplex algorithm for piecewise-linear programming. III: Computational analysis and applications
- An Improved Algorithm for Discrete l₁ Linear Approximation
- Convex programming and systems of elementary monotonic relations
- Discrete approximation in the L1 norm
- scientific article; zbMATH DE number 3853853 (Why is no real title available?)
- scientific article; zbMATH DE number 3856812 (Why is no real title available?)
- scientific article; zbMATH DE number 3961334 (Why is no real title available?)
- scientific article; zbMATH DE number 3740690 (Why is no real title available?)
- Large-Scale Portfolio Optimization
- Linear Programming via a Nondifferentiable Penalty Function
- Linear Programming with Special Ordered Sets
- Nonlinear Power of Adjacent Extreme Point Methods in Linear Programming
- Optimal estimation of executive compensation by linear programming
- Piecewise-linear programming: The compact (CPLP) algorithm
- Recent advances in linear programming
- The Composite Simplex Algorithm
- Degeneracy in the presence of roundoff errors
- A simplex algorithm for piecewise-linear programming. II: Finiteness, feasibility and degeneracy
- A simplex algorithm for piecewise-linear programming. III: Computational analysis and applications
- A practical anti-cycling procedure for linearly constrained optimization
- Optimal expansion of capacitated transshipment networks
- Algorithms for network piecewise-linear programs: A comparative study
- The empirical performance of a polynomial algorithm for constrained nonlinear optimization
- Vendor selection with price breaks
- On degeneracy in linear programming and related problems
- Piecewise lexicographic programming: A new model for practical decision problems
- A restricted-entry method for a transportation problem with piecewise- linear concave costs
- Optimal objective function approximation for separable convex quadratic programming
- Discontinuous piecewise linear optimization
- Piecewise linear programming via interior points
- The hill detouring method for minimizing hinging hyperplanes functions
- Piecewise-linear functions of several variables; their modelling, local behaviour and extrema
- Exact penalty and optimality condition for nonseparable continuous piecewise linear programming
- A simplex algorithm for network flow problems with piecewise linear fractional objective function
- On location-allocation problems for dimensional facilities
- Vector and matrix apportionment problems and separable convex integer optimization
- A parametric simplex algorithm for biobjective piecewise linear programming problems
- Mixed integer linear programming formulation techniques
- On Lipschitz optimization based on gray-box piecewise linearization
- Solving capacitated part-routing problems with setup times and costs: a Dantzig-Wolfe decomposition-based solution approach
- Objective variation simplex algorithm for continuous piecewise linear programming
- Relationships among linear formulations of separable convex piecewise linear programs
- A simplex algorithm for piecewise-linear programming. I: Derivation and proof
- An efficient algorithm for minimizing a multivariate polyhedral function along a line
- Piecewise-linear programming: The compact (CPLP) algorithm
- Designing satellite communication networks by zero—one quadratic programming
- Solving Piecewise-Linear Programs: Experiments with a Simplex Approach
- Transporting and Mixing Gasses with Different Qualities
- Transporting and Mixing Gasses with Different Qualities
- Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks
- scientific article; zbMATH DE number 1131737 (Why is no real title available?)
- Multiple objective programming with piecewise linear functions
- Formalization of Incremental Simplex Algorithm by Stepwise Refinement
- On a dual method for a specially structured linear programming problem with application to stochastic programming
- A Dual Simplex Algorithm for Piecewise-Linear Programming
- scientific article; zbMATH DE number 776091 (Why is no real title available?)
- An algorithm for piece-wise indefinite quadratic programming problem
- Reverse 1-centre problem on trees under convex piecewise-linear cost function
- Maximin Problem and a Duality Theorem for Mixed‐Integer Quadratic Programming
- An algorithm for linearly-constrained piecewise lexicographic programming problems.
- A simplex algorithm for piecewise-linear fractional programming problems
- A survey of dynamic network flows
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)