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.



Optimization problem
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.


