# Multivariable Constrained Optimization

• Jun 4th 2010, 02:58 AM
vaibhavphalak
Multivariable Constrained Optimization
hi
i want to find values of a,b,c such that..

Minimize (a+b+c)
constrained to

(x-a)^2 + (y-b)^2 + (z-c)^2 less than equal to R(z)

(x-a)^2 + (y-b)^2 + (z-c)^2 greater than equal to r(z)

can anyone help me solving this?? I need to write c++ code for this so which method should b computationally better?
• Jun 4th 2010, 03:57 AM
vaibhavphalak
in the above problem," x,y,z" are given and
one more constraint:

-z1 < z < z2

z1,z2 > 0.
• Jun 4th 2010, 10:10 AM
Ackbeet
Further Clarification
What is R(z) and r(z) for your problem?
• Jun 8th 2010, 10:26 PM
vaibhavphalak
R(z) and r(z) are radius of bigger and smaller approx. spheres like shapes and they are function of z.
or let's consider them constants..
is there any good book on optimization ?
• Jun 9th 2010, 02:52 AM
Ackbeet
One of the better books on optimization is this one. I found it very helpful in that most elusive of all topics: choosing appropriate algorithms for your specific problem.

Ok, so to restate your problem slightly: you need to minimize a linear function over a spherical annular region in space. As a clarification, you do mean $\displaystyle (r(z))^{2}\le(a-x)^{2}+(b-y)^{2}+(c-z)^{2}\le(R(z))^{2}$, right? As in, the two radii are squared? Another clarification: are you minimizing $\displaystyle (a+b+c)$, or $\displaystyle |a+b+c|$?

To me, this suggests evaluating the linear function on the boundaries of your region (i.e., the inner and outer spherical surfaces that bound your region) and looking for the minimum there. What if you were to switch to spherical coordinates? As in, take the following definitions for the inner surface (here I'm using $\displaystyle \theta$ for the polar angle, and $\displaystyle \varphi$ for the azimuthal):

$\displaystyle a-x=r(z)\,\sin(\theta)\cos(\varphi)$
$\displaystyle b-y=r(z)\,\sin(\theta)\sin(\varphi)$
$\displaystyle c-z=r(z)\,\cos(\theta)$,

with a similar definition for the outer sphere.

Your problem then reduces to minimizing the function
$\displaystyle x+r(z)\,\sin(\theta)\cos(\varphi)+y+r(z)\,\sin(\th eta)\sin(\varphi)+z+r(z)\,\cos(\theta)$, subject to $\displaystyle 0\le\theta\le\pi$, and $\displaystyle 0\le\varphi\le 2\pi$. You have effectively eliminated one variable.

Now, if you are minimizing, as you originally said, $\displaystyle (a+b+c)$, I think it's pretty clear there can be only one solution. Moreover, all the functions you're dealing with are very well-behaved. Therefore, I would hazard a guess that most any algorithm you choose will converge fairly well. I would probably use a sampling algorithm: take the intervals for $\displaystyle \theta$ and $\displaystyle \varphi$, and sample the function to be minimized at various regular points in those intervals. Take the minimum point, and construct smaller intervals about that point. Continue "zooming in" until the point doesn't change much. You're essentially claiming that such a Cauchy sequence converges, which is true if the space is complete.

Here's another approach. If you're minimizing the linear function, without the absolute value signs, then I think it is a theorem of linear programming that your max and min will occur somewhere on the boundaries of your region. So picture your annular spherical region (hollowed-out sphere). Now consider the family of planes $\displaystyle a+b+c=\text{constant}$. What you're interested in, due to that theorem of linear programming, are places where members of the family of planes are tangent to either the inner or the outer sphere (probably the outer sphere contains the solution, but you want to be careful). So compute the four locations where the family of planes are tangent to either the inner or the outer sphere, evaluate the sum to be minimized at each of those four locations, and pick the minimum. Done.

Hope this helps.
• Jun 9th 2010, 03:30 AM
vaibhavphalak
sorry i dint state problem correctly earlier , i want to minimize
( lal + lbl + lcl )

which method can be applied now??
• Jun 9th 2010, 04:55 AM
Ackbeet
Ok, with that function to be minimized, you're not going to be able to use the planes approach, since the function does not correspond to a plane. The question also arises whether the first approach I mentioned, with the spherical coordinates, will work. If you can convince yourself that the min will occur on a boundary of the domain, then you can still use the earlier approach I mentioned. You're just going to have to evaluate the function

$\displaystyle |x+r(z)\sin(\theta)\cos(\varphi)|+|y+r(z)\sin(\the ta)\sin(\varphi)|+|z+r(z)\cos(\theta)|$,

instead of the the one I mentioned earlier.

If, however, you can't convince yourself that the extremum occurs on the boundary, you're going to have to define your variables this way (I think I'd still use spherical coordinates, because of the symmetry and organization they provide for this problem):

$\displaystyle a-x=r\sin(\theta)\cos(\varphi)$
$\displaystyle b-y=r\sin(\theta)\sin(\varphi)$
$\displaystyle c-z=r\cos(\theta)$,

where $\displaystyle r(z)\le r\le R(z)$, $\displaystyle 0\le\theta\le\pi$, and $\displaystyle 0\le\varphi\le 2\pi$. Then you do your "zooming in" in all three variables, $\displaystyle r, \theta, \varphi$.
• Jun 10th 2010, 01:52 AM
vaibhavphalak
Thanks for the help so far,

(a,b,c) is centre and (x,y,z) is on the sphere , my goal is to minimize the displacement of centre (a,b,c)

and yes, I am convinced that minimum will occur on a boundary of domain.

can u tell me how to minimize this function??

l x + r sin( θ)cos( ψ) l + l y + r sin( θ)cos( ψ) l + l z + r cos( θ) l
• Jun 10th 2010, 02:36 AM
Ackbeet
I've already given you one (I think) workable algorithm in posts #5 and #7. Have you tried those?