5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ And $Ax-b\ge 0$ is to be understood for each component? $\endgroup$ – Guido Kanschat Sep 7 '13 at 13:18
  • $\begingroup$ Yes. Thanks. I have revised the inequality symbol to make it more clear. $\endgroup$ – Mike Sep 7 '13 at 15:06
  • 1
    $\begingroup$ In optimization, use of $\geq$ to mean componentwise nonstrict inequality is standard. Use $\succeq$ if you want to say that a matrix is positive semidefinite (or explicitly define what you mean by $\succeq$). $\endgroup$ – Geoff Oxberry Sep 8 '13 at 23:43
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Geoff. Thanks for the formulation. I was trying to solve the original minimization ($P_0$) using the Matlab function fmincon. It can get correct solution some times, but can also fail some times. Also, it is quite sensitive to the initialization. Regarding your formulation, I am wondering that which kind of techniques can be used. If we also use the Matlab function fmincon. I guess it is quite similar to solve ($P_0$) directly. $\endgroup$ – Mike Sep 9 '13 at 3:23
  • $\begingroup$ It really depends on what you mean by "solve". If your problem is provably convex, standard nonlinear programming solvers are guaranteed to converge to a global optimum (barring numerical errors). However, your problem is not, so it's more likely that it will converge to a local optimum. This may or may not be good enough for your purposes. If it's not, the next level of sophistication would be to use strategies like multistart, simulated annealing, etc. -- these will help you find better solutions. If you need to find the global optimum, then you should use methods from global optimization. $\endgroup$ – Geoff Oxberry Sep 9 '13 at 16:43
0
$\begingroup$

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$.

$\endgroup$

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.