# How to find the stationary point under constraints analitically?

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.

• @ChristianBlatter, I have added some details $A \gg B > 0 \in \mathbb{R}$, $k \in \mathbb{Z}^+$, and $f(X)>1$. – Nick Feb 15 at 12:19
• 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. – user619894 Feb 17 at 10:26
• @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. – Nick Feb 17 at 10:44
• In fact I demonstrated $F(X)\rightarrow \infty$ – user619894 Feb 17 at 11:47
• 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. – user619894 Feb 18 at 5:18

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.

• Thank for the derivative. What are the possible critical points you mean? – Nick Feb 19 at 9:46
• I think before red $\lambda k$ should be the $2$. – Nick Feb 20 at 0:52
• 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? – Nick Feb 22 at 4:23
• @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. – Alex Ravsky Feb 22 at 4:29
• 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}$. – Nick Feb 23 at 0:39

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:

image 2:

image 3:

• 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? – Nick Feb 18 at 23:16
• @Nick We have $x_i>0$ also in the initial problem, because we have a term $1/x_i$ in it. – Alex Ravsky Feb 19 at 0:04
• @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$. – Alex Ravsky Feb 19 at 0:13
• @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. – River Li Feb 19 at 1:50