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