1
$\begingroup$

I am thinking of the maximal value and minimal value of two vectors in some special case.

Following is my problem statement.

$\max\sum_{i=1}^Nx_iy_i$ and $\min\sum_{i=1}^Nx_iy_i$ subject to the conditions:

  • $x_i \geq 0$,
  • $y_i \geq 0$,
  • $x_1 \geq x_2 \geq \cdots \geq x_N$,
  • $y_1 \geq y_2 \geq \cdots \geq y_N$
  • $\lVert x\rVert_2=1$
  • $\lVert y\rVert_2=1$

I find the "descending order" constrains is quite annoying and I don't know how to handle it.

1 Answers 1

1

The maximum is always $1$, which happens whenever $\vec{x}=\vec{y}$, e.g. for $x_i=y_i=\frac1{\sqrt n}$ for all $i$ or for $\vec{x}=\vec{y}=(1,0,\dots,0)$. Let $a_n$ be the desired minimum in $n$ dimensions. It measures how far apart the vectors can get, since the dot product of unit vectors is the cosine of the angle between them, and the cosine function decreases for $\theta\in[0,\frac{\pi}2]$. The constraint space is a sector of the $(n-1)$-sphere, the positive quadrant/octant/portion, reduced by the symmetry of permuting the ordinates. For example, for $n=2$, our space is half of the unit circle in the first quadrant, which spans an angle $\frac\pi4$, so that $a_2=\frac1{\sqrt 2}$. In $n$ dimensions, the minimum is $\frac1{\sqrt n}$, which is obtained, for example, when $x_i=\frac1{\sqrt n},y_i=\delta_i$ (i.e. $y_1=1$ and $y_i=0$ for $i>1$). You should be able to prove this with induction, for which you can without loss of generality assume ascending rather than descending order if it is more convenient.