Thread Subject: using fmincon with high dimension optimization

Hi,

I need to estimate 11 parameters by using fmincon with linear inequality constraints and bound conditions. I supplied the gradient and hessian of objective function.

function [LLH,G,H] = Objf(params,data)

[x, f, EXITFLAG, OUTPUT] = fmincon('Objf',...
                                  InitialParams, sumA,sumB,[],[],LB,UB,[],options,data)

After I run, the message that I got was:
Warning: Trust-region-reflective method does not currently solve this type of problem,
 using active-set (line search) instead.
> In fmincon at 437
Maximum number of function evaluations exceeded;
 increase OPTIONS.MaxFunEvals.

I checked my gradient and hessian, they same ok. I also varied option settings. Warning msg still appears. Here is my question:
Can "interior-point" algorithm be used for linear inequality constrant? if answer is yes, how can I get the hessian of the Lagrangian. If not, which algorithm should I use?

thank you very much, any help would be greatly appreciated!

Yes, the interior-point algorithm can be used with linear inequality
constraints. For this type of constraint the Hessian of the Lagrangian
is just the Hessian of the objective function. To see an example of how
to pass the Hessian for the interior-point algorithm:
http://www.mathworks.com/access/helpdesk/help/toolbox/optim/ug/brn4nh7.html#bri8026

Alan Weiss
MATLAB mathematical toolbox documentation

Gibran zhong wrote:
> Hi,
>
> I need to estimate 11 parameters by using fmincon with linear inequality constraints and bound conditions. I supplied the gradient and hessian of objective function.
>
> function [LLH,G,H] = Objf(params,data)
>
> [x, f, EXITFLAG, OUTPUT] = fmincon('Objf',...
> InitialParams, sumA,sumB,[],[],LB,UB,[],options,data)
>
> After I run, the message that I got was:
> Warning: Trust-region-reflective method does not currently solve this type of problem,
> using active-set (line search) instead.
>> In fmincon at 437
> Maximum number of function evaluations exceeded;
> increase OPTIONS.MaxFunEvals.
>
> I checked my gradient and hessian, they same ok. I also varied option settings. Warning msg still appears. Here is my question:
> Can "interior-point" algorithm be used for linear inequality constrant? if answer is yes, how can I get the hessian of the Lagrangian. If not, which algorithm should I use?
>
> thank you very much, any help would be greatly appreciated!

Hi Alan,
Thank you for the help, really appreciated! I tried again with reduced parameter numbers (6 parameters in total) and set options as the followings
options = optimset('LargeScale' , 'on');
options = optimset('Algorithm','interior-point');
options = optimset('Display' , 'iter');
options = optimset('Diagnostics' , 'on');
options = optimset('GradObj' , 'on');
options = optimset('Hessian' , 'on');
options = optimset('MaxFunEvals' , 1e+15);
options = optimset('TolFun' , 1e-6);
options = optimset('MaxIter' , 1e+15);

The Initial value for the parameters which I used are estimated by using fminsearch. The values are quite reasonable. however, when I change to fmincon, the Warning msg appears:
Warning: Trust-region-reflective method does not currently solve this type of problem,
 using active-set (line search) instead.
> In fmincon at 437
Maximum number of function evaluations exceeded;
 increase OPTIONS.MaxFunEvals.
x =
  1.0e+010 *
    0.0019 0.0000 0.0000 1.0934 0 -0.0000

f =
   NaN

EXITFLAG =
     0

OUTPUT =
         iterations: 99
          funcCount: 604
       lssteplength: 2
           stepsize: NaN
          algorithm: 'medium-scale: SQP, Quasi-Newton, line-search'
      firstorderopt: Inf
    constrviolation: 8.9523e-018
            message: [1x79 char]

I am not quite sure what the problem is. Can you help me on this? Thanks

Yan


Alan Weiss <aweiss@mathworks.com> wrote in message <hdse2g$bq2$2@fred.mathworks.com>...
> Yes, the interior-point algorithm can be used with linear inequality
> constraints. For this type of constraint the Hessian of the Lagrangian
> is just the Hessian of the objective function. To see an example of how
> to pass the Hessian for the interior-point algorithm:
> http://www.mathworks.com/access/helpdesk/help/toolbox/optim/ug/brn4nh7.html#bri8026
>
> Alan Weiss
> MATLAB mathematical toolbox documentation
>
> Gibran zhong wrote:
> > Hi,
> >
> > I need to estimate 11 parameters by using fmincon with linear inequality constraints and bound conditions. I supplied the gradient and hessian of objective function.
> >
> > function [LLH,G,H] = Objf(params,data)
> >
> > [x, f, EXITFLAG, OUTPUT] = fmincon('Objf',...
> > InitialParams, sumA,sumB,[],[],LB,UB,[],options,data)
> >
> > After I run, the message that I got was:
> > Warning: Trust-region-reflective method does not currently solve this type of problem,
> > using active-set (line search) instead.
> >> In fmincon at 437
> > Maximum number of function evaluations exceeded;
> > increase OPTIONS.MaxFunEvals.
> >
> > I checked my gradient and hessian, they same ok. I also varied option settings. Warning msg still appears. Here is my question:
> > Can "interior-point" algorithm be used for linear inequality constrant? if answer is yes, how can I get the hessian of the Lagrangian. If not, which algorithm should I use?
> >
> > thank you very much, any help would be greatly appreciated!

Hi Yan,

I have a few points here (inserted below):
"yan zhong" <yanp.zhong@gmail.com> wrote in message <hdsgck$o0f$1@fred.mathworks.com>...
> Hi Alan,
> Thank you for the help, really appreciated! I tried again with reduced parameter numbers (6 parameters in total) and set options as the followings
> options = optimset('LargeScale' , 'on');
> options = optimset('Algorithm','interior-point');
> options = optimset('Display' , 'iter');
> options = optimset('Diagnostics' , 'on');
> options = optimset('GradObj' , 'on');
> options = optimset('Hessian' , 'on');
> options = optimset('MaxFunEvals' , 1e+15);
> options = optimset('TolFun' , 1e-6);
> options = optimset('MaxIter' , 1e+15);
                                  ^
                                  |
Here's your problem. When you call OPTIMSET like this, it returns a new structure. The end result of your code is an options structure with only "MaxIter" set. What you want to do is pass the struct "options" to OPTIMSET when changing or setting another option:

   options = optimset('LargeScale' , 'on');
   options = optimset(options,'Algorithm','interior-point');
   options = optimset(options,'Display','iter');
                  ...

> The Initial value for the parameters which I used are estimated by using fminsearch. The values are quite reasonable. however, when I change to fmincon, the Warning msg appears:
> Warning: Trust-region-reflective method does not currently solve this type of problem,
> using active-set (line search) instead.
> > In fmincon at 437
> Maximum number of function evaluations exceeded;
> increase OPTIONS.MaxFunEvals.
> x =
> 1.0e+010 *
> 0.0019 0.0000 0.0000 1.0934 0 -0.0000
>
> f =
> NaN
>
> EXITFLAG =
> 0
>
> OUTPUT =
> iterations: 99
> funcCount: 604
> lssteplength: 2
> stepsize: NaN
> algorithm: 'medium-scale: SQP, Quasi-Newton, line-search'
> firstorderopt: Inf
> constrviolation: 8.9523e-018
> message: [1x79 char]
>

Yikes! Are the initial values (x0) on the order of 1e10? That is awfully large for any algorithm to handle? Does your objective, constraint, or gradient/Jacobian produce large values? Are those quantities defined everywhere? Can they evaluate to Infs or NaNs? (Note: you can check this setting the option 'FunValCheck' to 'on').

These are things to check, because they will likely cause the algorithm to break down. You may have better luck with the interior point algorithm due to some internal scaling and, if you have MATLAB R2009b, increased robustness to Inf and NaN values from objective and constraint functions.

Hi Steve,
Thank you so much for the helps! I made a stupid mistake in option setting.

The initial value (x0) which I used was not large
InitialParams = [-0.0078 0.1052 0.4820 0.0472 0.98 0.00001]

After I made changes to option settings and add option 'FunValCheck' to 'on', it returned the warning msg:
User function 'Objf' returned a complex value when evaluated;
 FMINCON cannot continue.

Do this problem cause by my objective function, or constraints, or both? Any help would be really appreciated!

Thanks
Yan
 


"Steve" <steve.grikschat@mathworks.com> wrote in message <hdsjr6$uk$1@fred.mathworks.com>...
> Hi Yan,
>
> I have a few points here (inserted below):
> "yan zhong" <yanp.zhong@gmail.com> wrote in message <hdsgck$o0f$1@fred.mathworks.com>...
> > Hi Alan,
> > Thank you for the help, really appreciated! I tried again with reduced parameter numbers (6 parameters in total) and set options as the followings
> > options = optimset('LargeScale' , 'on');
> > options = optimset('Algorithm','interior-point');
> > options = optimset('Display' , 'iter');
> > options = optimset('Diagnostics' , 'on');
> > options = optimset('GradObj' , 'on');
> > options = optimset('Hessian' , 'on');
> > options = optimset('MaxFunEvals' , 1e+15);
> > options = optimset('TolFun' , 1e-6);
> > options = optimset('MaxIter' , 1e+15);
> ^
> |
> Here's your problem. When you call OPTIMSET like this, it returns a new structure. The end result of your code is an options structure with only "MaxIter" set. What you want to do is pass the struct "options" to OPTIMSET when changing or setting another option:
>
> options = optimset('LargeScale' , 'on');
> options = optimset(options,'Algorithm','interior-point');
> options = optimset(options,'Display','iter');
> ...
>
> > The Initial value for the parameters which I used are estimated by using fminsearch. The values are quite reasonable. however, when I change to fmincon, the Warning msg appears:
> > Warning: Trust-region-reflective method does not currently solve this type of problem,
> > using active-set (line search) instead.
> > > In fmincon at 437
> > Maximum number of function evaluations exceeded;
> > increase OPTIONS.MaxFunEvals.
> > x =
> > 1.0e+010 *
> > 0.0019 0.0000 0.0000 1.0934 0 -0.0000
> >
> > f =
> > NaN
> >
> > EXITFLAG =
> > 0
> >
> > OUTPUT =
> > iterations: 99
> > funcCount: 604
> > lssteplength: 2
> > stepsize: NaN
> > algorithm: 'medium-scale: SQP, Quasi-Newton, line-search'
> > firstorderopt: Inf
> > constrviolation: 8.9523e-018
> > message: [1x79 char]
> >
>
> Yikes! Are the initial values (x0) on the order of 1e10? That is awfully large for any algorithm to handle? Does your objective, constraint, or gradient/Jacobian produce large values? Are those quantities defined everywhere? Can they evaluate to Infs or NaNs? (Note: you can check this setting the option 'FunValCheck' to 'on').
>
> These are things to check, because they will likely cause the algorithm to break down. You may have better luck with the interior point algorithm due to some internal scaling and, if you have MATLAB R2009b, increased robustness to Inf and NaN values from objective and constraint functions.

"yan zhong" <yanp.zhong@gmail.com> wrote in message <hdsnjn$kq3$1@fred.mathworks.com>...
> Hi Steve,
> Thank you so much for the helps! I made a stupid mistake in option setting.
>
> The initial value (x0) which I used was not large
> InitialParams = [-0.0078 0.1052 0.4820 0.0472 0.98 0.00001]
>
> After I made changes to option settings and add option 'FunValCheck' to 'on', it returned the warning msg:
> User function 'Objf' returned a complex value when evaluated;
> FMINCON cannot continue.
>
> Do this problem cause by my objective function, or constraints, or both? Any help would be really appreciated!
>
> Thanks
> Yan

It appears to come from your objective "Objf" or gradient. You probably have a sqrt() in there. fmincon cannot solve complex valued problems.

Hi Steve
I found the problem. My objective "objf" has log(). Thank you so much for this!
I fixed it and re-run the code with 'Algorithm','interior-point' and "'LargeScale' , 'on', it returned the warning msg
%
 End diagnostic information

                                         First-order Norm of
 Iter F-count f(x) Feasibility optimality step
    0 1 5.160639e+008 9.328e-001 3.753e+005
Optimization terminated: no feasible point found and relative change in x is less than options.TolX.

Is "no feasible point found" caused by my objective function? Thanks!

Yan

"Steve" <steve.grikschat@mathworks.com> wrote in message <hducrk$l4n$1@fred.mathworks.com>...
> "yan zhong" <yanp.zhong@gmail.com> wrote in message <hdsnjn$kq3$1@fred.mathworks.com>...
> > Hi Steve,
> > Thank you so much for the helps! I made a stupid mistake in option setting.
> >
> > The initial value (x0) which I used was not large
> > InitialParams = [-0.0078 0.1052 0.4820 0.0472 0.98 0.00001]
> >
> > After I made changes to option settings and add option 'FunValCheck' to 'on', it returned the warning msg:
> > User function 'Objf' returned a complex value when evaluated;
> > FMINCON cannot continue.
> >
> > Do this problem cause by my objective function, or constraints, or both? Any help would be really appreciated!
> >
> > Thanks
> > Yan
>
> It appears to come from your objective "Objf" or gradient. You probably have a sqrt() in there. fmincon cannot solve complex valued problems.

"No feasible point" means fmincon could not find a point where all your
constraints are satisfied. It has nothing to do with your objective
function.

Try to find a feasible point yourself, and use it as your starting
point. Or examine your constraint functions--maybe you made a mistake in
the formulation, or included too many constraints.

Alan Weiss
MATLAB mathematical toolbox documentation

yan zhong wrote:
> Hi Steve
> I found the problem. My objective "objf" has log(). Thank you so much for this!
> I fixed it and re-run the code with 'Algorithm','interior-point' and "'LargeScale' , 'on', it returned the warning msg
> %
> End diagnostic information
>
> First-order Norm of
> Iter F-count f(x) Feasibility optimality step
> 0 1 5.160639e+008 9.328e-001 3.753e+005
> Optimization terminated: no feasible point found and relative change in x is less than options.TolX.
>
> Is "no feasible point found" caused by my objective function? Thanks!
>
> Yan
>
> "Steve" <steve.grikschat@mathworks.com> wrote in message <hducrk$l4n$1@fred.mathworks.com>...
>> "yan zhong" <yanp.zhong@gmail.com> wrote in message <hdsnjn$kq3$1@fred.mathworks.com>...
>>> Hi Steve,
>>> Thank you so much for the helps! I made a stupid mistake in option setting.
>>>
>>> The initial value (x0) which I used was not large
>>> InitialParams = [-0.0078 0.1052 0.4820 0.0472 0.98 0.00001]
>>>
>>> After I made changes to option settings and add option 'FunValCheck' to 'on', it returned the warning msg:
>>> User function 'Objf' returned a complex value when evaluated;
>>> FMINCON cannot continue.
>>>
>>> Do this problem cause by my objective function, or constraints, or both? Any help would be really appreciated!
>>>
>>> Thanks
>>> Yan
>> It appears to come from your objective "Objf" or gradient. You probably have a sqrt() in there. fmincon cannot solve complex valued problems.