4
$\begingroup$

I'm sorry for this silly question. Several times I faced with optimization problems which can be expressed as

$$\begin{array}{ll} \text{minimize} & \mathrm x^T \mathrm A \mathrm x\\ \text{subject to} & \|\mathrm x\| = 1\end{array}$$

where $\mathrm A$ is square matrix and $\mathrm x$ is vector.

(This kind of problem arises in PCA or rigid alignment of 3D point sets)

I know that solution of this problem is eigenvalue decomposition of $\mathrm A$. Smallest eigenvalue should be minimum of optimization problem and corresponding eigenvector should be solution.

I want to know is there exist special name for such optimization problem?

PS: Sorry for my poor English.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Thank you for reply! I thought that well-known problems have own names like Least Squares, Linear/Quadratic/Convex programming, etc. So this fact is surprise for me. Can you rewrite your comment as answer? $\endgroup$ – Dark_Daiver Oct 13 '16 at 16:06
  • $\begingroup$ Done! Glad to help. $\endgroup$ – Christian Clason Oct 13 '16 at 16:19
10
$\begingroup$

Since the optimization problem has a well-known closed-form solution, it is rarely used in itself and hence usually not given a name. The objective function $x^TAx$ (using $\|x\|=1$), however, is known under the name Rayleigh quotient; the set of its values is called field of values, or numerical range (of $A$).

More generally, this is a textbook example of a quadratic programming problem with a single differentiable equality constraints (if written as $\|x\|^2-1=0$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Due to the equality constraint and that $1-\|x\|$ is not a convex function, this isn't a convex constraint. $\endgroup$ – Deathbreath Nov 1 '16 at 15:41
  • $\begingroup$ @Deathbreath Actually, it is convex if written as $g(x):=\|x\|^2-1=0$. I've made this explicit now. $\endgroup$ – Christian Clason Nov 1 '16 at 16:52
  • $\begingroup$ that still isn't convex. To make it precise, a convex constraint is $g(x) \le 0$, where $g$ is a convex function. The above equality constraint is only a convex constraint for linear $g$. Since equality implies $g(x)\le 0$ and $-g(x) \le 0$ and $-g(x)=1-\|x\|^2$ is concave, this is not a convex problem. Or more to the point, the surface of a sphere is not a convex set, hence the feasible set here isn't convex. $\endgroup$ – Deathbreath Nov 1 '16 at 18:20
  • $\begingroup$ But it's not an inequality constraint, but an equality constraint defined by a convex function. I never claimed that the problem itself is convex (because I know that the nomenclature here is not fully consistent, for one). Be that as it may, I have removed the offending claim. $\endgroup$ – Christian Clason Nov 1 '16 at 18:27
  • 1
    $\begingroup$ I'm fully aware of the difference; I claimed the latter but not the former. But I agree that the formulation was misleading, which is why I edited the answer. $\endgroup$ – Christian Clason Nov 1 '16 at 18:33
7
$\begingroup$

I know this should be a comment but I do not have enough reputation to comment. I just want to point out that for an arbitrary $A$ with real entries the solution (minimum) to this problem is the smallest eigenvalue of the symmetric part of $A$, namely $S(A)=\frac{(A+A^T)}{2}$, and in the special case when $A$ is symmetric this indeed (as in the original question) gives the smallest eigenvalue of $A$.

| cite | improve this answer | |
$\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.