1
$\begingroup$

I have a function $h(y,x_1,x_2,\ldots,x_n)$. It is known that the minimum value of $h$ for any $y$ is attained when $x_1 = x_n$ and $x_2 = x_3 = \cdots = x_{n-1}$. Now consider the following function \begin{equation} g(x_1,\ldots,x_n) = \int_{y\in\Theta}h(y,x_1,x_2,\ldots,x_n)f(y)dy \end{equation} where $f$ is some probability density function and $\Theta$ is appropriate space for $y$.

Numerically, I am getting that $g$ is also minimised when $x_1 = x_n$ and $x_2 = x_3 = \cdots = x_{n-1}$. However, analytically it is difficult to prove. Is there any result which ensures the optimal symmetry of solution even after taking the integration?

Edit 1: It is know that $h$ is a concave function of $(x_1,\ldots,x_n)$ and the vector $(x_1,\ldots,x_n)$ belongs to a convex set. Moreover, the density function is continuous (not discrete).

Edit 2: It is given that $(x_1,\ldots,x_n)\in\{(x_1,\ldots,x_n):x_i\geq 0,\sum_{i=1}^{n}x_i = 1\}$.

$\endgroup$
5
  • $\begingroup$ If $h$ is concave as a function of $(x_1,\ldots,x_n)$, doesn't that mean that the minimum as a function of those variables occurs on the boundary? Is that really what you want? $\endgroup$ Jan 25 at 6:02
  • $\begingroup$ @Michael could not get your question properly. What I want is to prove that the solution if of the form given in the question. $\endgroup$ Jan 25 at 6:12
  • $\begingroup$ For example, $h=-x_1^2 -x_2^2-x_3^2-x_4^2$ is concave. It does not have a minimum inside the set of $(x_1,\ldots,x_4)$. The minimum is on the boundary. I'm just making sure that this is the type of scenario you are interested in, because it seems somewhat counterintuitive to me. $\endgroup$ Jan 25 at 6:19
  • $\begingroup$ @Michael I edited the question. In Edit 2 the space where $(x_1,\ldots,x_n)$ belongs is defined. It is actually a unit simplex. I thing the solution I am expecting ($x_1=x_n, x_2=\cdots=x_{n-1}$) is a boundary point of the set. $\endgroup$ Jan 25 at 6:25
  • $\begingroup$ Ah, ok. It is good to have clarified this - it is a significant constraint. $\endgroup$ Jan 25 at 6:28

2 Answers 2

1
+50
$\begingroup$

With no additional structure, no.

Let $y$ take the value $0$ and $1$ with probability $1/2$ each. That has no density, but densities sufficiently close will do too.

Let $h(y,x_1,x_2)=\sqrt{|y-x_1|}+(y-x_2)^2$. Clearly, for each $y$ it is optimal to have $x_1=x_2=y$. It is straightforward to calculate that the minimal $x_2$ for the integral $$1/2 \Big(\sqrt{|x_1|}+x_2^2\Big)+1/2\Big(\sqrt{|1-x_1|}+(1-x_2)^2\Big)$$ is $x_2=1/2$, but $x_1=1$ gives a smaller value than $x_1=1/2$.

If $h$ is convex, this problem should not occur.

$\endgroup$
2
  • $\begingroup$ What if $h$ is concave in $\boldsymbol{x}=(x_1,\ldots,x_n)$? Additionally, it is known that the set where $\boldsymbol{x}$ belongs is a convex set. If the answer is yes please any hint to prove. $\endgroup$ Jan 23 at 5:17
  • $\begingroup$ I'm afraid, I don't know the answer. $\endgroup$ Jan 24 at 15:14
-1
$\begingroup$

EDIT: The answer is based on the stronger assumption that there is a value $h_{\min}$ such that for all $y\in \Theta$ and $a,b$ it holds $$ \min_{x_1,\dots,x_n} h(y,x_1,\dots,x_n) = h(y,a,b,\dots,b)=: h_{\min}. $$ In the OPs setting the minimizes $x_1,\dots,x_n$ might be $y$ dependent.

For $y$-independent minimizer: On the one hand $$\begin{align*} \min_{x_1,\dots,x_n} g(x_1,\dots,x_n) &= \min_{x_1,\dots,x_n} \int_\Theta h(y,x_1,\dots,x_n) f(y) \, dy \\ &\geq \int_{\Theta} \min_{x_1,\dots,x_n} h(y,x_1,\dots,x_n) f(y) \, dy \\ &= \int_{\Theta} h_{\min} f(y) \, dy = h_{\min}, \end{align*} $$ since $f$ is a probability density on $\Theta$.

On the other hand for the choice $x_1=x_n=a$ and $x_2=x_3=\dots=x_{n-1}=b$ it also holds $$ g(a,b,\dots,b,a) = \int_\Theta h(y,a,b,\dots ,b,a) f(y) \,dy = \int_{\Theta} h_{\min} f(y) \, dy = h_{\min}, $$ by assumption.

$\endgroup$
2
  • $\begingroup$ @Schlichting: Only the form of the solution is known that is $x_1 = x_n$ and $x_2=\ldots=x_{n-1}$ for any $y$. However, exact values of optimal $x_i$'s depends on y. So we can not assume that $x_1=x_2 = a$ and $x_2=\ldots=x_{n-1} = b$ for all $y$. In numerical results optimal solution of integrated function has the same symmetry but it is different than the optimal solution minimising $h$. $\endgroup$ Jan 22 at 10:25
  • $\begingroup$ Thanks for clarifying. I missed the dependency on $y$ of the minimizer. $\endgroup$ Jan 22 at 12:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.