Thread Subject: Problems using fmincon

I want to perform parametrized function optimization with constraints using fmincon. I wrote appropriate nested function, that is being optimized, defined constraints and so on. However I run into a problem: optimization stops in the second iteration (Optimization terminated: first-order optimality measure less than options.TolFun and maximum constraint violation is less than options.TolCon.) and no further optimization is performed. I managed to find the reason of this problem, but I don't know how to solve it.

The problem is as follows. As a starting point for optimization (x0) I select 1.0. My function is evaluated in this point by fmincon. Then, the second point in which fmincon evaluates the function is 1.000000014901161. However, my function operates on discrete values (images, to be exact) and such a small change in optimized variable's value doesn't lead to any change in optimized function's value, since - at some point - double values are rounded to integers. I made a test: if I remove rounding and let my function operate on doubles instead of integers, then optimization works as it should. How can I solve this problem (removing rounding is not an option in the final version of my algorithm, I've done it only for debugging purposes).

Hi Jan,

The second evaluation I believe is determined by fmincon in order to calculate the approximated derivatives through the finite difference. Therefore, to avoid the small deviation of x, either you have to provide your own derivatives or you need to rescale your problem so that it can use most of the double range. For example, you can scale your solution range within 0 - 1.

HTH
Yi

"Jan " <fremenzone@poczta.onet.pl> wrote in message <ho25kj$66m$1@fred.mathworks.com>...
> I want to perform parametrized function optimization with constraints using fmincon. I wrote appropriate nested function, that is being optimized, defined constraints and so on. However I run into a problem: optimization stops in the second iteration (Optimization terminated: first-order optimality measure less than options.TolFun and maximum constraint violation is less than options.TolCon.) and no further optimization is performed. I managed to find the reason of this problem, but I don't know how to solve it.
>
> The problem is as follows. As a starting point for optimization (x0) I select 1.0. My function is evaluated in this point by fmincon. Then, the second point in which fmincon evaluates the function is 1.000000014901161. However, my function operates on discrete values (images, to be exact) and such a small change in optimized variable's value doesn't lead to any change in optimized function's value, since - at some point - double values are rounded to integers. I made a test: if I remove rounding and let my function operate on doubles instead of integers, then optimization works as it should. How can I solve this problem (removing rounding is not an option in the final version of my algorithm, I've done it only for debugging purposes).

"Jan " <fremenzone@poczta.onet.pl> wrote in message <ho25kj$66m$1@fred.mathworks.com>...
>How can I solve this problem (removing rounding is not an option in the final version of my algorithm, I've done it only for debugging purposes).

Then FMINCON is a wrong tool for your problem. FMINCON assumes a differentiable cost function. If you have rounding, then you should use other minimizer.

Bruno

Which minimizer would be the best for such task?

Let me clarify, that minimized function returns doubles, not integers, however this doesn't change much since these doubles are calculated based on integers. I'm afraid that scaling of my problem is not possible.

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ho27cq$1b9$1@fred.mathworks.com>...
> "Jan " <fremenzone@poczta.onet.pl> wrote in message <ho25kj$66m$1@fred.mathworks.com>...
> >How can I solve this problem (removing rounding is not an option in the final version of my algorithm, I've done it only for debugging purposes).
>
> Then FMINCON is a wrong tool for your problem. FMINCON assumes a differentiable cost function. If you have rounding, then you should use other minimizer.
>
> Bruno

"Jan " <fremenzone@poczta.onet.pl> wrote in message <ho2brc$510$1@fred.mathworks.com>...
> Which minimizer would be the best for such task?

Probably integer programming, but they are out of my fields of expertise so hope someone who knows better those techniques can guide you.

Bruno

You always can scale your problem. For example, your currentl problem requires the solution x to be discrete between 1 to 1000, then you can scale it as y = x / 1000 so that the solution range for y is between 0 - 1. When you calculate cost or constraints, you can convert y back to x as x = round(1000 * y). Following the same principle, you can even scale your problem to a range 0 - a << 1 so that you can get more resolution from fmincon. Although fmincon is for continous variables, but it should still be feasible to solve discrete problem. All you have to do is integer relaxiation. Unfortunately, as I know, matlab optimization toolbox does not have any solver for integer problems.

HTH
Yi

"Jan " <fremenzone@poczta.onet.pl> wrote in message <ho2brc$510$1@fred.mathworks.com>...
> Which minimizer would be the best for such task?
>
> Let me clarify, that minimized function returns doubles, not integers, however this doesn't change much since these doubles are calculated based on integers. I'm afraid that scaling of my problem is not possible.
>
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ho27cq$1b9$1@fred.mathworks.com>...
> > "Jan " <fremenzone@poczta.onet.pl> wrote in message <ho25kj$66m$1@fred.mathworks.com>...
> > >How can I solve this problem (removing rounding is not an option in the final version of my algorithm, I've done it only for debugging purposes).
> >
> > Then FMINCON is a wrong tool for your problem. FMINCON assumes a differentiable cost function. If you have rounding, then you should use other minimizer.
> >
> > Bruno

"Jan " <fremenzone@poczta.onet.pl> wrote in message <ho25kj$66m$1@fred.mathworks.com>...
 
How can I solve this problem (removing rounding is not an option in the final version of my algorithm, I've done it only for debugging purposes).
=================

It might be worth hearing why you can't remove rounding. You might have a false impression that this is insurmountable.

Other than that, you could try fminsearch() which doesn't require derivatives.

The issue with using fmincon here is the rounding aspect of the
objective function. If you were to plot the objective function against
the optimization variable, you would probably see a stair-step looking
response, instead of a smooth (i.e., differentiable) curve. You might
have to zoom in to see this. fmincon is a gradient-based algorithm,
which requires that objective and constraint functions are
differentiable with respect to the optimization variable(s). Any
function that involves rounding is not differentiable, so fmincon is not
appropriate for solving this problem.

When you start fmincon, it takes a small step to calculate a
finite-difference approximation to the gradient. With default algorithm
settings, these small steps are very small (as you have observed), and
it looks like the step is taken in a small flat region of your objective
function; fmincon sees this as a zero gradient, and thinks that you are
at a stationary point (potential local optimum).

I would suggest trying patternsearch from the Global Optimization
Toolbox (previously the GADS toolbox):

http://www.mathworks.com/products/global-optimization/

It can handle non-smooth functions, and typically converges faster than
the genetic algorithm (ga), a heuristic optimization algorithm in the
Global Optimization Toolbox that also handles non-smooth problems.

I can think of two other alternatives:

1) Adjust fmincon parameters to handle this problem using optimset. You
will need to increase the bounds on the finite difference step size, as
well as loosen the tolerances on the optimization variable and
objective/constraint functions. This will help the algorithm 'skip over'
the non-smoothness in the response, and you may be able to get fmincon
to converge very quickly. The tradeoff is your solution will not be as
precise. You may want to compare results from this approach with
patternsearch to see if the precision is acceptable.

2) Use a successive surrogate modeling approach. Sample the objective
and constraint functions (using lhsdesign, etc.), and fit a smooth
surrogate function to the data (such as a polynomial surface or neural
network model). Find the minimum of the surrogate model using fmincon.
Resample the objective and constraint functions near the approximate
solution, and fit a new model. Repeat this iteratively, shrinking the
sampling region, until you have sufficient precision. This is a more
advanced approach, but if you are developing an algorithm that will be
used repeatedly, this might be a worthwhile investment.

I hope this helps,

-James

Jan wrote:
> Which minimizer would be the best for such task?
>
> Let me clarify, that minimized function returns doubles, not integers,
> however this doesn't change much since these doubles are calculated
> based on integers. I'm afraid that scaling of my problem is not possible.
>
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> <ho27cq$1b9$1@fred.mathworks.com>...
>> "Jan " <fremenzone@poczta.onet.pl> wrote in message
>> <ho25kj$66m$1@fred.mathworks.com>...
>> >How can I solve this problem (removing rounding is not an option in
>> the final version of my algorithm, I've done it only for debugging
>> purposes).
>>
>> Then FMINCON is a wrong tool for your problem. FMINCON assumes a
>> differentiable cost function. If you have rounding, then you should
>> use other minimizer.
>>
>> Bruno

fminsearch applies only to unconstrained problems; Jan mentioned that
the optimization problem has constraints. I suggest patternsearch from
the Global Optimization Toolbox. See my more detailed remarks in
response to Jan's second post.

-James

Matt J wrote:
> "Jan " <fremenzone@poczta.onet.pl> wrote in message
> <ho25kj$66m$1@fred.mathworks.com>...
>
> How can I solve this problem (removing rounding is not an option in the
> final version of my algorithm, I've done it only for debugging purposes).
> =================
>
> It might be worth hearing why you can't remove rounding. You might have
> a false impression that this is insurmountable.
>
> Other than that, you could try fminsearch() which doesn't require
> derivatives.

James Allison <james.allison@mathworks.com> wrote in message <ho8533$p5k$2@fred.mathworks.com>...
> fminsearch applies only to unconstrained problems; Jan mentioned that
> the optimization problem has constraints.
==========

Then perhaps this constrained version from the FEX?

http://www.mathworks.com/matlabcentral/fileexchange/13469-fminsearchcon

In any case, I think we need to hear from the OP whether this problem originated by discretizing a differentiable cost function. If so, then it might be possible to pass an analytical derivative to fmincon(), possibly post-discretized in the same way (cf. Yi's suggestion).

Hi,I have my objective function based on the examples given and then gave to the fmincon solver using toolbox..
 this time there is an error it is

Attempted to access a(2); index out of bounds because numel(a)=1.

my objective function is:

function f=new1(a)
f=1-1/1+exp(((exp(9.54+0.134*a(2))*(9.62+exp(-1.017+0.00584*a(4))*(13.32+exp(3.23-0.00117*a(2))*(13.32*exp(3.118-0.00215*a(2))+6))))+(578.55*exp((-0.03353*a(1)*a(1)*a(1)*a(1))-(0.2179*a(1)*a(1)))*(1+(exp(3.23-0.00117*a(2))*(1+exp(3.118-0.00215*a(2)))*(1+exp(-1.017+0.00558*a(4))))))+(exp(3.118-0.00215*a(2))*(1+exp(-1.017+0.00558*a(4))+exp(6.348-0.00332*a(2)))+2.3*exp(3.23-0.00117*a(2)))+(exp(3.118-0.00215*a(2))*(12.06+15.76*exp(-1.017+0.00558*a(4))+9.62*exp(3.23-0.00117*a(2))))+((3.7*exp(-1.017+0.00558*a(4))*((1+exp(3.23-0.00117*a(2)))*(1+exp(3.118-0.00215*a(2))))))+(578.55*exp((-0.03353*a(1)*a(1)*a(1)*a(1))-(0.2179*a(1)*a(1)))*(1+exp(3.118-0.00215*a(2))))+((exp(3.23-0.00117*a(2))*(2.44+578.55*exp((-0.03353*a(1)*a(1)*a(1)*a(1))-(0.2179*a(1)*a(1)))*(1+exp(3.118-0.00215*a(2))*(1+exp(3.23-0.00117*a(2)))))))-(2.44*(exp(3.118-0.00215*a(2))*(1+exp(3.23-0.00117*a(2))))))/((1+exp(3.23-0.00117*a(2
)))*(1+exp(9.54+0.134*a(3)))*(1+exp(-1.017+0.00558*a(4)))*(1+exp(3.118-0.00215*a(2)))));


please can u help in this I must my submit my optimization tomorrow

Joe Ajay
Apparently you called the function "new1" with a single number (a
constant or a scalar variable), not an array of 4 or more numbers like
the function requires. Set a breakpoint and figure out what's going
on. You're never going to get far in MATLAB if you don't learn how to
use the debugger.

P.S. You should start a new thread for questions like this, not add on
to some 9 month old thread on a different topic.

On 04/12/10 11:10 PM, Joe Ajay wrote:

> function f=new1(a)
> f=1-1/1+exp(((exp(9.54+0.134*a(2))*(9.62+exp(-1.017+0.00584*a(4))*(13.32+exp(3.23-0.00117*a(2))*(13.32*exp(3.118-0.00215*a(2))+6))))+(578.55*exp((-0.03353*a(1)*a(1)*a(1)*a(1))-(0.2179*a(1)*a(1)))*(1+(exp(3.23-0.00117*a(2))*(1+exp(3.118-0.00215*a(2)))*(1+exp(-1.017+0.00558*a(4))))))+(exp(3.118-0.00215*a(2))*(1+exp(-1.017+0.00558*a(4))+exp(6.348-0.00332*a(2)))+2.3*exp(3.23-0.00117*a(2)))+(exp(3.118-0.00215*a(2))*(12.06+15.76*exp(-1.017+0.00558*a(4))+9.62*exp(3.23-0.00117*a(2))))+((3.7*exp(-1.017+0.00558*a(4))*((1+exp(3.23-0.00117*a(2)))*(1+exp(3.118-0.00215*a(2))))))+(578.55*exp((-0.03353*a(1)*a(1)*a(1)*a(1))-(0.2179*a(1)*a(1)))*(1+exp(3.118-0.00215*a(2))))+((exp(3.23-0.00117*a(2))*(2.44+578.55*exp((-0.03353*a(1)*a(1)*a(1)*a(1))-(0.2179*a(1)*a(1)))*(1+exp(3.118-0.00215*a(2))*(1+exp(3.23-0.00117*a(2)))))))-(2.44*(exp(3.118-0.00215*a(2))*(1+exp(3.23-0.00117*a(2))))))/((1+exp(3.23-0.00117*a(2
> )))*(1+exp(9.54+0.134*a(3)))*(1+exp(-1.017+0.00558*a(4)))*(1+exp(3.118-0.00215*a(2)))));
>
>
> please can u help in this I must my submit my optimization tomorrow

Why does your function start with 1-1/1 ? Are you missing some brackets?
Should it be

f = 1 - 1/(1 + exp.....) ?