10
$\begingroup$

This builds on my earlier questions here and here.


Let $B$ be a symmetric positive definite matrix in $\mathbb{R}^{k\times k}$ and consider the problem

$$\begin{array}{ll} \text{maximize} & x^\top B x\\ \text{subject to} & \|x\|=1 \\ & b^\top x = a\end{array}$$

where $b$ is an arbitrary unit vector and $a > 0$ is a small positive number. Let $$\lambda_1 > \lambda_2 \geq \cdots \geq \lambda_k > 0$$ be the eigenvalues of $B$ with corresponding eigenvectors $z_1,...,z_k$. I conjecture that the optimal value of the problem is bounded below by $a^2 \lambda_1 + \left(1-a^2\right)\lambda_2$, at least if $a$ is small enough.


To motivate this conjecture, let us consider two special cases. First, suppose that $a= 0$. Then, as was explained to me in one of my previous posts, the optimal value is between $\lambda_1$ and $\lambda_2$ by the Courant-Fischer theorem. Thus, $\lambda_2$ is a lower bound, and it also coincides with my conjectured lower bound in this special case.

Second, let $a > 0$ but suppose that $b = z_i$ for some $i = 1,...,k$. Any feasible $x$ can be written as

$$x = ab + \sqrt{1-a^2} \cdot \hat{b}$$

where $\hat{b}\perp b$. If $b = z_1$, I can take $\hat{b} = z_2$, and if $b = z_i$ for $i \neq 1$, I can take $\hat{b} = z_1$. Either way, the objective value of $x$ is bounded below by $a^2 \lambda_1 + \left(1-a^2\right)\lambda_2$ as long as $a$ is small enough (note that this requires $\lambda_1 > \lambda_2$).

The difficulty is showing that it holds in the case where $b$ is not one of the eigenvectors of $B$ (perhaps with additional restrictions on how large $a$ can be). My intuition is that, if $b$ is not required to be orthogonal to $x$, but only "almost" orthogonal (meaning that $a$ may be required to be sufficiently small), you should be able to go a bit further in the direction of the principal eigenvector than in the case where $a = 0$.


Here is the most up-to-date work on this problem. In the answer below, it was found that the optimal value $v$ of the problem is a generalized eigenvalue of the system

$$PBx = vPx,$$

which in turn was derived from the system

$$PBPy + aPBb = v Py.$$

Any pair $\left(y,v\right)$ that solves these equations then leads to a feasible $x = ab+Py$, with $v$ being the objective value.

We can write

$$\left(vI - PB\right)Py = aPBb.$$

Note that, for any $v$ that is not an eigenvalue of $PB$, the matrix $vI-PB$ is invertible, whence

$$Py = a\left(vI-PB\right)^{-1}PBb.$$

The normalization $x^\top x = 1$ then becomes $y^\top P y = 1-a^2$, leading to the equation

$$\frac{1-a^2}{a^2} = b^\top BP\left(vI-PB\right)^{-2} PBb.$$

The largest root of this equation is the optimal value of the problem. Perhaps, as suggested, it can be found numerically.

$\endgroup$
13
  • 1
    $\begingroup$ I guess in your example with $b=z_i$, we have $x^\top B x=\sum \lambda_i x_i^2$. $\endgroup$ – Alex Ravsky Sep 9 '20 at 21:37
  • 1
    $\begingroup$ What do you mean by "for more general $B$"? Without loss of generality, it suffices to consider symmetric $B$ since $x^TBx = x^TSx$, where $S = \frac 12 (B + B^T)$. Do you simply mean that we allow $B$ to be a symmetric matrix with negative eigenvalues? $\endgroup$ – Ben Grossmann Sep 12 '20 at 20:33
  • 1
    $\begingroup$ I don't follow your argument that the optimum objective value is bounded below by $\ a^2\lambda_1+\left(1-a^2\right)\lambda_2\ $ when $\ b=z_i\ $ with $\ i\not\in\{1,2\}\ $. In that case, if $\ a>0\ $, $\ \lambda_1=\lambda_2>\lambda_i\ $, and $\ \displaystyle x=\sum_j x_j z_j\ $, then $\ x_i=a\ $ and $\ \displaystyle \sum_{j\ne i}x_j^2= 1-a^2\ $, and $$x^\top Bx =\sum_j\lambda_j x_j^2\\ \le\lambda_1\sum_{j\ne i}x_j^2+\lambda_ix_i^2\\ =\lambda_1\left(1-a^2\right) +a^2\lambda_i\\ <a^2\lambda_1 + \left(1-a^2\right)\lambda_2\ . $$ So it looks to me like this case provides a counterexample. $\endgroup$ – lonza leggiera Sep 13 '20 at 7:31
  • 1
    $\begingroup$ This Lagrangian approach looks more promising than my pseudo-eigenvalue approach. $\endgroup$ – greg Sep 13 '20 at 17:11
  • 1
    $\begingroup$ You just need to solve a scalar nonlinear equation for $\mu.\,$ It's analytically difficult but numerically easy. $\endgroup$ – greg Sep 13 '20 at 17:31
2
+200
$\begingroup$

The following analysis explores various approaches to the problem, but ultimately fails to produce a satisfactory solution.

One of the constraints can be rewritten using the nullspace projector of $b$ $$\eqalign{ P &= \Big(I-(b^T)^+b^T\Big) = \left(I-\frac{bb^T}{b^Tb}\right) \;=\; I-\beta bb^T \\ Pb &= 0,\qquad P^2=P=P^T \\ }$$ and the introduction of an unconstrained vector $y$ $$\eqalign{ b^Tx &= a \\ x &= Py + (b^T)^+a \\ &= Py + a\beta b \\ &= Py + \alpha_0 b \\ }$$ The remaining constraint can be absorbed into the definition of the objective function itself $$\eqalign{ \lambda &= \frac{x^TBx}{x^Tx} \;=\; \frac{y^TPBPy +2\alpha_0y^TPBb +\alpha_0^2\,b^TBb}{y^TPy +\alpha_0^2\,b^Tb} \;=\; \frac{\theta_1}{\theta_2} \tag{0} \\ }$$ The gradient can be calculated by a straightforward (if tedious) application of the quotient rule as $$\eqalign{ \frac{\partial\lambda}{\partial y} &= \frac{2\theta_2(PBPy +\alpha_0PBb)-2\theta_1Py} {\theta_2^2} \\ }$$ Setting the gradient to zero yields $${ PBPy +\alpha_0PBb = \lambda Py \tag{1} \\ }$$ which can be rearranged into a generalized eigenvalue equation. $$\eqalign{ PB\left(Py+\alpha_0b\right) &= \lambda Py \\ PBx &= \lambda Px \tag{2} \\ }$$ Note that multiplying the standard eigenvalue equation $$\eqalign{ Bx &= \lambda x \tag{3} \\ }$$ by $P$ reproduces equation $({2})$. So both standard and generalized eigenvalues are potential solutions.

Unlike the discrete $\lambda$ values yielded by the eigenvalue methods, equation $({1})$ is solvable for a continuous range of $\lambda$
$$\eqalign{ y &= \alpha_0(\lambda P-PBP)^+PBb \\ }$$ and produces a $y$ vector which satisfies the zero gradient condition $({1})$.

Unfortunately, none of these approaches yields a solution which satisfies all of the constraints.

But solving equation $(0)$ for an optimal $y$ vector is still the appropriate goal, and requires a numerical rather than an analytical approach.

$\endgroup$
9
  • $\begingroup$ Thanks. This looks difficult to solve analytically. I suppose one could assume the bound does not hold, so $\lambda < a^2\lambda_1 + \left(1-a^2\right)\lambda_2$, and then try to convert these into contradictory inequalities. The difficulty is that it is not clear whether $\lambda$ is being multiplied by positive or negative numbers in each equation. But I also think that using the nullspace projector is key somehow. I have been trying to come up with some vector whose projection would have an objective value satisfying the bound (then the bound holds for the opt. value). $\endgroup$ – sven svenson Sep 12 '20 at 23:34
  • $\begingroup$ Interesting! What does the $\left(\cdot\right)^+$ notation mean here? Normalization by $b^\top b$? We can assume that $b^\top b = 1$ for simplicity. $\endgroup$ – sven svenson Sep 13 '20 at 15:17
  • 1
    $\begingroup$ The $A^+$ denotes the Moore-Penrose pseudoinverse of $A$. $\endgroup$ – greg Sep 13 '20 at 15:27
  • 1
    $\begingroup$ Damn! You're right, that term should be $b^TBb$. $\endgroup$ – greg Sep 13 '20 at 15:56
  • 1
    $\begingroup$ The solution that you noted is a well known solution to the Rayleigh quotient problem, but it doesn't satisfy the $b^Tx$ constraint. I updated the post with my latest thoughts. $\endgroup$ – greg Sep 15 '20 at 18:03
1
$\begingroup$

I don't think the conjecture is correct. For a counter example, take $B=\begin{pmatrix} 1&0&0 \\0&1&0 \\ 0&0&\varepsilon \end{pmatrix}$ and $b=\begin{pmatrix}0\\ 0\\ 1\end{pmatrix}$. Then the desired maximum is $(1-a^2)+a^2\varepsilon < 1$.

$\endgroup$
3
  • $\begingroup$ While very insightful, note that this example does not satisfy $\lambda_1 > \lambda_2$. $\endgroup$ – Surb Sep 14 '20 at 8:19
  • $\begingroup$ Ow, missed this condition. Back to the blackboard then $\endgroup$ – sss89 Sep 14 '20 at 9:23
  • $\begingroup$ Yeah, as was pointed out in the comments above, there is some relationship between how small $a$ has to be and the gaps between the eigenvalues. If $\lambda_1=\lambda_2$ then $a$ must be zero. In the case where $b$ is an eigenvector the range is $\frac{1-a^2}{a^2} < \frac{\lambda_1}{\lambda_1-\lambda_2}$. $\endgroup$ – sven svenson Sep 14 '20 at 12: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.