Re: Constrained Optimization

*To*: mathgroup at smc.vnet.net*Subject*: [mg57710] Re: Constrained Optimization*From*: Maxim <ab_def at prontomail.com>*Date*: Sun, 5 Jun 2005 04:17:52 -0400 (EDT)*References*: <d7mj30$bqm$1@smc.vnet.net> <d7pb7q$t80$1@smc.vnet.net> <d7rk7r$blu$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

On Sat, 4 Jun 2005 07:11:55 +0000 (UTC), Caspar von Seckendorff <seckendorff at alphatec.de> 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: In[1]:= Reduce[ForAll[x, 1/5 <= x <= 2/5, (x - x^2)*y <= a], {y, a}] Out[1]= (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: In[2]:= Reduce[ForAll[{x, y}, x^2 + y^3 == 1 && y >= 0, x^2 + (y - y0)^2 <= a]] Out[2]= (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: In[3]:= Minimize[{a, %}, {a, y0}] Out[3]= {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 inbox.ru