Optimization of non-convex function over simplexes: Minimum on boundary?

64 Views Asked by At

Consider the following function

$$f(\vec \alpha,\vec\beta,\vec\gamma)=\prod_{(i,j,k)\in [n]^3} \bigl(1-(1-p^{\alpha_{ijk}})(1-p^{\beta_{ijk}})(1-p^{\gamma_{ijk}})\bigr),$$ where $p$ is a constant in $(0,1)$, $[n]=\{1,..,n\}$ for some fixed natural number, for each $(i,j,k)\in[n]^3$, we have real values $$ 0\leq \alpha_{ijk}\leq 1, \quad 0\leq \beta_{ijk}\leq 1, \text{ and } 0\leq \gamma_{ijk}\leq 1, $$ and furthermore, for each $i\in[n]$, $$ \sum_{(j,k)\in[n]^2} \alpha_{ijk}=1, $$ for each $j\in[n]$, $$ \sum_{(i,k)\in[n]^2} \beta_{ijk}=1, $$ and for each $k\in[n]$, $$ \sum_{(i,j)\in[n]^2} \gamma_{ijk}=1. $$ I would like to show that this function achieves it minimum at the boundary of the constraint set, i.e., where the $\alpha$'s, $\beta$'s and $\gamma$'s take $0/1$ values. It is readily verified that on such boundary points, the minimum value that $f$ can take is $$ (1-(1-p)^3)^n. $$ (e.g., by assigning for each $i\in[n]$, $\alpha_{iii}=\beta_{iii}=\gamma_{iii}=1$ and all other parameters to $0$.)

How to show that the function $f$ does not attain a smaller value inside the constraint set? It is, for example, true that symmetry arguments imply that such a minimum must occur at a point in which $\alpha_{ijk}=\beta_{ijk}=\gamma_{ijk}=\frac{1}{n^2}$ for all $(i,j,k)\in[n]^3$?

As a note aside, this problem arises as part of an optimization problem in the context of probabilistic databases.