In article <f7pb3o$6rm$1@news.Stanford.EDU>,
"Gino Victor" <gino_victor@hotmail.com> writes:

"Peter Spellucci" <spellucci@fb04373.mathematik.tu-darmstadt.de> wrote in
message news:f7o0kl$5g0$1@fb04373.mathematik.tu-darmstadt.de...

In article <f7nisf$9jr$1@news.Stanford.EDU>,
"Gino Victor" <gino_victor@hotmail.com> writes:

"Peter Spellucci" <spellucci@fb04373.mathematik.tu-darmstadt.de> wrote
in
message news:f7nhn8$3r3$1@fb04373.mathematik.tu-darmstadt.de...

In article <f7msus$e9u$1@news.Stanford.EDU>,
"Gino Victor" <gino_victor@hotmail.com> writes:

Hi there,

I was wondering if there are resources and articles that explain
the
Matlab's optimization results and iteration displays better?

For example, Matlab "fmincon" displays the following during
execution,
and
at the end it will terminate with message showing that why it ends.
And
it
will also mention how many constraints are active or inactive, etc.

What do all these stuff mean? I searched Matlab's own documentation
but
couldn't find a good explanation of these terms. Specifically I ask
these
questions because my optimization doesn't yield good results and a
lot
of
times the solver seems to terminate very fast after just few
function
evaluations, and the "optimal" x values are some boundary values.

I imagine an expert on practical optimization will be able to gain
a
lot
of
insights from Matlab's output messages during and at the end of the
iterations... I want to learn such technical skills. Could anybody
give
me
some pointers? Thanks a lot and much appreciated!

--------------------------------------------------------------------

Max Line search Directional
First-order
Iter F-count f(x) constraint steplength derivative
optimality Procedure
0 15 6.21466 1.11e-016

the written documentation for the optimization toolbox contains some
info
on the meaning of this output, but in order to be able to properly
interpret
this you must know a lot about the optimization method behind:
the book "numerical optimization" by Nocedal and Wright is quite
accessible
for nonspecialists and explains many of these algorithms.
in the above case, F-count means the objective has been evaluated 15
times,
the current point satisfies all constraints up to 1.11e-16
(which by far is enough in the sense of the defaults)
, and no step has been done at all
because the Kuhn-Tucker criteria are satisfied sufficiently (in the
menaing
of the code). if the input x is no solution in your sense, there
might
be
an effect I have observed quite often in practice: obviously you
force
fmincon to compute the gradients by finite differences. (otherwise
it
is
hard to
see no step computed but 15 function evaluations spent).
If your function evaluation is insensisitve against very small
changes
in
x
(for example a simulation program where output depends not sensitive
on
design due to discretization) , and the default variations in the
finite
differencing in fmincon are very small, (you can change this via
optimset),
then the computed finite difference gradient of f appears as
(almost)
zero,
the multipliers are set to zero and the problem is solved (in the
sense
of
the software)
hth
peter

Thanks a lot Peter. Your explaination makes sense.Do you think

(1) Supplying a gradient myself to Matlab;

supplying the gradient is always useful and you should do that if
it is feasible for you at all,
there are of course occasions there this is impossible
(functions coming from a simulation program for which you have the
binary
only and which doesn't deliver sensitivity information)

and/or
(2) make the step size of finite differencing larger;

will work?

For (2), I am afraid that if I make the step size large, it may not
work
for
other part of the function. Let's say some parts of the function is
sensitive to a small variation, some other parts of the function is
sensitive to a large variation. Then there is no uniformly good step
size?

I've read the Nocedal book and other books and have even taken
classes on
optimization. But it is just to link the class stuff to the practical
stuff.
It's all about experience and no school can teach that unless there
are
TAs
or the professors are good at practical stuff themselves and are
willing
to
spend time with students hands-on. But these are not realistic
expectations.
So please shed some lights on how to further enhance my learning about
these
experience stuff -- any books/resources/tutorials at least more
practical?
Thanks again!

using numerical gradients is pretty tricky in real life:
your function will also have some evaluation noise
(for example if you are running a FEM analysis which uses adaptivity
then the output will _not_ behave as a smooth function of the current
design if a change in the design changes the grid)
this noise can completely spoil your information

therefore , if forced to use numerical gradients, you should first
run some experiments with numerical differencing. In the situation you
describe you could use scaling of the variables. one rule of thumb says
that the Hessian should have diagonal entries of approximately equal
size
(this applies for uniformly convex linearly constrained problems) but
another rule of thumb proposes to scale the variables to make them all
of approximately equal size. this rule may contradict the first one.
example
f(x) = 0.5*( 0.01*x_1^2 +x_2^2) -b*x_1 - x_2 , b in [0,1000]

matlab gives you the opportunity to provide a "typical X"
which is used for defining such a scaling.
if you have decided on this, then compute your gradient numerically
and check whether
f(x+t*g) = f(x)+t*norm(g)^2 approximately for small t
and play around with the differencing stepsize for this. this might
help.

Hi Peter,

I don't understand your two rules of thumbs and your example. Could you
please elaborate a bit more? Thanks!

Perhaps there are books called "practical optimization with Matlab" or
something like that?

these two rules are quite easy to understand (and quite common, compare
the old classic "practical optimization" by Gill and Murray )

in 1969, van der Sluis proved the following:
a symmetric positive definite matrix is optimally scaled with respect
to diagonal scaling
A-> DAD
up to a factor sqrt(n) if its diagonal is a multiple of the unit matrix.
as you will (should) know the conditioning of the Hessian is quite
important
for the performance of optimization algorithms and the Hessian of the
objective
is also the Hessian of the Lagrangian if all constraints are affine
linear.
hence rule of thumb number one:
if you transform
Dz = x
and
ftilde(z)=f(Dz)=f(x)
then
Hessian(ftilde) =D Hessian(f)*D
and of course
z=inv(D)*x
hence you might want to minimize ftilde with a scaling which makes
the diagonal of its Hessian approximately a multiple of the unit matrix.
in the example above
D=diag(0.1,1)
and
ftilde(z)=0.5*(z_1^2+z_2^2) -10*b*z_1-z_2.
here one step of the ordinary gradient minimization does the complete job!

on the other side, imagine a problem where in the original variables the
solution
is
(100000,60000,0.1,-0.2).
the initial guess being 50000,30000,0.01,0.
the problem being highly sensitive with respect to x_3 and x_4.
(this is no artifice, many practical problems show such effects)
clearly you must make large moves in x_1 and x_2 , but small moves
in x_3 and x_4. now you cannot hope that search directions generated,
either by
quasi-Newton , true Newton , cg or whatever will always reflect these
relative
sizes and you may have to make horribly many very small moves to reach the
solution. here it might be much better to introduce
z_1=10^(-6)*x_1,z_2=10^(-5)*x_2, z_3=x_3, z_4=x_4
and exactly this is done if you provide fmincon with typical x =
(1000000,100000,1,1).

lasdon and coworkers performed a study on the benefits of automatic
scaling with
no clearcut outcome: sometimes this scaling is better, sometimes the
other,
sometimes no scaling at all is the best advice:



Lasdon, L.S.; Beck, P.O.
Scaling nonlinear programs. (English)
[J] Oper. Res. Lett. 1, 6-9 (1981). ISSN 0167-6377


you simply must experiment with your problem in order to see what is best.


hth
peter

On Thu, 19 Jul 2007 23:42:54 -0400, "Gino Victor"

<gino_vic...@hotmail.com> wrote:

Hi Peter,

I don't understand your two rules of thumbs and your example. Could you
please elaborate a bit more? Thanks!

I don't understand these rules either.

Consider function of 2 variables named "Rosenbrock banana valley" that
is standard optimization benchmark

100*(x[2]-x[1]^2)^2+(1-x[1])^2

Plot this function and thing what is the "best" value of increment to
calulate. Plot you can find here

http://en.wikipedia.org/wiki/Rosenbrock_function

This function has deep, narrow, "banana shape" valley with flat
bottom. Gradient optimization gets to the bottom of valley very
quickly, and then progreses along the bottom of the valley. Think what
discretization increment would be needed in various parts of the
valley. Since valley is "banana shape", the best increment will depend
strongly on the point where you are calculating the derivative.

This illustrates that a) finding "universal" step can be hard if not
impossible, b) "best" step can be defined only locally, c) "best" step
changes as optimziation progresses and some adaptive algorithm for
step selection must be implemented.