 |
 |
 |
 |
|
 |
 |
50
Доказательство.
Доказательство достаточно провести для случая вогнутой функции, т. к. для противоположного
случая оно будет абсолютно аналогичным с точностью до знака.
Пусть х — произвольная точка, отличная от точки х*. Тогда, для любого ?
[0,1], в силу вогнутости
функции f(x) будет выполняться
из чего следует
Если ввести вектор l = х - х* и обозначить
?
х = ?(x
–
х*) = ?l, то длина вектора
?
х будет равна
||?x||=?||l||. Следовательно,
Устремив
?
>
0 и учитывая, что вектор l сонаправлен с
?
х, получим
По условию теоремы
f(x*)=0. Это означает, что для любого вектора l (а, стало быть, для любой
точки х) согласно формуле, выражающей производную по направлению через градиент,
Следовательно, для любой точки х, не равной х*, справедливо неравенство f(x)-f(x)
?
0 <=> f(x)
? f(x
*),
т.е. х* — точка глобального максимума.
Поскольку выпуклые функции обладают столь «полезными» оптимизационными качествами, они
занимают исключительно важное место в теории исследования операций. Соответствующий раздел
получил название выпуклого программирования, а общая задача выпуклого программирования
формулируется как проблема поиска максимума вогнутой (минимума выпуклой) функции на выпуклом
множестве.
2.1.5. Метод допустимых направлений. Данный метод также называется методом возможных
направлений или же по имени автора—методом Зойтендейка, см. [16]. Его основную идею будет
удобно продемонстрировать на примере ЗНП с ограничениями в форме неравенств:
В указанном методе так же, как и в градиентных методах, находится последовательность точек х
(0)
х
(1)
,..., х
(q)
..., таких, что f(х
(q+1)
)
?
f(x
(q)
) *. При этом переход от точки x
(q)
)
к точке х
(q+1)
)
происходит по
некоторому выбранному направлению s
(q)
с шаговым множителем ?
q
:
* Так как в данных методах при переходе к очередной рассматриваемой точке происходит улучшение значения целевой
функции (в частности, для задачи минимизации — уменьшение), их также называют релаксационными методами.
По отношению к векторам, задающим направления перемещения, вводятся два фундаментальных
понятия.