Rounding on the standard simplex: regular grids for global optimization
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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\ell ^p$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mi>ℓ</mi> <mi>p</mi> </msup> </math> </EquationSource> </InlineEquation>-norms for <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$p\ge 1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>p</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math> </EquationSource> </InlineEquation>. We show that the minimal <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$\ell ^p$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mi>ℓ</mi> <mi>p</mi> </msup> </math> </EquationSource> </InlineEquation>-distance to the regular grid on the standard simplex can exceed one, even for very fine mesh sizes in high dimensions. Furthermore, for <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$p=1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>p</mi> <mo>=</mo> <mn>1</mn> </mrow> </math> </EquationSource> </InlineEquation>, the maximum minimal distance approaches the <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$\ell ^1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mi>ℓ</mi> <mn>1</mn> </msup> </math> </EquationSource> </InlineEquation>-diameter of the standard simplex. We also put our results into perspective with respect to the literature on approximating global optimization problems over the standard simplex by means of the regular grid. Copyright Springer Science+Business Media New York 2014
