Поиск минимума. Гладкие задачи

из "Приближенное решение задач оптимального управления "

Ради простоты мы опустили в (10) индекс п- -1/г при коэффициентах а, 6,. . ., -f. [c.389]
Здесь будут рассмотрены основные идеи, которые используются при численном решении следующих типичных задач оптимизации. Они перечислены в порядке возрастания формальной сложности. [c.389]
В этой задаче на значения переменных х никаких ограничений не наложено, поэтому о ней говорят, как о задаче безусловной минимизации. [c.390]
Мы будем считать все функции /, (i=0, 1,. . ., п), входящие в постановку задачи, достаточно гладкими, т. е. имеющими непрерывные производные до того порядка, который будет необходим при тех или иных выкладках. Этот случай мы будем считать стандартным и не требующим специальных оговорок. Наоборот, если та или иная из нужных нам производных может не существовать в отдельных точках х, будем считать, что в этом случае требуется специальное предупреждение. [c.390]
Стоит еще отметить, что различие между задачами (2), (3) и (4) кажется условным. Ведь всегда можно определить множество X как совокупность точек, удовлетворяющих условиям / ( г)=0 ( 0). С другой стороны, фактически область X определяется именно набором подобных равенств и неравенств. Тем не менее в специальном выделении множества X имеется определенный смысл, если геометрия области X очень проста. Критерием простоты является простота важной в дальнейшем операции проектирования на X. [c.390]
Это есть система линейных алгебраических уравнений относительно yf коэффициенты системы содержат неизвестный параметр X, значение которого определяется условием у Х (11). Имея в виду общий случай, мы можем лишь при разных значениях X решать систему и затем подбирать значение X так, чтобы было выполнено условие (11). Речь идет о решении скалярного равенства Л (л)=1, где функция Л (А) определена следующим алгоритмом вычисления. [c.392]
Вычислительная сложность этой задачи проектирования (11) определяется в основном размерностью пространства га если п достаточно велико, задача может оказаться очень сложной, так как в общем случае трудоемкость решения системы п линейных уравнений составляет О (res) операций. [c.392]
Алгоритмы безусловной минимизации. Теперь мы приступим к описанию основных алгоритмов решения задач минимизации. Это алгоритмы спуска, в которых, имея некоторую точку я°, находим рядом с ней другую точку х1, такую, что / (а 1) / (я0). Если это невозможно, у нас есть основания утверждать, что найдена точка минимума / (х). [c.392]
Используя тот или иной метод построения последовательности х°, х1,. . ., следует четко представлять себе, какие точки являются тупиковыми для данного метода, не являясь при этом точками локального минимума. [c.393]
Одномерный поиск минимума. Мы начнем с простой задачи, в которой аргумент х — скаляр. Эта задача полезна постольку, поскольку она появляется в качестве элемента в более сложных задачах. [c.393]
Разумеется, эта задача решается приближенно. Что касается направления спуска, то наиболее популярными являются следующие рецепты. [c.394]
Эти утверждения вполне очевидны, и мы их доказывать не будем. Отметим лишь, что чем уже множество стационарных точек, тем надежнее метод поиска. С этой точки зрения предпочтителен случайный поиск. Однако с точки зрения эффективности предпочтительнее метод наискорейшего спуска. Не исключенная в принципе опасность застрять в точке перегиба маловероятна, так как такие точки являются неустойчивыми точками метода наискорейшего спуска, в отличие от точки локального минимума, являющейся устойчивой. [c.395]
Теперь мы докажем характерную теорему о сходимости метода наискорейшего спуска. Эта теорема, в частности, позволит уточнить требования к точности определения шага спуска s. Обозначим через R (у) область re-мерного пространства, определяемую условием х R (у) / (х) . / (у). Функцию / (х) будем считать гладкой (достаточно непрерывности вторых производных). [c.395]
Теорема. Пусть R (x°) — ограниченная замкнутая область, и f (х в R (х°) имеет лишь единственную точку х, в которой fx (х )=0 эта точка, таким образом, является единственной точкой локального минимума f (х) в R (x°). Тогда метод наискорейшего спуска, стартующий из точки х°, сходится к х. [c.395]
Другими словами, метод строит последовательность х°, а 1,. . . . , ., xk,., .- . Доказательство использует два основан факта. [c.395]
Это следует из предположения, что fx 0 лишь в точке х. [c.396]
Покажем теперь, что единственной предельной точкой последовательности хъ (а все xk ft (хй), следовательно, хотя бы одна предельная точка существует) может быть только х — точка минимума / (х) в R (х°). В самом деле, пусть х (= х ) — предельная точка последовательности х . Пусть Д ( )=е 0, и пусть в силу непрерывности Д (х) е/2 при х— т]. В rj-окрестности точки х найдется бесконечно много точек из последовательности xk , причем переход из каждой такой точки в следующую сопровождается уменьшением / не менее, чем на е/2. Поскольку при всех переходах от xk к xk+l значение / по меньшей мере не возрастает, получено противоречие с предположенной ограниченностью / (х) в области R (х°). Таким образом, единственной предельной точкой последовательности х является х. Теорема доказана. [c.396]

Вернуться к основной статье