Методы выпуклого математического программирования и безусловные нелинейные оценки
Методы безусловной минимизации позволяют определить минимум выпуклых функционалов при отсутствии ограничений па переменные и получить нелинейные оценки функционалов для анализа и принятия решений. Эти методы и могут быть составной частью методов условной оптимизации.
Метод наискорейшего спуска
Метод наискорейшего спуска является наиболее простым по вычислительной схеме и требует относительно малого объема вычислительной работы.
Вычислительная схема метода
Рассмотрим решение задачи безусловной минимизации в постановке: вычислить вектор
где функционал <р(х) удовлетворяет условию выпуклости.
Определение 1.
Функционал ф(х) называется выпуклым функционалом на интервале [х яг"], если выполнено условие
Свойство выпуклости функционала иллюстрируется на рис. 2.3.
Необходимо учитывать, что для выпуклых на интервале функционалов метод наискорейшего спуска доставляет глобальный минимум, а в общем (невыпуклом случае) метод приводит к одному из локальных минимумов. Для вычисления точки минимума выпуклой функции строится последовательность {х^}, сходящаяся к указанной точке с элементами вида
где хА+1 и хк — последующее и предыдущее приближения;
— направление движения из точки хк; <хк — шаг в направлении рк. Выбор направления определяет ряд методов. В данном случае направление рк определяется как вектор антиградиента функционала:
В результате вычислительная схема метода принимает вид хм = х^ тфф Алгоритм метода наискорейшего спуска (2.5.1, б) содержит параметр аь, выбор которого может быть выполнен по-разному, но важно, чтобы он обеспечивал сходимость последовательности {х^} к точке минимума.
Теорема о сходимости метода наискорейшего спуска накладывает ограничения па выбор скалярного параметра о^.
Теорема 1 (о сходимости). Пусть выполнены условия:
1) функционал ф(х) ограничен снизу;
2) градиент функционала ф'(х) удовлетворяет условию Липшица (условию типа непрерывности)
3) параметр ак выбирается из условия
Тогда для предельного значения градиента функционала выполнено необходимое условие оптимальности
Другими словами, при выполнении указанных условий теоремы последовательность (2.5.1, б), соответствующая методу наискорейшего спуска, сходится к стационарной точке функционала ф(х).
Доказательство. Рассмотрим приращение функционала, пользуясь теоремой о среднем:
Добавим и вычтем в правой части последнего равенства слагаемое (фд, х-х^). Тогда
где равенство -аф£ = х х^ имеет место в силу вычислительной схемы алгоритма наискорейшего спуска (2.5.1, б).
Далее проведем оценки приращения функционала с учетом равенства (2.5.2, а). В результате получим цепочку соотношений:
Из последних соотношений следует, что для монотонного уменьшения функционала необходимо, чтобы выполнялось неравенство: -1 + аЬ < е.
Откуда следует, что скалярный параметр а должен выбираться из условия + а < (1 - г)/Ь и для того, чтобы было а > 0, параметр с должен быть таким, чтобы 0 < с < 1.
Таким образом, при выборе шага из условия
функционал <р(х) монотонно уменьшается, и в силу ограниченности снизу этот функционал на последовательности {хА} достигает минимума.
Условия сходимости позволяют сформулировать алгоритм метода в соответствии с ограничениями теоремы па выбор шага.
Шаг 1. Выбирается произвольный вектор х0 — начальное приближение. Полагается хА = х0.
Шаг 2. Выбирается произвольное значение а.
Шаг 3. Определяется новое Приближение Х^+| = Х^ "Т/С&.ф
Шаг 4. Вычисляется ф(хы) = ср(х^-аАф^)и ф(х^).
Шаг 5. Если ф(хА+1)-ф(х^)<еа(ф^,р^),0<е<1, то значение а принимается в качестве искомого = а и происходит переход к шагу 6, иначе производится деление а пополам и выполняется переход к шаг}' 4.
Шаг 6. Вычисляется новое приближение хы = хк ^фф
Шаг 7, Проверяется условие стационарности:
II 1|2 II ||2
||Ф!ы|Г = ( 4+1 • 4+1) -8 8=0, и если ||Фы|~^8, то выполняется переход к шагу 8, иначе — к шагу 2, положив хА = хк+{. Шаг 8. Останов.
Геометрическая интерпретация минимизации функционала в двумерном пространстве процесса вычислений приведена на рис. 2.4.
Рассмотрим вычислительную схему метода наискорейшего спуска на примере.
Пример
Пусть в двумерном пространстве задан квадратичный функционал у(х) = х'( +л*2 -Юл', -6л'2 +39. Вычислить точку минимума в двумерном пространстве.
Решение. Рассмотрим последовательно шаги алгоритма.
Шаг 1. Задается х(| - (л-,,,, дгм) = (7, -2)т. Полагается Хд, = х0.
Шаг 2. Выбирается а = 0,3.
Шаг 3. Определяется вектор нового приближения:
Рис. 2.4
Шаг 4. Вычисляется значение функционала в новом и предыдущем приближениях: ф(х^+,) = 9.64, фх^) ^$4.
Шаг 5. Проверяется выполнение условия стационарности — неравенства типа (2.5.2): Ф(х£+|)-<р(хд)<£(х(ф£,р^),0<е< 1, которое выполняется при значении параметров а = 0,3, е = 0,1, а также условие (<р'к, />*) = (И,- 10], 101>= 116. Принимается а/(, = 0,3, и выполняется переход к шагу 6.
Шаг 6. Вычисляется вектор
Шаг 7. Проверяется условие стационарности (2.5.2):
||ф£+1|| 58 = 0,1, которое не выполняется, и осуществляется переход к шагу 2. Последовательное выполнение шагов 2—7 позволяет определите значениях ^ =[5,32 I 2,20]г,х=[5,12 I 2,6817;х= [5,05 I 2,87]'. Решение, полученное на пятой итерации х5= [5,02 I 2,95]7', соответствует приближенному решению с учетом ограничения нормы градиента функционала в окрестности точки стационарности функционала.
Необходимо иметь в виду, что в силу утверждения теоремы 1 сходимость метода — асимптотическая при бесконечно большом числе шагов алгоритма.
Рассмотренный метод может использоваться самостоятельно, а также служить частью более сложных вычислительных алгоритмов минимизации, в частности при решении задач условной минимизации.