Home > Archive > Mathematica > June 2005 > Constrained Optimization
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Constrained Optimization
|
|
| Caspar von Seckendorff 2005-06-02, 9:06 am |
| Hi,
I'd like to do constrained optimization with Mathematica 5.1 on a
function that is defined piecewise. Unfortunately Maximize[] does not
work as I expected. A short & simple example to illustrate:
f[x_,y_]:= (x-x^2) y
Maximize[{f[x, y], 1/5 <= x <= 2/5, y > 0}, x]
As a result I get:
"The objective function (x-x^2) y contains a nonconstant expression y
independent of variables {x}."
Obviously for this Maximization, knowing that y > 0 I can do the
following to get the desired value for x:
Maximize[{x-x^2, 1/5 <= x <= 2/5}, x]
Out[]= {6/25, {x -> 2/5}}
Is there a way to achieve this without manual intervention? The reason
is, that the functions I want to Maximize are defined Piecewise with
several constraints...
Thanks,
-Caspar
| |
| David Park 2005-06-03, 9:10 am |
| Caspar,
Don't you need to maximize over two variables?
f[x_, y_] := (x - x^2) y
Maximize[{f[x, y], 1/5 <= x <= 2/5, y > 0}, {x, y}]
{Infinity, {x -> Indeterminate, y -> Indeterminate}}
You still obtain an error message but that is because there is no maximum on
the domain.
If you restrict the y domain you will obtain a maximum.
Maximize[{f[x, y], 1/5 <= x <= 2/5, 0 < y <= 10}, {x, y}]
{12/5, {x -> 2/5, y -> 10}}
David Park
djmp@earthlink.net
http://home.earthlink.net/~djmp/
From: Caspar von Seckendorff [mailto:seckendorff@alphatec.de]
Hi,
I'd like to do constrained optimization with Mathematica 5.1 on a
function that is defined piecewise. Unfortunately Maximize[] does not
work as I expected. A short & simple example to illustrate:
f[x_,y_]:= (x-x^2) y
Maximize[{f[x, y], 1/5 <= x <= 2/5, y > 0}, x]
As a result I get:
"The objective function (x-x^2) y contains a nonconstant expression y
independent of variables {x}."
Obviously for this Maximization, knowing that y > 0 I can do the
following to get the desired value for x:
Maximize[{x-x^2, 1/5 <= x <= 2/5}, x]
Out[]= {6/25, {x -> 2/5}}
Is there a way to achieve this without manual intervention? The reason
is, that the functions I want to Maximize are defined Piecewise with
several constraints...
Thanks,
-Caspar
| |
| Bill Rowe 2005-06-03, 9:10 am |
| On 6/2/05 at 5:16 AM, seckendorff@alphatec.de (Caspar von
Seckendorff) wrote:
>I'd like to do constrained optimization with Mathematica 5.1 on a
>function that is defined piecewise. Unfortunately Maximize[] does
>not work as I expected. A short & simple example to illustrate:
>f[x_,y_]:= (x-x^2) y
>Maximize[{f[x, y], 1/5 <= x <= 2/5, y > 0}, x]
>As a result I get: "The objective function (x-x^2) y contains a
>nonconstant expression y independent of variables {x}."
You can avoid this error by adding y as one of the parameters to be maximized, i.e., doing
Maximize[{f[x, y], 1/5 <= x <= 2/5, y > 0}, {x,y}]
But this won't be any better since the constraints you've given aren't adequate to determine a maximum. (For any value of x satisfying your constraints, f increases linearly with y without bound.)
>Obviously for this Maximization, knowing that y > 0 I can do the
>following to get the desired value for x:
>Maximize[{x-x^2, 1/5 <= x <= 2/5}, x]
>Out[]= {6/25, {x -> 2/5}}
>Is there a way to achieve this without manual intervention?
You can achieve the same result by doing
Maximize[{f[x, y], 1/5 <= x <= 2/5, y == 0}, {x,y}]
or
Maximize[{f[x, 1], 1/5 <= x <= 2/5}, x]
--
To reply via email subtract one hundred and four
| |
|
| Hi Caspar,
see below.
sincerely, Daniel
Caspar von Seckendorff wrote:
> Hi,
>
> I'd like to do constrained optimization with Mathematica 5.1 on a
> function that is defined piecewise. Unfortunately Maximize[] does not
> work as I expected. A short & simple example to illustrate:
>
> f[x_,y_]:= (x-x^2) y
> Maximize[{f[x, y], 1/5 <= x <= 2/5, y > 0}, x]
Maximize is a numerical functions. Therefore, f[,] needs numeric input.
However, y is so far a puer symbol and has no numerical value. If I
understand your problem correctly, y is assumed to be a constant. But in
this case the maximum value depends on the unspecified y.
Mathematica gives you a correct error message.
>
> As a result I get:
> "The objective function (x-x^2) y contains a nonconstant expression y
> independent of variables {x}."
>
> Obviously for this Maximization, knowing that y > 0 I can do the
> following to get the desired value for x:
>
> Maximize[{x-x^2, 1/5 <= x <= 2/5}, x]
> Out[]= {6/25, {x -> 2/5}}
>
> Is there a way to achieve this without manual intervention? The reason
> is, that the functions I want to Maximize are defined Piecewise with
> several constraints...
>
> Thanks,
>
> -Caspar
>
| |
| Caspar von Seckendorff 2005-06-04, 8:58 am |
| 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
dh schrieb:
> ...
> Maximize is a numerical functions. Therefore, f[,] needs numeric input.
> However, y is so far a puer symbol and has no numerical value. If I
> understand your problem correctly, y is assumed to be a constant. But in
> this case the maximum value depends on the unspecified y.
> Mathematica gives you a correct error message.
>
| |
| Andrzej Kozlowski 2005-06-05, 8:57 am |
|
On 4 Jun 2005, at 16:04, Caspar von Seckendorff wrote:
> *This message was transferred with a trial version of CommuniGate
> (tm) Pro*
> 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
Actually, it seems you are not asking for too much. Just that
Maximize is not the function to use.
This is how you do it:
f[x_, a_] := (x - x^2) a
Resolve[ForAll[z, 1/5 <= z <= 2/5, 1/5 <= x <= 2/5 &&
f[z, a] <= f[x, a]]]
(a < 0 && x == 1/5) || (a == 0 && 1/5 <= x <= 2/5) ||
(a > 0 && x == 2/5)
Is this what you had in mind?
Andrzej Kozlowski
Chiba, Japan
| |
|
| On Sat, 4 Jun 2005 07:11:55 +0000 (UTC), Caspar von Seckendorff
<seckendorff@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@inbox.ru
| |
| Paul Abbott 2005-06-06, 8:59 am |
| In article <d7rk7r$blu$1@smc.vnet.net>,
Caspar von Seckendorff <seckendorff@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 ;-)
In the forthcoming edition of The Mathematica Journal (Vol. 9, Issue 4),
there is an article entitled "Using Reduce To Solve The Kuhn-Tucker
Equations" by Frank J. Kampas (fkampas@msn.com). The following code,
KuhnTucker[obj_, cons_List, vars_, domain___] :=
Module[{consconvrule = {(x_) >= (y_) -> y - x <= 0,
(x_) > (y_) -> y - x < 0, (x_) == (y_) ->
x - y == 0, (x_) <= (y_) -> x - y <= 0}, stdcons,
eqcons, ineqcons, lambdas, mus, numequals,
numinequals, lagrangian, eqs1, eqs2, eqs3},
stdcons = cons /. consconvrule;
eqcons = Cases[stdcons, (x_) == 0 :> x];
ineqcons = Cases[stdcons, (x_) <= 0 :> x];
numequals = Length[eqcons]; numinequals =
Length[ineqcons]; lambdas = Array[la, numequals];
mus = Array[m, numinequals]; lagrangian =
obj + lambdas . eqcons + mus . ineqcons;
eqs1 = (D[lagrangian, #1] == 0 & ) /@ vars;
eqs2 = Thread[mus >= 0];
eqs3 = Table[mus[[i]]*ineqcons[[i]] == 0,
{i, numinequals}]; Reduce[Join[eqs1, eqs2, eqs3,
cons], Join[vars, lambdas, mus], domain,
Backsubstitution -> True]]
taken from that article, sets up Lagrange multipliers for equality
constraints and the Kuhn-Tucker equations for inequality constraints
(see http://mathworld.wolfram.com/Kuhn-TuckerTheorem.html) and solve using
Reduce.
In some cases, this approach can solve problems which cannot directly be
solved with Maximize and Minimize. However, it does not appear to help
for your example ...
Cheers,
Paul
--
Paul Abbott Phone: +61 8 6488 2734
School of Physics, M013 Fax: +61 8 6488 1014
The University of Western Australia (CRICOS Provider No 00126G)
AUSTRALIA http://physics.uwa.edu.au/~paul
http://InternationalMathematicaSymposium.org/IMS2005/
| |
| Caspar von Seckendorff 2005-06-07, 9:03 am |
| Paul Abbott schrieb:
> KuhnTucker[obj_, cons_List, vars_, domain___] :=
....
>
> In some cases, this approach can solve problems which cannot directly be
> solved with Maximize and Minimize. However, it does not appear to help
> for your example ...
That's great. Actually it seems to work:
In[]:= KuhnTucker[-(x - x^2) y, {1/5 <= x, x <= 2/5, y > 0}, {x}, Reals]
Out[]:= y > 0 && x == 2/5 && m[1] == 0 && m[2] == y/5
Thanks also for pointing out how to use ForAll[...] to get the upper
bound (Maxim) and the maximizing x (Andrzej Kozlowski). Being new to
Mathematica, I have not worked with this function before, but it seems
that you can do a lot with it...
Greetings,
-Caspar
| |
| Andrzej Kozlowski 2005-06-08, 9:01 am |
|
On 7 Jun 2005, at 18:59, Caspar von Seckendorff wrote:
> Thanks also for pointing out how to use ForAll[...] to get the upper
> bound (Maxim) and the maximizing x (Andrzej Kozlowski). Being new to
> Mathematica, I have not worked with this function before, but it seems
> that you can do a lot with it...
>
All that is based on "quantifier elimination over the Reals"-a
beautiful mathematical theory due to the great Polish logician Alfred
Tarski. However, his original approach was not computationally
feasible. Mathematica, I believe, uses Cylindrical Algbraic
Decomposition, an algorithm due to Collins, which has polynomial
complexity if the number of variables is kept constant but is double
exponential in the number of variables. This has been implemented for
Mathematica by Adam Strzebonski of WRI and the University of Cracow
(quite appropriately ;-))
There is a much faster algorithm due to Basu and Roy, but I don't
think it has been implemented in any symbolic algebra program.
Andrzej Kozlowski
|
|
|
|
|