Non-Linear Constrained Minimization


Alessandro
06-16-2009, 11:34 AM
Hi all,
I have a constrained minimization problem for which I wonder if a
closed form solution, i.e., no numerical algorithm, exists.
I have a vector x of 5 unknowns, such that

PHI * x = 0

where PHI is a matrix with 4 rows, but in general, because of noise problems, more rows should be considered.
Moreover, rank(PHI)=4 or, because of noise rank(PHI) =5, with the smaller singular value close to zero.

In addition, the following constrain arises (on
the first 2 components):

x_1^2 + x_2^2 = 1

that takes into account that, actually, x_1=cos(alpha) and x_2=sin(alpha).

Is there an analytical and elegant solution for that?

Thanks,
Alessandro

gjm
07-14-2009, 07:15 AM
Your title is "Nonlinear constrained minimization", but you haven't said what you're trying to minimize. Are you looking for a least-squares solution to PHI.x = 0 in the case where PHI has lots of rows?

If so: Given x1 and x2, the least-squares minimizer of PHI.x determines all the other components of x as certain linear (er, affine) functions of x1,x2. So x3 = a + p.x1 + q.x2; x4 = b + r.x1 + s.x2; x5 = c + t.x1 + u.x2.

So the sum of squares of components of PHI.x is some quadratic form in x1,x2: Ax1^2 + Bx1x2 + Cx2^2 + Dx1 + Ex2 + F. You want to minimize this subject to x1^2 + x2^2 = 1.

This is eminently doable analytically. For instance, as follows. You've got a family of concentric ellipses, and you want the outermost one that meets x1^2 + x2^2 = 1. Well, your ellipse has to be tangent to that circle there (else some direction of movement around the circle takes you further "out" w.r.t. the centre of the ellipses), which turns out to mean (if I've done my algebra right) (Bx1+2Cx2+E)x1 = (2Ax1+Bx2+D)x2. So you're now looking for the intersection of that and x1^2+x2^2=1. Change variables to x1+x2 and x1-x2, and everything should be pretty easy. Or you could write everything in terms of your angle parameter alpha and set the derivative to 0, which should also work out OK.