maximum of a product over the set of all permutation of $(1,2,\ldots n)$

Question

MY PROBLEM

Let $n$ be a non-negative integer, $b_i$ ($i = 1,\ldots, n$) be real parameters, and $(a_1, a_2, \ldots, a_n)$ be a permutation of $(1,2,\ldots, n)$.

I have a product given as $$\prod\limits_{i=1}^n(b_i + (-1)^{a_i}).$$

I'd like to consider the set of the function values where $(a_1,a_2,\ldots, a_n)$ takes on each and every permutation of $(1,2,\ldots, n)$. Last, I'd like to take both the maximum of that set.

MY FIRST SOLUTION

Adapting from @Bart (edited by @Yuval Filmus) in [1], I write

$\alpha = \max\left(\left\{\prod\limits_{i=1}^n(b_i + (-1)^{a_i}) \mid (a_1,a_2,\ldots, a_n)~\textrm{is a permutation of}~(1,2,\ldots, n) \right\}\right).$

I know from [2] that ``$\left\{ x \mid \phi ( x ) \right\}$ is the set of all values of $x$ that satisfy the formula [or rule] $\phi$.'' Therefore, it is clear that I am taking the maximum of all the permutations.

MY SECOND SOLUTION

This problem has more than one variables, along with functions acting on them [2]. So, I write as follows.

Let $S_n$ be the symmetric group [3]. I write the maximum of the product as $$\max\left(\left\{y \in \mathbb{R} \mid \exists (a_1,a_2,\ldots, a_n), y = \prod\limits_{i=1}^n(b_i + (-1)^{a_i})~\textrm{and}~ (a_1,a_2,\ldots, a_n) \in S_n \right\}\right).$$

QUESTIONS

(1's) Are my solution correct? Is one more correct than the other? How come?

(2's) Is there a more elegant or more correct solution? How do you write them?

BIBLIOGRAPHY

[1] Mathematical notation for the maximum of a set of function values

[2] https://en.wikipedia.org/wiki/Set-builder_notation

[3] https://en.wikipedia.org/wiki/Symmetric_group

Answer 1

You can solve this problem via integer linear programming as follows. Define binary variable $x_i$, which will represent $a_i \pmod 2$. Taking a logarithm to linearize the product, we want to maximize $$\log \prod_{i=1}^n (b_i + (-1)^{a_i}) = \sum_{i=1}^n \log \left(b_i + (-1)^{a_i}\right) = \sum_{i=1}^n \left[\log \left(b_i - 1\right)x_i + \log \left(b_i + 1\right)(1-x_i)\right].$$ Now impose a cardinality constraint $$\sum_{i=1}^n x_i = \lceil n/2 \rceil$$ to capture the fact that every permutation of $(1,2,\dots,n)$ has exactly $\lceil n/2 \rceil$ odd numbers.

To recover an optimal permutation from an optimal $x$, just respect the parity. For example, if $x_i=1$, let $a_i$ be the next unused odd number from $\{1,2,\dots,n\}$; otherwise let $a_i$ be the next unused even number.

Answer 2

Claim: If $b_i > 1$ for all $i$, then putting the $\lceil n/2 \rceil$ largest values of $b_i$ in the odd positions is optimal.

Proof: Suppose some pair $(i,j)$ has $b_i < b_j$ with $a_i$ odd and $a_j$ even. Then switching the two positions (so that $a_i$ is even and $a_j$ is odd) multiplies the product by $$\frac{(b_i+1)(b_j-1)}{(b_i-1)(b_j+1)} = \frac{b_i b_j-b_i+b_j-1}{b_i b_j+b_i-b_j-1} = \frac{b_i b_j-b_i-b_j-1+2b_j}{b_i b_j-b_i-b_j-1+2b_i} > 1.$$