[NLopt-discuss] Regular hanging of NLopt

[Rob Clark]

I am using NLopt from C with the NLOPT_LN_COBYLA algorithm. Often this
works very well but sometimes the program hangs altogether with no calls
being made to the objective function or constraints functions. It seems
I can call nlopt_set_initial_step1() with certain values and it'll fix
the problem for a given set of inputs.



It's possible these problems would go away with the choice of another
algorithm but I wanted to query the problem as it seems to be an
infinite loop within the algorithm rather than a simple failure to
converge.



I have pasted the source-code below, it's a hacked version of the basic
example from the wiki. It is of-course very likely that I am using the
optimiser incorrectly or specifying the problem poorly.



I am working on Windows XP with NLopt 2.2 and compiling my code with
4.5.0 (MinGW) with the following command:

gcc -I X:\tools\nlopt-2.2.1 -L X:\tools\nlopt-2.2.1 -std=c99 -g
use_nlopt.c -o use_nlopt -lm -lnlopt-0



Many thanks for any feedback, even if it's just "works for me" ...

Rob



#include <math.h>

#include <nlopt.h>

#include <stdio.h>

#include <stdlib.h>



typedef struct {

int n, m;

double *forecast, *position;

double lambda;

} obj_data;



double myfunc(unsigned n, const double *x, double *grad, void *data) {

obj_data *k = (obj_data *) data;



double exp = 0, turnover = 0;

for(unsigned i = 0 ; i < n ; ++i) {

exp += x[i] * k->forecast[i];

turnover += fabs(x[i] - k->position[i]);

}



turnover *= k->lambda;



++k->n;

if(k->n % 1000 == 0)

printf(" %d\n", k->n);



//printf("Expected-return: %g, Turnover penalty: %g\n", exp,
turnover);



return exp - turnover;

}



double face_value(unsigned n, const double *x, double *grad, void *data)
{

double face = 0;

for(unsigned i = 0 ; i < n ; ++i)

face += fabs(x[i]);

return face - (data == NULL ? 0 : *((double *) data));

}



double net_delta(unsigned n, const double *x, double *grad, void *data)
{

double net = 0;

for(unsigned i = 0 ; i < n ; ++i)

net += x[i];



double res = fabs(net);

return res;

}



int main() {

int n = 20;

double lb[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10000, -10000,
-10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000 },

ub[] = { 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,
10000, 10000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

f[] = { 0.00619, 0.01767, 0.00470, 0.02252, 0.00330, 0.00468,
0.01701, 0.00925, 0.01865, 0.00991, -0.00092, -0.00394, -0.00980,
-0.00886, -0.00129, -0.00979, -0.02236, -0.00212, -0.00393, -0.00882 },

x[] = { 9806, 1905, 145, 4142, 6611, 5474, 5608, 87, 1443, 4252,
-7441, -4996, -3037, -6291, -5614, -4044, -6640, -4933, -8412, -7507 };



double *position = malloc(sizeof(double) * n);

for(int i = 0 ; i < n ; ++i)

position[i] = 0;



nlopt_opt opt = nlopt_create(NLOPT_LN_COBYLA, n);

nlopt_set_lower_bounds(opt, lb);

nlopt_set_upper_bounds(opt, ub);



obj_data data;

data.n = data.m = 0;

data.forecast = f;

data.position = position;

data.lambda = .00055;



nlopt_set_max_objective(opt, myfunc, &data);



double max_face_value = 100000;



nlopt_add_inequality_constraint(opt, face_value, &max_face_value,
1e-8);

nlopt_add_inequality_constraint(opt, net_delta, NULL, 1e-8);



nlopt_set_xtol_rel(opt, 1e-1);



// If we set this then the optimiser returns

//nlopt_set_initial_step1(opt, 100);



double minf; /* the minimum objective value, upon return */

if (nlopt_optimize(opt, x, &minf) < 0) {

printf("nlopt failed!\n");

}

else {

printf("found maximum at f = %g after %d evaluations\n", minf,
data.n);

for(int i = 0 ; i < n ; ++i)

printf(" %g\t%g\n", f[i], fabs(x[i]) < 1 ? 0 : x[i]);

printf("face-value: %g, net-delta: %g\n", face_value(n, x, NULL,
NULL), net_delta(n, x, NULL, NULL));

}

nlopt_destroy(opt);

}


Liquid Capital Securities Limited ("LCS") (Registered Number 04118899)
and Liquid Capital Trading LLP (Registered Number OC313325) are authorised
and regulated by the Financial Services Authority in the United Kingdom.
LCS (France) and LCS (Germany) are branches of LCS and are subject to the
regulation of the AMF (France) and the Bafin (Germany).

LCS is also registered with the National Futures Association ("NFA") as an
Exempt Foreign Broker. Liquid Capital Australia Pty Ltd is registered by the
Australian Securities and Investment Commission. Liquid Capital Management
LLP is a registered limited liability partnership.

Liquid Capital Markets, LLC ("LCM LLC") is a registered broker dealer whose
Designated Examining Authority is the Chicago Board Options Exchange ("CBOE").
LCM LLC is also a member of the CBOE and the Chicago Mercantile Exchange. Liquid
Capital Securities, LLC (“LCS LLC”) is a FINRA registered broker dealer and an
NFA registered introducing broker whose main office is located at 71 South Wacker
Drive, Suite 2100, Chicago, IL 60606. For more information about LCS LLC, please
contact [phone]. In accordance with SEC Rule 17a-4 and NASD Rule 3010,
e-mails sent to and from this address may be recorded and are subject to archival,
monitoring, review and retrieval by the LCS LLC Compliance Department.

Please click this <a href=http://www.liquidcapital.com/group/index.php?
location=/web/General/Disclaimer>link</a> for terms relating to email correspondence.

[Steven G. Johnson]

Hi Rob,

I tried your code on my machine (Debian GNU/Linux, x86-64), and it
seems to work for me (unmodified, with nlopt_set_initial_step1
commented out). The output is:

1000
found maximum at f = 1398.9 after 1759 evaluations
0.00619 0
0.01767 10000
0.0047 0
0.02252 10000
0.0033 0
0.00468 0
0.01701 10000
0.00925 0
0.01865 10000
0.00991 9999.92
-0.00092 0
-0.00394 0
-0.0098 -10000
-0.00886 -10000
-0.00129 0
-0.00979 -10000
-0.02236 -10000
-0.00212 0
-0.00393 0
-0.00882 -10000
face-value: 100000, net-delta: 2.18279e-11


Note, by the way, that because your objective and constraints involve
absolute values, they are not differentiable. However, it is always
possible to transform absolute values into additional nonlinear
constraints that are differentiable.

For example, if you have a constraint
|x| + |y| <= 3
you can transform this into:
x + y <= 3
x - y <= 3
-x + y <= 3
-x - y <= 3
or alternatively into:
t1 >= x
t1 >= -x
t2 >= y
t2 >= -y
t1 + t2 <= 3
where t1 and t2 are new dummy variables.

As another example, if you are minimizing the objective
x - |y|
you can instead minimize
x - t
where t is a new dummy variable and you introduce the constraints
t <= y
t <= -y

In fact, looking at your problem, it seems to me that if you do these
transformations you actually get an LP (linear programming problem),
which is convex and has all sorts of specialized algorithms available
for it.

Even if you don't take advantage of the fact that you have an LP (e.g.
because you want to add nonlinear terms later), you should strongly
consider reformulating your problem in terms of a differentiable
objective and differentiable constraints. COBLYA internally
constructs an approximate derivative, so it will usually converge much
more quickly if your problem is differentiable. Also, if it is
differentiable, you can compute an analytical derivative and use
algorithms like MMA and SLSQP that exploit this.

See the section on "Equivalent formulations" in the NLopt introduction.

Steven