Minimization of convex functions on the convex hull of a point set |
| |
Authors: | Nikolai D Botkin Josef Stoer |
| |
Institution: | 1. Center of advanced european studies and research (caesar), Ludwig-Erhard-Allee 2, D-53175, Bonn, Germany 2. Institut für Angewandte Mathematik und Statistik der Universit?t Würzburg Am Hubland, D-97074, Würzburg, Germany
|
| |
Abstract: | A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function)
defined on the convex hull of m points in R
n
is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial
cone in R
m
, which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates.
It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating
with the optimal solution. |
| |
Keywords: | Convex functions on simplexes Barycentric coordinates Projection of directions on simplexes |
本文献已被 SpringerLink 等数据库收录! |
|