Главная > Нелинейное программирование. Единый подход
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

10.2. АЛГОРИТМ ЛАГРАНЖА

Во всех методах, рассмотренных до этого, в качестве функции которая указывает продвижение процессов, использовалась сама целевая функция. Однако возможны и другие функции . В частности, в методе Лагранжа используетсй функция которая представляет собой расстояние между точкой и седловой точкой. Метод сходится для задачи (10.1) в случае, если функции и вогнуты и непрерывно дифференцируемы.

Предположения о седловой точке. Как было показано в теореме 2.18, если функция Лагранжа обладает седловой точкой , то х решает задачу (10.1). Метод Лагранжа предполагает, что такая

седловая точка существует. В явной форме это означает существование точки , удовлетворяющей условиям

Кроме того, предполагается, что существует единственная точка которая решает задачу (10.6). Тогда

(Простое условие, гарантирующее выполнение этого предположения, приведено в упр. 8.)

Если определим множество — седловая точка для то будет множеством всех , для которых является седловой точкой. По предположению не пусто, однако, кроме того, предполагаем, что компактно. Несмотря на то, что обычно компактно, в следующей лемме даны условия, обеспечивающие выполнение этого требования.

Лемма 10.1. Пусть существует точка для которой тогда компактно.

Доказательство. По определению седловой точки для любой

Из того, что следует, что

Но так как

т. е. все компоненты ограничены.

Теперь мы замкнутость множества Пусть где Должо быть установлено, что По определению седловой точки для любых

Переходя к пределу в (10.8), получаем

Поэтому замкнуто и ограничено. Лемма доказана.

Алгоритмическое отображение. Теперь определим алгоритмическое отображение. Пусть

является градиентом по х, а

— градиентом по X. Тогда по данному алгоритмическое отображение дает с помощью уравнений

где — параметр, указывающий длину шага, представляет собой фиксированную скалярную величину, которая будет определена далее. Операция в (10.12) является покомпонентной операцией, т. е. согласно (10.12)

Обратите внимание на то, что для определения алгоритмического отображения требуется как х, так и Я. Следовательно, и алгоритмическое отображение представляет собой функцию

Функция Мы определяем функцию следующим образом:

Иначе говоря, определяется как расстояние между и ближайшей седловой точкой . Заметим, что из теоремы 7.1 и компактности следует, что минимум достигается, а согласно теореме 7.2 функция непрерывна (см. упр. 6). Так как значения функции представляет собой расстояние, то множества

компактны для любых положительных у и (см. упр. 7),

Подходящая точка. Точка называется подходящей, если для данного

Таким образом, является подходящей точкой, если расстояние между точкой х и оптимальной точкой х не превышает .

Если точка окажется подходящей, то алгоритм завершает поиск.

Выбор в алгоритмическом отображении. После того как определены понятия подходящей точки и функции можно дать определение параметра в алгоритмическом отображении.

Для заданной произвольной исходной точки где положим . Тогда определяется следующим образом:

Согласно (10.14) множества, по которым выполняется минимизация, являются компактными, при этом полезно заметить, что требование обеспечивает неравенство

На основе непрерывной дифференцируемости функций функция в (10.16) является непрерывной. Как показывает следующая лемма, она также положительна во всех точках. Тогда из следствия 2.1.1 получаем, что

Лемма 10.2. Пусть и вогнуты и непрерывно дифференцируемы. Тогда

Доказательство. Согласно вогнутости по х

Из а по определений функцйй Лагранжа

Но тогда комбинация соотношений (10.19) и (10.20) дает

По определению седловой точки и по (10.7), если то

Наконец, из (10.21) и (10.22) получаем

Доказательство сходимости. Теперь установим сходимость процедуры Лагранжа, используя теорему сходимости А. Для полноты мы вкратце приведем все предположения, которые требуются для сходимости. Функции и вогнуты и непрерывно дифференцируемы. Существует седловая точка единственно. Кроме того, компактно. Теперь будет доказана сходимость.

Условие 3. Условие 3 следует непосредственно, так как алгоритмическое отображение является непрерывной функцией.

Условие 2. Для того чтобы доказать выполнение условия 2, требуются некоторые предварительные рассмотрения.

Обозначим

Возводя в квадрат (10.12), получаем

Кроме того, из (10.12), учитывая, что имеем

Далее, используя (10.23) и (10.24), после небольших преобразований приходим к

Точно так же, как (10.25) было получено из (10.12), из (10.11) мы можем получить соотношение

Складывая (10.25) и (10.26), получаем

Теперь уже мы можем установить выполнение условия 2. Заметим, что в данном случае необходимо убедиться в справедливости неравенства Пусть не является подходящей точкой. Анализируя (10.27) и определение видим, что для того, чтобы доказать неравенство необходимо лишь установить

Учитывая (10.17) и то, что точка не является подходящей, получаем

Теперь с помощью определения видим, что левая часть (10.28) больше, чем

где последнее неравенство следует из леммы 10.2. Таким образом, установлена справедливость (10.28), а значит, и выполнение условия 2а (см. упр. 12),

Выполнение условия 26 следует сразу же, так как, если является подходящей точкой, то алгоритм завершает поиск.

Итак, выполнение условия 2 установлено

Условие 1. Заметим, что условие 2 дает Тогда согласно (10.14) все входят в компактное множество и, следовательно, условие I также выполняется. Итак, алгоритм сходится.

Замечания. Необходимо отметить, что из того, как определено — длина шага, возникает следующий вопрос. Параметр определяется через решение, с другой стороны, цель алгоритма заключается в определении этого решения. Здесь можно привести следующее обоснование. Если дано то существует для которого алгоритм сходится. Вычисление точного значения невозможно. При выполнении расчетов по этому алгоритму варьируется для того, чтобы достигнуть «хорошего» значения. Выяснение того, когда является подходящей точкой, также может оказаться нелегкой задачей.

В большинстве предшествовавших алгоритмов трудной частью было доказательство условия замкнутости, условия 3. Обычно выполнение условия 2 вытекало непосредственно. Для алгоритма Лагранжа имеет место противоположная ситуация. Справедливость условия 3 была установлена быстро, тогда как проверка условия

2 потребовала скрупулезного рассмотрения. Одной из причин этого отличия является то, что в методе Лагранжа ищется седловая точка; таким образом, мы решаем задачу на . С другой стороны, большинство рассмотренных алгоритмов решает чистую задачу на максимум и целевая функция, так как она всегда возрастает, может быть использована как функция . В методе Лагранжа функцией, которую следовало бы рассматривать в качестве функции является сама функция Лагранжа. Но вследствие особенностей операции функция Лагранжа как возрастает, так и убывает и не может быть использована в качестве функции Вместо нее приходится использовать сложную функцию основанную на расстоянии до седловой точки. Поэтому проверка выполнения условия 2, которая требует, чтобы мы все ближе и ближе подходили к седловой точке, была сравнительно трудной.

Можно также отметить, что для этого алгоритма мы доказали выполнение условия 1, условия компактности.

В большинстве предшествовавших алгоритмов выполнение условия 1 не доказывалось, а предполагалось. Это объясняется тем, что в предыдущих алгоритмах постулирование условия 1 является геометрически обоснованным. Достаточно беглого рассмотрения, чтобы видеть, что такие алгоритмы, за исключением необычных ситуаций, должны вырабатывать точки, входящие в компактное множество. К сожалению, для метода Лагранжа нелегко получить такое геометрическое представление. Поэтому мы привели математическое доказательство справедливости условия 1. Ситуации, когда компактность не имеет места, рассмотрены в гл. 11.

1
Оглавление
email@scask.ru