api/nlopt_minimize_constrained.3

   1 .\"
   2 .\" Copyright (c) 2007 Massachusetts Institute of Technology
   3 .\"
   4 .\" Copying and distribution of this file, with or without modification,
   5 .\" are permitted in any medium without royalty provided the copyright
   6 .\" notice and this notice are preserved.
   7 .\"
   8 .TH NLOPT_MINIMIZE_CONSTRAINED 3  2007-08-23 "MIT" "NLopt programming manual"
   9 .SH NAME
  10 nlopt_minimize_constrained \- Minimize a multivariate nonlinear function subject to nonlinear constraints
  11 .SH SYNOPSIS
  12 .nf
  13 .B #include <nlopt.h>
  14 .sp
  15 .BI "nlopt_result nlopt_minimize_constrained(nlopt_algorithm " "algorithm" ,
  16 .br
  17 .BI "                            int " "n" ,
  18 .BI "                            nlopt_func " "f" ,
  19 .BI "                            void* " "f_data" ,
  20 .BI "                            int " "m" ,
  21 .BI "                            nlopt_func " "c" ,
  22 .BI "                            void* " "fc_data" ,
  23 .BI "                            ptrdiff_t " "fc_datum_size" ,
  24 .BI "                            const double* " "lb" ,
  25 .BI "                            const double* " "ub" ,
  26 .BI "                            double* " "x" ,
  27 .BI "                            double* " "minf" ,
  28 .BI "                            double " "minf_max" ,
  29 .BI "                            double " "ftol_rel" ,
  30 .BI "                            double " "ftol_abs" ,
  31 .BI "                            double " "xtol_rel" ,
  32 .BI "                            const double* " "xtol_abs" ,
  33 .BI "                            int " "maxeval" ,
  34 .BI "                            double " "maxtime" );
  35 .sp
  36 You should link the resulting program with the linker flags
  37 -lnlopt -lm on Unix.
  38 .fi
  39 .SH DESCRIPTION
  40 .BR nlopt_minimize_constrained ()
  41 attempts to minimize a nonlinear function
  42 .I f
  43 of
  44 .I n
  45 design variables, subject to
  46 .I m
  47 nonlinear constraints described by the function
  48 .I fc
  49 (see below), using the specified
  50 .IR algorithm .
  51 The minimum function value found is returned in
  52 .IR minf ,
  53 with the corresponding design variable values returned in the array
  54 .I x
  55 of length
  56 .IR n .
  57 The input values in
  58 .I x
  59 should be a starting guess for the optimum.
  60 The inputs
  61 .I lb
  62 and
  63 .I ub
  64 are arrays of length
  65 .I n
  66 containing lower and upper bounds, respectively, on the design variables
  67 .IR x .
  68 The other parameters specify stopping criteria (tolerances, the maximum
  69 number of function evaluations, etcetera) and other information as described
  70 in more detail below.  The return value is a integer code indicating success
  71 (positive) or failure (negative), as described below.
  72 .PP
  73 By changing the parameter
  74 .I algorithm
  75 among several predefined constants described below, one can switch easily
  76 between a variety of minimization algorithms.  Some of these algorithms
  77 require the gradient (derivatives) of the function to be supplied via
  78 .IR f ,
  79 and other algorithms do not require derivatives.  Some of the
  80 algorithms attempt to find a global minimum within the given bounds,
  81 and others find only a local minimum.  Some of the algorithms can handle
  82 nonlinear constraints, but most of the algorithms only handle the
  83 case where
  84 .I m
  85 is zero (no explicit nonlinear constraints).
  86 .PP
  87 The
  88 .B nlopt_minimize_constrained
  89 function is a wrapper around several free/open-source minimization packages,
  90 as well as some new implementations of published optimization algorithms.
  91 You could, of course, compile and call these packages separately, and in
  92 some cases this will provide greater flexibility than is available via the
  93 .B nlopt_minimize_constrained
  94 interface.  However, depending upon the specific function being minimized,
  95 the different algorithms will vary in effectiveness.  The intent of
  96 .B nlopt_minimize_constrained
  97 is to allow you to quickly switch between algorithms in order to experiment
  98 with them for your problem, by providing a simple unified interface to
  99 these subroutines.
 100 .SH OBJECTIVE FUNCTION
 101 .BR nlopt_minimize_constrained ()
 102 minimizes an objective function
 103 .I f
 104 of the form:
 105 .sp
 106 .BI "      double f(int " "n" ,
 107 .br
 108 .BI "               const double* " "x" ,
 109 .br
 110 .BI "               double* " "grad" ,
 111 .br
 112 .BI "               void* " "f_data" );
 113 .sp
 114 The return value should be the value of the function at the point
 115 .IR x ,
 116 where
 117 .I x
 118 points to an array of length
 119 .I n
 120 of the design variables.  The dimension
 121 .I n
 122 is identical to the one passed to
 123 .BR nlopt_minimize_constrained ().
 124 .sp
 125 In addition, if the argument
 126 .I grad
 127 is not NULL, then
 128 .I grad
 129 points to an array of length
 130 .I n
 131 which should (upon return) be set to the gradient of the function with
 132 respect to the design variables at
 133 .IR x .
 134 That is,
 135 .IR grad[i]
 136 should upon return contain the partial derivative df/dx[i],
 137 for 0 <= i < n, if
 138 .I grad
 139 is non-NULL.
 140 Not all of the optimization algorithms (below) use the gradient information:
 141 for algorithms listed as "derivative-free," the
 142 .I grad
 143 argument will always be NULL and need never be computed.  (For
 144 algorithms that do use gradient information, however,
 145 .I grad
 146 may still be NULL for some calls.)
 147 .sp
 148 The
 149 .I f_data
 150 argument is the same as the one passed to
 151 .BR nlopt_minimize_constrained (),
 152 and may be used to pass any additional data through to the function.
 153 (That is, it may be a pointer to some caller-defined data
 154 structure/type containing information your function needs, which you
 155 convert from void* by a typecast.)
 156 .sp
 157 .SH BOUND CONSTRAINTS
 158 Most of the algorithms in NLopt are designed for minimization of functions
 159 with simple bound constraints on the inputs.  That is, the input vectors
 160 x[i] are constrainted to lie in a hyperrectangle lb[i] <= x[i] <= ub[i] for
 161 0 <= i < n, where
 162 .I lb
 163 and
 164 .I ub
 165 are the two arrays passed to
 166 .BR nlopt_minimize_constrained ().
 167 .sp
 168 However, a few of the algorithms support partially or totally
 169 unconstrained optimization, as noted below, where a (totally or
 170 partially) unconstrained design variable is indicated by a lower bound
 171 equal to -Inf and/or an upper bound equal to +Inf.  Here, Inf is the
 172 IEEE-754 floating-point infinity, which (in ANSI C99) is represented by
 173 the macro INFINITY in math.h.  Alternatively, for older C versions
 174 you may also use the macro HUGE_VAL (also in math.h).
 175 .sp
 176 With some of the algorithms, especially those that do not require
 177 derivative information, a simple (but not especially efficient) way
 178 to implement arbitrary nonlinear constraints is to return Inf (see
 179 above) whenever the constraints are violated by a given input
 180 .IR x .
 181 More generally, there are various ways to implement constraints
 182 by adding "penalty terms" to your objective function, which are
 183 described in the optimization literature.
 184 A much more efficient way to specify nonlinear constraints is described
 185 below, but is only supported by a small subset of the algorithms.
 186 .SH NONLINEAR CONSTRAINTS
 187 The
 188 .B nlopt_minimize_constrained
 189 function also allows you to specify
 190 .I m
 191 nonlinear constraints via the function
 192 .IR fc ,
 193 where
 194 .I m
 195 is any nonnegative integer.  However, nonzero
 196 .I m
 197 is currently only supported by the
 198 .B NLOPT_LD_MMA
 199 algorithm below.
 200 .sp
 201 In particular, the nonlinear constraints are of the form
 202 \fIfc\fR(\fIx\fR) <= 0, where the function
 203 .I fc
 204 is of the same form as the objective function described above:
 205 .sp
 206 .BI "      double fc(int " "n" ,
 207 .br
 208 .BI "                const double* " "x" ,
 209 .br
 210 .BI "                double* " "grad" ,
 211 .br
 212 .BI "                void* " "fc_datum" );
 213 .sp
 214 The return value should be the value of the constraint at the point
 215 .IR x ,
 216 where
 217 the dimension
 218 .I n
 219 is identical to the one passed to
 220 .BR nlopt_minimize_constrained ().
 221 As for the objective function, if the argument
 222 .I grad
 223 is not NULL, then
 224 .I grad
 225 points to an array of length
 226 .I n
 227 which should (upon return) be set to the gradient of the function with
 228 respect to
 229 .IR x .
 230 (For any algorithm listed as "derivative-free" below, the
 231 .I grad
 232 argument will always be NULL and need never be computed.)
 233 .sp
 234 The
 235 .I fc_datum
 236 argument is based on the
 237 .I fc_data
 238 argument passed to
 239 .BR nlopt_minimize_constrained (),
 240 and may be used to pass any additional data through to the function,
 241 and is used to distinguish between different constraints.
 242 .sp
 243 In particular, the constraint function
 244 .I fc
 245 will be called
 246 .I m
 247 times for each
 248 .IR x ,
 249 and the i-th constraint (0 <= i <=
 250 .IR m )
 251 will be passed an
 252 .I fc_datum
 253 argument equal to
 254 .I fc_data
 255 offset by i *
 256 .IR fc_datum_size .
 257 For example, suppose that you have a data structure of type "foo"
 258 that describes the data needed by each constraint, and you store
 259 the information for the constraints in an array "foo data[m]".  In
 260 this case, you would pass "data" as the
 261 .I fc_data
 262 parameter to
 263 .BR nlopt_minimize_constrained ,
 264 and "sizeof(foo)" as the
 265 .I fc_datum_size
 266 parameter.  Then, your
 267 .I fc
 268 function would be called
 269 .I m
 270 times for each point, and be passed data[0] through data[m-1] in sequence.
 271 .SH ALGORITHMS
 272 The
 273 .I algorithm
 274 parameter specifies the optimization algorithm (for more detail on
 275 these, see the README files in the source-code subdirectories), and
 276 can take on any of the following constant values.  Constants with
 277 .B _G{N,D}_
 278 in their names
 279 refer to global optimization methods, whereas
 280 .B _L{N,D}_
 281 refers to local optimization methods (that try to find a local minimum
 282 starting from the starting guess
 283 .IR x ).
 284 Constants with
 285 .B _{G,L}N_
 286 refer to non-gradient (derivative-free) algorithms that do not require the
 287 objective function to supply a gradient, whereas
 288 .B _{G,L}D_
 289 refers to derivative-based algorithms that require the objective
 290 function to supply a gradient.  (Especially for local optimization,
 291 derivative-based algorithms are generally superior to derivative-free
 292 ones: the gradient is good to have
 293 .I if
 294 you can compute it cheaply, e.g. via an adjoint method.)
 295 .TP
 296 .B NLOPT_GN_DIRECT_L
 297 Perform a global (G) derivative-free (N) optimization using the
 298 DIRECT-L search algorithm by Jones et al. as modified by Gablonsky et
 299 al. to be more weighted towards local search.  Does not support
 300 unconstrainted optimization.  There are also several other variants of
 301 the DIRECT algorithm that are supported:
 302 .BR NLOPT_GLOBAL_DIRECT ,
 303 which is the original DIRECT algorithm;
 304 .BR NLOPT_GLOBAL_DIRECT_L_RAND ,
 305 a slightly randomized version of DIRECT-L that may be better in
 306 high-dimensional search spaces;
 307 .BR NLOPT_GLOBAL_DIRECT_NOSCAL ,
 308 .BR NLOPT_GLOBAL_DIRECT_L_NOSCAL ,
 309 and
 310 .BR NLOPT_GLOBAL_DIRECT_L_RAND_NOSCAL ,
 311 which are versions of DIRECT where the dimensions are not rescaled to
 312 a unit hypercube (which means that dimensions with larger bounds are
 313 given more weight).
 314 .TP
 315 .B NLOPT_GN_ORIG_DIRECT_L
 316 A global (G) derivative-free optimization using the DIRECT-L algorithm
 317 as above, along with
 318 .B NLOPT_GN_ORIG_DIRECT
 319 which is the original DIRECT algorithm.  Unlike
 320 .B NLOPT_GN_DIRECT_L
 321 above, these two algorithms refer to code based on the original
 322 Fortran code of Gablonsky et al., which has some hard-coded
 323 limitations on the number of subdivisions etc. and does not support
 324 all of the NLopt stopping criteria, but on the other hand supports
 325 arbitrary nonlinear constraints as described above.
 326 .TP
 327 .B NLOPT_GD_STOGO
 328 Global (G) optimization using the StoGO algorithm by Madsen et al.  StoGO
 329 exploits gradient information (D) (which must be supplied by the
 330 objective) for its local searches, and performs the global search by a
 331 branch-and-bound technique.  Only bound-constrained optimization
 332 is supported.  There is also another variant of this algorithm,
 333 .BR NLOPT_GD_STOGO_RAND ,
 334 which is a randomized version of the StoGO search scheme.  The StoGO
 335 algorithms are only available if NLopt is compiled with C++ enabled,
 336 and should be linked via -lnlopt_cxx (via a C++ compiler, in order
 337 to link the C++ standard libraries).
 338 .TP
 339 .B NLOPT_LN_SUBPLEX
 340 Perform a local (L) derivative-free (N) optimization, starting at
 341 .IR x ,
 342 using the Subplex algorithm of Rowan et al., which is an improved
 343 variant of Nelder-Mead simplex algorithm.  (Like Nelder-Mead, Subplex
 344 often works well in practice, even for discontinuous objectives, but
 345 there is no rigorous guarantee that it will converge.)  Subplex is
 346 best for unconstrained optimization, but constrained optimization also
 347 works (both for simple bound constraints via
 348 .I lb
 349 and
 350 .I ub
 351 as well as nonlinear constraints as described above).
 352 .TP
 353 .B NLOPT_LN_PRAXIS
 354 Local (L) derivative-free (N) optimization using the principal-axis
 355 method, based on code by Richard Brent.  Designed for unconstrained
 356 optimization, although bound constraints are supported too (via a
 357 potentially inefficient method).
 358 .TP
 359 .B NLOPT_LD_LBFGS
 360 Local (L) gradient-based (D) optimization using the limited-memory BFGS
 361 (L-BFGS) algorithm.  (The objective function must supply the
 362 gradient.)  Unconstrained optimization is supported in addition to
 363 simple bound constraints (see above).  Based on an implementation by
 364 Luksan et al.
 365 .TP
 366 .B NLOPT_LD_VAR2
 367 Local (L) gradient-based (D) optimization using a shifted limited-memory
 368 variable-metric method based on code by Luksan et al., supporting both
 369 unconstrained and bound-constrained optimization.
 370 .B NLOPT_LD_VAR2
 371 uses a rank-2 method, while
 372 .B .B NLOPT_LD_VAR1
 373 is another variant using a rank-1 method.
 374 .TP
 375 .B NLOPT_LD_TNEWTON_PRECOND_RESTART
 376 Local (L) gradient-based (D) optimization using an
 377 LBFGS-preconditioned truncated Newton method with steepest-descent
 378 restarting, based on code by Luksan et al., supporting both
 379 unconstrained and bound-constrained optimization.  There are several
 380 other variants of this algorithm:
 381 .B NLOPT_LD_TNEWTON_PRECOND
 382 (same without restarting),
 383 .B NLOPT_LD_TNEWTON_RESTART
 384 (same without preconditioning), and
 385 .B NLOPT_LD_TNEWTON
 386 (same without restarting or preconditioning).
 387 .TP
 388 .B NLOPT_GN_CRS2_LM
 389 Global (G) derivative-free (N) optimization using controlled random
 390 search (CRS2) algorithm of Price, with the "local mutation" (LM)
 391 modification suggested by Kaelo and Ali.
 392 .TP
 393 \fBNLOPT_GD_MLSL_LDS\fR, \fBNLOPT_GN_MLSL_LDS\fR
 394 Global (G) derivative-based (D) or derivative-free (N) optimization
 395 using the multi-level single-linkage (MLSL) algorithm with a
 396 low-discrepancy sequence (LDS).  This algorithm executes a quasi-random
 397 (LDS) sequence of local searches, with a clustering heuristic to
 398 avoid multiple local searches for the same local minimum.  The local
 399 search uses the derivative/nonderivative algorithm set by
 400 .I nlopt_set_local_search_algorithm
 401 (currently defaulting to
 402 .I NLOPT_LD_LBFGS
 403 and
 404 .I NLOPT_LN_SUBPLEX
 405 for derivative/nonderivative searches, respectively).  There are also
 406 two other variants, \fBNLOPT_GD_MLSL\fR and \fBNLOPT_GN_MLSL\fR, which use
 407 pseudo-random numbers (instead of an LDS) as in the original MLSL algorithm.
 408 .TP
 409 .B NLOPT_LD_MMA
 410 Local (L) gradient-based (D) optimization using the method of moving
 411 asymptotes (MMA), or rather a refined version of the algorithm as
 412 published by Svanberg (2002).  (NLopt uses an independent free
 413 implementation of Svanberg's algorithm.)  The
 414 .B NLOPT_LD_MMA
 415 algorithm supports both bound-constrained and unconstrained optimization,
 416 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
 417 as described above.
 418 .SH STOPPING CRITERIA
 419 Multiple stopping criteria for the optimization are supported, as
 420 specified by the following arguments to
 421 .BR nlopt_minimize_constrained ().
 422 The optimization halts whenever any one of these criteria is
 423 satisfied.  In some cases, the precise interpretation of the stopping
 424 criterion depends on the optimization algorithm above (although we
 425 have tried to make them as consistent as reasonably possible), and
 426 some algorithms do not support all of the stopping criteria.
 427 .sp
 428 Important: you do not need to use all of the stopping criteria!  In most
 429 cases, you only need one or two, and can set the remainder to values where
 430 they do nothing (as described below).
 431 .TP
 432 .B minf_max
 433 Stop when a function value less than or equal to
 434 .I minf_max
 435 is found.  Set to -Inf or NaN (see constraints section above) to disable.
 436 .TP
 437 .B ftol_rel
 438 Relative tolerance on function value: stop when an optimization step
 439 (or an estimate of the minimum) changes the function value by less
 440 than
 441 .I ftol_rel
 442 multiplied by the absolute value of the function value.  (If there is any chance that your minimum function value is close to zero, you might want to set an absolute tolerance with
 443 .I ftol_abs
 444 as well.)  Disabled if non-positive.
 445 .TP
 446 .B ftol_abs
 447 Absolute tolerance on function value: stop when an optimization step
 448 (or an estimate of the minimum) changes the function value by less
 449 than
 450 .IR ftol_abs .
 451 Disabled if non-positive.
 452 .TP
 453 .B xtol_rel
 454 Relative tolerance on design variables: stop when an optimization step
 455 (or an estimate of the minimum) changes every design variable by less
 456 than
 457 .I xtol_rel
 458 multiplied by the absolute value of the design variable.  (If there is
 459 any chance that an optimal design variable is close to zero, you
 460 might want to set an absolute tolerance with
 461 .I xtol_abs
 462 as well.)  Disabled if non-positive.
 463 .TP
 464 .B xtol_abs
 465 Pointer to an array of length
 466 .I
 467 n giving absolute tolerances on design variables: stop when an
 468 optimization step (or an estimate of the minimum) changes every design
 469 variable
 470 .IR x [i]
 471 by less than
 472 .IR xtol_abs [i].
 473 Disabled if non-positive, or if
 474 .I xtol_abs
 475 is NULL.
 476 .TP
 477 .B maxeval
 478 Stop when the number of function evaluations exceeds
 479 .IR maxeval .
 480 (This is not a strict maximum: the number of function evaluations may
 481 exceed
 482 .I maxeval
 483 slightly, depending upon the algorithm.)  Disabled
 484 if non-positive.
 485 .TP
 486 .B maxtime
 487 Stop when the optimization time (in seconds) exceeds
 488 .IR maxtime .
 489 (This is not a strict maximum: the time may
 490 exceed
 491 .I maxtime
 492 slightly, depending upon the algorithm and on how slow your function
 493 evaluation is.)  Disabled if non-positive.
 494 .SH RETURN VALUE
 495 The value returned is one of the following enumerated constants.
 496 .SS Successful termination (positive return values):
 497 .TP
 498 .B NLOPT_SUCCESS
 499 Generic success return value.
 500 .TP
 501 .B NLOPT_MINF_MAX_REACHED
 502 Optimization stopped because
 503 .I minf_max
 504 (above) was reached.
 505 .TP
 506 .B NLOPT_FTOL_REACHED
 507 Optimization stopped because
 508 .I ftol_rel
 509 or
 510 .I ftol_abs
 511 (above) was reached.
 512 .TP
 513 .B NLOPT_XTOL_REACHED
 514 Optimization stopped because
 515 .I xtol_rel
 516 or
 517 .I xtol_abs
 518 (above) was reached.
 519 .TP
 520 .B NLOPT_MAXEVAL_REACHED
 521 Optimization stopped because
 522 .I maxeval
 523 (above) was reached.
 524 .TP
 525 .B NLOPT_MAXTIME_REACHED
 526 Optimization stopped because
 527 .I maxtime
 528 (above) was reached.
 529 .SS Error codes (negative return values):
 530 .TP
 531 .B NLOPT_FAILURE
 532 Generic failure code.
 533 .TP
 534 .B NLOPT_INVALID_ARGS
 535 Invalid arguments (e.g. lower bounds are bigger than upper bounds, an
 536 unknown algorithm was specified, etcetera).
 537 .TP
 538 .B NLOPT_OUT_OF_MEMORY
 539 Ran out of memory.
 540 .SH PSEUDORANDOM NUMBERS
 541 For stochastic optimization algorithms, we use pseudorandom numbers generated
 542 by the Mersenne Twister algorithm, based on code from Makoto Matsumoto.
 543 By default, the seed for the random numbers is generated from the system
 544 time, so that they will be different each time you run the program.  If
 545 you want to use deterministic random numbers, you can set the seed by
 546 calling:
 547 .sp
 548 .BI "            void nlopt_srand(unsigned long " "seed" );
 549 .sp
 550 Some of the algorithms also support using low-discrepancy sequences (LDS),
 551 sometimes known as quasi-random numbers.  NLopt uses the Sobol LDS, which
 552 is implemented for up to 1111 dimensions.
 553 .SH BUGS
 554 Currently the NLopt library is in pre-alpha stage.  Most algorithms
 555 currently do not support all termination conditions: the only
 556 termination condition that is consistently supported right now is
 557 .BR maxeval .
 558 .SH AUTHORS
 559 Written by Steven G. Johnson.
 560 .PP
 561 Copyright (c) 2007-2008 Massachusetts Institute of Technology.
 562 .SH "SEE ALSO"
 563 nlopt_minimize(3)