Optimization Online


Rounding on the standard simplex: regular grids for global optimization

Immanuel M. Bomze (immanuel.bomze***at***univie.ac.at)
Stefan Gollowitzer (stefan.gollowitzer***at***univie.ac.at)
E. Alper Yildirim (alperyildirim***at***ku.edu.tr)

Abstract: Given a point on the standard simplex, we calculate a proximal point on the regular grid which is closest with respect to any norm in a large class, including all $\ell^p$-norms for $p\ge 1$. We show that the minimal $\ell^p$-distance to the regular grid on the standard simplex can exceed one, even for very fine mesh sizes in high dimensions. Furthermore, for $p=1$, the maximum minimal distance approaches the $\ell^1$-diameter of the standard simplex. We also put our results into perspective to the literature on approximating global optimization problems over the standard simplex by means of the regular grid.

Keywords: approximation; maximin distance; proximal point

Category 1: Global Optimization (Theory )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 09/17/2013
Entry Accepted: 09/17/2013
Entry Last Modified: 10/19/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society