# Specific optimization problem algorithm

This task is related to optimization problems, where we set the objective function equal to a given fixed number, subject to a number of constraints. Consider a gambling situation. We have a particular box, with one of $$n$$ items inside. The probability of getting $$i$$th item from the box is $$p_i$$. Pulling from a particular item from the box is an elementary outcome: these outcomes are independent of each other, and the sum of the probabilities of the onset of all elementary outcomes is equal to one. A player wants to open the box, and he pays a price of $$C$$ for this. Each of $$n$$ items that may be pulled from the box has its value $$c_i,i=(1,n)$$ ̅. These values may be smaller or significantly greater than the box price. Let $$x$$ is a random variable, which reflects the value of an item pulled from the box. This is a discrete random variable, therefore, its expectation is: $$E(x)=\sum_{i=1}^nc_i p_i$$ A game owner has a desired level of profitability, which can be calculated as follows: $$R(x)=\frac{C-E(x)}{C}$$ In addition, the owner wants this profitability to be controlled by changing the probabilities of elementary outcomes in the way, such that $$R(x)=R_0$$, the desired level of profitability. Box price and values of all items, as well as their number are constants. Some probabilities, for example, $$p_1,…,p_k,k, can be manually assigned, therefore, the remaining variables will be only $$p_(k+1),….,p_n$$. Upon studying competitors’ experience, it was found out that there is a requirement to the distribution of random variable $$x$$. In particular, this distribution should be skewed to the right:

Let’s sort the prices on items in the ascending order of price levels: $$c_1≤c_2≤⋯≤c_n$$
Then, we come to the optimization problem of the following form:


Set the objective function $$R(x)=1-\frac{\sum_{i=1}^nc_i p_i}{C}→R_0$$ Subject to constraints: $$p_1,p_2,…p_n>0$$ $$\sum_{i=1}^np_i =1$$ $$p_1 $$p_n Where $$m$$ is an index of a particular item, pulled from the box, with a cost $$c_m$$, which depends from the value of the box approximately as follows (these bounds were received experimentally): $$0.4C≤c_m≤1.15C$$ The last constraint is an attempt to assign higher probabilities to items with “middle” level of values, as compared to those with low and high values. This should imply the probability distribution to have the desired form.

What is required? To write down the algorithm of calculations, which can solve the optimization problem and can be implemented on PhP. This task can be solved in Excel using Excel Solver, however, since we cannot work with Excel files effectively, we need a manually written algorithm, which can be implemented in a programming code.

• It does not makes sense to say " these outcomes are independent of each other, and the sum of the probabilities of the onset of all elementary outcomes is equal to one." Outcomes are not events, and disjoint events cannot be independent except for very special cases like when all events are the empty set. I think you can delete this and just say $\sum_{i=1}^np_i=1$. – Michael Oct 12 '19 at 18:44
• I don't know if you are trying to maximize or minimize $R(x)$. I think $m \in \{1, ..., n\}$ is a fixed integer that you know. You may want to chagne constraints $<$ to constraints $\leq$ to ensure a solution exists. Assuming I understand the problem, the answer is either to $(z,z,..,z,0,0,...,0)$ or $(0,0,..,0,z,z,...,z)$ depending on if you are maximizing or minimizing $R(x)$, where $z$ is a number that makes all nonzero components sum to 1. I also observe that $R(x)$ is defined without any $x$, I think it should be $R(p_1, ..., p_n)$. – Michael Oct 12 '19 at 19:10
• Yes, with $<=$ constraints, the solution with zeros and some fixed numbers exists, but this is not what we want. We need these probabilities to look somehow like a positively skewed distribution. This is a gambling, we should have different probabilities for different items. Cheap and expensive prizes should be rare, but as we are moving to the middle-value prizes, the probabilities should grow. Presumably, we have to determine the relationship between each $p_i$ and $p_{i+1}$ more accurately. But at the moment I have no idea how to do so. – Sergei Oct 12 '19 at 19:26
• And we do not maximize or minimize R(x). We set it to be equal to a particular value. Like in Excel, when you run solver, you can select whether to maximize, minimize, or set equal to a fixed value. – Sergei Oct 12 '19 at 19:41
• Then, I have no idea what your question is. You posed it as a convex program with an objective function $R(x)$. Obviously any solution with $\leq$ can be perturbed by at most $\delta$ to enforce $<$ without changing utiltiy by more than $\delta$. See standard form for convex programs here: en.wikipedia.org/wiki/Convex_optimization – Michael Oct 12 '19 at 20:00

Fix $$n$$ as a positive integer and fix $$m \in \{1, ..., n\}$$. Let $$\mathcal{P}$$ be the set of all vectors $$p=(p_1, ..., p_n)$$ that satisfy these constraints: \begin{align} &\sum_{i=1}^n p_i = 1\\ &p_i \geq 0 \quad \forall i \in \{1, ..., n\}\\ &p_1 \leq p_2 \leq ... \leq p_m\\ &p_m \geq p_{m+1} \geq ... \geq p_n \end{align} Now fix constants $$C, C_1, ..., C_n$$ and assume $$C>0$$ and $$0\leq C_1 \leq C_2 \leq ... \leq C_n$$ Define the function $$R(p)$$ (for the vector $$p=(p_1,...,p_n)$$) by: $$R(p) = 1 - \frac{1}{C}\sum_{i=1}^n p_iC_i$$ One may want to know the possible values of $$R(p)$$, considering all vectors $$p \in \mathcal{P}$$. The smallest possible value is $$R_{min}$$ and is achieved at: \begin{align} p^{min} &= (p_1^{min},..., p_n^{min}) \\ &= \left(0, 0, ..., 0, \underbrace{\frac{1}{n-m+1}}_{\mbox{location m}}, \frac{1}{n-m+1},..., \frac{1}{n-m+1}\right) \end{align} so that $$\boxed{R_{min} = R(p^{min})}$$ The largest possible value is $$R_{max}$$ and is achieved at: \begin{align} p^{max}&=(p_1^{max},..., p_n^{max}) \\ &= \left(\frac{1}{m}, \frac{1}{m}, ..., \underbrace{\frac{1}{m}}_{\mbox{location m}}, 0, 0, ..., 0\right) \end{align} so that $$\boxed{R_{max} = R(p^{max})}$$

Now since $$p^{min} \in \mathcal{P}$$ and $$p^{max} \in \mathcal{P}$$ we have that for every $$\theta \in [0,1]$$: $$\theta p^{min} + (1-\theta)p^{max} \in \mathcal{P}$$ which means that for any $$R_0 \in [R_{min}, R_{max}]$$ there is a $$\theta_0$$ such that $$R_0 = \theta_0 R_{min} + (1-\theta_0)R_{max}$$ and this value $$R_0$$ is achieved by the probability vector: $$\theta_0p^{min} + (1-\theta_0)p^{max}$$ meaning that $$\boxed{R(\theta_0p^{min} + (1-\theta_0)p^{max}) = R_0}$$ In particular, if $$R_0 \notin [R_{min}, R_{max}]$$ then it is impossible to find a vector $$p \in \mathcal{P}$$ that satisfies $$R(p)=R_0$$.

For example if $$n=6$$ and $$m=3$$ and $$\theta_0=1/2$$ then \begin{align} &(1/2)p^{min} + (1/2)p^{max} \\ &= (1/2)(0, 0, 1/4, 1/4, 1/4, 1/4) + (1/2)(1/3, 1/3, 1/3, 0, 0,0)\\ &=(1/6, 1/6, 7/24, 1/8, 1/8, 1/8) \end{align}

Now open inequalities $$<$$ are usually not used in optimization. One reason is that closed inequalities $$\leq$$ typically yield problems with well defined optimums, while $$<$$ often do not. Another reason is that, if desired, we know we can perturb a solution by $$\delta$$, where $$0<\delta < 10^{-1000000}$$, to change $$\leq$$ into $$<$$. For example: $$(1/6, 1/6 + \delta, 7/24, 1/8, 1/8-\delta/3, 1/8 - 2\delta/3)$$ and such precision to a million decimal places is clearly impractical, is merely an annoyance, and so we might as well use the (simpler) $$\leq$$ constraints.

For example do you really care if $$p_6$$ is: $$p_6 = 0.125$$ versus $$p_6 = 0.124\underbrace{9999999999999999999999999999999999....9}_{\mbox{a million 9s}}$$ ?

It would be a different story if you wanted the gap to be at least some value, say, $$gap=0.01$$, so that $$p_1+0.01\leq p_2$$ and so on. Of course, the $$gap$$ value must be sized so that the constraints are feasible. One could also potentially pose this as a problem of maximizing $$gap$$ subject to the desired constraints.