Re: Constrained Optimization
- To: mathgroup at smc.vnet.net
- Subject: [mg57726] Re: Constrained Optimization
- From: Paul Abbott <paul at physics.uwa.edu.au>
- Date: Mon, 6 Jun 2005 04:50:55 -0400 (EDT)
- Organization: The University of Western Australia
- 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
In article <d7rk7r$blu$1 at smc.vnet.net>,
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 ;-)
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 at 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/