On Feb 3, 12:29 am, "Mike Middleton" wrote:
monir -
Yes, a combination of a 6th deg poly and Solver is generally a problem! <
Please educate me. When is a 6th degree polynomial appropriate?
I can understand using a 2nd degree polynomial to model a single-bulge
relationship, and occasionally there may be an S-shaped relationship that
needs a 3rd degree polynomial.
But what kind of real-world situation needs a model with a 6th degree
polynomial?
(In most data analysis applications, I would be very concerned with
over-fitting and the numerical precision difficulties associated with
raising values to the 6th power.)
I really am curious.
- Mike Middletonhttp://www.DecisionToolworks.com
Decision Analysis Add-ins for Excel
"monir" wrote in message
...
Dana;
Thank you for taking the time.
1) Your thoughts are valid. Yes, a combination of a 6th deg poly and
Solver
is generally a problem! However, as I indicated in my OP, for any value
of
the changing variable P, say P1, E has a single extremum (max) within the
range of interest of J and P.
Thus, Solver should not really get confused by seeing multiple min and
max!
There's only one local max point.
2) It seems to me that Excel / Solver performs better when the target is
set
to a value rather than to a max or min! And that's precisely why I had to
reformulate the problem such that d(E)/d(J) is set to zero instead of
(originally) setting E to max. It works!
3) It's evident from your reply that you're familiar with the subject
matter, and possibly have tried other optimizers. If so, would you be
kind
enough to share some of your experience and thoughts on such other
optimizers
regarding: reliability, limitations, options, availability of VBA code,
etc.
Thank you.
Monir
"Dana DeLouis" wrote:
1) I've reformulated the optimization problem by deriving the
analytical
expression for the 1st derivative d(E)/d(J) as a function of J and P.
(fn1, fn2, fn4 are complicated, lengthy, 6th deg polys, ~ 1 page long
each
Just a thought. Without knowing what you have, solving 6th Deg Polyn.
can
be hard, and have multiple solutions.(Derivative =0's)
Solver was probably seeing multiple local Min & Max points on your curve.
As one curve was increasing, probably the other curves were decreasing,
etc... Once Solver gets confused, it easily gives up. Once Solver locks
onto an incorrect local minimum, Solver doesn't have enought logic to get
out of it, and give proper warnings.
Make sure you model was not using functions like IF(), as these cause
problems for Solver.
Mentioning 6th Deg Polys with Solver should send a red flag! It may be
possible to write a vba routine using the Newton Method. That can
sometimes
help.
You may have a valid solution, but my experience would suggest caution
with
the answer given.
--
Dana DeLouis
"monir" wrote in message
...
Steve;
Thank you kindly for your thoughtful reply.
It's very clear that Excel / Solver (also developed by Frontline!) is
the
problem!!! No surprise.
1) I've reformulated the optimization problem by deriving the
analytical
expression for the 1st derivative d(E)/d(J) as a function of J and P.
The
problem now reads:
Given the relations:
..T = fn1(J, P)
..Q = fn2(J, P)
..E = fn3(T, Q, J)
..B = fn4(J, Q)
find the values of:
..J (bet 0.05 and 1.40)
..P (bet 0.50 and 1.50)
such that:
..target: d(E)/d(J) = 0.0
..constraint: B = a known B0
(fn1, fn2, fn4 are complicated, lengthy, 6th deg polys, ~ 1 page long
each.
That's why I didn't include them in my OP.)
2) Now the Solver solution (J, P, E) is perfect!!
3) I've never used or even heard of NLP IPOPT (Fortran)!! but will look
at
it. Thanks for the link.
4) One of the difficulties would be to convert IPOPT to VBA. It is
hard
to
know without examining the code. My programming experience is about
60/40
Fortran/VBA. But again, the feasibility of the task would depend on
the
complexity of IPOPT.
Based on your expertise in the field, do you know of or used a reliable
VBA
optimizer macro ??
Thank you once again for your help.
Monir
"SteveM" wrote:
On Jan 29, 2:21 pm, monir wrote:
Steve;
Thank you for your prompt reply.
a) Let me first clarify item 2) of my OP.
The 2nd sentence should read:
"For any value of the changing variable P, say P1, in the range
P=0.50
to
1.50, there is a max E1 at J1, which DOES NOT necessarily satisfy
the
constraint B18 = 1."
b) Please review my suggestion item 3) of my OP in light of the
above
clarification.
c) I'm running Excel Solver from a macro.
d) FYI. Frontline Premium Solver is poorly developed and
technically
unreliable! I've extensively tested it earlier on, and reported its
numerous
and serious errors to Frontline.
Any thoughts ?? Thank you
"SteveM" wrote:
On Jan 29, 12:00 pm, monir
wrote:
Hello;
I would very much appreciate your help in the following
relatively
simple
non-linear optimization problem.
1) By applying Solver:
....Set target cell: E18 to max....(E18 represents dependent
variable E)
....By changing cells: J18 ..........(J18 represents independent
variable J)
............................: P18...........(P18 represents
independent
variable P)
....Subject to constraints: B18=1
....................................: J range 0.05 to 1.40
....................................: P range 0.50 to 1.50
it produces a feasible solution (J, P, E), which is not exactly
the
"correct" one (differs by about 10% of what it should be)
2) The difficulty is directly associated with the above
formulation
of the
problem.
For any value of the changing variable P, say P1, in the range
P=0.50 to
1.50, there is a max E1 at J1.
Solver in 1) above appears to seek the solution for max E based
on
the
changing combinations of J and P and settles for the combination
that
produces max E in comparison with other combinations and subject
to
the
constraints.
This is clearly not what I had in mind!!
3) The correct formulation of the problem should be, I think,
something like:
..Solver1: for each tried value of P, say, P1 in the range 0.50
to
1.50
..Set target cell: E18 to max.....(E18 represents dependent
variable E)
..By changing cells: J18 ...........(J18 represents independent
variable J)
..Subject to constraints: J range 0.05 to 1.40
.............(solution: J1, max E1 at each P1)
....Solver2:
....Set target cell: B18 = 1
....By changing cells: J18 ..........(J18 now represents the new
variable J1)
....Subject to constraints: J1 range 0.05 to 1.40 (same range of
J
is fine)
.............(solution: J2, P2, max E2)
4) How would you intelligently combine Solver1 and Solver2 as a
2-level
Solver ?? either by running Solver manually or by a macro. And,
is
it
possible to do so relying entirely on the Solver internal trial
solutions
without establishing the relation between P1s and E1s (which is
not
easy to
do) ??
Thank you kindly.
monir,
Well first of all, what are you trying to maximize? If your 1 is
formulated properly then yes, it is doing what it is supposed to
be
doing. So if not E then what?
It's better to describe your problem in equation (not Excel) form
because that is much clearer to another modeler. I.e., it would
be
good to know what the functional relationship of P's and J's are
to
E. BTW, if P and J are changing cells then they are decision
variables. It's not clear what they are either. Are they single
cells or a vector of cells. What are the non-linear constraint
functions that are functions of them? If you could post that it
would
be helpful.
Your 2 implies E is only a function of J unless there is some sort
of
plus/minus symmetry between J and P. But then you could make a P
a
function of J and replace all the P's in your formulation. But
assuming there is not then P is not in the basis for any value of
J.
Otherwise you'd a different Emax. So if P is not in the objective
function and always non basic. I don't see how including it can
contribute to the formulation.
You proposed parametric
...
read more
I gotta step in here. Regardless of what the function is (excepting
that it's smooth and continuous in the feasible region, the max/min
value of the objective function may be meaningless by itself. I.e.
setting first derivatives to 0. Because the feasible region is
defined by the bounded poly-tope comprised of both the objective
function and the constraint set.
Say you have a simple parabola, y = x2 that you want to minimize.
Setting the first derivative = 0, gives an inflection point. Simple
enough. But now add the constraint y = 3 which is represented by a
line that passes right through the parabola. So now the feasible
region has been reduced taking the 0 point of the objective function
out of play. So the derivative by itself provides you with no value.
The convexity of higher order systems of non-linear inequalities is
generally impossible to establish by inspection. It can be determined
by examining if the Hessian of the Lagrangian equation meets KKT
conditions. I.e. is positive/negative definite. I'm not an NLP guy
per se. (But was taught by the best, Fiacco and McCormick who
formulated the SUMT technique which is the basis for barrier solvers),
but KKT evaluation requires that the Lagrangian be twice
differentiable. But sometimes it's not, e.g. the case above, but
there are ways around that. I don't know how complex the solvers are
these days because I'm mostly a MIP guy, but part of their power is
being able to look at the formulation and deduce what kind of animal
it's dealing with. It all gets kind of complicated.
One other thing, Newton's Method can be used as search strategy for
NLP, but it's generally not used because it is a "steepest descent"
algorithm I think. That's a greedy method that often has the solver
stuck iterating around a flat spot of the poly-tope if the wrong
feasible starting point was selected and the iteration step size is
not properly scaled. There are superior quasi-Newton methods as well
as others. Much of the time, the efficiency of an optimization is
based on search parameters set by the modeler. The more sophisticated
the solver package that more switches can be set. I know for MIP
problems though, there are tons of search parameter combinations and
often the right combination is discovered serendipitously. BTW, a
solution time can sometimes be knocked back from hours to seconds if
you get it right.
OK, so back to the original poster's original question. I still don't
know what his/her functional form is, so really have know idea what's
what with his/her problem. But related to NLP and solvers, you all
can check these references if you wish:
http://www-new.mcs.anl.gov/otc/Guide/
is a wonderful site with a link to a list of solvers.
Another great site is run my Hans Mittelmann at Arizona State:
http://plato.asu.edu/sub/websub.html
Note that LINGO and What's Best directly interface with Excel. What's
Best models are formulated like Frontline. LINGO is an algebraic
modeling language. Both are put out by LINDO Systems so you can be
sure that the NLP solvers are not very robust. But you can probably
download a trial version of What's Best and see if it works. (I'm
sure LINGO uses the same NLP engine.)
I use a model management system called MPL,
www.maximal-usa.com and
the XA LP/MIP solver which is very good for medium to large problems
and is priced right. The developer, Sunset Technologies,
www.sunsetsoft.com
also has NLP modules. Their shop is small but they know what they are
doing. And again if their stuff at their prices can solve your
problem, then why not?
MPL also has a component library called Optimax that allows you to
embed your model directly in Excel using VBA. I use MPL and Optimax
in tandem and it works out very well. MPL also has trial downloads of
the product itself, plus a reduced version of CPLEX, which is one of
the most powerful (and expensive) optimizers out there. If your
problem is small enough and non-recurrent, the trial download may work
for you. (Although the CPLEX parameter set is huge. But MPL allows
you set them via it's intuitive interface.)
If you want additional help, you can visit the Google OR newsgroup,
sci.op-research. Dr. Paul Rubin from Michigan State is an
optimization guy who is always lurking around looking to help.
Including "Dr. Rubin, Help!?" in your subject line is like putting a
worm in front of a fish.
Oh, if you actually need to purchase product and contact those guys,
Jim at Sunset and Bjarni at Maximal, tell them I sent you J.
OK, I'm tapped out.
SteveM