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
6 个评论
Walter Roberson
2011-3-31
Should that be norm(p)=1 instead of norm(q)=1 ?
Andrew Newell
2011-3-31
He's minimizing f(q).
Martin
2011-3-31
Walter Roberson
2011-3-31
Sorry got the two mixed up.
Martin
2011-4-1
Bjorn Gustavsson
2011-4-2
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?
采纳的回答
Andrew Newell
2011-3-31
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.
6 个评论
Martin
2011-3-31
Walter Roberson
2011-3-31
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
2011-3-31
@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
2011-3-31
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
2011-3-31
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
2011-3-31
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.
更多回答（1 个）
Bjorn Gustavsson
2011-3-31
0 个投票
I'd go about it this way (if I've gotten the question right):
- calculate the gradient of f: df
- calculate Df = df - dot(p,df)*p - should be the gradient of f in the plane perpendicular to p.
- calculate q = -Df/norm(Df)
- fmin = f(q)
HTH, Bjoern
类别
在 帮助中心 和 File Exchange 中查找有关 Linear Least Squares 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
