Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $f(x)$ be a scalar function of a vector $x\in \mathbb R^n$. If we want to find $x$ such that $f(x)$ is maximized or minimized. I think we can compute the differential of $f(x)$ with respect to $x$ and then let the coefficient of $dx$ be zero. For example, I get the differential of $f(x)$ as $$df(x)=g(x)^T dx$$ where $g(x)$ is a vector function of $x$. Then $g(x)=0$ can give the extrema.

My question is: if in some context the vector $x$ is a unit vector ($||x||=1$). At this time, $dx$ is constrained. Can we still get the extrema by solving $g(x)=0$?

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

This really is a comment to Shiyu's "weird methods", but is too long, and contains too much mathematics to fit into the comment box.

Diagrammatically, the three different methods can be captured by

$$ \mathbb{S}^n \overset{i}{\longrightarrow} \mathbb{R}^{n+1}\setminus \{0\} \overset{j}{\longrightarrow} \mathbb{S}^n $$

where $i$ is the inclusion map of the unit sphere into Euclidean space, and $j$ is the projection map $j(y) = y / \|y\|$. Note that $j\circ i$ is the identity map on the sphere.

Given a function $f:\mathbb{R}^{n+1}\to\mathbb{R}$. You want to find its maximum on the unit sphere. Geometrically your methods correspond to

  • Method 1: consider instead the function $\tilde{f} = f \circ i : \mathbb{S}^n \to \mathbb{R}$. Now $\tilde{f}$ is a function on the sphere, which is a smooth manifold. So the critical points of $\tilde{f}$ corresponds to $d\tilde{f} = 0$ where the derivative is taken on the smooth manifold. (As it happens, the sphere is extra nice, in the sense that the set of rotations gives rise to a set of vectors that span the tangent space at every point. Since $d\tilde{f} = 0$ is equivalent to the directional derivatives of $\tilde{f}$ relative to any tangent vector being 0.) Now, by the chain rule, $d\tilde{f} = df|_{i(\mathbb{S}^{n})} \cdot di$. $di$ being the differential of the inclusion map, it spans precisely the tangent plane to the unit sphere. So this says that $df$, when restricted to the tangent plane to the unit sphere, must be 0. And this is precisely $g(x)\times x = 0$. In general, for an arbitrary submanifold $S$ of $\mathbb{R}^{n+1}$. You can do the same canonical inclusion and get that $f|_{S}$ has a critical point if and only if $df$ is normal to the surface $S$ at the point. (Unlike the sphere, the normals are not so nicely parametrized in the general case.)
  • Method 2: you are looking at the map $\bar{f} :\mathbb{R}^{n+1}\setminus\{0\}\to \mathbb{R}$ given by $\bar{f} = f \circ i \circ j$. At any critical point, $d(f\circ i) = 0$ as shown above, and hence $d\bar{f}$ will also be zero. But doing the expansion a different way, you have $$ d\bar{f} = df \cdot d(i\circ j) = 0$$ (where $i\circ j:\mathbb{R}^{n+1}\setminus\{0\} \to \mathbb{R}^{n+1}\setminus\{0\}$ is given by $i\circ j(y) = y / \|y\|$). The computation give what you wrote. Notice that $$ I - xx^t $$ for $\|x\| = 1$ is a projection matrix to the orthogonal complement of $x$. So indeed, the second method also gives rise to the statement that $df$ restricted to the tangent space of the sphere (remember that for the sphere, its tangent is orthogonal to the radial vector) is 0. Which is the same conclusion as method 1.

Geometrically the method of Lagrange multipliers and the two methods described above are completely identical. They just represent different ways to compute the same thing.

share|improve this answer
    
Thank you. Willie. I didn't notice that $I-xx^T$ is a projection matrix and $(I-xx^T)y=0$ implies $y$ is collinear with $x$. Then solution 1, 2 and 3 actually give the same result. –  Shiyu Mar 18 '11 at 12:57
add comment

See http://en.wikipedia.org/wiki/Lagrange_multipliers.

share|improve this answer
    
Thank you very much. I can solve the problem using the Lagrange multiplier. But I have other two solutions. Could you please see whether they are wrong? Thank you. –  Shiyu Mar 17 '11 at 13:18
add comment

It seems a quite simple problem if we use Lagrange multiplier. But I have some other methods which seem very weird. Can anybody help me to fix them?

Weird solution 1: Using a rotation matrix.~~~~~~~~~~~~~~~~~~~~~~~~~

Since the length of $x$ is fixed, $x$ can vary on a sphere. That means any variance of $x$ is caused by a rotation matrix $R$. $$\delta x = Rx-x=(R-I)x$$ According to rotation axis-angle formula, a rotation matrix can be written as $$R=e^{[w]_{\times}}$$ where $w$ is the product of the rotation axis and rotation angle. $[w]_{\times}$ is the associating skew-symmetric matrix of the vector $w$. The first order Taylor expansion of $R$ is $$R=I+[w]_{\times}$$ Hence we have $$dx=(R-I)x=[dw]_{\times}x=[x]_{\times}dw$$ Now $$df(x)=g(x)^Tdx=g(x)^T[x]_{\times}dw$$ Since $dw$ has no constraints, solving the following equation can give the extrema. $$g(x)^T [x]_{\times}=0$$ That is the cross product $$g(x) \times x=0$$

Weird solution 2:~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

$||x||=1$, $dx$ is not free. But we can find a free vector $y$ such that $x=\frac{y}{||y||}$. Then $dy$ should be free. And we have $$dx=\frac{dy||y||-yd||y||}{||y||^2}=\frac{1}{||y||}\left( I-xx^T \right) dy$$ Therefore $$df(x)=g(x)^Tdx=\frac{1}{||y||}g(x)^T\left( I-xx^T \right) dy$$ Since $dy$ has no constraints, solving the following equation can give the extrema. $$\frac{1}{||y||}g(x)^T\left( I-xx^T \right)=0 $$

Normal Solution 3: using Lagrange multiplier.~~~~~~~~~~~~~~~~~~~~~~~~~ $$d[f(x)+\lambda (x^T x-1)]=\left( g(x)^T+2\lambda x^T \right)dx$$ So we have $$g(x)+2\lambda x=0$$

Remark: Note the solution 1 is the same as the solution 3, because both of them just mean $g(x)$ is collinear with $x$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.