1 /* Copyright (c) 2007-2014 Massachusetts Institute of Technology
3 * Permission is hereby granted, free of charge, to any person obtaining
4 * a copy of this software and associated documentation files (the
5 * "Software"), to deal in the Software without restriction, including
6 * without limitation the rights to use, copy, modify, merge, publish,
7 * distribute, sublicense, and/or sell copies of the Software, and to
8 * permit persons to whom the Software is furnished to do so, subject to
9 * the following conditions:
11 * The above copyright notice and this permission notice shall be
12 * included in all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
17 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
18 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
19 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
20 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
29 #include "nlopt-internal.h"
31 /*************************************************************************/
33 void NLOPT_STDCALL nlopt_destroy(nlopt_opt opt)
37 if (opt->munge_on_destroy) {
38 nlopt_munge munge = opt->munge_on_destroy;
40 for (i = 0; i < opt->m; ++i)
41 munge(opt->fc[i].f_data);
42 for (i = 0; i < opt->p; ++i)
43 munge(opt->h[i].f_data);
45 for (i = 0; i < opt->m; ++i)
47 for (i = 0; i < opt->p; ++i)
49 free(opt->lb); free(opt->ub);
53 nlopt_destroy(opt->local_opt);
60 nlopt_opt NLOPT_STDCALL nlopt_create(nlopt_algorithm algorithm, unsigned n)
64 if (((int) algorithm) < 0 || algorithm >= NLOPT_NUM_ALGORITHMS)
67 opt = (nlopt_opt) malloc(sizeof(struct nlopt_opt_s));
69 opt->algorithm = algorithm;
71 opt->f = NULL; opt->f_data = NULL; opt->pre = NULL;
73 opt->munge_on_destroy = opt->munge_on_copy = NULL;
75 opt->lb = opt->ub = NULL;
76 opt->m = opt->m_alloc = 0;
78 opt->p = opt->p_alloc = 0;
81 opt->stopval = -HUGE_VAL;
82 opt->ftol_rel = opt->ftol_abs = 0;
83 opt->xtol_rel = 0; opt->xtol_abs = NULL;
87 opt->force_stop_child = NULL;
89 opt->local_opt = NULL;
90 opt->stochastic_population = 0;
91 opt->vector_storage = 0;
96 opt->lb = (double *) malloc(sizeof(double) * (n));
97 if (!opt->lb) goto oom;
98 opt->ub = (double *) malloc(sizeof(double) * (n));
99 if (!opt->ub) goto oom;
100 opt->xtol_abs = (double *) malloc(sizeof(double) * (n));
101 if (!opt->xtol_abs) goto oom;
102 nlopt_set_lower_bounds1(opt, -HUGE_VAL);
103 nlopt_set_upper_bounds1(opt, +HUGE_VAL);
104 nlopt_set_xtol_abs1(opt, 0.0);
115 nlopt_opt NLOPT_STDCALL nlopt_copy(const nlopt_opt opt)
117 nlopt_opt nopt = NULL;
121 nopt = (nlopt_opt) malloc(sizeof(struct nlopt_opt_s));
123 nopt->lb = nopt->ub = nopt->xtol_abs = NULL;
124 nopt->fc = nopt->h = NULL;
125 nopt->m_alloc = nopt->p_alloc = 0;
126 nopt->local_opt = NULL;
129 opt->force_stop_child = NULL;
131 munge = nopt->munge_on_copy;
132 if (munge && nopt->f_data)
133 if (!(nopt->f_data = munge(nopt->f_data))) goto oom;
136 nopt->lb = (double *) malloc(sizeof(double) * (opt->n));
137 if (!opt->lb) goto oom;
138 nopt->ub = (double *) malloc(sizeof(double) * (opt->n));
139 if (!opt->ub) goto oom;
140 nopt->xtol_abs = (double *) malloc(sizeof(double) * (opt->n));
141 if (!opt->xtol_abs) goto oom;
143 memcpy(nopt->lb, opt->lb, sizeof(double) * (opt->n));
144 memcpy(nopt->ub, opt->ub, sizeof(double) * (opt->n));
145 memcpy(nopt->xtol_abs, opt->xtol_abs, sizeof(double) * (opt->n));
149 nopt->m_alloc = opt->m;
150 nopt->fc = (nlopt_constraint *) malloc(sizeof(nlopt_constraint)
152 if (!nopt->fc) goto oom;
153 memcpy(nopt->fc, opt->fc, sizeof(nlopt_constraint) * (opt->m));
154 for (i = 0; i < opt->m; ++i) nopt->fc[i].tol = NULL;
156 for (i = 0; i < opt->m; ++i)
157 if (nopt->fc[i].f_data &&
159 = munge(nopt->fc[i].f_data)))
161 for (i = 0; i < opt->m; ++i)
162 if (opt->fc[i].tol) {
163 nopt->fc[i].tol = (double *) malloc(sizeof(double)
165 if (!nopt->fc[i].tol) goto oom;
166 memcpy(nopt->fc[i].tol, opt->fc[i].tol,
167 sizeof(double) * nopt->fc[i].m);
172 nopt->p_alloc = opt->p;
173 nopt->h = (nlopt_constraint *) malloc(sizeof(nlopt_constraint)
175 if (!nopt->h) goto oom;
176 memcpy(nopt->h, opt->h, sizeof(nlopt_constraint) * (opt->p));
177 for (i = 0; i < opt->p; ++i) nopt->h[i].tol = NULL;
179 for (i = 0; i < opt->p; ++i)
180 if (nopt->h[i].f_data &&
182 = munge(nopt->h[i].f_data)))
184 for (i = 0; i < opt->p; ++i)
186 nopt->h[i].tol = (double *) malloc(sizeof(double)
188 if (!nopt->h[i].tol) goto oom;
189 memcpy(nopt->h[i].tol, opt->h[i].tol,
190 sizeof(double) * nopt->h[i].m);
194 if (opt->local_opt) {
195 nopt->local_opt = nlopt_copy(opt->local_opt);
196 if (!nopt->local_opt) goto oom;
200 nopt->dx = (double *) malloc(sizeof(double) * (opt->n));
201 if (!nopt->dx) goto oom;
202 memcpy(nopt->dx, opt->dx, sizeof(double) * (opt->n));
208 nopt->munge_on_destroy = NULL; // better to leak mem than crash
213 /*************************************************************************/
215 nlopt_result NLOPT_STDCALL nlopt_set_precond_min_objective(nlopt_opt opt,
221 if (opt->munge_on_destroy) opt->munge_on_destroy(opt->f_data);
222 opt->f = f; opt->f_data = f_data; opt->pre = pre;
224 if (nlopt_isinf(opt->stopval) && opt->stopval > 0)
225 opt->stopval = -HUGE_VAL; /* switch default from max to min */
226 return NLOPT_SUCCESS;
228 return NLOPT_INVALID_ARGS;
231 nlopt_result NLOPT_STDCALL nlopt_set_min_objective(nlopt_opt opt,
232 nlopt_func f, void *f_data)
234 return nlopt_set_precond_min_objective(opt, f, NULL, f_data);
237 nlopt_result NLOPT_STDCALL nlopt_set_precond_max_objective(nlopt_opt opt,
243 if (opt->munge_on_destroy) opt->munge_on_destroy(opt->f_data);
244 opt->f = f; opt->f_data = f_data; opt->pre = pre;
246 if (nlopt_isinf(opt->stopval) && opt->stopval < 0)
247 opt->stopval = +HUGE_VAL; /* switch default from min to max */
248 return NLOPT_SUCCESS;
250 return NLOPT_INVALID_ARGS;
253 nlopt_result NLOPT_STDCALL nlopt_set_max_objective(nlopt_opt opt,
254 nlopt_func f, void *f_data)
256 return nlopt_set_precond_max_objective(opt, f, NULL, f_data);
259 /*************************************************************************/
262 NLOPT_STDCALL nlopt_set_lower_bounds(nlopt_opt opt, const double *lb)
264 if (opt && (opt->n == 0 || lb)) {
265 memcpy(opt->lb, lb, sizeof(double) * (opt->n));
266 return NLOPT_SUCCESS;
268 return NLOPT_INVALID_ARGS;
272 NLOPT_STDCALL nlopt_set_lower_bounds1(nlopt_opt opt, double lb)
276 for (i = 0; i < opt->n; ++i)
278 return NLOPT_SUCCESS;
280 return NLOPT_INVALID_ARGS;
284 NLOPT_STDCALL nlopt_get_lower_bounds(const nlopt_opt opt, double *lb)
286 if (opt && (opt->n == 0 || lb)) {
287 memcpy(lb, opt->lb, sizeof(double) * (opt->n));
288 return NLOPT_SUCCESS;
290 return NLOPT_INVALID_ARGS;
294 NLOPT_STDCALL nlopt_set_upper_bounds(nlopt_opt opt, const double *ub)
296 if (opt && (opt->n == 0 || ub)) {
297 memcpy(opt->ub, ub, sizeof(double) * (opt->n));
298 return NLOPT_SUCCESS;
300 return NLOPT_INVALID_ARGS;
304 NLOPT_STDCALL nlopt_set_upper_bounds1(nlopt_opt opt, double ub)
308 for (i = 0; i < opt->n; ++i)
310 return NLOPT_SUCCESS;
312 return NLOPT_INVALID_ARGS;
316 NLOPT_STDCALL nlopt_get_upper_bounds(const nlopt_opt opt, double *ub)
318 if (opt && (opt->n == 0 || ub)) {
319 memcpy(ub, opt->ub, sizeof(double) * (opt->n));
320 return NLOPT_SUCCESS;
322 return NLOPT_INVALID_ARGS;
325 /*************************************************************************/
327 #define AUGLAG_ALG(a) ((a) == NLOPT_AUGLAG || \
328 (a) == NLOPT_AUGLAG_EQ || \
329 (a) == NLOPT_LN_AUGLAG || \
330 (a) == NLOPT_LN_AUGLAG_EQ || \
331 (a) == NLOPT_LD_AUGLAG || \
332 (a) == NLOPT_LD_AUGLAG_EQ)
335 NLOPT_STDCALL nlopt_remove_inequality_constraints(nlopt_opt opt)
338 if (!opt) return NLOPT_INVALID_ARGS;
339 if (opt->munge_on_destroy) {
340 nlopt_munge munge = opt->munge_on_destroy;
341 for (i = 0; i < opt->m; ++i)
342 munge(opt->fc[i].f_data);
344 for (i = 0; i < opt->m; ++i)
345 free(opt->fc[i].tol);
348 opt->m = opt->m_alloc = 0;
349 return NLOPT_SUCCESS;
352 static nlopt_result add_constraint(unsigned *m, unsigned *m_alloc,
353 nlopt_constraint **c,
354 unsigned fm, nlopt_func fc, nlopt_mfunc mfc,
362 if ((fc && mfc) || (fc && fm != 1) || (!fc && !mfc))
363 return NLOPT_INVALID_ARGS;
365 for (i = 0; i < fm; ++i) if (tol[i] < 0) return NLOPT_INVALID_ARGS;
367 tolcopy = (double *) malloc(sizeof(double) * fm);
368 if (fm && !tolcopy) return NLOPT_OUT_OF_MEMORY;
370 memcpy(tolcopy, tol, sizeof(double) * fm);
372 for (i = 0; i < fm; ++i) tolcopy[i] = 0;
376 /* allocate by repeated doubling so that
377 we end up with O(log m) mallocs rather than O(m). */
379 *c = (nlopt_constraint *) realloc(*c,
380 sizeof(nlopt_constraint)
385 return NLOPT_OUT_OF_MEMORY;
391 (*c)[*m - 1].pre = pre;
392 (*c)[*m - 1].mf = mfc;
393 (*c)[*m - 1].f_data = fc_data;
394 (*c)[*m - 1].tol = tolcopy;
395 return NLOPT_SUCCESS;
398 static int inequality_ok(nlopt_algorithm algorithm) {
399 /* nonlinear constraints are only supported with some algorithms */
400 return (algorithm == NLOPT_LD_MMA || algorithm == NLOPT_LD_CCSAQ
401 || algorithm == NLOPT_LD_SLSQP
402 || algorithm == NLOPT_LN_COBYLA
403 || AUGLAG_ALG(algorithm)
404 || algorithm == NLOPT_GN_ISRES
405 || algorithm == NLOPT_GN_ORIG_DIRECT
406 || algorithm == NLOPT_GN_ORIG_DIRECT_L);
410 NLOPT_STDCALL nlopt_add_inequality_mconstraint(nlopt_opt opt, unsigned m,
411 nlopt_mfunc fc, void *fc_data,
415 if (!m) { /* empty constraints are always ok */
416 if (opt && opt->munge_on_destroy) opt->munge_on_destroy(fc_data);
417 return NLOPT_SUCCESS;
419 if (!opt || !inequality_ok(opt->algorithm)) ret = NLOPT_INVALID_ARGS;
420 else ret = add_constraint(&opt->m, &opt->m_alloc, &opt->fc,
421 m, NULL, fc, NULL, fc_data, tol);
422 if (ret < 0 && opt && opt->munge_on_destroy)
423 opt->munge_on_destroy(fc_data);
428 NLOPT_STDCALL nlopt_add_precond_inequality_constraint(nlopt_opt opt,
435 if (!opt || !inequality_ok(opt->algorithm)) ret = NLOPT_INVALID_ARGS;
436 else ret = add_constraint(&opt->m, &opt->m_alloc, &opt->fc,
437 1, fc, NULL, pre, fc_data, &tol);
438 if (ret < 0 && opt && opt->munge_on_destroy)
439 opt->munge_on_destroy(fc_data);
444 NLOPT_STDCALL nlopt_add_inequality_constraint(nlopt_opt opt,
445 nlopt_func fc, void *fc_data,
448 return nlopt_add_precond_inequality_constraint(opt, fc, NULL, fc_data,
453 NLOPT_STDCALL nlopt_remove_equality_constraints(nlopt_opt opt)
456 if (!opt) return NLOPT_INVALID_ARGS;
457 if (opt->munge_on_destroy) {
458 nlopt_munge munge = opt->munge_on_destroy;
459 for (i = 0; i < opt->p; ++i)
460 munge(opt->h[i].f_data);
462 for (i = 0; i < opt->p; ++i)
466 opt->p = opt->p_alloc = 0;
467 return NLOPT_SUCCESS;
470 static int equality_ok(nlopt_algorithm algorithm) {
471 /* equality constraints (h(x) = 0) only via some algorithms */
472 return (AUGLAG_ALG(algorithm)
473 || algorithm == NLOPT_LD_SLSQP
474 || algorithm == NLOPT_GN_ISRES
475 || algorithm == NLOPT_LN_COBYLA);
479 NLOPT_STDCALL nlopt_add_equality_mconstraint(nlopt_opt opt, unsigned m,
480 nlopt_mfunc fc, void *fc_data,
484 if (!m) { /* empty constraints are always ok */
485 if (opt && opt->munge_on_destroy) opt->munge_on_destroy(fc_data);
486 return NLOPT_SUCCESS;
488 if (!opt || !equality_ok(opt->algorithm)
489 || nlopt_count_constraints(opt->p, opt->h) + m > opt->n)
490 ret = NLOPT_INVALID_ARGS;
491 else ret = add_constraint(&opt->p, &opt->p_alloc, &opt->h,
492 m, NULL, fc, NULL, fc_data, tol);
493 if (ret < 0 && opt && opt->munge_on_destroy)
494 opt->munge_on_destroy(fc_data);
499 NLOPT_STDCALL nlopt_add_precond_equality_constraint(nlopt_opt opt,
506 if (!opt || !equality_ok(opt->algorithm)
507 || nlopt_count_constraints(opt->p, opt->h) + 1 > opt->n)
508 ret = NLOPT_INVALID_ARGS;
509 else ret = add_constraint(&opt->p, &opt->p_alloc, &opt->h,
510 1, fc, NULL, pre, fc_data, &tol);
511 if (ret < 0 && opt && opt->munge_on_destroy)
512 opt->munge_on_destroy(fc_data);
517 NLOPT_STDCALL nlopt_add_equality_constraint(nlopt_opt opt,
518 nlopt_func fc, void *fc_data,
521 return nlopt_add_precond_equality_constraint(opt, fc, NULL, fc_data, tol);
524 /*************************************************************************/
526 #define SET(param, T, arg) \
527 nlopt_result NLOPT_STDCALL nlopt_set_##param(nlopt_opt opt, T arg) \
531 return NLOPT_SUCCESS; \
533 return NLOPT_INVALID_ARGS; \
537 #define GET(param, T, arg) T NLOPT_STDCALL \
538 nlopt_get_##param(const nlopt_opt opt) { \
542 #define GETSET(param, T, arg) GET(param, T, arg) SET(param, T, arg)
544 GETSET(stopval, double, stopval)
546 GETSET(ftol_rel, double, ftol_rel)
547 GETSET(ftol_abs, double, ftol_abs)
548 GETSET(xtol_rel, double, xtol_rel)
551 NLOPT_STDCALL nlopt_set_xtol_abs(nlopt_opt opt, const double *xtol_abs)
554 memcpy(opt->xtol_abs, xtol_abs, opt->n * sizeof(double));
555 return NLOPT_SUCCESS;
557 return NLOPT_INVALID_ARGS;
561 NLOPT_STDCALL nlopt_set_xtol_abs1(nlopt_opt opt, double xtol_abs)
565 for (i = 0; i < opt->n; ++i)
566 opt->xtol_abs[i] = xtol_abs;
567 return NLOPT_SUCCESS;
569 return NLOPT_INVALID_ARGS;
573 NLOPT_STDCALL nlopt_get_xtol_abs(const nlopt_opt opt, double *xtol_abs)
575 memcpy(xtol_abs, opt->xtol_abs, opt->n * sizeof(double));
576 return NLOPT_SUCCESS;
579 GETSET(maxeval, int, maxeval)
581 GETSET(maxtime, double, maxtime)
583 /*************************************************************************/
586 NLOPT_STDCALL nlopt_set_force_stop(nlopt_opt opt, int force_stop)
589 opt->force_stop = force_stop;
590 if (opt->force_stop_child)
591 return nlopt_set_force_stop(opt->force_stop_child, force_stop);
592 return NLOPT_SUCCESS;
594 return NLOPT_INVALID_ARGS;
597 GET(force_stop, int, force_stop)
598 nlopt_result NLOPT_STDCALL nlopt_force_stop(nlopt_opt opt) {
599 return nlopt_set_force_stop(opt, 1);
602 /*************************************************************************/
604 GET(algorithm, nlopt_algorithm, algorithm)
605 GET(dimension, unsigned, n)
607 /*************************************************************************/
610 NLOPT_STDCALL nlopt_set_local_optimizer(nlopt_opt opt,
611 const nlopt_opt local_opt)
614 if (local_opt && local_opt->n != opt->n) return NLOPT_INVALID_ARGS;
615 nlopt_destroy(opt->local_opt);
616 opt->local_opt = nlopt_copy(local_opt);
618 if (!opt->local_opt) return NLOPT_OUT_OF_MEMORY;
619 nlopt_set_lower_bounds(opt->local_opt, opt->lb);
620 nlopt_set_upper_bounds(opt->local_opt, opt->ub);
621 nlopt_remove_inequality_constraints(opt->local_opt);
622 nlopt_remove_equality_constraints(opt->local_opt);
623 nlopt_set_min_objective(opt->local_opt, NULL, NULL);
624 nlopt_set_munge(opt->local_opt, NULL, NULL);
625 opt->local_opt->force_stop = 0;
627 return NLOPT_SUCCESS;
629 return NLOPT_INVALID_ARGS;
632 /*************************************************************************/
634 GETSET(population, unsigned, stochastic_population)
635 GETSET(vector_storage, unsigned, vector_storage)
637 /*************************************************************************/
639 nlopt_result NLOPT_STDCALL nlopt_set_initial_step1(nlopt_opt opt, double dx)
642 if (!opt || dx == 0) return NLOPT_INVALID_ARGS;
643 if (!opt->dx && opt->n > 0) {
644 opt->dx = (double *) malloc(sizeof(double) * (opt->n));
645 if (!opt->dx) return NLOPT_OUT_OF_MEMORY;
647 for (i = 0; i < opt->n; ++i) opt->dx[i] = dx;
648 return NLOPT_SUCCESS;
652 NLOPT_STDCALL nlopt_set_initial_step(nlopt_opt opt, const double *dx)
655 if (!opt) return NLOPT_INVALID_ARGS;
657 free(opt->dx); opt->dx = NULL;
658 return NLOPT_SUCCESS;
660 for (i = 0; i < opt->n; ++i) if (dx[i] == 0) return NLOPT_INVALID_ARGS;
661 if (!opt->dx && nlopt_set_initial_step1(opt, 1) == NLOPT_OUT_OF_MEMORY)
662 return NLOPT_OUT_OF_MEMORY;
663 memcpy(opt->dx, dx, sizeof(double) * (opt->n));
664 return NLOPT_SUCCESS;
668 NLOPT_STDCALL nlopt_get_initial_step(const nlopt_opt opt, const double *x,
671 if (!opt) return NLOPT_INVALID_ARGS;
672 if (!opt->n) return NLOPT_SUCCESS;
674 nlopt_opt o = (nlopt_opt) opt; /* discard const temporarily */
675 nlopt_result ret = nlopt_set_default_initial_step(o, x);
676 if (ret != NLOPT_SUCCESS) return ret;
677 memcpy(dx, o->dx, sizeof(double) * (opt->n));
678 free(o->dx); o->dx = NULL; /* don't save, since x-dependent */
681 memcpy(dx, opt->dx, sizeof(double) * (opt->n));
682 return NLOPT_SUCCESS;
686 NLOPT_STDCALL nlopt_set_default_initial_step(nlopt_opt opt, const double *x)
688 const double *lb, *ub;
691 if (!opt || !x) return NLOPT_INVALID_ARGS;
692 lb = opt->lb; ub = opt->ub;
694 if (!opt->dx && nlopt_set_initial_step1(opt, 1) == NLOPT_OUT_OF_MEMORY)
695 return NLOPT_OUT_OF_MEMORY;
697 /* crude heuristics for initial step size of nonderivative algorithms */
698 for (i = 0; i < opt->n; ++i) {
699 double step = HUGE_VAL;
701 if (!nlopt_isinf(ub[i]) && !nlopt_isinf(lb[i])
702 && (ub[i] - lb[i]) * 0.25 < step && ub[i] > lb[i])
703 step = (ub[i] - lb[i]) * 0.25;
704 if (!nlopt_isinf(ub[i])
705 && ub[i] - x[i] < step && ub[i] > x[i])
706 step = (ub[i] - x[i]) * 0.75;
707 if (!nlopt_isinf(lb[i])
708 && x[i] - lb[i] < step && x[i] > lb[i])
709 step = (x[i] - lb[i]) * 0.75;
711 if (nlopt_isinf(step)) {
712 if (!nlopt_isinf(ub[i])
713 && fabs(ub[i] - x[i]) < fabs(step))
714 step = (ub[i] - x[i]) * 1.1;
715 if (!nlopt_isinf(lb[i])
716 && fabs(x[i] - lb[i]) < fabs(step))
717 step = (x[i] - lb[i]) * 1.1;
719 if (nlopt_isinf(step) || step == 0) {
722 if (nlopt_isinf(step) || step == 0)
727 return NLOPT_SUCCESS;
730 /*************************************************************************/
732 void NLOPT_STDCALL nlopt_set_munge(nlopt_opt opt,
733 nlopt_munge munge_on_destroy,
734 nlopt_munge munge_on_copy) {
736 opt->munge_on_destroy = munge_on_destroy;
737 opt->munge_on_copy = munge_on_copy;
741 void NLOPT_STDCALL nlopt_munge_data(nlopt_opt opt,
742 nlopt_munge2 munge, void *data) {
745 opt->f_data = munge(opt->f_data, data);
746 for (i = 0; i < opt->m; ++i)
747 opt->fc[i].f_data = munge(opt->fc[i].f_data, data);
748 for (i = 0; i < opt->p; ++i)
749 opt->h[i].f_data = munge(opt->h[i].f_data, data);
753 /*************************************************************************/