Minimizing a linear objective function under a unit-sphere constraint

Hi folks,

It might be pretty simple question for some of you, but it would be great to share this idea with me.

I have an objective function to minimize and it's given as a linear.

Let's say that f(q) where f is linear.

q is of unit length m-dimensional vector and there is another given m-dimensional vector p which is orthogonal to q.

The question is how I can minimize the objective function s.t.

norm(q) = 1 and p'q = 0.

In particular, I'd like to use the simplex method.

Is there any way to tackle this problem using linprog function?

If not, is there any other way to utilize the simplex method in solving this?

Thanks in advance.

Martin

[Walter Roberson]

Should that be norm(p)=1 instead of norm(q)=1 ?

[Andrew Newell]

He's minimizing f(q).

[Martin]

Anyway, p is another unit-length vector GIVEN.

[Walter Roberson]

Sorry got the two mixed up.

[Martin]

Thanks guys. I do appreciate your kind and nice explanation on my question. However, is there any way of doing this with simplex optimization algorithm? That's something I am aiming at. Thanks.

[Bjorn Gustavsson]

Why do you want to use an optimization algorithm for this problem. As I outlined below it has a simple solution. Is your real problem more complex? If so in what way?

Answer 1

[Andrew Newell]

You could use fmincon with the constraint ceq(q)=0, where

ceq = @(x) abs(norm(x)-1) + abs(p'*x);

(ceq is an anonymous function). I added the absolute values to make sure that both terms have to be zero for ceq to be zero.

EDIT: Actually, since ceq can return a vector, a better formulation would be

ceq = @(x) [norm(x)-1; p'*x];

FURTHER EDIT: You might get better numerical behavior if you use

ceq = @(x) [x'*x-1; p'*x];

because then you don't have to take a square root.

[Martin]

Thanks Andrew. Let me try.

[Walter Roberson]

I guess, but that sounds too much to me like hoping to balance on an undulating curved knife edge. Surely there would be a better way? For example, dropping it down one dimension and calculating the final vector value based upon the constraints.

The fact that f is linear in q is suggestive of minimizing (f')^2 to find the zeros of f.

[Andrew Newell]

@Walter, I don't know about @Martin but I'm not following your reasoning here. By "dropping it down one dimension", do you mean projecting q onto the p'q =0 hyperplane? Also, if f(q) = A*q for some matrix A, there may be no zero unless A has a zero eigenvalue. But even if there are zeros, what do they have to do with minimizing f(q) on the unit sphere?

[Walter Roberson]

if q[1:m-1] has been determined then the constraints allow one to exactly calculate q[m] . If it comes out as a non-real number then q[1:m] was not feasible for any q[m-1] . Doing this saves you from generating a random value for q[m-1] and _hoping_ that it matches the norm constraints (except perhaps down to choosing a sign for q[m-1]).

I suspect that a character in what I wrote is not visible. I propose minimizing the square of f fprime -- that is, the square of the (sum of the partial?) derivative of f, which is the usual technique for using a minimizer to find the zeros of the derivate of f (as the zeros of the derivatives are the function extremes or inflection values.)

[Andrew Newell]

You're right - I can't see the prime (although I can see it in (f')^2). That makes a lot more sense.

[Andrew Newell]

One advantage my third formulation has is that you have a problem that contains nothing worse than second order polynomials. If you drop the dimension by one, you have to deal with square roots and the chance that imaginary components can creep in, while gaining nothing. If I understand FMINCON, the initial guess doesn't have to satisfy the constraints.

Answer 2

[Bjorn Gustavsson]

I'd go about it this way (if I've gotten the question right):

1. calculate the gradient of f: df
2. calculate Df = df - dot(p,df)*p - should be the gradient of f in the plane perpendicular to p.
3. calculate q = -Df/norm(Df)
4. fmin = f(q)

HTH, Bjoern