Results 1 to 9 of 9

Math Help - Multivariable Constrained Optimization

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    5

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jun 2010
    Posts
    5
    in the above problem," x,y,z" are given and
    one more constraint:

    -z1 < z < z2

    z1,z2 > 0.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Further Clarification

    What is R(z) and r(z) for your problem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2010
    Posts
    5
    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 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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 (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 (a+b+c), or |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 \theta for the polar angle, and \varphi for the azimuthal):

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

    with a similar definition for the outer sphere.

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

    Now, if you are minimizing, as you originally said, (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 \theta and \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 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jun 2010
    Posts
    5
    sorry i dint state problem correctly earlier , i want to minimize
    ( lal + lbl + lcl )

    which method can be applied now??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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

    |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):

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

    where r(z)\le r\le R(z), 0\le\theta\le\pi, and 0\le\varphi\le 2\pi. Then you do your "zooming in" in all three variables, r, \theta, \varphi.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jun 2010
    Posts
    5
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I've already given you one (I think) workable algorithm in posts #5 and #7. Have you tried those?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Constrained Optimization
    Posted in the Calculus Forum
    Replies: 0
    Last Post: May 19th 2010, 02:05 AM
  2. Constrained Optimization again
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 5th 2010, 05:45 AM
  3. A Question on Constrained Optimization
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: December 3rd 2009, 08:00 AM
  4. Replies: 5
    Last Post: October 20th 2008, 02:04 PM
  5. Need help with Constrained Optimization
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 1st 2006, 12:41 PM

Search Tags


/mathhelpforum @mathhelpforum