Задачи оптимизации в евклидовом пространствеРефераты >> Математика >> Задачи оптимизации в евклидовом пространстве
,
где 
- положительная постоянная, называемая овражным шагом. Из точки
,
которая, вообще говоря. Находится на «склоне оврага», производят спуск с помощью градиентного метода и определяют следующую точку 
на «дне оврага».
Если уже известны точки 
, то из точки 
(12)
Совершают спуск с помощью градиентного метода и находят следующую точку 
на «дне оврага».
Величина овражного шага 
подбирается эмпирически с учетом информации о минимизирующей функции, получаемой в ходе поиска минимума. От правильного выбора существенно зависит скорость сходимости метода. Если шаг велик, то на крутых поворотах «оврага» точки 
могут слишком удаляться от «дна оврага» и спуск из точки в точку 
может потребовать большого объема вычислений. Кроме того, при больших на крутых поворотах может произойти выброс точки из «оврага», и правильное направление поиска точки минимума будет потеряно. Если шаг слишком мал, то поиск может очень замедлиться и эффект от применения овражного метода может стать незначительным.
Эффективность овражного метода может существенно возрасти, если величину овражного шага выбирать переменной, реагирующей на повороты «оврага» с тем, чтобы: 1) по возможности быстрее проходить прямолинейные участки на «дне оврага» за счет увеличения овражного шага: 2) на крутых поворотах «оврага» избежать выброса из «оврага» за счет уменьшения овражного шага; 3) добиться по возможности меньшего отклонения точек от «дна оврага» и тем самым сократить объем вычислений, требуемый для градиентного спуска из точки в точку 
. Интуитивно ясно, что для правильной реакции на поворот «оврага» надо учитывать «кривизну дна оврага», причем информацию о «кривизне» желательно получить, опираясь на результаты предыдущих итераций овражного метода.
Пример. Минимизировать в 
функцию 
методом градиентного спуска, завершив вычисления при 
, 
.
Решение. Выбрав начальное приближение 
и 
, построим последовательность 
, 
, 
, записывая результаты в таблицу.
Таблица 1.
| k | x1k | x2k | f(xk) | df(xk)/dx1 | df(xk)/dx2 | αk | Примечание |
|
0 | 1 | 0 | 5,436564 | 10,87313 |
-5,43656 | 0,5 |
Условие выполнено |
|
1 | 0,5 | -0,5 | 3,397852 | 8,834416 |
-6,11613 | 0,5 |
Условие выполнено |
|
2 | -3,91721 | 2,558067 | 0,084126 | 0,064168 |
-0,0532 | 0,5 |
Условие выполнено |
|
3 | -3,94929 | 2,584668 | 0,080717 | 0,061726 |
-0,05131 | 0,5 |
Условие выполнено |
|
4 | -3,98015 | 2,610321 | 0,077553 | 0,059451 |
-0,04953 | 0,5 |
Условие выполнено |
|
5 | -4,00988 | 2,635088 | 0,074612 | 0,057328 |
-0,04787 | 0,5 |
Условие выполнено |
|
6 | -4,03854 | 2,659025 | 0,07187 | 0,055342 |
-0,04631 | 0,5 |
Условие выполнено |
|
7 | -4,06621 | 2,682181 | 0,069309 | 0,053481 |
-0,04484 | 0,5 |
Условие выполнено |
|
8 | -4,09296 | 2,704603 | 0,066913 | 0,051734 |
-0,04346 | 0,5 |
Условие выполнено |
|
9 | -4,11882 | 2,726333 | 0,064666 | 0,050091 |
-0,04216 | 0,5 |
Условие выполнено |
|
10 | -4,14387 | 2,747412 | 0,062555 | 0,048544 |
-0,04092 | 0,5 |
Условие выполнено |
|
11 | -4,16814 | 2,767874 | 0,060569 | 0,047084 |
-0,03976 | 0,5 |
Условие выполнено |
|
12 | -4,19168 | 2,787753 | 0,058698 | 0,045704 |
-0,03865 | 0,5 |
Условие выполнено |
|
13 | -4,21453 | 2,807079 | 0,056931 | 0,044399 |
-0,0376 | 0,5 |
Условие выполнено |
|
14 | -4,23673 | 2,825882 | 0,055262 | 0,043163 |
-0,03661 | 0,5 |
Условие выполнено |
|
15 | -4,25831 | 2,844186 | 0,053682 | 0,04199 |
-0,03566 | 0,5 |
Условие выполнено |
|
16 | -4,27931 | 2,862017 | 0,052184 | 0,040876 |
-0,03476 | 0,5 |
Условие выполнено |
|
17 | -4,29975 | 2,879398 | 0,050763 | 0,039817 |
-0,0339 | 0,5 |
Условие выполнено |
|
18 | -4,31966 | 2,896349 | 0,049412 | 0,038809 |
-0,03308 | 0,5 |
Условие выполнено |
|
19 | -4,33906 | 2,912891 | 0,048128 | 0,037848 |
-0,0323 | 0,5 |
Условие выполнено |
|
20 | -4,35798 | 2,929041 | 0,046905 | 0,036931 |
-0,03155 | 0,5 |
Условие выполнено |
|
21 | -4,37645 | 2,944818 | 0,045739 | 0,036055 |
-0,03084 | 0,5 |
Условие выполнено |
|
22 | -4,39448 | 2,960237 | 0,044626 | 0,035218 |
-0,03015 | 0,5 |
Условие выполнено |
|
23 | -4,41209 | 2,975313 | 0,043563 | 0,034418 |
-0,0295 | 0,5 |
Условие выполнено |
|
24 | -4,4293 | 2,990061 | 0,042547 | 0,033651 |
-0,02887 | 0,5 |
Условие выполнено |
|
25 | -4,44612 | 3,004495 | 0,041575 | 0,032916 |
-0,02826 | 0,5 |
Условие выполнено |
|
26 | -4,46258 | 3,018626 | 0,040644 | 0,032211 |
-0,02768 | 0,5 |
Условие выполнено |
|
27 | -4,47869 | 3,032467 | 0,039751 | 0,031535 |
-0,02712 | 0,5 |
Условие выполнено |
|
28 | -4,49445 | 3,046029 | 0,038895 | 0,030885 |
-0,02659 | 0,5 |
Условие выполнено |
|
29 | -4,5099 | 3,059322 | 0,038073 | 0,03026 |
-0,02607 | 0,5 |
Условие выполнено |
|
30 | -4,52503 | 3,072357 | 0,037283 | 0,029659 |
-0,02557 | 0,5 |
Условие выполнено |
|
31 | -4,53986 | 3,085143 | 0,036524 | 0,02908 |
-0,02509 | 0,5 |
Условие выполнено |
|
32 | -4,5544 | 3,097689 | 0,035793 | 0,028523 |
-0,02463 | 0,5 |
Условие выполнено |
|
33 | -4,56866 | 3,110004 | 0,03509 | 0,027985 |
-0,02418 | 0,5 |
Условие выполнено |
|
34 | -4,58265 | 3,122096 | 0,034412 | 0,027467 |
-0,02375 | 0,5 |
Условие выполнено |
|
35 | -4,59638 | 3,133971 | 0,033758 | 0,026967 |
-0,02333 | 0,5 |
Условие выполнено |
|
36 | -4,60987 | 3,145639 | 0,033128 | 0,026484 |
-0,02293 | 0,5 |
Условие выполнено |
|
37 | -4,62311 | 3,157105 | 0,03252 | 0,026017 |
-0,02254 | 0,5 |
Условие выполнено |
|
38 | -4,63612 | 3,168376 | 0,031933 | 0,025566 |
-0,02217 | 0,5 |
Условие выполнено |
|
39 | -4,6489 | 3,179458 | 0,031365 | 0,025129 |
-0,0218 | 0,5 |
Условие выполнено |
|
40 | -4,66146 | 3,190358 | 0,030816 | 0,024707 |
-0,02145 | 0,5 |
Условие выполнено |
|
41 | -4,67382 | 3,201081 | 0,030285 | 0,024298 |
-0,0211 | 0,5 |
Условие выполнено |
|
42 | -4,68597 | 3,211633 | 0,029772 | 0,023902 |
-0,02077 | 0,5 |
Условие выполнено |
|
43 | -4,69792 | 3,222019 | 0,029274 | 0,023518 |
-0,02045 | 0,5 |
Условие выполнено |
|
44 | -4,70968 | 3,232243 | 0,028792 | 0,023145 |
-0,02014 | 0,5 |
Условие выполнено |
|
45 | -4,72125 | 3,242311 | 0,028325 | 0,022784 |
-0,01983 | 0,5 |
Условие выполнено |
|
46 | -4,73264 | 3,252227 | 0,027873 | 0,022434 |
-0,01954 | 0,5 |
Условие выполнено |
|
47 | -4,74386 | 3,261996 | 0,027434 | 0,022094 |
-0,01925 | 0,5 |
Условие выполнено |
|
48 | -4,7549 | 3,271621 | 0,027007 | 0,021763 |
-0,01897 | 0,5 |
Условие выполнено |
|
49 | -4,76579 | 3,281108 | 0,026594 | 0,021442 |
-0,0187 | 0,5 |
Условие выполнено |
|
50 | -4,77651 | 3,290458 | 0,026192 | 0,02113 |
-0,01844 | 0,5 |
Условие выполнено |
|
51 | -4,78707 | 3,299677 | 0,025801 | 0,020827 |
-0,01818 | 0,5 |
Условие выполнено |
|
52 | -4,79749 | 3,308768 | 0,025422 | 0,020531 |
-0,01793 | 0,5 |
Условие выполнено |
|
53 | -4,80775 | 3,317734 | 0,025053 | 0,020244 |
-0,01769 | 0,5 |
Условие выполнено |
|
54 | -4,81787 | 3,326578 | 0,024694 | 0,019965 |
-0,01745 | 0,5 |
Условие выполнено |
|
55 | -4,82786 | 3,335305 | 0,024345 | 0,019692 |
-0,01722 | 0,5 |
Условие выполнено |
|
56 | -4,8377 | 3,343915 | 0,024005 | 0,019427 |
-0,017 | 0,5 |
Условие выполнено |
|
57 | -4,84741 | 3,352414 | 0,023674 | 0,019169 |
-0,01678 | 0,5 |
Условие выполнено |
|
58 | -4,857 | 3,360803 | 0,023352 | 0,018917 |
-0,01656 | 0,5 |
Условие выполнено |
|
59 | -4,86646 | 3,369085 | 0,023037 | 0,018672 |
-0,01636 | 0,5 |
Условие выполнено |
|
60 | -4,87579 | 3,377262 | 0,022731 | 0,018432 |
-0,01615 | 0,5 |
Условие выполнено |
|
61 | -4,88501 | 3,385338 | 0,022433 | 0,018199 |
-0,01595 | 0,5 |
Условие выполнено |
|
62 | -4,89411 | 3,393315 | 0,022142 | 0,017971 |
-0,01576 | 0,5 |
Условие выполнено |
|
63 | -4,90309 | 3,401195 | 0,021858 | 0,017748 |
-0,01557 | 0,5 |
Условие выполнено |
|
64 | -4,91197 | 3,408979 | 0,021581 | 0,017531 |
-0,01538 | 0,5 |
Условие выполнено |
|
65 | -4,92073 | 3,416672 | 0,021311 | 0,017319 |
-0,0152 | 0,5 |
Условие выполнено |
|
66 | -4,92939 | 3,424274 | 0,021047 | 0,017111 |
-0,01503 | 0,5 |
Условие выполнено |
|
67 | -4,93795 | 3,431788 | 0,020789 | 0,016909 |
-0,01485 | 0,5 |
Условие выполнено |
|
68 | -4,9464 | 3,439215 | 0,020537 | 0,016711 |
-0,01469 | 0,5 |
Условие выполнено |
|
69 | -4,95476 | 3,446558 | 0,020291 | 0,016518 |
-0,01452 | 0,5 |
Условие выполнено |
|
70 | -4,96302 | 3,453818 | 0,02005 | 0,016328 |
-0,01436 | 0,5 |
Условие выполнено |
|
71 | -4,97118 | 3,460997 | 0,019815 | 0,016143 |
-0,0142 | 0,5 |
Условие выполнено |
|
72 | -4,97925 | 3,468098 | 0,019586 | 0,015962 |
-0,01405 | 0,5 |
Условие выполнено |
|
73 | -4,98723 | 3,47512 | 0,019361 | 0,015785 |
-0,01389 | 0,5 |
Условие выполнено |
|
74 | -4,99513 | 3,482067 | 0,019141 | 0,015612 |
-0,01375 | 0,5 |
Условие выполнено |
|
75 | -5,00293 | 3,48894 | 0,018926 | 0,015442 |
-0,0136 | 0,5 |
Условие выполнено |
|
76 | -5,01065 | 3,49574 | 0,018715 | 0,015276 |
-0,01346 | 0,5 |
Условие выполнено |
|
77 | -5,01829 | 3,502469 | 0,018509 | 0,015113 |
-0,01332 | 0,5 |
Условие выполнено |
|
78 | -5,02585 | 3,509128 | 0,018307 | 0,014953 |
-0,01318 | 0,5 |
Условие выполнено |
|
79 | -5,03332 | 3,515719 | 0,018109 | 0,014797 |
-0,01305 | 0,5 |
Условие выполнено |
|
80 | -5,04072 | 3,522243 | 0,017916 | 0,014644 |
-0,01292 | 0,5 |
Условие выполнено |
|
81 | -5,04805 | 3,528701 | 0,017726 | 0,014494 |
-0,01279 | 0,5 |
Условие выполнено |
|
82 | -5,05529 | 3,535094 | 0,01754 | 0,014347 |
-0,01266 | 0,5 |
Условие выполнено |
|
83 | -5,06247 | 3,541425 | 0,017358 | 0,014202 |
-0,01254 | 0,5 |
Условие выполнено |
|
84 | -5,06957 | 3,547693 | 0,01718 | 0,014061 |
-0,01242 | 0,5 |
Условие выполнено |
|
85 | -5,0766 | 3,553901 | 0,017005 | 0,013922 |
-0,0123 | 0,5 |
Условие выполнено |
|
86 | -5,08356 | 3,560049 | 0,016833 | 0,013786 |
-0,01218 | 0,5 |
Условие выполнено |
|
87 | -5,09045 | 3,566138 | 0,016665 | 0,013652 |
-0,01206 | 0,5 |
Условие выполнено |
|
88 | -5,09728 | 3,57217 | 0,016499 | 0,013521 |
-0,01195 | 0,5 |
Условие выполнено |
|
89 | -5,10404 | 3,578145 | 0,016337 | 0,013393 |
-0,01184 | 0,5 |
Условие выполнено |
|
90 | -5,11073 | 3,584065 | 0,016178 | 0,013266 |
-0,01173 | 0,5 |
Условие выполнено |
|
91 | -5,11737 | 3,589931 | 0,016022 | 0,013142 |
-0,01162 | 0,5 |
Условие выполнено |
|
92 | -5,12394 | 3,595743 | 0,015869 | 0,01302 |
-0,01152 | 0,5 |
Условие выполнено |
|
93 | -5,13045 | 3,601502 | 0,015719 | 0,012901 |
-0,01142 | 0,5 |
Условие выполнено |
|
94 | -5,1369 | 3,60721 | 0,015571 | 0,012783 |
-0,01131 | 0,5 |
Условие выполнено |
|
95 | -5,14329 | 3,612868 | 0,015426 | 0,012668 |
-0,01121 | 0,5 |
Условие выполнено |
|
96 | -5,14963 | 3,618475 | 0,015283 | 0,012554 |
-0,01112 | 0,5 |
Условие выполнено |
|
97 | -5,1559 | 3,624033 | 0,015143 | 0,012443 |
-0,01102 | 0,5 |
Условие выполнено |
|
98 | -5,16212 | 3,629544 | 0,015006 | 0,012333 |
-0,01093 | 0,5 |
Условие выполнено |
|
99 | -5,16829 | 3,635007 | 0,014871 | 0,012225 |
-0,01083 | 0,5 |
Условие выполнено |
|
100 | -5,1744 | 3,640423 | 0,014738 | 0,01212 |
-0,01074 | 0,5 |
Условие выполнено |
|
101 | -5,18046 | 3,645794 | 0,014607 | 0,012015 |
-0,01065 | 0,5 |
Условие выполнено |
|
102 | -5,18647 | 3,651119 | 0,014479 | 0,011913 |
-0,01056 | 0,5 |
Условие выполнено |
|
103 | -5,19243 | 3,656401 | 0,014353 | 0,011812 |
-0,01048 | 0,5 |
Условие выполнено |
|
104 | -5,19833 | 3,661638 | 0,014229 | 0,011713 |
-0,01039 | 0,5 |
Условие выполнено |
|
105 | -5,20419 | 3,666833 | 0,014106 | 0,011616 |
-0,01031 | 0,5 |
Условие выполнено |
|
106 | -5,21 | 3,671985 | 0,013986 | 0,01152 |
-0,01022 | 0,5 |
Условие выполнено |
|
107 | -5,21576 | 3,677096 | 0,013868 | 0,011425 |
-0,01014 | 0,5 |
Условие выполнено |
|
108 | -5,22147 | 3,682167 | 0,013752 | 0,011332 |
-0,01006 | 0,5 |
Условие выполнено |
|
109 | -5,22714 | 3,687196 | 0,013638 | 0,011241 |
-0,00998 | 0,5 |
Условие выполнено |
|
110 | -5,23276 | 3,692187 | 0,013525 | 0,011151 |
-0,0099 | 0,5 |
Условие выполнено |
|
111 | -5,23833 | 3,697138 | 0,013414 | 0,011062 |
-0,00983 | 0,5 |
Условие выполнено |
|
112 | -5,24386 | 3,70205 | 0,013305 | 0,010975 |
-0,00975 | 0,5 |
Условие выполнено |
|
113 | -5,24935 | 3,706925 | 0,013198 | 0,010889 |
-0,00968 | 0,5 |
Условие выполнено |
|
114 | -5,25479 | 3,711763 | 0,013092 | 0,010804 |
-0,0096 | 0,5 |
Условие выполнено |
|
115 | -5,2602 | 3,716564 | 0,012988 | 0,010721 |
-0,00953 | 0,5 |
Условие выполнено |
|
116 | -5,26556 | 3,721328 | 0,012886 | 0,010638 |
-0,00946 | 0,5 |
Условие выполнено |
|
117 | -5,27088 | 3,726057 | 0,012785 | 0,010558 |
-0,00939 | 0,5 |
Условие выполнено |
|
118 | -5,27615 | 3,730751 | 0,012686 | 0,010478 |
-0,00932 | 0,5 |
Условие выполнено |
|
119 | -5,28139 | 3,73541 | 0,012588 | 0,010399 |
-0,00925 | 0,5 |
Условие выполнено |
|
120 | -5,28659 | 3,740035 | 0,012491 | 0,010322 |
-0,00918 | 0,5 |
Условие выполнено |
|
121 | -5,29175 | 3,744626 | 0,012396 | 0,010245 |
-0,00912 | 0,5 |
Условие выполнено |
|
122 | -5,29688 | 3,749184 | 0,012302 | 0,01017 |
-0,00905 | 0,5 |
Условие выполнено |
|
123 | -5,30196 | 3,753709 | 0,01221 | 0,010096 |
-0,00899 | 0,5 |
Условие выполнено |
|
124 | -5,30701 | 3,758202 | 0,012119 | 0,010023 |
-0,00892 | 0,5 |
Условие выполнено |
|
125 | -5,31202 | 3,762664 | 0,012029 | 0,009951 |
-0,00886 | 0,5 |
Точность достигнута |
| Точность: |
0,01 | ||||||
Скачать реферат
