optimize

optimize (non)linear (in)equality constrained functions with FMINSEARCH

Description

OPTIMIZE is an improvement upon the functions FMINSEARCHBND and FMINSEARCHCON written by John d'Errico (also available on the file exchange). It solves the optimization problem

min f(x)

s.t.

lb <= x <= ub
A * x < b
Aeq * x = beq
c(x) <= 0
ceq(x) = 0

using a coordinate transformation for the bound constraints, and penalty functions for the other constraints. The penalty functions used are pseudo-adaptive: normally, an exponential penalty is used. However, if the amount of constraint violation is severe, this could lead to numerical overflow. To prevent this, the penalty function is converted to a linear function in case it is too large for the exponential constraint.

The main differences between OPTIMIZE and FMINSEARCHCON are

 - (non)linear equality constraints can now be used
 - strictness is more controllable

While FMINSEARCHCON does not permit ANY function evaluation outside the feasible domain, OPTIMIZE can be either allowed (default) or disallowed ('strict' or 'superstrict' options) to do so.

Its behavior is similar to that of FMINCON (except for the really fancy stuff), which makes it useful for those who do not have the optimization toolbox. Also, it is particularly useful in case your function is hard or impossible to differentiate. In such cases, FMINCON is forced to compute the derivatives numerically, which usually takes > 60% of the computation time if you have a sizeable problem. Since FMINSEARCH is the engine for OPTIMIZE, no derivatives are required, which might make it more efficient than using FMINCON.

Some basic examples are included in a published M-file. I recycled most of the examples (and help text) from FMINSEARCHCON -- see its documentation for more underlying theory.

UPDATES:
--------------------------
    You may now also omit the argument [x0], which (when [lb] and [ub] are given) will try to optimize the problem *globally*; simply a few randomly generated starting points inside [lb,ub] will be used to optimize the problem, so that the minimum returned is more likely to be the global minimum. Note however that the number of required function evaluations is considerable. This method should only be used for "cheap" objective functions. See my other release (GODLIKE) for a more robust way to optimize problems globally.

    Also, an additional argument [algorithm] may be provided. When you set it to 'NelderMead', an internal version of the Nelder-Mead simplex method will be used, in stead of the one implemented in FMINSEARCH. The internal one is usually less accurate, but slightly more robust and internally more efficient. This is the recommended method for problems of larger dimensionality.

Usage:
--------------------------
sol = OPTIMIZE(func, x0)
sol = OPTIMIZE(func, x0, lb, ub)
sol = OPTIMIZE(func, x0, lb, ub, A, b)
sol = OPTIMIZE(func, x0, lb, ub, A, b, Aeq, beq)
sol = OPTIMIZE(func, x0, lb, ub, A, b, Aeq, beq, nonlcon)
sol = OPTIMIZE(func, x0, lb, ub, A, b, Aeq, beq, nonlcon, strictness)
 sol = OPTIMIZE(func, x0, lb, ub, A, b, Aeq, beq, nonlcon, strictness, options)
 sol = OPTIMIZE(func, x0, lb, ub, A, b, Aeq, beq, nonlcon, strictness, options, algorithm)

[sol, fval] = OPTIMIZE(func, ...)
[sol, fval, exitflag] = OPTIMIZE(func, ...)
[sol, fval, exitflag, output] = OPTIMIZE(func, ...)

Acknowledgements

Fminsearchbnd, Fminsearchcon inspired this file.

This file inspired Core: Conceptual Optimization Of Rotorcraft Environment.

• MATLAB release: MATLAB 7.7 (R2008b)

[ZAFAR]

Dear Oldenhuis,
Actually my problem (let it be 3 variable problem) has one linear equality constraint e.g. Aeq =[1 1 1], beq = 200 and also there is lower and upper bound for each variable e.g. lb = [30 40 50] and ub = [80 100 85]. Let x0 = [60 70 80]. Let the function is fn. There is no iequality constraint
I write the optimize statement as follows

sol=optimize(@fn,x0,[],[],Aeq,beq,lb,ub)

But it did not work and the message comes to be

Error using optimize/check_input (line 466)
Given linear constraint vector [b] has incompatible
size with given [x0].

Error in optimize (line 347)
check_input;

Kindly advise.

[ZAFAR]

@Oldenhuis,
What to do till then. What should be the order of input arguments. Without this facility, this utility cannot be used for constrained optimization. Kindly give your advice.

[Rody Oldenhuis]

@ZAFAR:

You are right -- In one of the updates, I changed the order of the input arguments so that they correspond with fmincon(). However, I did NOT update the documentation to reflect these changes.

I'm unfortunately very short on time now, but I will do my best to update optimize() soon.

[ZAFAR]

Dear Rody Oldenhuis,

When i try to optimize the following fn (with inequality constraints)

rosen = @(x) (1-x(1)).^2 + 105*(x(2)-x(1).^2).^2;

optimize(rosen,[0 0],[],[],[1 1], 1)

I get the error message

Error using optimize/check_input (line 466)
Given linear constraint vector [b] has incompatible
size with given [x0].

Error in optimize (line 347)
check_input;

Why is this so, although i used the example given with optimize.m
Similar is the problem with equality constraints. Kindly spare a little of your precious time to reply

[ZAFAR]

Please read the first line of my mrssage as

"When i try to optimize the following fn (with inequality constraints)"

[Guillaume]

Thanks so much for this function Rody!
Although, the syntax changes a little bit with respect to the fmincon.m utility, the optimization process runs equally as well (and maybe even faster!).

[Qu]

 

[pietro]

It works good, but sometimes it stucks at a strange objective function value (fval=7.22597e+086), but the function value is instead different, around 1000. I did several tries, but it doesn't change at all. Any suggestions is appreciated

[Shmuel]

nice, but change line 12 in the testoptimize
to :
clc, rosen = @(x) (1-x(1))^2 + 105*(x(2)-x(1)^2)^2 -6000*sinc(x(2)^2+x(1)^2); % adding local minima.
and you get a local minimume solver as fminsearch is.

[Marco G]

Very Good it does work!! I was using the routine to solve a constrained problem (my constraints are basically non negativity of the x´s and that they sum up to one: Sum_i x_i =1) with some additional parameters in the objective function. I noticed that the contraint of the sum is not perfectly matched (i.e sum is 0.9 or so) even though I used ´strict´ option. Is there a way to force the constraint to be respected and maybe lose something somewhere else( e.g. less optimal minimization)? thx for help

[Alexei]

 

[Ryan Webb]

I use optimize for many problems, however I have found a bug when optimize is used with the distributed computing toolbox. When it is being run on a worker, it gives an "Undefined Function Handle" error.

Unfortuntely I am unable to trace exactly what line this error comes from, but I can say that it is after line 398. The likely culprit is when optimize calls fminsearch and funfncP is out of scope somehow...

[Sky Sartorius]

 

[Andre Guy Tranquille]

 

[Nagendra]

please specify the algorithm journal paper which is used to write this algorithm

[Ben]

Code seems to work great. Thanks.
Is there any way to set the increment size for the x0 range? Allow me to clarify: lets say a have a lower bound of -2 and an upper bound of 2. I want the guesses to increment by 0.1. So effectively, I want to check the values [-2:0.1:2]. Where in your code can I set the 0.1 increment? Also, can that increment be different for each variable in x0?

[Rody Oldenhuis]

Thierry: it's basically already included (the included HTML is a published M-file, so all commands can basically be copy-pasted). But once I get home tonight, I'll included it nonetheless for completeness. As for the demo, that would indeed be great! I'll see to it. Thanks for the suggestion!

As for the dependencies: To my knowledge, FMINSEARCH is indeed included in MATLAB's standard library (in my version it's located in R2008b\toolbox\matlab\funfun\fminsearch.m), but of course FMINCON is only included in the optimization toolbox (located in R2008b\toolbox\shared\optimlib\fmincon.m), so OPTIMIZE is for everyone in need of a "basic" FMINCON ^_^

[Thierry Dalon]

Hi!
looks GREAT!
could you add to the package the source for the testoptimize.m, please ?
maybe add it as well as a demo alike TMW optimdemos.

[John D'Errico]

Well done.