2
$\begingroup$

Im trying to maximize the probability of a particular outcome occurring subject to a constraint. In particular

$$max \prod_{i \leq n} 1 - (1 - x_i)^{y_i} \;\;\; s.t. \;\;\; i \in \mathbb{N}^+,\; 0 \leq x_i \leq 1,\; x_1*...*x_n = z, \forall n \in \mathbb{N}^+$$

where $y_i \in \mathbb{N}^+$ and $0 \leq z \leq 1$. The context really isn't important, I'm interested only in a solution to this problem. I've been able to find a solution for the minimum, but I haven't been able to for the max.

I highly suspect that the maximum is at $x_1 = ... = x_n = z^{(1/n)}$, but I have not been able to come close to proving this. I'm looking for a proof that either the solution that I have proposed is correct, or incorrect. I'm not necessarily looking for a solution, but it would be welcome. I've been trying to prove this for quite some time and haven't had any luck (proving it false or true). Any advice or suggestions would be greatly appreciated.

Edit:

Idea that I've been toying with. Could I try to reduce this problem to a problem in geometry? If I view my constraint $x_1*...*x_n = z$ as the $n$ dimensional volume of a $n$ hyperrectangle ($n$-orthotope) with sides $x_1,...,x_n$ and constraints given above, I'm wondering if I can solve this problem simply and easily. The problem could thus reduce to the following.

Consider a $n$ hyperrectangle where the length of each side $i$ is given by $x_i$ that has a $n$ dimensional volume of $x_1*...*x_n = z$. Suppose now we wish to extend the lengths of each side with the expression $1 - (1 - x_i)^{y_i}$ for a fixed $y_i \in \mathbb{N}^+$ corresponding to each side. The set of $x_i$ that gives the maximum $n$ dimensional volume for the fixed $y_i$ values I would then expect to be $x_1 = ... = x_n = z^{(1/n)}$. The (incorrect) intuition for this line of thought is that for a fixed perimeter ($n$ surface area?) the maximum area of a rectangle occurs when all sides are the same length (square). The constraint $x_1*...*x_n = z$ is sort of analogous to a fixed perimeter and so I'm wondering if this somewhat incorrect intuition could be used to build a reduction and provide a proof.

$\endgroup$
3
  • $\begingroup$ This is not a convex optimization problem as written: the objective function is not concave, and the nonlinear constraint is also disqualifying. I'm trying to reason whether it can be cast as a convex problem in an equivalent way, but I'm not yet sure. $\endgroup$ Mar 19 '17 at 18:40
  • $\begingroup$ OK. So $1-(1-x_i)^{y_i}$ is concave in $x_i$, which means that $\prod_i \left(1-(1-x_i)^{y_i}\right)^{1/n}$ is also concave in $x$. So we're good there (because convex maximizations require a concave objective function). If the constraint can be relaxed to $\left(\prod_i x_i \right)^{1/n} \geq z^{1/n}$ while preserving equivalence, we're good there, too. $\endgroup$ Mar 19 '17 at 18:42
  • $\begingroup$ Also posted to MO, mathoverflow.net/questions/265003/… $\endgroup$ Apr 19 '17 at 4:13

Your Answer

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

Browse other questions tagged or ask your own question.