3
$\begingroup$
  1. What is the max of $\sum\limits_{i=1}^n e^{x_i}$ as $(x_1,...,x_n)$ ranges over a sphere of given radius in $R^n$ ? Lagrange multipliers yields $n$ different candidates. Which of them is the max ?
  2. Analogous question for $\sum 2^{x_i}$ with $x_i$ INTEGERS in a given integral ball $\sum x_i^2\leq A$.

More on #1: There are $n$ (or fewer if the radius $R$ is small) candidate solutions $(x_1,...,x_n)$, all of the form (a,..,a,b,...,b) where $0<a<1<b$ and $e^a/a=e^b/b$. For each of those, you have a bordered Hessian, as in the comment below: [ M=\begin{matrix}0&-2x_1&...&-2x_n\\ -2x_1&2\lambda(x_1-1)&0...&0\\ \vdots&\vdots&\vdots&\vdots\\ -2x_n&0&...&2\lambda(x_n-1)\end{matrix}] For a max, this needs to be positive-definite, i.e. have all eigenvalues positive. Then, among all candidates yielding a positive-definite bordered hessian (if more than one), you need to maximize $\sum e^{x_i}$. So what's the answer ? My hunch is that (for large $n, R$) the max occurs for a vector of the form $(a,...,a,b)$ (SINGLE $b$): because for this the value is roughly $e^R$; for the opposite extreme, with all $x_i$ equal, the value is $ne^{R/\sqrt{n}}$ which is much smaller.

$\endgroup$
5
  • 2
    $\begingroup$ Hi user677727, welcome to MSE! What have you tried? This is not a forum where people just do your HW for you. Please see math.meta.stackexchange.com/questions/9959/… $\endgroup$ Jul 1, 2019 at 19:05
  • 1
    $\begingroup$ My interest is in question 2 which is motivated by a research problem in Algebraic Geometry. Question 1 is supposed to be an intermediate step and would yield an upper bound. As I said Lagrange multipliers yields a list of n candidates and the problem is which one yields the max. It looks simple but even though I asked several analysts (I'm not one), nobody could answer. This is not- to my knowledge- any homework problem. $\endgroup$
    – user677727
    Jul 2, 2019 at 20:10
  • $\begingroup$ Thanks for clarification. Perhaps a tag of 'analysis' will help it find the right audience? I'm also more of an algebraic/arithmetic geometer, and I think I'll have to pass on this one $\endgroup$ Jul 2, 2019 at 21:48
  • $\begingroup$ Can you show your work on these $n$ different candidates/at least write what they are? $\endgroup$
    – J.G
    Jul 3, 2019 at 22:42
  • $\begingroup$ These are, up to permutation $(a,...,a, b,...,b)$ where $0<a<1<b$ and $e^a/a=e^b/b$. This is direct from Lagrange multipliers. $\endgroup$
    – user677727
    Jul 4, 2019 at 23:08

1 Answer 1

1
$\begingroup$

The answer to the first question depends on the radius $R$.

Let's demonstrate this with two variables. Let $F = e^x + e^y + \lambda (R^2- x^2 - y^2)$.

Since the extremum occurs at $\frac{e^x}{x} = \frac{e^y}{y}$, we need to inspect the function $\frac{e^x}{x}$ which is convex and has a minimum at $x=1$. Hence the equation $\frac{e^x}{x} = \frac{e^y}{y}$ can only have different solutions $x \ne y$ if $x <1$ and $y > 1$ (or permuted).

We have to discuss cases:

Using the bordered Hessian condition for constrained maximization we have to show that for $x \ne y$ to be a maximum,

$$ \det \begin{bmatrix} 0 & \dfrac{\partial (R^2- x^2 - y^2)}{\partial x} & \dfrac{\partial (R^2- x^2 - y^2)}{\partial y} \\[2.2ex] \dfrac{\partial (R^2- x^2 - y^2)}{\partial x} & \dfrac{\partial^2 F}{\partial x^2}& \dfrac{\partial^2 F}{\partial x y} \\[2.2ex] \dfrac{\partial (R^2- x^2 - y^2)}{\partial y} & \dfrac{\partial^2 F}{\partial x y} & \dfrac{\partial^2 F}{\partial y^2} \end{bmatrix} > 0 $$
which is $x^2(y-1) + y^2(x-1) > 0$.

Let $y = ax$ then this is $(ax-1) + a^2(x-1) > 0$ or $x >\frac{1+a^2}{a^2+a}$ and we must have for a maximum:

$$R^2 = x^2 + y^2 = x^2(1+a^2) > \frac{(1+a^2)^3}{(a^2+a)^2} = g(a)$$

Now $g(a)$ has a minimum at $g(a=1) = 2$. Hence only for $R^2 > 2$ will there be a maximum with $x \ne y$, whereas the case $x=y$ will constitute a minimum.

Conversely, for $R^2 < 2$, there will be only the one extremum for $x=y$ which will be a maximum.

For more than two variables, this discussion will extend to more intervals of $R$.

EDIT 2019-07-25:

Now let's solve the general case. As stated in bordered Hessian condition for constrained maximization, conditions for a maximum are obtained from the leading principal minors (determinants of upper-left-justified sub-matrices) of the bordered Hessian, for which the first 2 leading principal minors are neglected, the smallest minor consisting of the truncated first 3 rows and columns, the next consisting of the truncated first 4 rows and columns, and so on, with the last being the entire bordered Hessian. A sufficient condition for a local maximum is that these minors alternate in sign with the smallest one having positive sign.

Evaluating these minors gives for any $n$ (!), when expanding by the last column

$$\det M_n \\ = \det \begin{bmatrix}0&-2x_1&...&-2x_n\\ -2x_1&2\lambda(x_1-1)&0...&0\\ \vdots&\vdots&\vdots&\vdots\\ -2x_n&0&...&2\lambda(x_n-1)\end{bmatrix}\\ = 2\lambda(x_n-1) \det M_{n-1} \\ - 2x_n (-1)^{n+1} \det \begin{bmatrix} -2x_1&2\lambda(x_1-1)&0...&0&0\\ \vdots&\vdots&\vdots&\vdots&0\\ -2x_{n-1}&0&...&0&2\lambda(x_{n-1}-1)\\ -2x_n&0&...&0&0\end{bmatrix} $$ Now the last determinant can be evaluated by expanding by the last row. Since the last row has just one entry $2x_n$, the first column and last row can be eliminated and what remains is the product of remaining diagonals. Hence:

$$\det M_n = 2\lambda(x_n-1) \det M_{n-1} + (2x_n)^2 \prod_{i=1}^{n-1}(2\lambda(x_i-1)) $$

Solving this recursion gives $$\det M_n = \prod_{i=1}^{n}(2\lambda(x_i-1)) \, \cdot \, \sum_{i=1}^{n} \frac{(2x_i)^2}{2\lambda(x_i-1)} $$

It is already known that candidate solutions $(x_1,...,x_n)$ are all of the form (a,..,a,b,...,b) where $0<b<1<a$ and $e^a/a=e^b/b$. Note that the convention $a >1$ has been adopted! Suppose there are $k$ many $a$'s and $n-k$ many $b$'s. Since the task is symmetric, we can assume that the $k$ many $a$'s are the first variables.

Then we have for the $n$th principal minor:

$$\det M_n = 2^{n+1} (\lambda)^{n-1} (a-1)^k (b-1)^{n-k} \Big( k \frac{a^2}{(a-1)} + (n-k) \frac{b^2}{(b-1)} \Big) $$

Reducing the order of the minors accounts for removing $b$'s. The $k$th principal minor is

$$\det M_k = 2^{k+1} (\lambda)^{k-1} (a-1)^k \Big( k \frac{a^2}{(a-1)} \Big) = 2^{k+1} (\lambda)^{k-1} (a-1)^{k-1} k a^2 $$

Now, as we go further to the $(k-1)$th principal minor, we observe that ${\rm sign} \det M_k ={\rm sign} \det M_{k-1}$, as $\lambda >0$ and $a >1$. This is a contradiction to the condition that, for a maximum, the minors must alternate in sign.

So, for a maximum, this situation mustn't occur. The way to achieve is is to make $k=1$. As the two-dimensional discussion above shows, this is only possible if the radius is large enough. Let us suppose this is the case. The large radius assures that the term $\Big( k \frac{a^2}{(a-1)} + (n-k) \frac{b^2}{(b-1)} \Big)$ will not change in sign if $n$ changes.

Then indeed, as $b-1 < 0$, the minors will alternate in sign, as for a change from the $q$th minor to the $(q+1)$th minor, always one additional product term $(b-1)$ is multiplied. This completes the proof. $\qquad \Box$

So, as the OP already hypothesized, indeed the maximum occurs for a vector of $x_i$ where $n-1$ entries are of the smaller value $<1$, solving $e^a/a=e^b/b$.

$\endgroup$
4
  • $\begingroup$ Thank you for pointing out the bordered Hessian condition which nicely settles the $n=2$ case and seems relevant more generally. But for large $n$- my case of interest- I don't see that the problem is solved. See below. $\endgroup$
    – user677727
    Jul 23, 2019 at 22:16
  • $\begingroup$ @user677727 I now added a proof for the general case, which shows that the hypothesis you set up in the question is indeed true. $\endgroup$
    – Andreas
    Jul 25, 2019 at 18:02
  • $\begingroup$ Beautiful solution. Thank you very much Andreas. $\endgroup$
    – user677727
    Jul 27, 2019 at 22:18
  • $\begingroup$ Thanks to Andreas, Problem 1 may be considered solved. This suggests but, think, doesn't prove, that the max for problem 2 for large $A$ is attained at $([\sqrt{A}], 0,...,0)$. $\endgroup$
    – user677727
    Jul 29, 2019 at 16:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .