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