4bbaf12b |
1 | // Created on: 2014-01-20 |
2 | // Created by: Alexaner Malyshev |
4b65fc77 |
3 | // Copyright (c) 2014-2015 OPEN CASCADE SAS |
4bbaf12b |
4 | // |
5 | // This file is part of Open CASCADE Technology software library. |
6 | // |
7 | // This library is free software; you can redistribute it and/or modify it under |
8 | // the terms of the GNU Lesser General Public License version 2.1 as published |
9 | // by the Free Software Foundation, with special exception defined in the file |
10 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT |
11 | // distribution for complete text of the license and disclaimer of any warranty. |
12 | // |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement |
15 | |
16 | #include <math_GlobOptMin.hxx> |
17 | |
18 | #include <math_BFGS.hxx> |
19 | #include <math_Matrix.hxx> |
20 | #include <math_MultipleVarFunctionWithGradient.hxx> |
21 | #include <math_MultipleVarFunctionWithHessian.hxx> |
22 | #include <math_NewtonMinimum.hxx> |
23 | #include <math_Powell.hxx> |
4bbaf12b |
24 | #include <Standard_Integer.hxx> |
25 | #include <Standard_Real.hxx> |
e8746a26 |
26 | #include <Precision.hxx> |
4bbaf12b |
27 | |
246c7a75 |
28 | //======================================================================= |
29 | //function : DistanceToBorder |
30 | //purpose : |
31 | //======================================================================= |
32 | static Standard_Real DistanceToBorder(const math_Vector & theX, |
33 | const math_Vector & theMin, |
34 | const math_Vector & theMax) |
35 | { |
36 | Standard_Real aDist = RealLast(); |
37 | |
38 | for (Standard_Integer anIdx = theMin.Lower(); anIdx <= theMin.Upper(); ++anIdx) |
39 | { |
40 | const Standard_Real aDist1 = Abs (theX(anIdx) - theMin(anIdx)); |
41 | const Standard_Real aDist2 = Abs (theX(anIdx) - theMax(anIdx)); |
42 | |
43 | aDist = Min (aDist, Min (aDist1, aDist2)); |
44 | } |
45 | |
46 | return aDist; |
47 | } |
48 | |
4bbaf12b |
49 | |
50 | //======================================================================= |
51 | //function : math_GlobOptMin |
52 | //purpose : Constructor |
53 | //======================================================================= |
54 | math_GlobOptMin::math_GlobOptMin(math_MultipleVarFunction* theFunc, |
55 | const math_Vector& theA, |
56 | const math_Vector& theB, |
5493d334 |
57 | const Standard_Real theC, |
58 | const Standard_Real theDiscretizationTol, |
59 | const Standard_Real theSameTol) |
4bbaf12b |
60 | : myN(theFunc->NbVariables()), |
61 | myA(1, myN), |
62 | myB(1, myN), |
63 | myGlobA(1, myN), |
64 | myGlobB(1, myN), |
1907fb9a |
65 | myIsConstLocked(Standard_False), |
4bbaf12b |
66 | myX(1, myN), |
67 | myTmp(1, myN), |
5493d334 |
68 | myV(1, myN), |
3f733bb1 |
69 | myMaxV(1, myN), |
4b65fc77 |
70 | myCellSize(0, myN - 1), |
5333268d |
71 | myFilter(theFunc->NbVariables()), |
72 | myCont(2) |
4bbaf12b |
73 | { |
74 | Standard_Integer i; |
75 | |
76 | myFunc = theFunc; |
77 | myC = theC; |
1907fb9a |
78 | myInitC = theC; |
78e7cada |
79 | myIsFindSingleSolution = Standard_False; |
836d7b64 |
80 | myFunctionalMinimalValue = -Precision::Infinite(); |
4bbaf12b |
81 | myZ = -1; |
82 | mySolCount = 0; |
83 | |
84 | for(i = 1; i <= myN; i++) |
85 | { |
86 | myGlobA(i) = theA(i); |
87 | myGlobB(i) = theB(i); |
88 | |
89 | myA(i) = theA(i); |
90 | myB(i) = theB(i); |
91 | } |
92 | |
5493d334 |
93 | for(i = 1; i <= myN; i++) |
94 | { |
95 | myMaxV(i) = (myB(i) - myA(i)) / 3.0; |
96 | } |
97 | |
98 | myTol = theDiscretizationTol; |
99 | mySameTol = theSameTol; |
100 | |
4b65fc77 |
101 | const Standard_Integer aMaxSquareSearchSol = 200; |
102 | Standard_Integer aSolNb = Standard_Integer(Pow(3.0, Standard_Real(myN))); |
103 | myMinCellFilterSol = Max(2 * aSolNb, aMaxSquareSearchSol); |
104 | initCellSize(); |
1907fb9a |
105 | ComputeInitSol(); |
4b65fc77 |
106 | |
4bbaf12b |
107 | myDone = Standard_False; |
108 | } |
109 | |
110 | //======================================================================= |
111 | //function : SetGlobalParams |
1907fb9a |
112 | //purpose : Set parameters without memory allocation. |
4bbaf12b |
113 | //======================================================================= |
114 | void math_GlobOptMin::SetGlobalParams(math_MultipleVarFunction* theFunc, |
115 | const math_Vector& theA, |
116 | const math_Vector& theB, |
5493d334 |
117 | const Standard_Real theC, |
118 | const Standard_Real theDiscretizationTol, |
119 | const Standard_Real theSameTol) |
4bbaf12b |
120 | { |
121 | Standard_Integer i; |
122 | |
123 | myFunc = theFunc; |
124 | myC = theC; |
1907fb9a |
125 | myInitC = theC; |
4bbaf12b |
126 | myZ = -1; |
127 | mySolCount = 0; |
128 | |
129 | for(i = 1; i <= myN; i++) |
130 | { |
131 | myGlobA(i) = theA(i); |
132 | myGlobB(i) = theB(i); |
133 | |
134 | myA(i) = theA(i); |
135 | myB(i) = theB(i); |
136 | } |
137 | |
3f733bb1 |
138 | for(i = 1; i <= myN; i++) |
139 | { |
140 | myMaxV(i) = (myB(i) - myA(i)) / 3.0; |
141 | } |
142 | |
5493d334 |
143 | myTol = theDiscretizationTol; |
144 | mySameTol = theSameTol; |
145 | |
4b65fc77 |
146 | initCellSize(); |
1907fb9a |
147 | ComputeInitSol(); |
4b65fc77 |
148 | |
4bbaf12b |
149 | myDone = Standard_False; |
150 | } |
151 | |
152 | //======================================================================= |
153 | //function : SetLocalParams |
1907fb9a |
154 | //purpose : Set parameters without memory allocation. |
4bbaf12b |
155 | //======================================================================= |
156 | void math_GlobOptMin::SetLocalParams(const math_Vector& theLocalA, |
157 | const math_Vector& theLocalB) |
158 | { |
159 | Standard_Integer i; |
160 | |
161 | myZ = -1; |
4bbaf12b |
162 | for(i = 1; i <= myN; i++) |
163 | { |
164 | myA(i) = theLocalA(i); |
165 | myB(i) = theLocalB(i); |
166 | } |
167 | |
5493d334 |
168 | for(i = 1; i <= myN; i++) |
169 | { |
170 | myMaxV(i) = (myB(i) - myA(i)) / 3.0; |
171 | } |
172 | |
4bbaf12b |
173 | myDone = Standard_False; |
174 | } |
175 | |
5493d334 |
176 | //======================================================================= |
177 | //function : SetTol |
178 | //purpose : Set algorithm tolerances. |
179 | //======================================================================= |
180 | void math_GlobOptMin::SetTol(const Standard_Real theDiscretizationTol, |
181 | const Standard_Real theSameTol) |
182 | { |
183 | myTol = theDiscretizationTol; |
184 | mySameTol = theSameTol; |
185 | } |
186 | |
187 | //======================================================================= |
188 | //function : GetTol |
189 | //purpose : Get algorithm tolerances. |
190 | //======================================================================= |
191 | void math_GlobOptMin::GetTol(Standard_Real& theDiscretizationTol, |
192 | Standard_Real& theSameTol) |
193 | { |
194 | theDiscretizationTol = myTol; |
195 | theSameTol = mySameTol; |
196 | } |
197 | |
4bbaf12b |
198 | //======================================================================= |
199 | //function : Perform |
200 | //purpose : Compute Global extremum point |
201 | //======================================================================= |
202 | // In this algo indexes started from 1, not from 0. |
78e7cada |
203 | void math_GlobOptMin::Perform(const Standard_Boolean isFindSingleSolution) |
4bbaf12b |
204 | { |
246c7a75 |
205 | myDone = Standard_False; |
4bbaf12b |
206 | |
207 | // Compute parameters range |
208 | Standard_Real minLength = RealLast(); |
209 | Standard_Real maxLength = RealFirst(); |
246c7a75 |
210 | for(Standard_Integer i = 1; i <= myN; i++) |
4bbaf12b |
211 | { |
212 | Standard_Real currentLength = myB(i) - myA(i); |
213 | if (currentLength < minLength) |
214 | minLength = currentLength; |
215 | if (currentLength > maxLength) |
216 | maxLength = currentLength; |
246c7a75 |
217 | |
218 | myV(i) = 0.0; |
4bbaf12b |
219 | } |
220 | |
e8746a26 |
221 | if (minLength < Precision::PConfusion()) |
222 | { |
223 | #ifdef OCCT_DEBUG |
04232180 |
224 | std::cout << "math_GlobOptMin::Perform(): Degenerated parameters space" << std::endl; |
e8746a26 |
225 | #endif |
226 | |
227 | return; |
228 | } |
229 | |
1907fb9a |
230 | if (!myIsConstLocked) |
231 | { |
232 | // Compute initial value for myC. |
233 | computeInitialValues(); |
234 | } |
e8746a26 |
235 | |
797d11c6 |
236 | myE1 = minLength * myTol; |
237 | myE2 = maxLength * myTol; |
78e7cada |
238 | |
239 | myIsFindSingleSolution = isFindSingleSolution; |
240 | if (isFindSingleSolution) |
241 | { |
1907fb9a |
242 | // Run local optimization if current value better than optimal. |
78e7cada |
243 | myE3 = 0.0; |
244 | } |
797d11c6 |
245 | else |
78e7cada |
246 | { |
247 | if (myC > 1.0) |
248 | myE3 = - maxLength * myTol / 4.0; |
249 | else |
250 | myE3 = - maxLength * myTol * myC / 4.0; |
251 | } |
4bbaf12b |
252 | |
1907fb9a |
253 | // Search single solution and current solution in its neighborhood. |
836d7b64 |
254 | if (CheckFunctionalStopCriteria()) |
255 | { |
256 | myDone = Standard_True; |
257 | return; |
258 | } |
259 | |
1907fb9a |
260 | myLastStep = 0.0; |
4b65fc77 |
261 | isFirstCellFilterInvoke = Standard_True; |
4bbaf12b |
262 | computeGlobalExtremum(myN); |
263 | |
264 | myDone = Standard_True; |
4bbaf12b |
265 | } |
266 | |
267 | //======================================================================= |
268 | //function : computeLocalExtremum |
269 | //purpose : |
270 | //======================================================================= |
271 | Standard_Boolean math_GlobOptMin::computeLocalExtremum(const math_Vector& thePnt, |
272 | Standard_Real& theVal, |
273 | math_Vector& theOutPnt) |
274 | { |
275 | Standard_Integer i; |
276 | |
277 | //Newton method |
5333268d |
278 | if (myCont >= 2 && |
279 | dynamic_cast<math_MultipleVarFunctionWithHessian*>(myFunc)) |
4bbaf12b |
280 | { |
747f90db |
281 | math_MultipleVarFunctionWithHessian* aTmp = |
4bbaf12b |
282 | dynamic_cast<math_MultipleVarFunctionWithHessian*> (myFunc); |
747f90db |
283 | math_NewtonMinimum newtonMinimum(*aTmp); |
91806b90 |
284 | newtonMinimum.SetBoundary(myGlobA, myGlobB); |
747f90db |
285 | newtonMinimum.Perform(*aTmp, thePnt); |
859a47c3 |
286 | |
4bbaf12b |
287 | if (newtonMinimum.IsDone()) |
288 | { |
289 | newtonMinimum.Location(theOutPnt); |
290 | theVal = newtonMinimum.Minimum(); |
f79b19a1 |
291 | |
292 | if (isInside(theOutPnt)) |
293 | return Standard_True; |
4bbaf12b |
294 | } |
f79b19a1 |
295 | } |
4bbaf12b |
296 | |
297 | // BFGS method used. |
5333268d |
298 | if (myCont >= 1 && |
299 | dynamic_cast<math_MultipleVarFunctionWithGradient*>(myFunc)) |
4bbaf12b |
300 | { |
747f90db |
301 | math_MultipleVarFunctionWithGradient* aTmp = |
4bbaf12b |
302 | dynamic_cast<math_MultipleVarFunctionWithGradient*> (myFunc); |
747f90db |
303 | math_BFGS bfgs(aTmp->NbVariables()); |
f79b19a1 |
304 | bfgs.SetBoundary(myGlobA, myGlobB); |
747f90db |
305 | bfgs.Perform(*aTmp, thePnt); |
f79b19a1 |
306 | |
4bbaf12b |
307 | if (bfgs.IsDone()) |
308 | { |
309 | bfgs.Location(theOutPnt); |
310 | theVal = bfgs.Minimum(); |
f79b19a1 |
311 | |
312 | if (isInside(theOutPnt)) |
313 | return Standard_True; |
4bbaf12b |
314 | } |
f79b19a1 |
315 | } |
4bbaf12b |
316 | |
317 | // Powell method used. |
318 | if (dynamic_cast<math_MultipleVarFunction*>(myFunc)) |
319 | { |
320 | math_Matrix m(1, myN, 1, myN, 0.0); |
321 | for(i = 1; i <= myN; i++) |
aa1b48c7 |
322 | m(i, i) = 1.0; |
4bbaf12b |
323 | |
859a47c3 |
324 | math_Powell powell(*myFunc, 1e-10); |
325 | powell.Perform(*myFunc, thePnt, m); |
4bbaf12b |
326 | |
327 | if (powell.IsDone()) |
328 | { |
329 | powell.Location(theOutPnt); |
330 | theVal = powell.Minimum(); |
f79b19a1 |
331 | |
332 | if (isInside(theOutPnt)) |
333 | return Standard_True; |
4bbaf12b |
334 | } |
4bbaf12b |
335 | } |
336 | |
f79b19a1 |
337 | return Standard_False; |
4bbaf12b |
338 | } |
339 | |
797d11c6 |
340 | //======================================================================= |
341 | //function : computeInitialValues |
342 | //purpose : |
343 | //======================================================================= |
344 | void math_GlobOptMin::computeInitialValues() |
345 | { |
35dced1c |
346 | const Standard_Real aMinLC = 0.01; |
347 | const Standard_Real aMaxLC = 1000.; |
348 | const Standard_Real aMinEps = 0.1; |
349 | const Standard_Real aMaxEps = 100.; |
797d11c6 |
350 | Standard_Integer i; |
351 | math_Vector aCurrPnt(1, myN); |
352 | math_Vector aBestPnt(1, myN); |
e8746a26 |
353 | math_Vector aParamStep(1, myN); |
797d11c6 |
354 | Standard_Real aCurrVal = RealLast(); |
797d11c6 |
355 | |
1907fb9a |
356 | // Lipchitz const approximation. |
e8746a26 |
357 | Standard_Real aLipConst = 0.0, aPrevValDiag, aPrevValProj; |
797d11c6 |
358 | Standard_Integer aPntNb = 13; |
e8746a26 |
359 | myFunc->Value(myA, aPrevValDiag); |
360 | aPrevValProj = aPrevValDiag; |
797d11c6 |
361 | Standard_Real aStep = (myB - myA).Norm() / aPntNb; |
e8746a26 |
362 | aParamStep = (myB - myA) / aPntNb; |
797d11c6 |
363 | for(i = 1; i <= aPntNb; i++) |
364 | { |
e8746a26 |
365 | aCurrPnt = myA + aParamStep * i; |
797d11c6 |
366 | |
e8746a26 |
367 | // Walk over diagonal. |
368 | myFunc->Value(aCurrPnt, aCurrVal); |
369 | aLipConst = Max (Abs(aCurrVal - aPrevValDiag), aLipConst); |
370 | aPrevValDiag = aCurrVal; |
797d11c6 |
371 | |
e8746a26 |
372 | // Walk over diag in projected space aPnt(1) = myA(1) = const. |
373 | aCurrPnt(1) = myA(1); |
374 | myFunc->Value(aCurrPnt, aCurrVal); |
375 | aLipConst = Max (Abs(aCurrVal - aPrevValProj), aLipConst); |
376 | aPrevValProj = aCurrVal; |
797d11c6 |
377 | } |
e8746a26 |
378 | |
1907fb9a |
379 | myC = myInitC; |
e8746a26 |
380 | aLipConst *= Sqrt(myN) / aStep; |
35dced1c |
381 | if (aLipConst < myC * aMinEps) |
382 | myC = Max(aLipConst * aMinEps, aMinLC); |
383 | else if (aLipConst > myC * aMaxEps) |
384 | myC = Min(myC * aMaxEps, aMaxLC); |
1907fb9a |
385 | |
386 | // Clear all solutions except one. |
387 | if (myY.Size() != myN) |
797d11c6 |
388 | { |
1907fb9a |
389 | for(i = 1; i <= myN; i++) |
390 | aBestPnt(i) = myY(i); |
391 | myY.Clear(); |
392 | for(i = 1; i <= myN; i++) |
393 | myY.Append(aBestPnt(i)); |
797d11c6 |
394 | } |
1907fb9a |
395 | mySolCount = 1; |
797d11c6 |
396 | } |
397 | |
4bbaf12b |
398 | //======================================================================= |
399 | //function : ComputeGlobalExtremum |
400 | //purpose : |
401 | //======================================================================= |
402 | void math_GlobOptMin::computeGlobalExtremum(Standard_Integer j) |
403 | { |
404 | Standard_Integer i; |
246c7a75 |
405 | Standard_Real d = RealLast(), aPrevVal; // Functional in original and moved points. |
4bbaf12b |
406 | Standard_Real val = RealLast(); // Local extrema computed in moved point. |
3f733bb1 |
407 | Standard_Real aStepBestValue = RealLast(); |
3f733bb1 |
408 | math_Vector aStepBestPoint(1, myN); |
246c7a75 |
409 | Standard_Boolean isInside = Standard_False, |
410 | isReached = Standard_False; |
4bbaf12b |
411 | |
246c7a75 |
412 | Standard_Real r1, r2, r; |
1907fb9a |
413 | |
246c7a75 |
414 | for(myX(j) = myA(j) + myE1; !isReached; myX(j) += myV(j)) |
4bbaf12b |
415 | { |
416 | if (myX(j) > myB(j)) |
debc95ee |
417 | { |
4bbaf12b |
418 | myX(j) = myB(j); |
debc95ee |
419 | isReached = Standard_True; |
420 | } |
4bbaf12b |
421 | |
836d7b64 |
422 | if (CheckFunctionalStopCriteria()) |
423 | return; // Best possible value is obtained. |
424 | |
4bbaf12b |
425 | if (j == 1) |
426 | { |
427 | isInside = Standard_False; |
246c7a75 |
428 | aPrevVal = d; |
4bbaf12b |
429 | myFunc->Value(myX, d); |
246c7a75 |
430 | r1 = (d + myZ * myC * myLastStep - myF) * myZ; // Evtushenko estimation. |
431 | r2 = ((d + aPrevVal - myC * myLastStep) * 0.5 - myF) * myZ; // Shubert / Piyavsky estimation. |
432 | r = Min(r1, r2); |
4bbaf12b |
433 | if(r > myE3) |
434 | { |
246c7a75 |
435 | Standard_Real aSaveParam = myX(1); |
436 | |
437 | // Piyavsky midpoint estimation. |
438 | Standard_Real aParam = (2 * myX(1) - myV(1) ) * 0.5 + (aPrevVal - d) * 0.5 / myC; |
439 | if (Precision::IsInfinite(aPrevVal)) |
440 | aParam = myX(1) - myV(1) * 0.5; // Protection from upper dimension step. |
441 | |
442 | myX(1) = aParam; |
443 | Standard_Real aVal = 0; |
444 | myFunc->Value(myX, aVal); |
445 | myX(1) = aSaveParam; |
446 | |
447 | if ( (aVal < d && aVal < aPrevVal) || |
448 | DistanceToBorder(myX, myA, myB) < myE1 ) // Condition optimization case near the border. |
449 | { |
450 | isInside = computeLocalExtremum(myX, val, myTmp); |
451 | } |
4bbaf12b |
452 | } |
3f733bb1 |
453 | aStepBestValue = (isInside && (val < d))? val : d; |
454 | aStepBestPoint = (isInside && (val < d))? myTmp : myX; |
4bbaf12b |
455 | |
78e7cada |
456 | // Solutions are close to each other |
457 | // and it is allowed to have more than one solution. |
458 | if (Abs(aStepBestValue - myF) < mySameTol * 0.01 && |
459 | !myIsFindSingleSolution) |
4bbaf12b |
460 | { |
3f733bb1 |
461 | if (!isStored(aStepBestPoint)) |
4bbaf12b |
462 | { |
3f733bb1 |
463 | if ((aStepBestValue - myF) * myZ > 0.0) |
464 | myF = aStepBestValue; |
4bbaf12b |
465 | for(i = 1; i <= myN; i++) |
3f733bb1 |
466 | myY.Append(aStepBestPoint(i)); |
4bbaf12b |
467 | mySolCount++; |
468 | } |
469 | } |
470 | |
78e7cada |
471 | // New best solution: |
472 | // new point is out of (mySameTol * 0.01) surrounding or |
473 | // new point is better than old + single point search. |
474 | Standard_Real aFunctionalDelta = (aStepBestValue - myF) * myZ; |
475 | if (aFunctionalDelta > mySameTol * 0.01 || |
476 | (aFunctionalDelta > 0.0 && myIsFindSingleSolution)) |
4bbaf12b |
477 | { |
478 | mySolCount = 0; |
3f733bb1 |
479 | myF = aStepBestValue; |
4bbaf12b |
480 | myY.Clear(); |
481 | for(i = 1; i <= myN; i++) |
3f733bb1 |
482 | myY.Append(aStepBestPoint(i)); |
4bbaf12b |
483 | mySolCount++; |
4b65fc77 |
484 | |
485 | isFirstCellFilterInvoke = Standard_True; |
4bbaf12b |
486 | } |
487 | |
836d7b64 |
488 | if (CheckFunctionalStopCriteria()) |
489 | return; // Best possible value is obtained. |
490 | |
1907fb9a |
491 | myV(1) = Min(myE2 + Abs(myF - d) / myC, myMaxV(1)); |
492 | myLastStep = myV(1); |
4bbaf12b |
493 | } |
494 | else |
495 | { |
496 | myV(j) = RealLast() / 2.0; |
497 | computeGlobalExtremum(j - 1); |
3f733bb1 |
498 | |
499 | // Nullify steps on lower dimensions. |
500 | for(i = 1; i < j; i++) |
501 | myV(i) = 0.0; |
4bbaf12b |
502 | } |
3f733bb1 |
503 | if (j < myN) |
4bbaf12b |
504 | { |
246c7a75 |
505 | Standard_Real aUpperDimStep = Max(myV(j), myE2); |
3f733bb1 |
506 | if (myV(j + 1) > aUpperDimStep) |
507 | { |
508 | if (aUpperDimStep > myMaxV(j + 1)) // Case of too big step. |
509 | myV(j + 1) = myMaxV(j + 1); |
510 | else |
511 | myV(j + 1) = aUpperDimStep; |
512 | } |
4bbaf12b |
513 | } |
514 | } |
515 | } |
516 | |
517 | //======================================================================= |
518 | //function : IsInside |
519 | //purpose : |
520 | //======================================================================= |
521 | Standard_Boolean math_GlobOptMin::isInside(const math_Vector& thePnt) |
522 | { |
523 | Standard_Integer i; |
524 | |
525 | for(i = 1; i <= myN; i++) |
526 | { |
527 | if (thePnt(i) < myGlobA(i) || thePnt(i) > myGlobB(i)) |
528 | return Standard_False; |
529 | } |
530 | |
531 | return Standard_True; |
532 | } |
533 | //======================================================================= |
534 | //function : IsStored |
535 | //purpose : |
536 | //======================================================================= |
537 | Standard_Boolean math_GlobOptMin::isStored(const math_Vector& thePnt) |
538 | { |
539 | Standard_Integer i,j; |
540 | Standard_Boolean isSame = Standard_True; |
20a216fe |
541 | math_Vector aTol(1, myN); |
542 | aTol = (myB - myA) * mySameTol; |
4bbaf12b |
543 | |
4b65fc77 |
544 | // C1 * n^2 = C2 * 3^dim * n |
545 | if (mySolCount < myMinCellFilterSol) |
4bbaf12b |
546 | { |
4b65fc77 |
547 | for(i = 0; i < mySolCount; i++) |
4bbaf12b |
548 | { |
4b65fc77 |
549 | isSame = Standard_True; |
550 | for(j = 1; j <= myN; j++) |
4bbaf12b |
551 | { |
4b65fc77 |
552 | if ((Abs(thePnt(j) - myY(i * myN + j))) > aTol(j)) |
553 | { |
554 | isSame = Standard_False; |
555 | break; |
556 | } |
4bbaf12b |
557 | } |
4b65fc77 |
558 | if (isSame == Standard_True) |
559 | return Standard_True; |
4bbaf12b |
560 | } |
4b65fc77 |
561 | } |
562 | else |
563 | { |
50bc8f96 |
564 | NCollection_CellFilter_Inspector anInspector(myN, Precision::PConfusion()); |
4b65fc77 |
565 | if (isFirstCellFilterInvoke) |
566 | { |
567 | myFilter.Reset(myCellSize); |
4bbaf12b |
568 | |
4b65fc77 |
569 | // Copy initial data into cell filter. |
570 | for(Standard_Integer aSolIdx = 0; aSolIdx < mySolCount; aSolIdx++) |
571 | { |
572 | math_Vector aVec(1, myN); |
573 | for(Standard_Integer aSolDim = 1; aSolDim <= myN; aSolDim++) |
574 | aVec(aSolDim) = myY(aSolIdx * myN + aSolDim); |
575 | |
576 | myFilter.Add(aVec, aVec); |
577 | } |
578 | } |
579 | |
580 | isFirstCellFilterInvoke = Standard_False; |
581 | |
582 | math_Vector aLow(1, myN), anUp(1, myN); |
583 | anInspector.Shift(thePnt, myCellSize, aLow, anUp); |
584 | |
585 | anInspector.ClearFind(); |
586 | anInspector.SetCurrent(thePnt); |
587 | myFilter.Inspect(aLow, anUp, anInspector); |
588 | if (!anInspector.isFind()) |
589 | { |
590 | // Point is out of close cells, add new one. |
591 | myFilter.Add(thePnt, thePnt); |
592 | } |
4bbaf12b |
593 | } |
594 | return Standard_False; |
595 | } |
596 | |
4bbaf12b |
597 | //======================================================================= |
598 | //function : Points |
599 | //purpose : |
600 | //======================================================================= |
601 | void math_GlobOptMin::Points(const Standard_Integer theIndex, math_Vector& theSol) |
602 | { |
603 | Standard_Integer j; |
604 | |
605 | for(j = 1; j <= myN; j++) |
606 | theSol(j) = myY((theIndex - 1) * myN + j); |
607 | } |
4b65fc77 |
608 | |
609 | //======================================================================= |
610 | //function : initCellSize |
611 | //purpose : |
612 | //======================================================================= |
613 | void math_GlobOptMin::initCellSize() |
614 | { |
615 | for(Standard_Integer anIdx = 1; anIdx <= myN; anIdx++) |
616 | { |
617 | myCellSize(anIdx - 1) = (myGlobB(anIdx) - myGlobA(anIdx)) |
618 | * Precision::PConfusion() / (2.0 * Sqrt(2.0)); |
619 | } |
620 | } |
836d7b64 |
621 | |
622 | //======================================================================= |
623 | //function : CheckFunctionalStopCriteria |
624 | //purpose : |
625 | //======================================================================= |
626 | Standard_Boolean math_GlobOptMin::CheckFunctionalStopCriteria() |
627 | { |
1907fb9a |
628 | // Search single solution and current solution in its neighborhood. |
836d7b64 |
629 | if (myIsFindSingleSolution && |
630 | Abs (myF - myFunctionalMinimalValue) < mySameTol * 0.01) |
631 | return Standard_True; |
632 | |
633 | return Standard_False; |
634 | } |
1907fb9a |
635 | |
636 | //======================================================================= |
637 | //function : ComputeInitSol |
638 | //purpose : |
639 | //======================================================================= |
640 | void math_GlobOptMin::ComputeInitSol() |
641 | { |
642 | Standard_Real aCurrVal, aBestVal; |
643 | math_Vector aCurrPnt(1, myN); |
644 | math_Vector aBestPnt(1, myN); |
645 | math_Vector aParamStep(1, myN); |
646 | // Check functional value in midpoint, lower and upper border points and |
647 | // in each point try to perform local optimization. |
648 | aBestPnt = (myGlobA + myGlobB) * 0.5; |
649 | myFunc->Value(aBestPnt, aBestVal); |
650 | |
651 | Standard_Integer i; |
652 | for(i = 1; i <= 3; i++) |
653 | { |
654 | aCurrPnt = myA + (myB - myA) * (i - 1) / 2.0; |
655 | |
656 | if(computeLocalExtremum(aCurrPnt, aCurrVal, aCurrPnt)) |
657 | { |
658 | // Local search tries to find better solution than current point. |
659 | if (aCurrVal < aBestVal) |
660 | { |
661 | aBestVal = aCurrVal; |
662 | aBestPnt = aCurrPnt; |
663 | } |
664 | } |
665 | } |
666 | |
667 | myF = aBestVal; |
668 | myY.Clear(); |
669 | for(i = 1; i <= myN; i++) |
670 | myY.Append(aBestPnt(i)); |
671 | mySolCount = 1; |
1907fb9a |
672 | } |