Tutorial
Moustache problem
\[\begin{array}{rl} (BB) \ \ \ \displaystyle \max_{x,y} & x\\ s.t. & y \in I(x)\\ \end{array}\]
The objective is to maximise $f(x, y) = x$ with $f$ not defined outside of a tight ribbon. At a given $x$, the interval of the admissible $y$ values is denoted $I(x) = [g(x) - \varepsilon(x)$, $g(x) + \varepsilon(x)]$, with
\[g(x) = -(|\cos(x)| + 0.1) \sin(x) + 2 ~~\text{and}~~ \varepsilon(x) = 0.05 + 0.05 \Bigg(1 + \dfrac{1}{1 + |x - 11|}\Bigg)\]
We can rewrite the problem such that it can be solved with NOMAD. We choose as starting point $(0, 2)$ and restrict the domain such that $x \in [0,20]$ and $y \in [0, 4]$.
\[\begin{array}{rrcll} (BB) \ \ \ \displaystyle - \min_{x \in \mathbb{R}^2} && -x_1\\ s.t. & & g(x_1) - \varepsilon(x_1) - x_2 & \leq 0 & \\ & & x_2 - g(x_1) + \varepsilon(x_1) & \leq 0 & \\ & 0 \leq & x_1 & \leq 20 & \\ & 0 \leq & x_2 & \leq 4 & \\ \end{array}\]
using NOMAD
# Objective
function f(x)
return -x[1]
end
# Constraints
function c(x)
g = -(abs(cos(x[1])) + 0.1) * sin(x[1]) + 2
ε = 0.05 + 0.05 * (1 - 1 / (1 + abs(x[1] - 11)))
constraints = [g - ε - x[2]; x[2] - g - ε]
return constraints
end
# Evaluator
function bb(x)
bb_outputs = [f(x); c(x)]
success = true
count_eval = true
return (success, count_eval, bb_outputs)
end
# Define Nomad Problem
p = NomadProblem(2, 3, ["OBJ"; "EB"; "EB"], bb,
lower_bound=[0.0;0.0],
upper_bound=[20.0;4.0])
# Fix some options
p.options.max_bb_eval = 1000 # total number of evaluations
p.options.display_stats = ["BBE", "EVAL", "SOL", "OBJ", "CONS_H"] # some display options
# Solution
result = solve(p, [0.0;2.0])
println("Solution: ", result.x_best_feas)BBE EVAL ( SOL ) OBJ CONS_H
1 1 ( 0 2 ) -0 0
11 12 ( 0.16 1.8 ) -0.16 0
28 34 ( 0.32 1.68 ) -0.32 0
29 35 ( 0.48 1.52 ) -0.48 0
32 38 ( 0.56 1.49 ) -0.56 0
36 42 ( 0.66 1.3725 ) -0.66 0
38 46 ( 0.74 1.3425 ) -0.74 0
44 52 ( 0.75 1.3625 ) -0.75 0
45 53 ( 0.8 1.3625 ) -0.8 0
49 58 ( 0.95 1.3625 ) -0.95 0
62 74 ( 0.96 1.3568 ) -0.96 0
63 75 ( 0.97 1.3561 ) -0.97 0
67 79 ( 0.98 1.3604 ) -0.98 0
68 81 ( 1.01 1.3733 ) -1.01 0
69 82 ( 1.1 1.4133 ) -1.1 0
78 93 ( 1.19 1.5733 ) -1.19 0
79 94 ( 1.28 1.6733 ) -1.28 0
81 96 ( 1.46 1.8133 ) -1.46 0
85 100 ( 1.51 1.7933 ) -1.51 0
86 101 ( 1.63 1.8533 ) -1.63 0
91 106 ( 1.66 1.8333 ) -1.66 0
97 112 ( 1.68 1.8533 ) -1.68 0
119 141 ( 1.71 1.844 ) -1.71 0
124 146 ( 1.72 1.844 ) -1.72 0
127 149 ( 1.73 1.834 ) -1.73 0
129 152 ( 1.76 1.804 ) -1.76 0
130 153 ( 1.85 1.714 ) -1.85 0
140 163 ( 2.12 1.444 ) -2.12 0
148 171 ( 3.12 2.024 ) -3.12 0
156 181 ( 4.12 2.514 ) -4.12 0
178 211 ( 4.16 2.584 ) -4.16 0
181 214 ( 4.2 2.564 ) -4.2 0
185 218 ( 4.21 2.514 ) -4.21 0
186 219 ( 4.24 2.484 ) -4.24 0
187 220 ( 4.27 2.514 ) -4.27 0
188 221 ( 4.32 2.504 ) -4.32 0
189 222 ( 4.36 2.424 ) -4.36 0
190 223 ( 4.44 2.354 ) -4.44 0
191 224 ( 4.52 2.374 ) -4.52 0
193 226 ( 4.64 2.224 ) -4.64 0
BBE EVAL ( SOL ) OBJ CONS_H
199 232 ( 4.67 2.164 ) -4.67 0
200 233 ( 4.75 2.064 ) -4.75 0
213 247 ( 4.76 2.084 ) -4.76 0
214 248 ( 4.78 2.094 ) -4.78 0
221 256 ( 4.79 2.114 ) -4.79 0
222 257 ( 4.81 2.144 ) -4.81 0
223 258 ( 4.83 2.154 ) -4.83 0
224 259 ( 4.87 2.194 ) -4.87 0
225 260 ( 4.9 2.244 ) -4.9 0
226 261 ( 4.96 2.324 ) -4.96 0
227 262 ( 5.02 2.374 ) -5.02 0
228 263 ( 5.13 2.494 ) -5.13 0
234 269 ( 5.21 2.594 ) -5.21 0
241 276 ( 5.23 2.604 ) -5.23 0
244 281 ( 5.25 2.614 ) -5.25 0
245 282 ( 5.27 2.624 ) -5.27 0
248 286 ( 5.28 2.624 ) -5.28 0
249 287 ( 5.3 2.634 ) -5.3 0
252 291 ( 5.31 2.634 ) -5.31 0
253 292 ( 5.33 2.644 ) -5.33 0
256 296 ( 5.34 2.644 ) -5.34 0
259 300 ( 5.37 2.644 ) -5.37 0
260 301 ( 5.46 2.644 ) -5.46 0
268 312 ( 5.55 2.644 ) -5.55 0
282 331 ( 5.59 2.644 ) -5.59 0
304 358 ( 5.6 2.644 ) -5.6 0
321 383 ( 5.6025 2.644 ) -5.6025 0
331 394 ( 5.6028 2.644072 ) -5.6028 0
344 408 ( 5.6044 2.643572 ) -5.6044 0
345 409 ( 5.6092 2.642072 ) -5.6092 0
346 410 ( 5.6236 2.637572 ) -5.6236 0
349 414 ( 5.6336 2.63319 ) -5.6336 0
351 416 ( 5.6636 2.62009 ) -5.6636 0
354 420 ( 5.6736 2.61569 ) -5.6736 0
355 421 ( 5.7036 2.60479 ) -5.7036 0
359 425 ( 5.7136 2.50899 ) -5.7136 0
360 426 ( 5.7236 2.45859 ) -5.7236 0
362 428 ( 5.7436 2.40319 ) -5.7436 0
366 432 ( 5.7536 2.43479 ) -5.7536 0
367 433 ( 5.7736 2.42289 ) -5.7736 0
BBE EVAL ( SOL ) OBJ CONS_H
372 438 ( 5.7836 2.45199 ) -5.7836 0
373 439 ( 5.8036 2.47639 ) -5.8036 0
374 440 ( 5.8236 2.46699 ) -5.8236 0
375 441 ( 5.8636 2.48439 ) -5.8636 0
380 446 ( 5.8836 2.47409 ) -5.8836 0
387 453 ( 5.9036 2.47219 ) -5.9036 0
400 471 ( 5.9236 2.45219 ) -5.9236 0
401 472 ( 5.9836 2.39219 ) -5.9836 0
402 473 ( 6.1636 2.21219 ) -6.1636 0
411 482 ( 6.7036 1.67219 ) -6.7036 0
421 495 ( 6.8436 1.50219 ) -6.8436 0
425 499 ( 7.0036 1.36219 ) -7.0036 0
431 505 ( 7.0336 1.35219 ) -7.0336 0
441 515 ( 7.0436 1.35219 ) -7.0436 0
442 516 ( 7.0636 1.35219 ) -7.0636 0
443 517 ( 7.0836 1.34219 ) -7.0836 0
445 519 ( 7.1136 1.34219 ) -7.1136 0
446 520 ( 7.1536 1.34219 ) -7.1536 0
449 523 ( 7.1636 1.35219 ) -7.1636 0
450 524 ( 7.2036 1.36219 ) -7.2036 0
456 530 ( 7.2536 1.37219 ) -7.2536 0
457 531 ( 7.3036 1.39219 ) -7.3036 0
459 533 ( 7.4036 1.43219 ) -7.4036 0
463 537 ( 7.4336 1.45219 ) -7.4336 0
472 547 ( 7.5236 1.51219 ) -7.5236 0
485 560 ( 7.5636 1.55219 ) -7.5636 0
486 561 ( 7.6036 1.59219 ) -7.6036 0
488 563 ( 7.6836 1.66219 ) -7.6836 0
489 564 ( 7.7636 1.74219 ) -7.7636 0
491 566 ( 7.9236 1.90219 ) -7.9236 0
502 577 ( 7.9336 1.90219 ) -7.9336 0
505 582 ( 7.9436 1.88219 ) -7.9436 0
506 583 ( 7.9536 1.87219 ) -7.9536 0
508 586 ( 7.9836 1.84219 ) -7.9836 0
509 587 ( 8.0736 1.75219 ) -8.0736 0
513 595 ( 8.3436 1.48219 ) -8.3436 0
521 606 ( 8.4736 1.40219 ) -8.4736 0
525 610 ( 8.5036 1.42219 ) -8.5036 0
526 611 ( 8.5836 1.39219 ) -8.5836 0
531 616 ( 8.6036 1.41219 ) -8.6036 0
BBE EVAL ( SOL ) OBJ CONS_H
532 617 ( 8.6736 1.42219 ) -8.6736 0
533 618 ( 8.7636 1.39219 ) -8.7636 0
535 620 ( 8.8536 1.42219 ) -8.8536 0
541 626 ( 8.8636 1.44219 ) -8.8636 0
542 627 ( 8.9136 1.47219 ) -8.9136 0
545 630 ( 8.9336 1.46219 ) -8.9336 0
547 632 ( 8.9936 1.51219 ) -8.9936 0
548 633 ( 9.0636 1.56219 ) -9.0636 0
551 636 ( 9.0836 1.59219 ) -9.0836 0
552 637 ( 9.1636 1.66219 ) -9.1636 0
555 640 ( 9.1936 1.67219 ) -9.1936 0
563 650 ( 9.5636 2.10219 ) -9.5636 0
569 662 ( 9.5936 2.11219 ) -9.5936 0
570 663 ( 9.8136 2.34219 ) -9.8136 0
573 666 ( 9.9336 2.49219 ) -9.9336 0
577 670 ( 10.0236 2.57219 ) -10.0236 0
592 697 ( 10.2236 2.51219 ) -10.2236 0
596 701 ( 10.4236 2.51219 ) -10.4236 0
597 702 ( 10.6236 2.48219 ) -10.6236 0
605 710 ( 10.6736 2.44219 ) -10.6736 0
606 712 ( 10.8236 2.32219 ) -10.8236 0
613 725 ( 10.8336 2.28219 ) -10.8336 0
614 726 ( 10.9136 2.20219 ) -10.9136 0
615 727 ( 11.0536 2.12219 ) -11.0536 0
641 767 ( 11.1436 2.21219 ) -11.1436 0
642 768 ( 11.4136 2.48219 ) -11.4136 0
652 778 ( 11.4436 2.53219 ) -11.4436 0
656 784 ( 11.4736 2.55219 ) -11.4736 0
660 788 ( 11.4836 2.54219 ) -11.4836 0
661 789 ( 11.5036 2.55219 ) -11.5036 0
662 790 ( 11.5236 2.58219 ) -11.5236 0
664 792 ( 11.5536 2.58219 ) -11.5536 0
665 793 ( 11.5936 2.60219 ) -11.5936 0
668 796 ( 11.6036 2.59219 ) -11.6036 0
669 797 ( 11.6436 2.60219 ) -11.6436 0
670 798 ( 11.7036 2.63219 ) -11.7036 0
672 800 ( 11.7536 2.63219 ) -11.7536 0
676 804 ( 11.7736 2.64219 ) -11.7736 0
689 822 ( 11.9736 2.59219 ) -11.9736 0
703 844 ( 11.9936 2.58219 ) -11.9936 0
BBE EVAL ( SOL ) OBJ CONS_H
709 852 ( 12.0536 2.55219 ) -12.0536 0
724 874 ( 12.0836 2.50219 ) -12.0836 0
725 875 ( 12.1736 2.35219 ) -12.1736 0
728 879 ( 12.2036 2.35219 ) -12.2036 0
729 880 ( 12.2836 2.28219 ) -12.2836 0
730 881 ( 12.3736 2.13219 ) -12.3736 0
732 883 ( 12.4836 2.06219 ) -12.4836 0
733 884 ( 12.6436 1.92219 ) -12.6436 0
734 885 ( 12.7336 1.77219 ) -12.7336 0
735 886 ( 12.9636 1.52219 ) -12.9636 0
738 889 ( 13.0136 1.51219 ) -13.0136 0
749 900 ( 13.0636 1.48219 ) -13.0636 0
750 901 ( 13.1136 1.46219 ) -13.1136 0
752 903 ( 13.2136 1.43219 ) -13.2136 0
753 904 ( 13.3136 1.39219 ) -13.3136 0
759 910 ( 13.3636 1.36219 ) -13.3636 0
763 916 ( 13.4136 1.35219 ) -13.4136 0
767 920 ( 13.4236 1.36219 ) -13.4236 0
768 921 ( 13.4536 1.36219 ) -13.4536 0
771 924 ( 13.4636 1.35219 ) -13.4636 0
773 926 ( 13.5036 1.36219 ) -13.5036 0
774 927 ( 13.5536 1.37219 ) -13.5536 0
781 936 ( 13.9936 1.78219 ) -13.9936 0
790 949 ( 14.2136 1.91219 ) -14.2136 0
835 1009 ( 14.2148 1.90899 ) -14.2148 0
839 1013 ( 14.2151 1.90319 ) -14.2151 0
840 1014 ( 14.2159 1.89869 ) -14.2159 0
841 1015 ( 14.2168 1.90129 ) -14.2168 0
842 1016 ( 14.2183 1.89879 ) -14.2183 0
843 1017 ( 14.2194 1.88849 ) -14.2194 0
844 1018 ( 14.2217 1.87829 ) -14.2217 0
845 1019 ( 14.2241 1.87839 ) -14.2241 0
846 1020 ( 14.2282 1.86829 ) -14.2282 0
847 1021 ( 14.2316 1.84779 ) -14.2316 0
848 1022 ( 14.2382 1.82229 ) -14.2382 0
849 1023 ( 14.2447 1.81229 ) -14.2447 0
850 1024 ( 14.2562 1.77929 ) -14.2562 0
851 1025 ( 14.2662 1.73329 ) -14.2662 0
853 1027 ( 14.2842 1.69029 ) -14.2842 0
857 1031 ( 14.2847 1.67799 ) -14.2847 0
BBE EVAL ( SOL ) OBJ CONS_H
861 1035 ( 14.2936 1.65959 ) -14.2936 0
865 1039 ( 14.2956 1.66119 ) -14.2956 0
866 1040 ( 14.3011 1.65279 ) -14.3011 0
871 1045 ( 14.3022 1.65529 ) -14.3022 0
872 1046 ( 14.3065 1.65319 ) -14.3065 0
873 1047 ( 14.3129 1.64389 ) -14.3129 0
874 1048 ( 14.322 1.63479 ) -14.322 0
875 1049 ( 14.3274 1.63519 ) -14.3274 0
876 1050 ( 14.3405 1.62639 ) -14.3405 0
877 1051 ( 14.356 1.60799 ) -14.356 0
878 1052 ( 14.3807 1.58539 ) -14.3807 0
879 1053 ( 14.3992 1.57699 ) -14.3992 0
880 1054 ( 14.4378 1.54809 ) -14.4378 0
881 1055 ( 14.478 1.50709 ) -14.478 0
883 1057 ( 14.5351 1.46979 ) -14.5351 0
887 1061 ( 14.5409 1.45859 ) -14.5409 0
891 1065 ( 14.568 1.44269 ) -14.568 0
895 1069 ( 14.5719 1.44429 ) -14.5719 0
896 1070 ( 14.5874 1.43719 ) -14.5874 0
897 1071 ( 14.6106 1.41969 ) -14.6106 0
898 1072 ( 14.6435 1.39949 ) -14.6435 0
899 1073 ( 14.6629 1.39399 ) -14.6629 0
907 1081 ( 14.6644 1.39629 ) -14.6644 0
908 1082 ( 14.6748 1.39469 ) -14.6748 0
909 1083 ( 14.6927 1.38689 ) -14.6927 0
910 1084 ( 14.7165 1.37949 ) -14.7165 0
911 1085 ( 14.7284 1.38019 ) -14.7284 0
912 1086 ( 14.7612 1.37329 ) -14.7612 0
913 1087 ( 14.8029 1.35809 ) -14.8029 0
914 1088 ( 14.867 1.33979 ) -14.867 0
928 1102 ( 14.917 1.37979 ) -14.917 0
929 1103 ( 14.967 1.38979 ) -14.967 0
932 1106 ( 14.997 1.42979 ) -14.997 0
933 1107 ( 15.067 1.47979 ) -15.067 0
934 1108 ( 15.137 1.48979 ) -15.137 0
935 1109 ( 15.257 1.54979 ) -15.257 0
936 1110 ( 15.357 1.63979 ) -15.357 0
937 1111 ( 15.557 1.76979 ) -15.557 0
942 1116 ( 15.627 1.83979 ) -15.627 0
951 1125 ( 15.697 1.89979 ) -15.697 0
BBE EVAL ( SOL ) OBJ CONS_H
955 1130 ( 15.727 1.93979 ) -15.727 0
956 1131 ( 15.757 1.97979 ) -15.757 0
958 1133 ( 15.817 2.04979 ) -15.817 0
959 1134 ( 15.877 2.12979 ) -15.877 0
961 1136 ( 15.997 2.28979 ) -15.997 0
962 1137 ( 16.117 2.44979 ) -16.117 0
969 1146 ( 16.177 2.51979 ) -16.177 0
974 1154 ( 16.207 2.55979 ) -16.207 0
987 1176 ( 16.267 2.45979 ) -16.267 0
995 1184 ( 16.277 2.43979 ) -16.277 0
A termination criterion is reached: Maximum number of blackbox evaluations (Eval Global) 1000
Best feasible solution: #167833 ( 16.277 2.43979 ) Evaluation OK f = -16.277000000000001023 h = 0
Best infeasible solution: Undefined.
Blackbox evaluations: 1000
Total model evaluations: 128524
Cache hits: 189
Total number of evaluations: 1189
Solution: [16.27700000000002, 2.42979026987685]Linear equality constraints
It is also possible to define linear equality constraints in a NomadProblem structure. NOMAD handles differently these constraints and solves the original problem on a reduced subspace. For more details we refer the reader to:
We consider the following example:
\[\begin{array}{rl} (BB) \ \ \ \displaystyle \min_{x \in \mathbb{R}^5} & (x_1 -1)^2 + (x_2 - x_3)^2 + (x_4 - x_5)^2\\ s.t. & x_1 + x_2 + x_3 + x_4 + x_5 = 5 \\ & x_3 -2 x_4 - 2 x_5 = -3\\ & -10 \leq x_1, x_2, x_3, x_4, x_5 \leq 10\\ \end{array}\]
This problem can be solved by Nomad the following way:
using NOMAD
# blackbox
function bb(x)
f = (x[1]- 1)^2 * (x[2] - x[3])^2 + (x[4] - x[5])^2
bb_outputs = [f]
success = true
count_eval = true
return (success, count_eval, bb_outputs)
end
# linear equality constraints
A = [1.0 1.0 1.0 1.0 1.0;
0.0 0.0 1.0 -2.0 -2.0]
b = [5.0; -3.0]
# Define blackbox
p = NomadProblem(5, 1, ["OBJ"], # the equality constraints are not counted in the outputs of the blackbox
bb,
lower_bound = -10.0 * ones(5),
upper_bound = 10.0 * ones(5),
A = A, b = b)
# Fix some options
p.options.max_bb_eval = 500
# Define starting points. It must satisfy A x = b.
x0 = [0.57186958424864897665429452899843;
4.9971472653643420613889247761108;
-1.3793445664086618762667058035731;
1.0403394252630473459930726676248;
-0.2300117084673765077695861691609]
# Solution
result = solve(p, x0)
println("Solution: ", result.x_best_feas)
println("Satisfy Ax = b: ", A * result.x_best_feas ≈ b)
println("And inside bound constraints: ", all(-10.0 .<= result.x_best_feas .<= 10.0))Computing variable bounds for the reduced problem ...Done
1 9.066529
6 3.831687
17 2.956805
24 1.091294
33 0.532633
56 0.449463
58 0.312224
59 0.150295
70 0.086348
74 0.000934
86 0.000421
94 0.000386
105 0.000113
107 0.0001
115 0.000001
135 0
A termination criterion is reached: No termination (all). Mesh minimum precision reached (Algo)
Best feasible solution: #18373 ( -0.082686 0.0259828 0.0256316 ) Evaluation OK f = 0 h = 0
Best infeasible solution: Undefined.
Blackbox evaluations: 363
Total model evaluations: 33173
Cache hits: 65
Total number of evaluations: 428
Solution: [0.9971576466583126, 1.0786149989159877, 0.9494849029504651, 0.9875467926028263, 0.9871956588724063]
Satisfy Ax = b: true
And inside bound constraints: trueThe reader can take a look at the test folder for more complex examples.
Trade-offs for computational time performance
The default parameters of NOMAD.jl closely follow the default parameters of the NOMAD software. More importantly, NOMAD tries to find the best solution according to the maximum budget of evaluations provided by the user.
However, it happens that the user has a cheap blackbox in terms of computational time and needs a solution in a "short" amount of time. In this case, the user can remove the default quadratic model options. Generally, the computation of a given solution will be faster, (i.e. NOMAD will evaluate more points in a given amount of time) at a potential detriment of the solution quality.
Let illustrate it on the following problem.
using NOMAD
# Objective
function f(x)
return sqrt((x[1]-20)^2 + (x[2]-1)^2)
end
# Constraints
function c(x)
constraints = [sin(x[1]) - 1/10 - x[2], x[2] - sin(x[1])]
return constraints
end
# Evaluator
function bb(x)
bb_outputs = [f(x); c(x)]
success = true
count_eval = true
return (success, count_eval, bb_outputs)
end
p = NomadProblem(2, 3, ["OBJ"; "PB"; "PB"], bb,
lower_bound=[0.0;0.0],
upper_bound=[20.0;4.0])
# Set some options
p.options.display_degree = 2
p.options.max_bb_eval = 1500
# Default
println("This is the default")
@time result_default = solve(p, [0.0;0.0])
# Deactivate quadratic models
p.options.quad_model_search = false # for the search step ..
p.options.direction_type = "ORTHO N+1 NEG" # .. and the computation of the n+1 direction.
# One can also deactivate the sorting of poll directions by quadratic models but it is not
# mandatory as it plays a minimal role in the computational performance.
p.options.eval_queue_sort = "DIR_LAST_SUCCESS"
println("Now with no quadratic models")
@time result_with_no_quad_models = solve(p, [0.0;0.0])(x_best_feas = [3.14159221500764, 7.0e-7], bbo_best_feas = [16.88804, -0.1, 0.0], x_best_inf = nothing, bbo_best_inf = nothing)Note that the deactivation of quadratic models allows the solver to return a solution in a shorter time.
A good rule of thumb is to keep quadratic models if the blackbox possesses smoothness properties even if the derivatives are not available.
For more details about the parameters used in this section, we refer the reader to: