An efficient algorithm for minimizing a multivariate polyhedral function along a line

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.

Full text not available from this repository.

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