Optimization problem

Question

I'm trying to solve a very practical optimization problem and I think I hit a dead-end.

There are $N$ products ($N \sim 50$). Each product can have a price $p_i$ in range between 1 and 40 dollars. For each product there's a non-decreasing demand function $d_i(p)$, $a > b \Rightarrow d(a) >= d(b)$. Demand functions are produced by running Monte-Carlo simulations, represented by a table and from the look of it cannot be easily approximated by something analytical and differentiable.

Total cost of all products is what is being maximized.

$\max \sum_{i} p_i d_i(p_i)$

There's only one constraint, it's a non-linear constraint on average price:

$\frac{\sum_{i} p_i d_i(p_i))}{\sum_{i} v_i d_i(p_i)} \le C$

where $v_i$ is a constant specified in advance for each product.

Any suggestions? I tried some heuristics, but results are highly unstable. Small change in $C$ leads to very different results.

Any help would be highly appreciated.

Answer 1

I would recommend first thinking carefully about the trivial case $N=1$ and the nontrivial case $N=2$.

For $N=1$, the constraint is simply $pd(p) \le Cvd(p)$, so it's pretty clear that you'll maximize $pd(p)$ when $p=Cv$ (since $d$ is non-decreasing).

For $N=2$, the constraint is

$$pd_1(p) + qd_2(q) \le Cv_1d_1(p)+Cv_2d_2(q).$$

(I'm writing $p$ and $q$ for $p_1$ and $p_2$ here, to reduce the number of subscripts.) Now let $p=Cv_1+x$ and $q=Cv_2-y$. The constraint boils down to one relating $x$ and $y$:

$$xd_1(Cv_1+x) \le yd_2(Cv_2-y).$$

Given that the demand functions $d_1$ and $d_2$ are unspecified (beyond being non-decreasing), I don't see how you can hope to say much about where the max is achieved. But maybe I'm missing something.