api/options.c

   1 /* Copyright (c) 2007-2010 Massachusetts Institute of Technology
   2  *
   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:
  10  *
  11  * The above copyright notice and this permission notice shall be
  12  * included in all copies or substantial portions of the Software.
  13  *
  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.
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <math.h>
  26 #include <string.h>
  27 #include <float.h>
  28
  29 #include "nlopt-internal.h"
  30 #include "nlopt-util.h"
  31
  32 /*************************************************************************/
  33
  34 void nlopt_destroy(nlopt_opt opt)
  35 {
  36      if (opt) {
  37           if (opt->free_f_data) {
  38                unsigned i;
  39                free(opt->f_data);
  40                for (i = 0; i < opt->m; ++i)
  41                     free(opt->fc[i].f_data);
  42                for (i = 0; i < opt->p; ++i)
  43                     free(opt->h[i].f_data);
  44           }
  45           free(opt->lb); free(opt->ub);
  46           free(opt->xtol_abs);
  47           free(opt->fc);
  48           free(opt->h);
  49           nlopt_destroy(opt->local_opt);
  50           free(opt->dx);
  51           free(opt);
  52      }
  53 }
  54
  55 nlopt_opt nlopt_create(nlopt_algorithm algorithm, unsigned n)
  56 {
  57      nlopt_opt opt;
  58
  59      if (((int) algorithm) < 0 || algorithm >= NLOPT_NUM_ALGORITHMS)
  60           return NULL;
  61
  62      opt = (nlopt_opt) malloc(sizeof(struct nlopt_opt_s));
  63      if (opt) {
  64           opt->algorithm = algorithm;
  65           opt->n = n;
  66           opt->f = NULL; opt->f_data = NULL;
  67           opt->maximize = 0;
  68           opt->free_f_data = 0;
  69
  70           opt->lb = opt->ub = NULL;
  71           opt->m = opt->m_alloc = 0;
  72           opt->fc = NULL;
  73           opt->p = opt->p_alloc = 0;
  74           opt->h = NULL;
  75
  76           opt->stopval = -HUGE_VAL;
  77           opt->ftol_rel = opt->ftol_abs = 0;
  78           opt->xtol_rel = 0; opt->xtol_abs = NULL;
  79           opt->maxeval = 0;
  80           opt->maxtime = 0;
  81           opt->force_stop = 0;
  82           opt->force_stop_child = NULL;
  83
  84           opt->local_opt = NULL;
  85           opt->stochastic_population = 0;
  86           opt->dx = NULL;
  87
  88           if (n > 0) {
  89                opt->lb = (double *) malloc(sizeof(double) * (n));
  90                if (!opt->lb) goto oom;
  91                opt->ub = (double *) malloc(sizeof(double) * (n));
  92                if (!opt->ub) goto oom;
  93                opt->xtol_abs = (double *) malloc(sizeof(double) * (n));
  94                if (!opt->xtol_abs) goto oom;
  95                nlopt_set_lower_bounds1(opt, -HUGE_VAL);
  96                nlopt_set_upper_bounds1(opt, +HUGE_VAL);
  97                nlopt_set_xtol_abs1(opt, 0.0);
  98           }
  99      }
 100
 101      return opt;
 102
 103 oom:
 104      nlopt_destroy(opt);
 105      return NULL;
 106 }
 107
 108 nlopt_opt nlopt_copy(const nlopt_opt opt)
 109 {
 110      nlopt_opt nopt = NULL;
 111      if (opt) {
 112           nopt = (nlopt_opt) malloc(sizeof(struct nlopt_opt_s));
 113           *nopt = *opt;
 114           nopt->lb = nopt->ub = nopt->xtol_abs = NULL;
 115           nopt->fc = nopt->h = NULL;
 116           nopt->m_alloc = nopt->p_alloc = 0;
 117           nopt->local_opt = NULL;
 118           nopt->dx = NULL;
 119           opt->force_stop_child = NULL;
 120           opt->free_f_data = 0;
 121
 122           if (opt->n > 0) {
 123                nopt->lb = (double *) malloc(sizeof(double) * (opt->n));
 124                if (!opt->lb) goto oom;
 125                nopt->ub = (double *) malloc(sizeof(double) * (opt->n));
 126                if (!opt->ub) goto oom;
 127                nopt->xtol_abs = (double *) malloc(sizeof(double) * (opt->n));
 128                if (!opt->xtol_abs) goto oom;
 129
 130                memcpy(nopt->lb, opt->lb, sizeof(double) * (opt->n));
 131                memcpy(nopt->ub, opt->ub, sizeof(double) * (opt->n));
 132                memcpy(nopt->xtol_abs, opt->xtol_abs, sizeof(double) * (opt->n));
 133           }
 134
 135           if (opt->m) {
 136                nopt->m_alloc = opt->m;
 137                nopt->fc = (nlopt_constraint *) malloc(sizeof(nlopt_constraint)
 138                                                       * (opt->m));
 139                if (!nopt->fc) goto oom;
 140                memcpy(nopt->fc, opt->fc, sizeof(nlopt_constraint) * (opt->m));
 141           }
 142
 143           if (opt->p) {
 144                nopt->p_alloc = opt->p;
 145                nopt->h = (nlopt_constraint *) malloc(sizeof(nlopt_constraint)
 146                                                      * (opt->p));
 147                if (!nopt->h) goto oom;
 148                memcpy(nopt->h, opt->h, sizeof(nlopt_constraint) * (opt->p));
 149           }
 150
 151           if (opt->local_opt) {
 152                nopt->local_opt = nlopt_copy(opt->local_opt);
 153                if (!nopt->local_opt) goto oom;
 154           }
 155
 156           if (opt->dx) {
 157                nopt->dx = (double *) malloc(sizeof(double) * (opt->n));
 158                if (!nopt->dx) goto oom;
 159                memcpy(nopt->dx, opt->dx, sizeof(double) * (opt->n));
 160           }
 161      }
 162      return nopt;
 163
 164 oom:
 165      nlopt_destroy(nopt);
 166      return NULL;
 167 }
 168
 169 /*************************************************************************/
 170
 171 nlopt_result nlopt_set_min_objective(nlopt_opt opt, nlopt_func f, void *f_data)
 172 {
 173      if (opt) {
 174           opt->f = f; opt->f_data = f_data;
 175           opt->maximize = 0;
 176           if (nlopt_isinf(opt->stopval) && opt->stopval > 0)
 177                opt->stopval = -HUGE_VAL; /* switch default from max to min */
 178           return NLOPT_SUCCESS;
 179      }
 180      return NLOPT_INVALID_ARGS;
 181 }
 182
 183 nlopt_result nlopt_set_max_objective(nlopt_opt opt, nlopt_func f, void *f_data)
 184 {
 185      if (opt) {
 186           opt->f = f; opt->f_data = f_data;
 187           opt->maximize = 1;
 188           if (nlopt_isinf(opt->stopval) && opt->stopval < 0)
 189                opt->stopval = +HUGE_VAL; /* switch default from min to max */
 190           return NLOPT_SUCCESS;
 191      }
 192      return NLOPT_INVALID_ARGS;
 193 }
 194
 195 /*************************************************************************/
 196
 197 nlopt_result nlopt_set_lower_bounds(nlopt_opt opt, const double *lb)
 198 {
 199      if (opt && (opt->n == 0 || lb)) {
 200           memcpy(opt->lb, lb, sizeof(double) * (opt->n));
 201           return NLOPT_SUCCESS;
 202      }
 203      return NLOPT_INVALID_ARGS;
 204 }
 205
 206 nlopt_result nlopt_set_lower_bounds1(nlopt_opt opt, double lb)
 207 {
 208      if (opt) {
 209           unsigned i;
 210           for (i = 0; i < opt->n; ++i)
 211                opt->lb[i] = lb;
 212           return NLOPT_SUCCESS;
 213      }
 214      return NLOPT_INVALID_ARGS;
 215 }
 216
 217 nlopt_result nlopt_get_lower_bounds(nlopt_opt opt, double *lb)
 218 {
 219      if (opt && (opt->n == 0 || lb)) {
 220           memcpy(lb, opt->lb, sizeof(double) * (opt->n));
 221           return NLOPT_SUCCESS;
 222      }
 223      return NLOPT_INVALID_ARGS;
 224 }
 225
 226 nlopt_result nlopt_set_upper_bounds(nlopt_opt opt, const double *ub)
 227 {
 228      if (opt && (opt->n == 0 || ub)) {
 229           memcpy(opt->ub, ub, sizeof(double) * (opt->n));
 230           return NLOPT_SUCCESS;
 231      }
 232      return NLOPT_INVALID_ARGS;
 233 }
 234
 235 nlopt_result nlopt_set_upper_bounds1(nlopt_opt opt, double ub)
 236 {
 237      if (opt) {
 238           unsigned i;
 239           for (i = 0; i < opt->n; ++i)
 240                opt->ub[i] = ub;
 241           return NLOPT_SUCCESS;
 242      }
 243      return NLOPT_INVALID_ARGS;
 244 }
 245
 246 nlopt_result nlopt_get_upper_bounds(nlopt_opt opt, double *ub)
 247 {
 248      if (opt && (opt->n == 0 || ub)) {
 249           memcpy(ub, opt->ub, sizeof(double) * (opt->n));
 250           return NLOPT_SUCCESS;
 251      }
 252      return NLOPT_INVALID_ARGS;
 253 }
 254
 255 /*************************************************************************/
 256
 257 #define AUGLAG_ALG(a) ((a) == NLOPT_LN_AUGLAG ||        \
 258                        (a) == NLOPT_LN_AUGLAG_EQ ||     \
 259                        (a) == NLOPT_LD_AUGLAG ||        \
 260                        (a) == NLOPT_LD_AUGLAG_EQ)
 261
 262 nlopt_result nlopt_remove_inequality_constraints(nlopt_opt opt)
 263 {
 264      if (!opt) return NLOPT_INVALID_ARGS;
 265      free(opt->fc);
 266      opt->fc = NULL;
 267      opt->m = opt->m_alloc = 0;
 268      return NLOPT_SUCCESS;
 269 }
 270
 271 static nlopt_result add_constraint(unsigned *m, unsigned *m_alloc,
 272                                    nlopt_constraint **c,
 273                                    nlopt_func fc, void *fc_data,
 274                                    double tol)
 275 {
 276      *m += 1;
 277      if (*m > *m_alloc) {
 278           /* allocate by repeated doubling so that
 279              we end up with O(log m) mallocs rather than O(m). */
 280           *m_alloc = 2 * (*m);
 281           *c = (nlopt_constraint *) realloc(*c,
 282                                             sizeof(nlopt_constraint)
 283                                             * (*m_alloc));
 284           if (!*c) {
 285                *m_alloc = *m = 0;
 286                return NLOPT_OUT_OF_MEMORY;
 287           }
 288      }
 289
 290      (*c)[*m - 1].f = fc;
 291      (*c)[*m - 1].f_data = fc_data;
 292      (*c)[*m - 1].tol = tol;
 293      return NLOPT_SUCCESS;
 294 }
 295
 296 nlopt_result nlopt_add_inequality_constraint(nlopt_opt opt,
 297                                              nlopt_func fc, void *fc_data,
 298                                              double tol)
 299 {
 300      if (opt && fc && tol >= 0) {
 301           /* nonlinear constraints are only supported with some algorithms */
 302           if (opt->algorithm != NLOPT_LD_MMA
 303               && opt->algorithm != NLOPT_LN_COBYLA
 304               && !AUGLAG_ALG(opt->algorithm)
 305               && opt->algorithm != NLOPT_GN_ISRES
 306               && opt->algorithm != NLOPT_GN_ORIG_DIRECT
 307               && opt->algorithm != NLOPT_GN_ORIG_DIRECT_L)
 308                return NLOPT_INVALID_ARGS;
 309           return add_constraint(&opt->m, &opt->m_alloc, &opt->fc,
 310                                 fc, fc_data, tol);
 311      }
 312      return NLOPT_INVALID_ARGS;
 313 }
 314
 315 nlopt_result nlopt_remove_equality_constraints(nlopt_opt opt)
 316 {
 317      if (!opt) return NLOPT_INVALID_ARGS;
 318      free(opt->h);
 319      opt->h = NULL;
 320      opt->p = opt->p_alloc = 0;
 321      return NLOPT_SUCCESS;
 322 }
 323
 324 nlopt_result nlopt_add_equality_constraint(nlopt_opt opt,
 325                                            nlopt_func h, void *h_data,
 326                                            double tol)
 327 {
 328      if (opt && h && tol >= 0) {
 329           /* equality constraints (h(x) = 0) only via some algorithms */
 330           if (!AUGLAG_ALG(opt->algorithm) && opt->algorithm != NLOPT_GN_ISRES)
 331                return NLOPT_INVALID_ARGS;
 332           return add_constraint(&opt->p, &opt->p_alloc, &opt->h,
 333                                 h, h_data, tol);
 334      }
 335      return NLOPT_INVALID_ARGS;
 336 }
 337
 338 /*************************************************************************/
 339
 340 #define SET(param, T, arg)                              \
 341    nlopt_result nlopt_set_##param(nlopt_opt opt, T arg) \
 342    {                                                    \
 343         if (opt) {                                      \
 344              opt->arg = arg;                            \
 345              return NLOPT_SUCCESS;                      \
 346         }                                               \
 347         return NLOPT_INVALID_ARGS;                      \
 348    }
 349
 350
 351 #define GET(param, T, arg) T nlopt_get_##param(const nlopt_opt opt) {   \
 352         return opt->arg;                                                \
 353    }
 354
 355 #define GETSET(param, T, arg) GET(param, T, arg) SET(param, T, arg)
 356
 357 GETSET(stopval, double, stopval)
 358
 359 GETSET(ftol_rel, double, ftol_rel)
 360 GETSET(ftol_abs, double, ftol_abs)
 361 GETSET(xtol_rel, double, xtol_rel)
 362
 363 nlopt_result nlopt_set_xtol_abs(nlopt_opt opt, const double *xtol_abs)
 364 {
 365      if (opt) {
 366           memcpy(opt->xtol_abs, xtol_abs, opt->n & sizeof(double));
 367           return NLOPT_SUCCESS;
 368      }
 369      return NLOPT_INVALID_ARGS;
 370 }
 371
 372 nlopt_result nlopt_set_xtol_abs1(nlopt_opt opt, const double xtol_abs)
 373 {
 374      if (opt) {
 375           unsigned i;
 376           for (i = 0; i < opt->n; ++i)
 377                opt->xtol_abs[i] = xtol_abs;
 378           return NLOPT_SUCCESS;
 379      }
 380      return NLOPT_INVALID_ARGS;
 381 }
 382
 383 nlopt_result nlopt_get_xtol_abs(const nlopt_opt opt, double *xtol_abs)
 384 {
 385      memcpy(xtol_abs, opt->xtol_abs, opt->n & sizeof(double));
 386      return NLOPT_SUCCESS;
 387 }
 388
 389 GETSET(maxeval, int, maxeval)
 390
 391 GETSET(maxtime, double, maxtime)
 392
 393 /*************************************************************************/
 394
 395 nlopt_result nlopt_set_force_stop(nlopt_opt opt, int force_stop)
 396 {
 397      if (opt) {
 398           opt->force_stop = force_stop;
 399           if (opt->force_stop_child)
 400                return nlopt_set_force_stop(opt->force_stop_child, force_stop);
 401           return NLOPT_SUCCESS;
 402      }
 403      return NLOPT_INVALID_ARGS;
 404 }
 405
 406 GET(force_stop, int, force_stop)
 407 nlopt_result nlopt_force_stop(nlopt_opt opt) {
 408      return nlopt_set_force_stop(opt, 1);
 409 }
 410
 411 /*************************************************************************/
 412
 413 GET(algorithm, nlopt_algorithm, algorithm)
 414 GET(dimension, unsigned, n)
 415
 416 /*************************************************************************/
 417
 418 nlopt_result nlopt_set_local_optimizer(nlopt_opt opt,
 419                                        const nlopt_opt local_opt)
 420 {
 421      if (opt) {
 422           if (local_opt && local_opt->n != opt->n) return NLOPT_INVALID_ARGS;
 423           nlopt_destroy(opt->local_opt);
 424           opt->local_opt = nlopt_copy(local_opt);
 425           if (local_opt) {
 426                if (!opt->local_opt) return NLOPT_OUT_OF_MEMORY;
 427                nlopt_set_lower_bounds(opt->local_opt, opt->lb);
 428                nlopt_set_upper_bounds(opt->local_opt, opt->ub);
 429                nlopt_remove_inequality_constraints(opt->local_opt);
 430                nlopt_remove_equality_constraints(opt->local_opt);
 431                nlopt_set_min_objective(opt->local_opt, NULL, NULL);
 432                opt->local_opt->force_stop = 0;
 433           }
 434           return NLOPT_SUCCESS;
 435      }
 436      return NLOPT_INVALID_ARGS;
 437 }
 438
 439 /*************************************************************************/
 440
 441 GETSET(population, unsigned, stochastic_population)
 442
 443 /*************************************************************************/
 444
 445 nlopt_result nlopt_set_initial_step1(nlopt_opt opt, double dx)
 446 {
 447      unsigned i;
 448      if (!opt || dx == 0) return NLOPT_INVALID_ARGS;
 449      if (!opt->dx && opt->n > 0) {
 450           opt->dx = (double *) malloc(sizeof(double) * (opt->n));
 451           if (!opt->dx) return NLOPT_OUT_OF_MEMORY;
 452      }
 453      for (i = 0; i < opt->n; ++i) opt->dx[i] = dx;
 454      return NLOPT_SUCCESS;
 455 }
 456
 457 nlopt_result nlopt_set_initial_step(nlopt_opt opt, const double *dx)
 458 {
 459      unsigned i;
 460      if (!opt || !dx) return NLOPT_INVALID_ARGS;
 461      for (i = 0; i < opt->n; ++i) if (dx[i] == 0) return NLOPT_INVALID_ARGS;
 462      if (!opt->dx && nlopt_set_initial_step1(opt, 1) == NLOPT_OUT_OF_MEMORY)
 463           return NLOPT_OUT_OF_MEMORY;
 464      memcpy(opt->dx, dx, sizeof(double) * (opt->n));
 465      return NLOPT_SUCCESS;
 466 }
 467
 468 nlopt_result nlopt_get_initial_step(const nlopt_opt opt, const double *x,
 469                                     double *dx)
 470 {
 471      if (!opt) return NLOPT_INVALID_ARGS;
 472      if (!opt->n) return NLOPT_SUCCESS;
 473      if (!opt->dx) {
 474           nlopt_opt o = (nlopt_opt) opt; /* discard const temporarily */
 475           nlopt_result ret = nlopt_set_default_initial_step(o, x);
 476           if (ret != NLOPT_SUCCESS) return ret;
 477           memcpy(dx, o->dx, sizeof(double) * (opt->n));
 478           free(o->dx); o->dx = NULL; /* don't save, since x-dependent */
 479      }
 480      else
 481           memcpy(dx, opt->dx, sizeof(double) * (opt->n));
 482      return NLOPT_SUCCESS;
 483 }
 484
 485 nlopt_result nlopt_set_default_initial_step(nlopt_opt opt, const double *x)
 486 {
 487      const double *lb, *ub;
 488      unsigned i;
 489
 490      if (!opt || !x) return NLOPT_INVALID_ARGS;
 491      lb = opt->lb; ub = opt->ub;
 492
 493      if (!opt->dx && nlopt_set_initial_step1(opt, 1) == NLOPT_OUT_OF_MEMORY)
 494           return NLOPT_OUT_OF_MEMORY;
 495
 496      /* crude heuristics for initial step size of nonderivative algorithms */
 497      for (i = 0; i < opt->n; ++i) {
 498           double step = HUGE_VAL;
 499
 500           if (!nlopt_isinf(ub[i]) && !nlopt_isinf(lb[i])
 501               && (ub[i] - lb[i]) * 0.25 < step && ub[i] > lb[i])
 502                step = (ub[i] - lb[i]) * 0.25;
 503           if (!nlopt_isinf(ub[i])
 504               && ub[i] - x[i] < step && ub[i] > x[i])
 505                step = (ub[i] - x[i]) * 0.75;
 506           if (!nlopt_isinf(lb[i])
 507               && x[i] - lb[i] < step && x[i] > lb[i])
 508                step = (x[i] - lb[i]) * 0.75;
 509
 510           if (nlopt_isinf(step)) {
 511                if (!nlopt_isinf(ub[i])
 512                    && fabs(ub[i] - x[i]) < fabs(step))
 513                     step = (ub[i] - x[i]) * 1.1;
 514                if (!nlopt_isinf(lb[i])
 515                    && fabs(x[i] - lb[i]) < fabs(step))
 516                     step = (x[i] - lb[i]) * 1.1;
 517           }
 518           if (nlopt_isinf(step) || step == 0) {
 519                step = x[i];
 520           }
 521           if (nlopt_isinf(step) || step == 0)
 522                step = 1;
 523
 524           opt->dx[i] = step;
 525      }
 526      return NLOPT_SUCCESS;
 527 }
 528
 529 /*************************************************************************/
 530
 531 GETSET(free_f_data, int, free_f_data)
 532
 533 /* the dup_f_data function replaces all f_data pointers with a new
 534    pointer to a duplicate block of memory, assuming all non-NULL
 535    f_data pointers point to a block of sz bytes...  this is pretty
 536    exclusively intended for internal use (e.g. it may lead to a
 537    double-free if one subsequently calles add_inequality_constraint
 538    etc.), e.g. in the C++ API */
 539
 540 static int dup(void **p, size_t sz) {
 541      if (*p) {
 542           void *pdup = malloc(sz);
 543           if (pdup) {
 544                memcpy(pdup, *p, sz);
 545                *p = pdup;
 546                return 1;
 547           }
 548           else return 0;
 549      }
 550      else return 1;
 551 }
 552
 553 nlopt_result nlopt_dup_f_data(nlopt_opt opt, size_t sz) {
 554      if (opt) {
 555           unsigned i;
 556           if (!dup(&opt->f_data, sz)) return NLOPT_OUT_OF_MEMORY;
 557           for (i = 0; i < opt->m; ++i)
 558                if (!dup(&opt->fc[i].f_data, sz)) return NLOPT_OUT_OF_MEMORY;
 559           for (i = 0; i < opt->p; ++i)
 560                if (!dup(&opt->h[i].f_data, sz)) return NLOPT_OUT_OF_MEMORY;
 561           nlopt_set_free_f_data(opt, 1); // nlopt_destroy must now free f_data!
 562           return NLOPT_SUCCESS;
 563      }
 564      return NLOPT_INVALID_ARGS;
 565 }
 566
 567 /*************************************************************************/