Looking for Clarification on fmincon and it's constraint violation allowances
Elizabeth
I would firstly like to qualify this thread by saying I am for the most part a self-taught MATLAB user, and with that I believe comes a number of things that I know I do not know.
I am running an optimisation using fmincon which has:
* lower and upper bounds (lower=0),
* linear inequalities,
* empty linear equalities,
* non-linear conditions (using c=0 only),
* a linear cost function and
* the vector to be optimised (x) is [280x1].
The problem I am representing is that of storage release and then transportation of 'packets' of substances round a geographical topology. There are in fact 8 systems, with their own flavour of packets that work individually and so x can be said to be 8 [35x1] vectors concatenated together.
When the problem is separated into the 8 flavours of systems and each solved separately fmincon can solve all of them individually using the active set algorithm with:
'TolX',1e-100,
'TolFun',1e-10,
'TolCon',1e-2,
'MaxIter',10000000,
'MaxFunEvals',10000000
'Display','final-detailed',
this was great news, and I did in fact do a little dance of joy MATLAB calculated what storage needed to be utilised, and where to allow packets to flow in order to reduce the over cost of satisfying demand.
However, I need all the flows and storage to be calculated simultaneously as in in one [280x1] vector, as I am going to be adding another level of complexity and this is just what I need without going into too much detail.
So, when I put all the bounds and constraints together and create an optimisation problem for the [280x1] vector I hit a snag. With the active set algorithm set with the following options, I do not get a solution. You will see from the below that I have brought in some options that I had not used previously, as looking at other messages on the forum I thought they may help, but sadly no. I also copy in the exit message from the optimisation.
i have also tried with the interior point algorithm, but it returns a highly in feasible result, for example one variable is bound by lb=0 and ub=0, but optimisation returns it with a value of 90.056.
I was also wondering if anyone could give clarification on:
1)how the constraint violation is calculated and
2) What TolCon, TonFun and TolX actually represent (I have read all the blurb in the help documentation, but to me they are not clear at all)
---------------------------------------------
options = optimset(
'Algorithm','active-set',
'TolFun',1e-10,
'TolCon',1e-2,
'TolX',1e-250,
'MaxIter',10000000,
'MaxFunEvals',10000000
'MaxSQPIter',1000000,
'Display','Iter',
'GradObj','off',
'DerivativeCheck','On',
'FunValCheck','on',
'AlwaysHonorConstraints','bounds',);
Max Line search Directional First-order
Iter F-count f(x) constraint steplength derivative optimality Procedure
0 281 0 48.87 Infeasible start point
1 562 -9.09615e+007 90.2 1 -4.36e+005 5.04e+007 unreliable
2 843 -2.7433e+008 113.9 1 -6.34e+005 4.1e+006 MaxSQPIter
3 1124 -3.52132e+008 93.55 1 -3.96e+005 4.1e+006 MaxSQPIter
4 1405 -7.18486e+008 76.68 1 -1.88e+006 4.1e+006 Hessian modified; MaxSQPIter
No feasible solution found.
fmincon stopped because the size of the current search direction is less than
twice the selected value of the step size tolerance but constraints were not
satisfied to within the selected value of the constraint tolerance.
<stopping criteria details>
fval = -7.1849e+008
exitflag = -2
output =
iterations: 5
funcCount: 1405
lssteplength: 1
stepsize: 0
algorithm: 'medium-scale: SQP, Quasi-Newton, line-search'
firstorderopt: 4.1000e+006
constrviolation: 76.6800
message: [1x757 char]
Elapsed time is 23269.036404 seconds.
thanks to all with the patience to read this!
Elizabeth
I would firstly like to qualify this thread by saying I am for the most part a self-taught MATLAB user, and with that I believe comes a number of things that I know I do not know.
I am running an optimisation using fmincon which has:
* lower and upper bounds (lower=0),
* linear inequalities,
* empty linear equalities,
* non-linear conditions (using c=0 only),
* a linear cost function and
* the vector to be optimised (x) is [280x1].
The problem I am representing is that of storage release and then transportation of 'packets' of substances round a geographical topology. There are in fact 8 systems, with their own flavour of packets that work individually and so x can be said to be 8 [35x1] vectors concatenated together.
When the problem is separated into the 8 flavours of systems and each solved separately fmincon can solve all of them individually using the active set algorithm with:
'TolX',1e-100,
'TolFun',1e-10,
'TolCon',1e-2,
'MaxIter',10000000,
'MaxFunEvals',10000000
'Display','final-detailed',
this was great news, and I did in fact do a little dance of joy MATLAB calculated what storage needed to be utilised, and where to allow packets to flow in order to reduce the over cost of satisfying demand.
However, I need all the flows and storage to be calculated simultaneously as in in one [280x1] vector, as I am going to be adding another level of complexity and this is just what I need without going into too much detail.
So, when I put all the bounds and constraints together and create an optimisation problem for the [280x1] vector I hit a snag. With the active set algorithm set with the following options, I do not get a solution. You will see from the below that I have brought in some options that I had not used previously, as looking at other messages on the forum I thought they may help, but sadly no. I also copy in the exit message from the optimisation.
i have also tried with the interior point algorithm, but it returns a highly in feasible result, for example one variable is bound by lb=0 and ub=0, but optimisation returns it with a value of 90.056.
I was wondering if anyone could give clarification on:
1)how the constraint violation is calculated and
2) What TolCon, TonFun and TolX actually represent (I have read all the blurb in the help documentation, but to me they are not clear at all)
Because, in the case of interior point fmincon is returning values completly without the feasible region and active set has an incredible high constraint violation, even though both have 'AlwaysHonorConstraints' set to 'bounds'.
Alan Weiss
1. Setting TolX lower than eps ~ 2e-16 is not sensible. I usually
recommend 1e-14 as the smallest value for any tolerance, and 1e-12 is
often too small. See
http://www.mathworks.com/help/toolbox/optim/ug/br44iv5-1.html#br53ci6
2. Setting TolCon to 1e-2 might not be a good idea. Why did you change
it from the default?
3. The interior-point algorithm strictly obeys bounds IF you start from
a point that satisfies all the constraints. So I recommend trying the
interior-point algorithm again.
4. Are you sure your problem is feasible? For suggestions on how to
proceed, see
http://www.mathworks.com/help/toolbox/optim/ug/br44iv5-1.html#br44i73
5. I also suggest you use iterative display with the default exit
message ('Display" = 'iter') to see what is going on during the
optimization. For more suggestions, read through
http://www.mathworks.com/help/toolbox/optim/ug/br44iv5-1.html
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation
Elizabeth
changing the bounds back to the defaults gives me the error i have seen many a time:
-----
First-order Norm of
Iter F-count f(x) Feasibility optimality step
0 561 1.143546e+008 4.788e+001 2.050e+006
1 1122 8.978627e+007 4.516e+001 2.050e+006 6.454e+000
2 1683 8.001420e+007 4.203e+001 2.050e+006 7.881e+000
3 2244 9.507585e+007 3.645e+001 2.050e+006 1.575e+001
4 2805 1.279014e+008 3.100e+001 2.050e+006 2.016e+001
5 3366 1.729441e+008 3.000e+001 1.418e+006 2.205e+001
6 3927 1.731837e+008 3.000e+001 6.631e+005 1.086e-001
7 4488 1.731912e+008 3.000e+001 6.216e+005 3.499e-003
No feasible solution found.
fmincon stopped because the size of the current step is less than
the selected value of the step size tolerance but constraints were not
satisfied to within the selected value of the constraint tolerance.
-----
This is why Tol X was set so low, because I was continually getting the message that it was the reason for stopping. Could you tell me how it is that the norm of the step is calculated for large vector variables? For a single variable I understand that it would simply be the change in that variable, but how is it done in the case of a vector? this may help me understand why what i am doing is wrong.
i know that my problem is feasible, not least because this is a test case I designed and I made it feasible, but also because as I said in the earlier post:
> > The problem I am representing is that of storage release and then
> > transportation of 'packets' of substances round a geographical topology.
> > There are in fact 8 systems, with their own flavour of packets that work
> > individually and so x can be said to be 8 [35x1] vectors concatenated
> > together.
> > When the problem is separated into the 8 flavours of systems and each
> > solved separately fmincon can solve all of them individually using the
> > active set algorithm with: 'TolX',1e-100,
> > 'TolFun',1e-10,
> > 'TolCon',1e-2,
> > 'MaxIter',10000000,
> > 'MaxFunEvals',10000000
> > 'Display','final-detailed',
> >
> > this was great news, and I did in fact do a little dance of joy MATLAB
> > calculated what storage needed to be utilised, and where to allow
> > packets to flow in order to reduce the over cost of satisfying demand.
> > However, I need all the flows and storage to be calculated
> > simultaneously as in in one [280x1] vector, as I am going to be adding
> > another level of complexity and this is just what I need without going
> > into too much detail.
As far as changing the start-point goes, as I said, this is a test case and so it is simple. in the future i am looking at a variable with up to 600 or 700 rows or more, and so in those cases, how would i go about determining a feasible start point? I do not want the user to have to come up with one, as even om paper this would be very very complicated. could matlab help there?
thanks for you help
Beth
Alan Weiss
1. You don't start at a feasible point. Please take a look at my
previous suggestion about infeasible solutions, and how to start at a
feasible point:
http://www.mathworks.com/help/toolbox/optim/ug/br44iv5-1.html#br44i73
2. Setting TolX to any value below eps can cause fmincon to assume TolX
is zero. This is not usually sensible. I understand, you want fmincon to
continue. But it is having trouble. You would do better to try to fix
the trouble than to blindly force fmincon to proceed. One way to fix the
trouble might be to start at a feasible point. Another is to look at
your problem formulation and see if you have any non-smooth functions,
such as abs, in an objective or nonlinear constraint. If you have a
nonsmooth function, then I recommend you smooth it.
3. To see how the various fmincon algorithms choose a step size, see
http://www.mathworks.com/help/toolbox/optim/ug/brnoxzl.html
Yes, there is a lot of detail here, and it is pretty dense.
4. Allow me to reiterate my suggestion that you try to follow the
suggestions in
http://www.mathworks.com/help/toolbox/optim/ug/br44iv5-1.html
To understand, for example, what the iterative display means, see
http://www.mathworks.com/help/toolbox/optim/ug/f12687.html#f12710
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation
Alan Weiss
Perhaps you can take a hybrid approach. An inner layer has your 8 systems with extra parameters passed in by the outer layer. Your outer layer takes the extra parameters and tries to optimize them.
The advantage of this approach, if it is feasible to formulate your problem this way, is the inner optimizations are much lower-dimensional, and so should have more reliable, faster solutions than a single high-dimensional minimization. To formulate your problem this way you would have to identify some parameters of the outer system, and give an outer objective function in terms of these parameters and in terms of the solutions of the inner problems. The inner problems would have to be independent of each other once the outer system parameters are given.
I don't know if this approach makes sense for your problem. If not, just chalk it up to good intentions from an uninformed onlooker.
Alan Weiss
MATLAB mathematical toolbox documentation
Alan Weiss <awe...@mathworks.com> wrote in message <i9pm10$r67$1...@fred.mathworks.com>...