Suppose $f:\mathbb{R}_+ \to \mathbb{R}_+$ is a strictly decreasing continuous function such that. Let $n$ be a natural number. I want to solve the following maximization problem $$ S_n = \max_{x_1 \leq \dots \leq x_n} x_1 f(x_1) + (x_2-x_1) f(x_2) + \dots + (x_n-x_{n-1}) f(x_n). $$ See the plot below for graphical illustration when $n=3$. I need to find two things:

  1. Characterization of optimal $(x_1,\dots,x_n)$
  2. Lower bound for the area covered.

This is a standard problem for example in economics (price discrimination) and it looks like someone probably has solved the problem, but I haven't been able to find it.

enter image description here

  • 1
    $\begingroup$ In your first line: "Let f.... such that." Such that what? $\endgroup$ – Jimmy R. Feb 5 '16 at 9:11

It seems to me that you have already done most of the work, writing the problem as an optimization problem for multiple variable. In general calling $\theta$ the actual value of the area as a function of the different points chosen.

$\theta(x_1,x_2,...,x_N) = x_1\cdot f(x_1) + \sum_{I=2}^N{f(x_I)\cdot(x_I-x_{I-1})}$

And we want to find the maximum of theta, so we search the point with all partial derivatives equal to zero

$\begin{cases}\frac{\partial \theta }{\partial x_1} = f(x_1) + x_1 \cdot f^{'}(x_1) - 0 \cdot f^{'}(x_1) - f(x_2) \\ \frac{\partial \theta }{\partial x_2} = f(x_2) + x_2 \cdot f^{'}(x_2) - x_1 \cdot f^{'}(x_2) - f(x_3) \\.... \\ \frac{\partial \theta }{\partial x_N} = f(x_N) + x_N \cdot f^{'}(x_N) - x_{N-1} \cdot f^{'}(x_N) - 0 \end{cases}$

This in addition to the conditions

$ \begin{cases} x_J>x_I & \text{for $J>I$} \\ x_I > 0 & \forall I \end{cases} $

will give you a system of equation that you can solve for the value of $x_I$. The system may not always be solvable, depending on the definition of $f$. Also you should check that the chosen point is a maxima and not a minima.

Some examples: For $f= 1-x$ the solution is always to split in equal part. For $f= 1-x^2$ and $N=2$ the two points are $ \begin{cases} x_1 = \sqrt{\frac{1}{9-2\sqrt3}} \approx 0.425\\ x_2 = \sqrt{\frac{9}{9-2\sqrt3}} \approx 0.736 \end{cases}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.