2
$\begingroup$

I am working with the optimization problem from the paper, eq.(5)

$$\max_{X=(x_1, x_2, \ldots, x_{n+1})} f(X)=(A-B\sum_{i=1}^n \frac{1}{x_i})\times x_{n+1}$$ subject to $$x_{n+1}=1-2k\sum_{i=1}^n x_i,$$ $$x_i \geq 0, \quad i = 1,2,\ldots, n+1.$$

Here $A \gg B > 0 \in \mathbb{R}$, $k \in \mathbb{Z}^+$, and $f(X)>1$.

From the paper I know the stationary point $$X^*=(\underbrace{\sqrt{\frac{B}{2kA}}, \ldots, \sqrt{\frac{B}{2kA}}}_{n\text{ times}}, 1 − 2 kn\sqrt{\frac{B}{2kA}} )$$ and the optimal value $$f(X^*)=(\sqrt{A} − n \sqrt{ 2 \cdot k \cdot B})^2.$$

Question. How to find the stationary point under constraints analytically? Is it possible for $n=3, k=10$ case?

Attempt.

I have tried to use the Lagrange multiplier:

$$F(X, \lambda) = x_{n+1}(A-B\sum \frac{1}{x_i}) + \lambda(x_{n+1} - 1 + 2k\sum x_i)=0$$ and found the partical derivatives and have the $(n+2)$ system with $n+2$ variables:

\begin{cases} F'_{x_i}(X, \lambda)= x_{n+1}\frac{B}{x_i^2} +2 \lambda k x_i=0, \quad i=1,2,..., n, \\ F'_{x_{n+1}}(X, \lambda)= A - B\sum \frac{1}{x_i}+\lambda=0, \\ F'_{\lambda}(X, \lambda)=x_{n+1} -1+2k\sum x_i =0. \end{cases}

My problem now is how to express $x_i$, $i=1,2,..., n$, and $x_{n+1}$ through $\lambda$ and find roots.

I know the stationary point and have found the A & Q. I will use the notation $\sum_{i=1}^n x_i := n \cdot x$ $\sum_{i=1}^n \frac{1}{x_i} := \frac{n} {x}$, and $x_{n+1}:=y$. Then the system will be

$$y\frac{B}{x^2}+2\lambda k x=0, \tag{2.1}$$ $$\lambda=B\frac{n}{x}-A, \tag{2.2}$$ $$y=1-2knx. \tag{2.3}$$

Put $(2.2)$ and $(2.3)$ in $(1.1)$:

$$( 1-2knx )\frac{B}{x^2}+2 (B\frac{n}{x}-A ) k x=0, \tag{3.1}$$ Multiple both sides $(3.1)$ on $x^2$:

$$( 1-2knx )B+2 (B\frac{n}{x}-A ) k x^3=0, \tag{4.1}$$ Open brackets and collect tems: $$2kAx^3-2nBkx^2+2nBkx-B=0, \tag{5.1}$$ divide both sides on $2kA$: $$x^3 - n\frac{B}{A}x^2 + n \frac{B}{A}x-\frac{1}{2k}\frac{B}{A}=0. \tag{6.1}$$

One can see the equation of power $3$, I am looking for a root $x \in \mathbb{R}$. I think the equation $(6.1)$ should has a simple real root and complex pair.

$\endgroup$
  • $\begingroup$ @ChristianBlatter, I have added some details $A \gg B > 0 \in \mathbb{R}$, $k \in \mathbb{Z}^+$, and $f(X)>1$. $\endgroup$ – Nick Feb 15 at 12:19
  • 1
    $\begingroup$ I think that a constraint is missing. If you select $x_0 =\epsilon <<1$ and the rest to be $x_j = y >>1$ you can get $F(X)\approx{B\over \epsilon}\times k(n-1)y$ which goes to infinity. $\endgroup$ – user619894 Feb 17 at 10:26
  • $\begingroup$ @user721481, I tried to solve the problem on a computer and I had result that is different from the analytical one. After your comment I think how to use the inequality $f(X)>1$ from the paper. $\endgroup$ – Nick Feb 17 at 10:44
  • 1
    $\begingroup$ In fact I demonstrated $F(X)\rightarrow \infty$ $\endgroup$ – user619894 Feb 17 at 11:47
  • 1
    $\begingroup$ Sorry, I meant $f(x)$ in both cases. Anyway, in the paper there are additional constraints, eg eq(1,2). I believe they should be included. $\endgroup$ – user619894 Feb 18 at 5:18
1
+100
$\begingroup$

Let’s follow your approach.

Unfortunately, the first $n$ equations of your system are wrong, we have $F'_{x_i}(X, \lambda)= x_{n+1}\frac{B}{x_i^2} +\color{red}{2\lambda k}=0$. Next, both values of $X^*$ from the paper and the first $n$ equations of the system (unless $\lambda=x_{n+1}=0$) says that for the stationary point all $x_i$’s for $1\le i\le n$ are equal to some value $x$. This lead as to a system

$$y\frac{B}{x^2}+2\lambda k=0, \tag{2’.1}$$ $$\lambda=B\frac{n}{x}-A, \tag{2’.2}$$ $$y=1-2knx. \tag{2’.3}$$

Put $(2’.2)$ and $(2’.3)$ in $(2’.1)$:

$$(1-2knx )\frac{B}{x^2}+2 (B\frac{n}{x}-A ) k=0.$$

$$\frac{B}{x^2}-2Ak=0.$$

$$x=\sqrt{\frac{B}{2kA}}.$$

Remark that in other to assure that the obtained value $$X^*=(\underbrace{\sqrt{\frac{B}{2kA}}, \ldots, \sqrt{\frac{B}{2kA}}}_{n\text{ times}}, 1 − 2 kn\sqrt{\frac{B}{2kA}})$$ provides the optimal value for $f(X^*)$, we also have to consider other possible critical points (which are often missed in applications, making them non-rigorous) provided by the following general

Lagrange’s theorem. Let $m$ be a natural number, $r\le m$, functions $f,g_1,\dots, g_r$ from $\Bbb R^m\to R$ are continuously differentiated in a neighborhood of a point $x$ such that $g_i(x)=0$ for each $1\le i\le m$ and rank of the Jacobi matrix $J(x)=\left\|\tfrac{\partial g_i}{\partial x_j}(x) \right\|$ equals $r$. If the function $f$ has a conditional extremum at the point $x$ then there exists numbers $\lambda_1,\dots,\lambda_n$ such that $\left(f+\lambda_1g_1+\dots+\lambda_rg_r\right)(x)=0$.

That is in our case we have also to check points for which $J(x)=0$. Luckily, $J(x)=(-2k,\dots,-2k,1)$ so its rank is always $r=1$ and we can skip this part.

Now we found condition for a local condition maximum of the function $f$. But we have to evaluate its global maximum (or supremum). For this usually we have also to check values of $f$ at the boundary points of its domain. In our case formally these are points $x=(x_i)$ with some of $x_i$ are zeros, but luckily, this is excluded by the expression for $f$.

Finally, it can happen that the global maximum of the function $f$ is not attained in any point of its domain. Luckily, this is not our case because we have $x_i\ge B/A$ for each $1\le i\le n$ and each point $x$ such that $f(x)\ge 0$. Since $f$ is a continuous function, it attains its maximum value in some point $x$ on a compact domain given by the conditions $B/A\le x_i\le 1/2k$ and $x_{n+1}=1-2k\sum_{i=1}^n x_i$. This points $x$ fits for Lagrange’s theorem.

$\endgroup$
  • 1
    $\begingroup$ Thank for the derivative. What are the possible critical points you mean? $\endgroup$ – Nick Feb 19 at 9:46
  • 1
    $\begingroup$ I think before red $\lambda k$ should be the $2$. $\endgroup$ – Nick Feb 20 at 0:52
  • 1
    $\begingroup$ thanks for the updated answer. In the original problem one can see the constraints $x_i \geq 0$, $i=1, 2, \ldots, n+1$, in your answer I see that $\frac{1}{2k} \geq x_i \geq \frac{A}{B}$, $i=1,2,\ldots, n$ and $x_{n+1} = 1-2k\sum x_i$. Are you specified (reduced) the points domain? $\endgroup$ – Nick Feb 22 at 4:23
  • 1
    $\begingroup$ @Nick Yes, I reduced domain for the application of Lagrange’s theorem (by requiring $x_i>0$). Then I argued that the maximum value of $f$ is attained in the domain reduced by $A/B≤x_i≤1/2k$. So the maximum value can be found by the application of Lagrange’s theorem that is by the method of Lagrange‘s multipliers. $\endgroup$ – Alex Ravsky Feb 22 at 4:29
  • 1
    $\begingroup$ I have returned to your answer and think that the domain should be $\frac{B}{A} \leq x_i \leq \frac{1}{2k}$, because in the target function we have $\sum \frac{1}{x_i}$ but not $\sum {x_i}$. $\endgroup$ – Nick Feb 23 at 0:39
2
$\begingroup$

EDIT

In the paper, they look for a set of probabilities $p_k\in (0, 1), k = 1, 2, \cdots, s$ and $p_{s+1} = 1 - 2n \sum_{k=1}^s p_k \in [0, 1]$ such that condition (5) is satisfied, i.e. $p_{s+1}(A - B\sum_{k=1}^s \frac{1}{p_k}) > 1$. (I put some images at the end.)

Condition (5) requires $A - B \sum_{k=1}^s \frac{1}{p_k} > 0$ and $p_{s+1} = 1 - 2n\sum_{k=1}^s p_k> 0$ which results in $\frac{A}{B} \cdot \frac{1}{2n} > \sum_{k=1}^s \frac{1}{p_k} \cdot \sum_{k=1}^s p_k \ge s^2$, or $A - 2ns^2 B > 0$.

As a result, in that paper, they solve the optimization problem under the condition $A - 2ns^2 B > 0$ and $p_k\in (0, 1), k=1, 2, \cdots, s$ and $p_{s+1}\in (0, 1)$. Under the condition $A - 2ns^2 B > 0$, $p_1 = p_2 = \cdots = p_s = \sqrt{\frac{B}{2nA}}$ satisfy $1 -2 n \sum_{k=1}^s p_k > 0$ and hence the solution.

In the OP, $p_k$ is replaced with $x_i$, $s$ is replaced with $n$, $n$ is replaced with $k$. (I think the notation of the paper should be used.)

Using the notation of the OP, assuming that $A - 2kn^2 B > 0$, we can solve the optimization problem as follows.

With $x_i > 0, \forall i$ and $1-2k \sum_{i=1}^n x_i \ge 0$, we have \begin{align} \Big(A- B\sum_{i=1}^n \frac{1}{x_i}\Big)x_{n+1} &= \Big(A- B\sum_{i=1}^n \frac{1}{x_i}\Big)\Big(1-2k \sum_{i=1}^n x_i\Big)\\ &\le \Big(A- B\frac{n^2}{\sum_{i=1}^n x_i}\Big)\Big(1-2k \sum_{i=1}^n x_i\Big) \tag{1}\\ &= A - B\frac{n^2}{\sum_{i=1}^n x_i} - 2k A \sum_{i=1}^n x_i + 2kn^2B\\ &\le A - 2\sqrt{B\frac{n^2}{\sum_{i=1}^n x_i}\cdot 2k A \sum_{i=1}^n x_i} + 2kn^2 B \tag{2}\\ &= A - 2\sqrt{2kn^2 AB} + 2kn^2 B\\ &= (\sqrt{A} - n\sqrt{2kB})^2 \end{align} with equality if and only if $x_1 = x_2 = \cdots = x_n = \sqrt{\frac{B}{2kA}}$, and $p_{n+1} = 1 - 2kn\sqrt{\frac{B}{2kA}}$ (note: $1 - 2kn\sqrt{\frac{B}{2kA}} > 0$ since $A - 2kn^2 B > 0$).
Explanation: in (1), we have used Cauchy-Bunyakovsky-Schwarz inequality to obtain $\sum_{i=1}^n \frac{1}{x_i} \ge \frac{n^2}{\sum_{i=1}^n x_i}$ with equality if and only if $x_1 = x_2 = \cdots = x_n$; in (2), we have used $a + b \ge 2\sqrt{ab}$ with equality if and only if $B\frac{n^2}{\sum_{i=1}^n x_i} = 2k A \sum_{i=1}^n x_i$ or $\sum_{i=1}^n x_i = \sqrt{\frac{Bn^2}{2kA}}$.

Some images from the paper:

image 1:

enter image description here

image 2:

enter image description here

image 3:

enter image description here

$\endgroup$
  • $\begingroup$ In your answer you used $x_i>0$ but not $x_i \geq 0$. Also do we need whether know some relations between $k$, $n$ and $\sum x_i$ there? $\endgroup$ – Nick Feb 18 at 23:16
  • $\begingroup$ @Nick We have $x_i>0$ also in the initial problem, because we have a term $1/x_i$ in it. $\endgroup$ – Alex Ravsky Feb 19 at 0:04
  • 2
    $\begingroup$ @Nick As I see, the only relation between $k$, $n$, and $\sum x_i$ we need to have the provided upper bound tight is $x_{n+1}\ge 0$ provided all other $x_i$ equals $\sqrt{\frac{B}{2kA}}$, that is $n\sqrt{\frac{2kB}{A}}\le 1$. It should hold, because $A\gg B$. $\endgroup$ – Alex Ravsky Feb 19 at 0:13
  • $\begingroup$ @Nick Just as what Alex Ravsky said (Thanks). Actually, $p_i \in (0, 1), \forall i$ is stated in (1) of the paper. I will edit my answer. $\endgroup$ – River Li Feb 19 at 1:50

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.