# Upper bound of an optimization problem

Please let me know whether there are closed-form optimal results (or upper bound) for the following optimization problem:

$$\max (\prod_{1\leq i\leq n}(x_i)^{y_i}-\prod_{1\leq i\leq n}(x_i-\alpha)^{y_i})$$

with the following constraints:

$$x_i\geq \alpha; \sum_{1\leq i\leq n} x_i=1$$

$$y_i\in\{0,1,\dots,m\}; \sum_{1\leq i\leq n} y_i=m$$

Only $x_i,y_i$ are variables. $\alpha$ is known and $0\leq \alpha \leq1/n$.

Thank you very much.

• Can you motivate? – MCH Nov 30 '11 at 21:58
• Is this homework? – Jeffε Nov 30 '11 at 23:21
• It's not homework. I'm trying to bound the optimality of piecewise linear approximation of a nonconvex function. – user7430 Dec 1 '11 at 0:42

## 1 Answer

To maximize the expression, given $x_i$, should set $y_i = m$ for the value of $i$ maximizing $x_i - \alpha$.

This implies you should set $x_2, \dots, x_n = \alpha$ and $x_1 = 1 - (n-1) \alpha$.

(I assume here that $0^0 = 1$; otherwise you must set $x_i = \alpha + \epsilon$, and the resulting function does not realize its supremum)

• Thanks. But $\alpha$ is a real number here. – user7430 Dec 1 '11 at 0:05