MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Constrained Optimization

On Sat, 4 Jun 2005 07:11:55 +0000 (UTC), Caspar von Seckendorff  
<seckendorff at> wrote:

> Thanks to all for your replies,
> Your're right "y" was meant to be an unknown constant. As I understand
> it know, Maximize[] does some sort of numerical optimization. I thought
> it would be able to use some concave Programming logic (like
> Kuhn-Tucker) to solve this problem for me, returning a list of possible
> optima in symbolic form together with the neccessary constraints... But
> I admit that maybe this is to much to ask for ;-)
> Greetings,
> -Capar

Here's how you can reformulate your problem:

Reduce[ForAll[x, 1/5 <= x <= 2/5, (x - x^2)*y <= a], {y, a}]

(y <= 0 && a >= (4*y)/25) || (y > 0 && a >= (6*y)/25)

This tells you that if you want to find an upper bound that may depend on  
y, then for y>0 you can take any value greater or equal to 6/25*y. I'm not  
sure if this formulation is what you were looking for though. Maximize  
just solves a different problem, but it also works by performing the  
decomposition of the region; it doesn't use the numerical methods employed  
by NMaximize.

Here's one interesting application of this technique. The example from the  
Maximize documentation shows how to solve the problem of finding the  
smallest circle centered at the origin and containing the set of points  
x^2 + y^3 == 1 && y >= 0. Now suppose that we want to solve a more general  
problem, when we can vary the position of the circle as well. First we  
find the lower bound for the radius as a function of the position of the  
center on the y axis:

Reduce[ForAll[{x, y}, x^2 + y^3 == 1 && y >= 0, x^2 + (y - y0)^2 <= a]]

(y0 <= -(1/2) && a >= 1 - 2*y0 + y0^2) || (Inequality[-(1/2), Less, y0,  
LessEqual, 1/8] && a >= (1/27)*(29 - 18*y0 + 27*y0^2) + (2/27)*Sqrt[1 -  
18*y0 + 108*y0^2 - 216*y0^3]) || (y0 > 1/8 && a >= 1 + y0^2)

And then minimize this function:

Minimize[{a, %}, {a, y0}]

{65/64, {a -> 65/64, y0 -> 1/8}}

The answer is Sqrt[65/64]. (There remains a question of what would be the  
simplest way to show that the optimum is achieved on the y axis.)

Maxim Rytin
m.r at

  • Prev by Date: Re: Re: Re: simple set operations
  • Next by Date: Finding Position in an ordered list
  • Previous by thread: Re: Re: Constrained Optimization
  • Next by thread: Re: Constrained Optimization