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

Nazareth JL (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 DOI: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: 02 Mar 2016 11:10
URI: http://pure.iiasa.ac.at/12147

Actions (login required)

View Item View Item

International Institute for Applied Systems Analysis (IIASA)
Schlossplatz 1, A-2361 Laxenburg, Austria
Phone: (+43 2236) 807 0 Fax:(+43 2236) 71 313