Nazareth, J.L.
(1985).
*An efficient algorithm for minimizing a multivariate polyhedral function along a line.*
In:
Mathematical Programming Essays in Honor of George B. Dantzig Part I.
pp. 116-125 Berlin/Heidelberg, Germany: Springer.
ISBN 978-3-642-00919-8 10.1007/BFb0121046.

## Abstract

We consider the problem of finding a minimum along a given direction d∈ℝ m , of a separable function ά(χ)=Σ l=1 m ψ l (χ l ). Each component ψ l (χ l ) is a piecewise-linear convex function expressed in slope-intercept form. To solve this problem we propose a specialized version of the generalized upper bounding (GUB) algorithm of Dantzig and Van Slyke. Each step of the simplex cycle is explicitly expressed as a simple algebraic formula and basis matrix operations are completely eliminated. This results in a concise, elegant and efficient algorithm.

Item Type: | Book Section |
---|---|

Uncontrolled Keywords: | Piecewise-Linear Minimization; Line Search; Polyhedral Functions; Nonsmooth Minimization; Specialized; GUB |

Depositing User: | Romeo Molina |

Date Deposited: | 02 Mar 2016 11:10 |

Last Modified: | 27 Aug 2021 17:40 |

URI: | https://pure.iiasa.ac.at/12147 |

### Actions (login required)

View Item |