An interior-point method for minimizing convex functions on the convex hull of a point set

Abstract

The article describes an interior-point method for minimizing a smooth strictly convex function f: Rⁿ → R, , on the convex hull P of m points in Rⁿ . The algorithm uses barycentric coordinates for representing points in P and generates points in P with positive coordinates. In particular, the algorithm can be used to compute the orthogonal projection of a point x^c∈ Rⁿ to P.

§ Dedicated to the memory of Prof. Dr. Franti[sbreve]ek No[zbreve]i[cbreve]ka.

Keywords:

• Minimizing convex functions on convex hulls
• Interior-point methods
• Barycentric coordinates

Keywords:

• Mathematics Subject Classifications 2000:
• 90C51
• 90C25

Acknowledgement

The author was supported by the Alexander von Humboldt-Foundation, Germany.

Notes

§ Dedicated to the memory of Prof. Dr. Franti[sbreve]ek No[zbreve]i[cbreve]ka.