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