How to solve a Rayleigh-quotient-like minimization with inequality constraints

Question

What I am trying to solve is the following Rayleigh-quotient-like minimization: \begin{eqnarray} \begin{split} (P_0)\quad\min_x \frac{\left( Ax - b\right)^\top \left( Ax - b\right)}{x^\top x}\\ s.t. \quad\quad Ax-b \geq 0 \end{split} \end{eqnarray} where $A\in R^{m\times n}$, $m>n$, is a full rank matrix.

It is well known that the solution of the Rayleigh-quotient minimization is the eigen vector correponding to the minimum eigen value. It seems that it cannot be solved using the same approach as the Rayleigh-quotient minimization. Thanks very much!

Answer 1

I think the comparison you're trying to draw is to the Rayleigh quotient minimization

\begin{align} \min_x &\frac{\left( Ax \right)^\top \left( Ax \right)}{x^\top x},\\ \end{align}

to try to find the eigenvalues of $A^{\top}A$.

The chief difference I see between those problems is that if $x$ is an optimal solution to the Rayleigh quotient minimization, then so is $cx$ for all scalar $c \neq 0$ (which makes sense; $x$ would be an eigenvector of $A^{\top}A$, so $cx$ is also an eigenvector for $c \neq 0$).

There is no such scale-invariance for solutions of the constrained optimization problem you've shown. Adding constraints and affine terms to the numerator of the objective destroys the property exploited by Rayleigh quotient iteration. Consequently, I would guess that you are correct: you probably cannot solve this problem using the same methods as Rayleigh quotient iteration.

The problem you've formulated looks to me like it's a nonlinear (probably nonconvex) program. It might be worth reformulating it so that it looks more like

\begin{align} \min_{x, f} &f \\ \textrm{s.t.} & (Ax - b)^{\top}(Ax - b) - f x^{\top}x = 0 \\ & Ax - b \geq 0; \end{align}

this sort of reformulation works great for linear fractional programming, but I don't know that it will help you much for your problem, other than to avoid issues occurring if the objective function is evaluated at $x = 0$. The $f$ term is a new variable introduced to stand for the fractional objective function. The term $f x^{\top}x$ is now a potential source of nonconvexity, along with the nonlinear equality constraint.

Answer 2

Let $f(x)=\dfrac{||Ax-b||^2}{||x||^2}$. We assume that $b$ is not in the image of $A$, otherwise there is nothing to do.

1. The first thing to do is to minimize $f(x)$ under the "free" constraint $Ax-b>0$. $Df_x:h\rightarrow \dfrac{2((Ax-b)^T(Ah)||x||^2-||Ax-b||^2x^Th)}{||x||^4}$. $Df_x=0$ iff, for every $h$, $(||x||^2(Ax-b)^TA-||Ax-b||^2x^T)h=0.$ That is equivalent to : $||x||^2(Ax-b)^TA=||Ax-b||^2x^T$. That implies $(Ax-b)^TAx=||Ax-b||^2$ and then $(Ax-b)^Tb=0$. Remark that if $b>0$ or $b<0$, then there is no solution.

2. In a second time, we must add constraints in the form $g_i(x)=e_i^T(Ax-b)=0$. Using Lagrange method, one has the condition $Df_x+2\sum_i\lambda_iDg_i(x)=0$, that is $||x||^2(Ax-b)^TA-||Ax-b||^2x^T+||x||^4\sum_i\lambda_ie_i^TA=0$.