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