problem with fminunc: roots containing NaN or Inf
in [Matlab]
|
From: Matt J on 18 Jan 2010 10:00 "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hj1sil$cva$1(a)fred.mathworks.com>... > > But then you end up using fmincon() which doesn't ensure that you stay away from the illegal values either, if any of the required constraints are non-linear. The different algorithms used by fmincon either do not support non-linear constraints or don't ensure that they are satisifed at each iteration... > > But NOT using a constrained optimizer is equivalent to > putting your head in the sand and pretending it never > happens! Well, as an alternative, couldn't you use an unconstrainted minimizer, but code the objective function so that it returns Inf for illegal input arguments? Would fminunc(), and even also fmincon(), be smart enough to backtrack once it hits an objective function value of Inf and refine the search from the last legal point? I've posted this question before, but never gotten an answer.
From: John D'Errico on 18 Jan 2010 10:52 "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hj1t24$eet$1(a)fred.mathworks.com>... > "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hj1sil$cva$1(a)fred.mathworks.com>... > > > > But then you end up using fmincon() which doesn't ensure that you stay away from the illegal values either, if any of the required constraints are non-linear. The different algorithms used by fmincon either do not support non-linear constraints or don't ensure that they are satisifed at each iteration... > > > > But NOT using a constrained optimizer is equivalent to > > putting your head in the sand and pretending it never > > happens! > > Well, as an alternative, couldn't you use an unconstrainted minimizer, but code the objective function so that it returns Inf for illegal input arguments? Would fminunc(), and even also fmincon(), be smart enough to backtrack once it hits an objective function value of Inf and refine the search from the last legal point? > I've posted this question before, but never gotten an answer. No. It will not be that smart, because it is not written to expect constraints, or garbage for the result of its objective function. It cannot do what it is not coded to do. I will point out that the proper way to deal with these problems is often to use a transformation. For example, suppose that your objective function uses the parameter log(p), yet it is set to optimize over the value p. p has no constraints, so when the optimizer tries to go negative, it blows up and you get crapola for a result. Instead, I'll suggest that you should be optimizing the parameter q = log(p), so that p = exp(q). q has no constraints on the real line, and p will always be positive. In fact, you can now use an unconstrained optimizer, within limits. You may still see underflows or overflows if you must compute exp(q) internally. So it still might make sense to use a bound constrained optimizer, even on the transformed problem. This class of "natural" transformations is often directly indicated by your objective function. John
From: Matt J on 18 Jan 2010 11:40 "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hj2034$7m0$1(a)fred.mathworks.com>... > "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hj1t24$eet$1(a)fred.mathworks.com>... > > "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hj1sil$cva$1(a)fred.mathworks.com>... > > > > > > But then you end up using fmincon() which doesn't ensure that you stay away from the illegal values either, if any of the required constraints are non-linear. The different algorithms used by fmincon either do not support non-linear constraints or don't ensure that they are satisifed at each iteration... > > > > > > But NOT using a constrained optimizer is equivalent to > > > putting your head in the sand and pretending it never > > > happens! > > > > Well, as an alternative, couldn't you use an unconstrainted minimizer, but code the objective function so that it returns Inf for illegal input arguments? Would fminunc(), and even also fmincon(), be smart enough to backtrack once it hits an objective function value of Inf and refine the search from the last legal point? > > I've posted this question before, but never gotten an answer. > > No. It will not be that smart, because it is not > written to expect constraints, or garbage for the > result of its objective function. It cannot do what > it is not coded to do. ================ Well, unfortunately, I cannot test this, because I don't own the Optimization Toolbox, nor do I command a budget to buy it. However, it seems strange to me that Inf would be processed as a garbage value. All of these algorithms used by fminunc and fmincon require some sort of sufficient decrease test, which means before a new iteration Xnew is processed at all, there has to be a line in the code which evaluates doUpdate = f(Xold)>f(Xnew)+c which should process fine even if f(Xnew)=Inf, and when this is the case, and doUpdate=false, it obviously wouldn't proceed to try to process Xnew...
From: Alan Weiss on 18 Jan 2010 13:14 Matt J wrote: > "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message > <hj1sil$cva$1(a)fred.mathworks.com>... > >> > But then you end up using fmincon() which doesn't ensure that you >> stay away from the illegal values either, if any of the required >> constraints are non-linear. The different algorithms used by fmincon >> either do not support non-linear constraints or don't ensure that they >> are satisifed at each iteration... >> >> But NOT using a constrained optimizer is equivalent to >> putting your head in the sand and pretending it never >> happens! > > Well, as an alternative, couldn't you use an unconstrainted minimizer, > but code the objective function so that it returns Inf for illegal input > arguments? Would fminunc(), and even also fmincon(), be smart enough to > backtrack once it hits an objective function value of Inf and refine the > search from the last legal point? > I've posted this question before, but never gotten an answer. According to this R2009b release note: http://www.mathworks.com/access/helpdesk/help/toolbox/optim/rn/br3lf3p-1.html "The fmincon interior-point algorithm attempts to continue when a user-supplied objective or constraint function returns Inf, NaN, or a complex result." Unfortunately, the active-set algorithm does not currently share this robustness. Furthermore, fminunc should never encounter any such problem, so it seems to me that there is no point making fminunc able to recover from this sort of error. Alan Weiss MATLAB mathematical toolbox documentation
From: Matt J on 18 Jan 2010 13:36
Alan Weiss <aweiss(a)mathworks.com> wrote in message <hj28dq$55r$1(a)fred.mathworks.com>... > > Unfortunately, the active-set algorithm does not currently share this > robustness. Furthermore, fminunc should never encounter any such > problem, so it seems to me that there is no point making fminunc able to > recover from this sort of error. I'm not sure why that would be the case, Alan. There are lots of cases where an objective has an open domain, but one which is not necessarily all of R^n. Unconstrained algorithms are perfectly applicable to these as long as you have a way of ensuring feasibility at each iteration. Allowing fminunc() to recognize f(x)=Inf as an indicator that it has stepped out of bounds would be one of doing so. |