Методы оптимизации

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «ИВАНОВСКИЙ ГОСУДАРСТВЕННЫЙ ЭНЕРГЕТИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ В.И.ЛЕНИНА» МЕТОДЫ ОПТИМИЗАЦИИ Курс лекций для студентов заочного обучения специальности 230105 Программное обеспечение вычислительной техники и автоматизированных систем Иваново 2009 Лекция 1. Методы оптимизации функции одной переменной Функции одной переменной Задача оптимизации, в которой целевая функция задана функцией одной переменной, относится к наиболее простому типу оптимизации задач. Тем не менее анализ задач такого типа занимает важное место в исследованиях. Это связано с тем, что одномерные методы оптимизации часто используются для анализа подзадач, которые возникают при реализации итеративных процедур, ориентированных на решение многомерных задач оптимизации. Свойства функций одной переменной Определение: Функция представляет собой правило, которое позволяет каждому значению поставить в соответствие единственное значение . В этом случае называется независимой переменной, – зависимой переменной (функцией). Обычно значения независимой переменной определены в некоторой области : . Если является подмножеством множества действительных чисел, то называется скалярной функцией, определенной на множестве . Например а) для всех , где R – множество действительных чисел. б) для всех . В теории оптимизации - называется целевой функцией, – областью допустимых значений (допустимой областью). Экстремумы функции. Функция имеет локальный минимум в точке , если существует окрестность точки такая, что для всех точек этой окрестности . Функция имеет глобальный минимум в точке если для всех из области допустимых значений () справедливо неравенство . Аналогичные определения глобального и локального максимума можно получить путем замены знака неравенства на противоположный. Топологические свойства функций Для выбора метода оптимизации важное значение имеет форма функций, определяющая топологические свойства функций в рассматриваемом интервале. Очевидно, что в зависимости от формы целевой функции и структуры допустимой области следует использовать различные методы для поиска точек оптимума. Первая классификация функций в соответствии с их формой предполагает их разделение на непрерывные, разрывные и дискретные. Монотонные функции Функция является монотонной, если для двух произвольных точек и , таких, что , выполняется одно из следующих неравенств: (монотонно возрастающая функция). (монотонно убывающая функция). Унимодальные функции Функция является унимодальной на отрезке в том и только том случае, если она монотонна по обе стороны от единственной на рассматриваемом интервале оптимальной точки . Экстремумы функции. Функция имеет локальный минимум в точке , если существует некоторая положительная величина , такая, что если , то , то есть если существует окрестность точки , такая, что для всех точек этой окрестности . Функция имеет глобальный минимум в точке , если для всех справедливо неравенство . Замечания. 1. Аналогичные определения глобального максимума и локального максимума можно получить путем замены знака неравенства на противоположный. 2. Если функция обладает свойством унимодальности, то локальный минимум автоматически является глобальным минимумом. 3. Если функция не является унимодальной, то возможно наличие нескольких локальных оптимумов; при этом глобальный минимум можно определить путем нахождения всех локальных оптимумов и выбора наименьшего из них. Классический метод оптимизации. Классический подход к задаче нахождения значений и состоит в поиске уравнений, которым эти значения должны удовлетворять. Можно сформулировать следующее правило: Если функция и ее производные непрерывны, то точка является точкой экстремума тогда и только тогда, когда – четное, где – порядок первой не обращающейся в нуль производной в точке . Если , то в точке достигается максимум, если , то – минимум. Пример1. Исследовать функцию на экстремумы. ; ; , т.е. ; – точки стационарные (особые). ; - в т. достигается максимум; -в т. достигается минимум. Это правило можно обосновать, если рассмотреть разложение функции в окрестности точки экстремума в ряд Тейлора. При достаточно малом шаге первое слагаемое доминирует над остальными. Если в точке достигается минимум, то левая часть будет неотрицательной для любого достаточно малого . Следовательно, первая производная должна быть равна нулю и это является необходимым условием существования минимума. (Если то при ). Так как всегда больше нуля, то при достигается минимум, а при достигается максимум функции в точке . Пример2. Исследовать функцию на экстремумы. Неоднозначность, возникающая при , можно разрешить, увеличив количество членов в формуле разложения в ряд Тейлора: При нулевых первой и второй производной доминирующим является третий член разложения, а так как его знак зависит от , то в точке оптимума третья производная должна равняться нулю. Вид экстремума (максимум, минимум) зависит от знака четвертой производной. Ряд можно продолжить, если нулевыми окажутся также третья и четвертая производные функции : Первая не обращающаяся в нуль производная в т. – шестая, – следовательно функция имеет минимум в точке . Пример 3. Исследовать функцию на экстремумы. , при ; , при ; , . Для функции точка не является точкой экстремума, но является особой точкой, т.к. в ней первая производная равна нулю. Определения. Стационарной точкой называется точка , в которой . Если стационарная точка не соответствует локальному оптимуму, то она является точкой перегиба или седловой точкой. Метод Ньютона. Для функции одной переменной классический подход при поиске значений , удовлетворяющих необходимому условию существования экстремума, состоит в решении уравнения. . Решить такое уравнение не всегда удается аналитическими методами. Поэтому целесообразно использовать численные методы решения таких уравнений. Вспомним один из таких методов – метод Ньютона. Приблизительный эскиз кривой позволяет получить приближенное решение. Далее метод Ньютона позволяет улучшить относительно грубую аппроксимацию корня Пусть РТ – касательная к кривой φ(х) в точке Р первого приближения. Т - точка, в которой касательная пересекает ось Х. Тогда в общем случае х=ОТ является лучшей аппроксимацией корня, лежащего в точке k. Очевидно ОТ=ОА-ТА=х0-ТА , следовательно и Аналогично в общем случае Метод секущих Логическая схема поиска предыдущего метода основана лишь на исследовании знака производной. При реализации метода секущих кроме знака производной используется также и ее значение. Пусть в процессе поиска стационарной точки функция в интервале (a,b) обнаружены две точки L и R, в которых знаки производных различны. Метод секущих позволяет аппроксимировать функцию на отрезке (L,R) прямой линией, соединяющей точки и . Следующее приближение к точке определяется по формуле Если , поиск следует закончить. В противном случае необходимо выбрать одну из точек L или R таким образом, чтобы знаки производной в этой точке и в точке Z были различны. Независимо от того, требуется ли найти максимальное или минимальное значение целевой функции можно пользоваться одними и теми же методами решения экстремальных задач, т.к. задачу минимизации можно превратить в задачу на поиск максимума, если поменять знак целевой функции на противоположный. Аналогично изменением знака целевой функции на противоположный задача на максимум превращается в задачу на минимум. Лекция 2. Методы исключения интервалов Задачу одномерной оптимизации можно поставить следующим образом: Минимизировать значение целевой функции на интервале изменения независимой переменной , если известно, что функция обладает свойством унимодальности. Интервал значений , в котором заключено оптимальное значение , будем называть интервалом неопределенности. В начале процесса оптимизации этот интервал имеет длину . Теорема ( правило исключения интервалов) Пусть функция унимодальна на замкнутом интервале, а ее минимум достигается в точке . Рассмотрим точки и, расположенные на интервале таким образом, что . Сравнивая значения функции в точках и можно сделать выводы: 1. Если , то точка минимума не лежит в интервале . 2. Если , то точка минимума не лежит в интервале . Доказательство: Рассмотрим случай, когда . Пусть утверждение теоремы не верно, т. е. . Поскольку - точка минимума, то по определению . Получаем двойное неравенство , при . Это неравенство не может выполняться, т. к. унимодальная функция должна быть монотонной по обе стороны от точки . Таким образом, получено противоречие, доказывающее утверждение теоремы. Аналогичные рассуждения справедливы в случае, когда . Согласно теореме можно реализовать процедуру поиска точки оптимума путем последовательного сужения интервала неопределенности. — исходный интервал неопределенности, — суженный интервал неопределенности. Поиск завершается, когда оставшийся интервал уменьшается до достаточно малых размеров , где - заданная точность вычисления оптимума. Существует несколько способов систематического сужения интервала неопределенности. Метод равномерного поиска Очевидно, наиболее простым способом сужения интервала неопределенности для одномерной унимодальной функции является деление его на несколько равных частей с последующим вычислением значений целевой функции в узлах полученной сетки. При наличии точек начальный интервал неопределенности равен шагу сетки. В результате применения правил исключения интервалов интервал неопределенности сужается до двух шагов сетки. В качестве оценки эффективности того или иного метода исключения интервалов используют коэффициент относительного уменьшения интервала неопределенности , где — исходный интервал неопределенности, — интервал неопределенности после N вычислений значений функции. Для метода равномерного поиска . Чтобы получить значение потребуется вычислить функцию в 199 точках. Ясно, что эффективность метода очень мала. Ее можно повысить, избрав, например такой путь: чтобы получить вычислить сначала функцию в 19 точках и получить , а затем вычислить еще 19 точек на сокращенном интервале получив всего за 38, а не за 199 вычислений функции. Метод деления интервала пополам Рассматриваемый метод позволяет исключать в точности половину интервала на каждой итерации. Метод основан на выборе трех пробных точек, равномерно распределенных в интервале поиска. Точки делят интервал на четыре равные части. В силу унимодальности функции возможны три ситуации: 1. , тогда согласно правилу исключения интервалов точка оптимума не лежит в интервале и, следовательно, этот интервал подлежит исключению. 2. , тогда по правилу исключения интервалов можно исключить из рассмотрения интервал . 3. и . Дважды применив правило, приходим к выводу, что можно исключить интервалы . Другие ситуации невозможны в силу унимодальности функции. Построим описание поисковой процедуры, предназначенной для нахождения точки минимума функции в интервале . begin  – интервал неопределенности ;  значение функции в точке ; ; { – средняя точка интервала, – длина интервала} repeat ; ; {точки делят интервал на четыре равные части } ; ; if then begin {средней точкой нового интервала становится x1} ; end else if then { сделать средней точкой нового интервала } begin ; end else { остается средней точкой } begin ; end ; Until { – интервал неопределенности; – средняя точка интервала; } End Средняя точка последовательно получаемых интервалов всегда совпадает с одной из пробных точек,или ,найденных на предыдущей итерации. Следовательно, на каждой итерации требуется не более двух вычислений значений функции. Таким образом, если проведено вычислений значений функции, то длина полученного интервала составляет длины исходного интервала, т.е. . Метод золотого сечения В методе золотого сечения функция вычисляется в точках интервала неопределенности расположенных таким образом, чтобы каждое вычисленное значение целевой функции давало полезную информацию. Сущность метода состоит в следующем. Интервал неопределенности делится на две неравные части таким образом, что отношение большого отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего отрезка. Выполним преобразования, разделим второе уравнение на Z Учтем из первого уравнения, что и после подстановки получим Решая это квадратное уравнение, находим для положительного корня Вторая точка выбирается расположенной в интервале неопределенности симметрично относительно первой. При делении интервала в этом отношении, два вычисления целевой функции позволяют уменьшить интервал неопределенности в 1/0.618 раза. Отметим что: , т.е. точка x1 является точкой золотого сечения для нового интервала неопределенности. Поэтому, чтобы уменьшить интервал неопределенности еще в 1/0.618 раз потребуется дополнительно вычислить только одно значение целевой функции в точке x3, определенной правилом золотого сечения: После вычисления N значений целевой функции коэффициент дробления интервала неопределенности составит . Сравнение методов исключения интервалов Для сравнения методов равномерного поиска, деления интервала пополам, золотого сечения вспомним коэффициенты относительного уменьшения интервала неопределенности. Равномерный поиск: ; Деление интервала пополам: ; Золотое сечение: . Величины относительного уменьшения интервала. Методы решения Количество вычислений функции N=2 N=5 N=10 N=15 N=20 Деление интервала пополам 0.5 0.177 0.031 0.006 0.0009 Золотого сечения 0.618 0.146 0.013 0.001 0.0001 Равномерного поиска 0.667 0.333 0.182 0.125 0.095 Из таблицы следует, что метод золотого сечения обеспечивает наибольшее относительное уменьшение интервала при одном и том же количестве вычислений значений функции. С другой стороны, можно сравнить количества вычислений значений функции, необходимые для достижения заданной точности вычислений. N вычисляется по следующим формулам : для равномерного поиска для деления интервала пополам для золотого сечения Требуемое количество вычислений значений функций. Метод поиска Заданная точность E = 0.1 E = 0.05 E = 0.01 E = 0.001 Деление интервала пополам 7 9 14 20 Золотого сечения 6 8 11 16 Равномерный поиск 19 39 199 1999 Полиномиальная аппроксимация Применение методов исключения интервалов накладывает единственное ограничение на исследуемую функцию: она должна быть унимодальной. Следовательно, указанные методы можно применять для анализа и непрерывных, и разрывных, и дискретных функций. Логическая структура поиска с помощью методов исключения интервалов основана на простом сравнении значений функции в двух точках. Методы аппроксимации позволяют учесть относительные изменения в значении функции, поэтому оказываются более эффективными. Однако эффективность достигается ценой дополнительного ограничения на форму исследуемых функций: они должны быть унимодальны и непрерывны. Согласно теореме Вейерштрасса, если функция непрерывна в некотором интервале, то её с любой степенью точности можно аппроксимировать полиномом достаточно большого порядка. Следовательно, если функция унимодальна и найден полином, который достаточно точно её аппроксимирует, то координату точки оптимума функции можно оценить путем вычисления координаты точки оптимума полинома. Качество оценок можно повышать двумя способами:  использованием полинома более высокого порядка;  уменьшением интервала аппроксимации; Второй способ, вообще говоря, является более предпочтительным. Квадратичная интерполяция Если задана последовательность точек и известны соответствующие им значения функции то функция может быть аппроксимирована квадратичной функцией Определим постоянные коэффициенты исходя из условия, что значения функции совпадают со значениями в контрольных точках. Для имеем , т.е. . Для имеем , откуда . Для : , откуда Используем полученный квадратичный полином для оценивания координаты точки оптимума. Отсюда, точка минимума функции аппроксимируется значением: . Метод, разработанный Пауэллом, основан на последовательном применении процедуры оценивания с использованием квадратичной аппроксимации. Схему алгоритма можно описать следующим образом: Пусть -начальная точка, - выбранная величина шага по оси . 1. Вычислить 2. Вычислить и 3. Если положить . Если положить . 4. Вычислить и найти , , которая соответствует . 5. По трем точкам вычислить, используя формулу квадратичной аппроксимации. 6. Проверка на окончание поиска: а) является ли разность достаточно малой? б) является ли разность достаточно малой? Если оба условия выполняются, закончить поиск. В противном случае перейти к п.7. 7. Выбрать наилучшую точку или и две точки по обе стороны от неё, или 3 точки, в которых функция имеет минимальные значения. Перейти к п.5. Методы с использованием производных Использование в методах поиска предположения о непрерывности функции в дополнение к предположению об унимодальности позволило получить более эффективный алгоритм квадратичной интерполяции. Целесообразно предположить, что если в дополнение к условию непрерывности ввести требование дифференцируемости функции, то эффективность поисковых процедур можно ещё более повысить. Метод средней точки Если функция унимодальна в заданном интервале поиска, то точкой оптимума является точка, в которой . Если имеется, возможность вычислить как значение функции, так и её производной, то для нахождения корня уравнения можно использовать следующий эффективный алгоритм исключения интервалов, на каждой итерации которого рассматривается лишь одна пробная точка. Определим 2 точки и таким образом, что . Стационарная точка расположена между и . Вычислим значение производной в средней точке рассматриваемого интервала . Если , то интервал можно исключить из интервала поиска. Если , то интервал можно исключить из интервала неопределенности. Коэффициент относительного уменьшения интервала неопределенности: Кубическая интерполяция В рассматриваемом методе исследуемая функция аппроксимируется кубическим полиномом. Для кубической интерполяции используются значение функции и её производной в двух точках. Работа алгоритма начинается в произвольно выбранной точке . Другая точканаходится из условия, что производные и имеют различные знаки. Аппроксимирующую кубическую функцию запишем в виде: Параметры аппроксимирующего полинома подбираются таким образом, чтобы значения функции, и её производной в точках совпадали со значениями полинома в этих точках. Первая производная функции равна: Коэффициенты полинома определяются по известным значениям : После решения полученной системы, приравняем нулю первую производную и найдем корни квадратного уравнения. Получим решение в следующем виде: где Формула для  обеспечивает надлежащий выбор одного из двух корней квадратного уравнения. Формула гарантирует, что получаемая точка расположена в интервале . Приведем описание алгоритма. Пусть заданы начальная точка , положительная величина шага  и параметры сходимости и. 1. Вычислить Если , вычислить для значений Если , вычислить для значений 2. Повторить вычисления до точки, в которой меняется знак производной, т.е. .Положить ; . Вычислить . 3. Найти точку оптимума кубического полинома. 4. Проверка на окончание поиска: Если поиск закончить Иначе а) , если б) , если Перейти к шагу 3. Сравнение методов С помощью теоретических выкладок доказано, что методы квадратичной и кубической интерполяции существенно эффективнее методов исключения интервалов. В случае, когда значения производной вычисляются непосредственно, метод поиска с использованием кубической аппроксимации оказывается наиболее эффективным. Однако, если значения производной вычисляются путём численного дифференцирования, то предпочтение следует отдать квадратичной интерполяции, которая вычислений производной не требует. Если необходимо получить решение с высокой степенью точности, то лучшим оказываются методы поиска на основе полиномиальной аппроксимации. С другой стороны при исследовании мультимодальных или быстро изменяющихся функций методы исключения интервалов сходятся быстрее. Если важно добиться надежной работы алгоритма, то целесообразно выбрать метод золотого сечения. Рекомендуется использовать поисковые методы полиномиальной аппроксимации совместно с методом золотого сечения. Метод Пауэлла, метод средней точки и метод золотого сечения использовались для минимизации функции Для всех функция имеет минимум в точке Однако с увеличением гладкость функции, которая обладает узкими впадинами в окрестности точки минимума, уменьшается. С ростом увеличились затраты времени, особенно при реализации метода средней точки, вследствие резкого увеличения градиента функции в окрестности точки минимума. Однако возрастание не оказывало заметного влияния на продолжительность счета методом золотого сечения. Точность решения падает с ростом для метода средней точки и метода Пауэлла. Метод же золотого сечения оказывается нечувствительным к изменениям крутизны функции. Поиск методом Фибоначчи Задача: определить минимум функции на интервале как можно точнее, использовав только n вычислений функции. Начальный интервал неопределенности . Для сужения интервала требуется знать значение функции как минимум в двух различных точках этого интервала. Как их разместить наилучшим образом внутри интервала? Поскольку не известно, какая из ситуаций будет иметь место, целесообразно разместить точки симметрично относительно интервала. Если можно выполнить еще одно вычисление функции, то нужно поместить следующую точку внутри интервала неопределенности симметрично уже имеющейся там точке. Для того, чтобы получить наибольшее уменьшение интервала на последнем ( n – м шаге) следует разместить точки как можно ближе к середине интервала. Тогда мы сможем получить коэффициент уменьшения интервала близкий к ½. Обозначим расстояние между точками и через , тогда интервалы неопределенности и будут связаны соотношением ( см. рис.). С учетом общей формулы имеем: Последовательность чисел Фибоначчи определяется следующим образом Очевидно, коэффициенты полученных соотношений для интервалов неопределенности являются числами Фибоначчи и поэтому их можно записать в виде . Для начального интервала имеем j=n-1; Отсюда Следовательно, после n вычислений функции коэффициент относительного уменьшения интервала неопределённости: где -число Фибоначчи. Мы до сих пор не выяснили: как разместить левую точку х1 в начальном интервале неопределенности ? Для ответа на этот вопрос надо определить . Числа Фибоначчи используются только для нахождения первой точки. Значения  определяются из практических соображений, но должно быть Действительно, возьмем последний шаг. Чтобы произошло уменьшение интервала неопределенности необходимо, чтобы. С другой стороны . Совместное решение уравнения и неравенства приводят к указанному результату. Если невозможно обеспечить выполнение неравенства по условиям вычисления функции(2-минимальное различимое расстояние между точками) то следует уменьшить, иначе мы будем понапрасну тратить время на последних итерациях. Связь метода Фибоначчи с методом золотого сечения Для золотого сечения также справедливо соотношение (из-за симметрии расположения точек): но неизвестно n и поэтому нельзя записать Вместо этого предположения, используем другое: относительное уменьшение интервала на каждом шаге должно быть одинаковым, т.е. т.е. получили отношение золотого сечения. Лекция 3. Функции n переменных Рассмотрим функцию действительных переменных . Точку в n-мерном евклидовом пространстве обозначим вектором столбцом . Градиент функции обозначим . Матрица Гессе (гессиан) функции обозначается, как и является симметрической матрицей nn элементов вида: Предположим, что в точке функция достигает минимума, тогда справедливо неравенство . Полагая функцию дифференцируемой, выполним разложение её в ряд Тейлора в окрестности точки : Сопоставляя два последних выражения, приходим к неравенству: ; Если , то в силу малости , первый член разложения будет доминирующим. Но тогда соответствующим подбором можно добиться того, что левая часть неравенства будет отрицательной. Следовательно, необходимым условием минимума является равенство нулю всех частных производных в точке минимума, т.е.: или Точка, в которой называется стационарной. В этой точке значение левой части неравенства определяется членом: . В точке минимума должна быть больше нуля или равна нулю (таким образом можно найти стационарную точку определить в ней матрицу Гессе и, подбирая малые посмотреть, как ведет себя функция в окрестности стационарной точки). Определения: Функция n переменных называется квадратичной формой, если где и . 1) Матрица является положительно определенной тогда и только тогда, когда значение квадратичной формы для всех . 2) Матрица является положительно полуопределенной, когда значение квадратичной формы и существует вектор такой что ; 3) Матрица является отрицательно определенной тогда и только тогда, когда есть положительно определенная матрица, т.е. или ; 4) Матрица является отрицательно полуопределенной тогда и только тогда, когда есть положительно полуопределенная матрица. 5) Матрица является неопределенной, если квадратичная форма может принимать как положительные, так и отрицательные значения. Следовательно: Необходимыми и достаточными условиями минимума являются положительно определена. По аналогии: Необходимыми и достаточными условиями максимума являются отрицательно определенная матрица. Если же выполнены условия, неопределенная матрица, то имеем седловую точку. Максимум, минимум и седловая точка функций в пространстве и в линиях уровня: Проверка матрицы на положительную определенность Квадратичной формой диагональной матрицы , где при является Т.е. представляет собой взвешенную сумму квадратов и позволяет легко судить о значении суммы на основании значений диагональных элементов. Собственные значения и собственные векторы матрицы Рассмотрим систему однородных алгебраических уравнений: где неизвестный скалярный параметр.  Значения параметра, для которого существуют нетривиальные ( ненулевые) решения системы уравнений, называются собственными числами матрицы .  Соответствующие собственным числам векторные решения называются собственными векторами матрицы . Система уравнений в векторных обозначениях имеет вид: Перенеся правую часть уравнения влево, получим , где- единичная матрица. Это уравнение обладает нетривиальным решением только тогда, когда определитель равен нулю: Разложение этого определителя приводит к характеристическому уравнению: Корни этого уравнения и есть собственные числа матрицы . Соответствующие каждому из этих значений векторные решения исходного уравнения составят собственных векторов, для которых, очевидно: Свойства : а) Все собственные значения действительной симметрической матрицы есть действительные числа. б) Собственные векторы действительной симметрической матрицы, соответствующие различным собственным значениям попарно ортогональны. в) Существует, по крайней мере, одно ортогональное множество векторов, удовлетворяющее условию нормализации т.е. . Диагонализация матриц Пусть - различные собственные значения симметрической матрицы , и - соответствующая им система нормализованных собственных векторов. Рассмотрим матрицу столбцами, которой служат собственные векторы. Распишем выражение , но для собственных векторов справедливо следовательно . Домножим выражение слева на матрицу : Учитывая, что имеем Произведем в квадратичной форме, замену переменных полагая , тогда или развертывая выражение имеем . Таким образом, мы получаем возможность судить о свойствах матрицы по ее собственным числам 1. Квадратичная форма является положительно определенной тогда, и только тогда, когда все собственные числа матрицы положительны. 2. Квадратичная форма является положительно полуопределенной, тогда и только тогда, когда все собственные значения неотрицательны и хотя бы одно из них равно нулю. 3. Квадратичная форма является неопределенной, когда матрица обладает как положительными, так и отрицательными собственными значениями. Пример: Исследовать экстремальные точки функции при Гессиан Характеристическое уравнение матрицы Все собственные значения положительные и равны 2. Матрица положительно определена. Пример: Найти максимумы и минимумы функции Необходимые условия удовлетворяются при Достаточное условие Характеристическое уравнение Рассматривая все точки, видим: а) — неопределенная матрица, седловая точка; б) матрица отрицательно определена - точка максимума. в) — точка минимума. г) — седловая точка. Метод последовательных исключений Для симметрической матрицы найти такую матрицу и диагональную матрицу , чтобы выполнялось равенство . Рассмотрим процедуру на примере. Положим а) Выберем ведущий элемент и разделим на него первую строку б) Умножим полученную первую строку на и вычтем из второй в) Выберем в качестве ведущего элемента ненулевой элемент второй строки и разделим на вторую строку матрицы : . Получением треугольной матрицы (на диагонали которой 1) процесс исключения заканчивается. Положим . В том что действительно выполняется равенство можно убедиться непосредственно. Произведем замену переменных в квадратичной форме ; тогда Таким образом, о свойствах квадратичной формы и, соответственно, симметрической матрицы мы можем судить по свойствам квадратичной формы и, соответственно, диагональной матрицы . Главный минор Ведущий главный минор порядка матрицы порядка строится путем исключения из матрицы последних строк и соответствующих столбцов. Положительно определенная матрица: а) Все диагональные элементы должны быть >0 б) Все ведущие главные миноры >0 Положительно полуопределенная матрица: а) Все диагональные элементы должны быть неотрицательны б) Все ведущие главные миноры неотрицательны. Пример: Главные миноры равны таким образом матрица положительно определенная. Примеры: - положительно определенная; - положительно полуопределенная; - отрицательно полуопределенная; -отрицательно определенная; - неопределенная; положительно определенная. Лекция 4. Численные методы безусловной минимизации В этом разделе мы будем рассматривать задачи безусловной минимизации функции переменных. Требуется минимизировать при отсутствии ограничений на , -вектор оптимизируемых параметров, - скалярная целевая функция. Методы, ориентированные на решение задач безусловной оптимизации, можно разделить на три класса в соответствии с типом используемой в них информации: 1. Методы прямого поиска, основанные на вычислении только значений целевой функции. 2. Градиентные методы, в которых используются точные значения первых производных . 3. Методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции . Методы прямого поиска. Метод покоординатного спуска Простейшим методом многомерного поиска является метод покоординатного спуска. Он состоит в последовательном изменении каждого оптимизируемого параметра до тех пор, пока не будет достигнут минимум целевой функции. Рассмотрим двумерную целевую функцию, подходящую для решения задачи этим методом. Особенность функции в том, что линии уровня близки по форме к эллипсам, оси которых параллельны осям координат. Если же оси наклонены к осям координат, то эффективность алгоритма снижается. Метод покоординатного спуска совершенно не применим, если линии уровня имеют точки излома. Движение от точки, находящейся на линии излома параллельно любой из координатных осей приводит к увеличению значения целевой функции. Достоинством метода является возможность использования любого из методов одномерного поиска для движения вдоль координатной оси. Поэтому его часто используют на первой стадии решения задачи, применяя затем более эффективные методы. Для оценки эффективности методов были предложены ряд функций, которые, из-за своих свойств являются тестовыми для таких методов. Функция Розенброка: Функция_Пауэлла Двумерная экспоненциальная функция: Симплексный поиск Простейшая стратегия поиска, состоящая в циклическом повторении движения вдоль координатных осей, приводит не только к малоэффективным алгоритмам, но и может привести к отсутствию сходимости к точке локального минимума даже при бесконечном количестве итераций. Метод поиска по симплексу позволяет найти выход из подобных состояний, так как направление движения в нем зависит от топологических свойств функции в исследуемой точке пространства параметров. В процедуре симплексного поиска экспериментальным образцом, позволяющим определить направление уменьшения целевой функции, является регулярный симплекс. Регулярный симплекс в N-мерном пространстве представляет собой многогранник, образованный равноотстоящими друг от друга точками (вершинами). Например, в случае двух переменных симплексом является равносторонний треугольник; в трехмерном пространстве симплекс представляет собой тетраэдр. В алгоритме используется важное свойство симплексов, согласно которому новый симплекс можно построить на любой грани начального симплекса, путем переноса выбранной вершины вдоль прямой, проведенной через эту вершину и центр тяжести остальных вершин. Алгоритм определяет следующую последовательность шагов: 1. Построить регулярный симплекс в пространстве независимых переменных. Обозначим вершины . 2. Найти значения функции в вершинах симплекса . 3. Найти точку, в которой функция имеет наибольшее значение 4. Найти центр тяжести всех остальных точек, за исключением . Пусть центром тяжести будет . 5. Спроецировать вершину через центр тяжести остальных вершин в новую точку . 6. Образовать новый симплекс, заменив в старом вершину на вершину . Пояснения: п.1. Построение исходного симплекса можно производить по заданной начальной точке и масштабном множителе , вычисляя остальные вершины по следующим формулам: Величина множителя выбирается исследователем. При , ребра симплекса имеют единичную длину. п.5. Отразить точку относительно центра тяжести в точку . Итеративное повторение пунктов 2-6 будет продолжаться до тех пор, пока не возникнет циклическое движение по двум и более симплексам. В этой ситуации можно воспользоваться следующими правилами: если некоторая вершина симплекса не исключается на протяжении итераций, то необходимо уменьшить размеры симплекса и построить новый симплекс, выбрав в качестве базовой точку, в которой функция имеет минимальное значение. Например можно вычислить по формуле , где- размерность задачи. Коэффициент уменьшения симплекса устанавливается исследователем. Критерий окончания поиска: Поиск завершается, когда размеры симплекса или разности между значениями функции в вершинах становятся достаточно малыми. Изложенный алгоритм обладает рядом достоинств: 1. Логическая структура метода отличается сравнительной простотой. 2. Уровень требования к объему памяти ЭВМ невысокий. Массив имеет размерность . 3. Алгоритм оказывается эффективным даже в тех случаях, когда ошибка вычислений значений целевой функции велика, поскольку оперирует наибольшими значениями функции, а не наименьшими. Алгоритм обладает также рядом существенных недостатков: 1. Не исключено возникновение трудностей, связанных с масштабированием, поскольку все координаты вершин симплекса зависят от одного масштабного множителя . В практических задачах следует промасштабировать переменные, чтобы они были сравнимы по величине. 2. Алгоритм работает медленно, так как полученная на предыдущих итерациях информация не используется для ускорения поиска. Метод Хука-Дживса Метод Хука-Дживса является одним из первых методов поиска ( 1961 год), в котором при определении нового направления учитывается информация, полученная на предыдущих итерациях. Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки, за которой, в случае успеха, следует поиск по образцу. Исследующий поиск. Для проведения исследующего поиска выбирается базисная точка , и шаг длиной для каждого из направлений . Каждая переменная по очереди изменяется прибавлением длины шага. Если это приводит к уменьшению значения функции- единичный вектор, направленный вдоль оси , то точка заменяется на точку. В противном случае вычисляется значение функции в точке . Когда будут рассмотрены все координатных осей, мы будем иметь новую базисную точку . Поиск по образцу заключается в реализации единственного шага из новой базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой точкой. Новая точка образца определяется в соответствии с формулой. — текущая базовая точка. — предыдущая базовая точка. — новая базовая точка. — точка, построенная при движении по образцу. Алгоритм поиска: 1. Задать: начальную точку приращение коэффициент уменьшения шага параметр окончания поиска 2. Провести исследующий поиск в точке . 3. Если найдена точка с меньшим значением целевой функции перейти к п.5. 4. Проверка на окончание поиска. Если выполняется неравенство прекратить поиск, иначе уменьшить приращение по формуле .Перейти к п.2. 5. Провести поиск по образцу. 6. Провести исследующий поиск в базовой точке . Пусть полученная в результате точка. 7. Если выполняется неравенство , то положить , т.е. принять точку в качестве базовой и перейти к шагу 5, иначе перейти к шагу 4. Пояснение к п.6,7: Требуется возвратиться в точку и провести исследующий поиск в точке с уменьшенным шагом.Рисунок Метод Хука-Дживса отличается несложной стратегией поиска и невысоким уровнем требований к объему памяти ЭВМ, который даже ниже, чем в случае использования метода поиска по симплексу. Благодаря этому алгоритм находит широкое применение. Однако необходимо отметить, что алгоритм при наличии значительных нелинейных эффектов вырождается в последовательность исследовательских поисков без перехода к ускоряющему поиску по образцу. Лекция 5. Градиентные методы. В предыдущем разделе рассматривались методы, позволяющие получить решение задачи на основе использования только значений целевой функции. Важность прямых методов несомненна, поскольку в ряде практических инженерных задач информация о значениях целевой функции является единственной надежной информацией, которой располагает исследователь. С другой стороны, при использовании даже самых эффективных прямых методов для получения решения требуется иногда вычисление слишком большого количества значений целевой функции. Это обстоятельство приводит к необходимости рассмотрения методов, основанных на использовании градиента целевой функции. Все они основаны на итерационной процедуре, реализуемой в соответствии с формулой: , где - текущее приближение к решению , - параметр, характеризующий длину шага, - направление поиска в N-мерном пространстве оптимизируемых параметров. Метод наискорейшего спуска. Определим в некоторой точке -пространства переменных направление наискорейшего локального уменьшения целевой функции. Разложим целевую функцию в окрестностях точки в ряд Тейлора: и отбросим члены второго порядка и выше. Очевидно, что локальное уменьшение целевой функции определяется вторым слагаемым, так как фиксировано. В более простом виде скалярное произведение моно записать так: , где - угол между векторами и . Для заданной величины скалярное произведение будет иметь минимальное отрицательное значение при , т. е. когда направление противоположно направлению градиента. Поэтому в основе простейшего градиентного метода наискорейшего спуска лежит формула , где - заданный положительный параметр. Метод обладает двумя недостатками: а) возникает необходимость выбора подходящего значения ; б) методу свойственна медленная сходимость к точке минимума вследствие малости в окрестности этой точки. Таким образом, задает направление, в котором следует двигаться, а шаг перемещения определяется параметром на каждой итерации . Значение вычисляется путем решения задачи минимизации вдоль направления с помощью того или иного метода одномерного поиска. Задача минимизации функции на прямой , где эквивалентна задаче минимизации функции при фиксированном значении точки . Метод наискорейшего спуска обладает важным свойством, которое заключается в том, что при достаточно малом шаге итерации обеспечивается выполнение неравенства . Кроме того, метод, как правило, позволяет существенно уменьшить значение целевой функции при движении из точек, расположенных на значительном расстоянии от точки минимума, и поэтому часто используется при реализации градиентных методов в качестве начальной процедуры. Метод Ньютона-Рафсона. Нетрудно видеть, что в методе наискорейшего спуска используется “наилучшая” локальная стратегия поиска с использованием градиента. Однако движение в направлении, противоположном градиенту, приводит в точку минимума лишь в том случае, когда линии уровня функции представляют собой окружности. Таким образом, направление, противоположное градиенту, в общем случае не может быть приемлемым глобальным направлением поиска оптимума нелинейных функций. В этом нет ничего удивительного, поскольку метод основывается на линейной аппроксимации целевой функции в окрестности текущей точки ; Если в разложении непрерывной функции в ряд Тейлора сохранить еще один член разложения, то получим аппроксимацию любой функции в окрестности точки квадратичной функцией следующего вида: ; где - матрица Гессе, матрица вторых частных производных, вычисленная а точке . Например. Если , то соответствующий Гессиан представляет собой матрицу . Разумной аппроксимацией минимума функции может быть минимум функции . Если минимум функции находится в точке , то ; откуда . . Таким образом, можно модифицировать общее итерационное уравнение градиентных методов и записать его в виде или в варианте , где длина шага определяется одномерным поиском вдоль оси направления . Пример. Найти минимум функции . ; ; . Обратная матрица определяется из условия: , в данном случае . Обращение диагональных матриц проблем не представляет . При по формуле метода Ньютона-Рафсона получаем точка является точкой оптимума. Возьмем другую начальную точку , тогда , т. е. снова . Таким образом задача минимизации квадратичной функции решается по методу Ньютона-Рафсона с помощью одной итерации при любой начальной точке. В случае произвольного вида функции потребуется большее количество итераций. Причем метод требует вычисления и обращения матрицы Гессе на каждом шаге, что часто является основной частью вычислений. Если точка близко расположена к точке оптимума, то сходимость метода будет быстрой, поскольку квадратичная функция хорошо аппроксимирует функцию общего вида в малой окрестности оптимальной точки. Можно сказать, что, если метод наискорейшего спуска эффективен при поиске на значительных расстояниях от точки минимума и плохо работает в окрестности этой точки, то метод Ньютона-Рафсона не отличается высокой надежностью при поиске из удаленной точки, однако оказывается весьма эффективным, когда находится вблизи точки минимума. Метод сопряженных градиентов Флетчера-Ривса. Метод сопряженных градиентов обладает положительными свойствами двух других градиентных методов и основан на вычислении значений только первых производных. Основная идея алгоритма заключается в том, что если квадратичная функция N переменных приведена к виду суммы полных квадратов, то ее оптимум может быть найден в результате реализации N одномерных поисков по преобразованным координатным направлениям. Например. - квадратичная функция общего вида; - функция вида суммы полных квадратов, т. е. функция не содержит перекрестных произведений аргументов. Процедура преобразования квадратичной функции к виду суммы квадратов эквивалентна нахождению такой матрицы преобразования , которая приводила бы матрицу квадратичной формы к диагональному виду. Таким образом заданная квадратичная форма путем преобразования координат приводится к виду , где - диагональная матрица, т. е. ее элементы отличны от нуля только при i=j. Например. Рассмотрим функцию и преобразование ; . или где . Подставив выражения для и в функцию получим квадратичную функцию, преобразованную к виду суммы квадратов . Пусть - j-я строка матрицы , тогда преобразование позволяет записать каждый вектор в виде линейной комбинации векторов . Иначе говоря, вместо координат вектора в стандартной координатной системе, где мы записываем функцию f от координат вектора в новой координатной системе . Поскольку матрица преобразований квадратичной формы имеет диагональный вид, то при записи функции в новой координатной системе оси эллипсов, изображающее линии уровня, будут осями координат. Итак, с помощью преобразования переменных квадратичной функции строится новая система координат, параллельных осям квадратичной функции. Следовательно, поиск методом покоординатного спуска в новой координатной системе дает максимальный эффект и позволяет достигнуть минимума функции ровно за N итераций (одномерных поисков). Полученная система векторов, приводящих матрицу к диагональному виду называется системой -сопряженных направлений. Поскольку , а все недиагональные элементы матрицы равны нулю, то следовательно . Отсюда вытекает следующее определение сопряженных направлений: Пусть - симметрическая матрица порядка ; Два направления и сопряжены относительно матрицы , если . В методе Флетчера-Ривса для получения сопряженных градиентов используется квадратичная аппроксимация функции и значения компонент градиента. Исходя из сказанного предположим, что целевая функция является квадратичной . Итерации, как и в других градиентных методах, проводятся по формуле . Для удобства записи введем обозначение градиента . Направление поиска на каждой итерации определяется с помощью следующих формул . Иначе говоря, формируется следующая последовательность N векторов-направлений. ; ; ; : . Коэффициенты выбираются таким образом, чтобы всякое направление было сопряжено по матрице со всеми построенными ранее направлениями поиска. Рассмотрим первое направление . Наложим на него условие сопряженности с направлением : , откуда . На начальной итерации, согласно формуле (2): ; следовательно или (11). Свойство 1 (квадратичной функции). Пусть пространстве переменных заданы 2 произвольные несовпадающие точки и . Градиент квадратичной функции равен . Таким образом Запишем изменение градиента при переходе от точки к точке . . Используя свойство 1 квадратичных функций из выражения (11) получаем ; откуда (14). Свойство 2. Пусть из точки производится поиск минимума функции в направлении . Иначе говоря, находится минимум функции . Тогда в точке минимума производная функции равна нулю . Последнее означает, что вектор , задающий направление поиска, направлен в точку по касательной к линии уровня. В свою очередь, градиент функции в точке перпендикулярен касательной, и следовательно, произведение векторов и равно нулю . Учитывая свойство 2 из уравнения (14), получаем . В общем случае, используя свойство 1 и свойство 2 можно доказать, что в формуле коэффициенты . Отсюда следует общая формула для направлений поиска, предложенная Флетчером и Ривсом: (16). Таким образом, если - квадратичная функция, то для нахождения точки минимума требуется провести N одномерных поисков вдоль сопряженных направлений, полученных по формуле (16). Если же функция не является квадратичной, количество поисков возрастает. На основе поисков предполагается на каждом N+1ом шаге принимать за направление поиска направление наискорейшего спуска , то есть возвращаться к началу алгоритма. Следующая блок-схема реализует эту идею. Лекция 6. Оптимизация при наличии ограничений. Ограничения в виде равенств. Рассмотрим общую задачу минимизации, содержащую K ограничений в виде равенств: минимизировать при ограничениях где Если систему из K уравнений можно разрешить относительно K неизвестных, то эти переменные можно из целевой функции вообще исключить. Наличие ограничений в виде равенств позволяет в этом случае уменьшить размерность исходной задачи с N до N-K и получить при этом задачу безусловной минимизации. Пример. Минимизировать при ограничении . Выразим переменную из равенства и исключим ее из целевой функции . Получим, таким образом, задачу безусловной минимизации функции двух переменных . Для оптимизации такой функции можно использовать один из методов, рассмотренных выше. Однако возможны ситуации, когда аналитическое выражение одной пременной через другие получить невозможно. Например, если ограничение задать в виде . Кроме того, при наличии большого числа ограничений процесс исключения переменных становится трудоемкой задачей. Множители Лагранжа. Метод множителей Лагранжа позволяет преобразовать задачу с ограничениями в виде равенств в задачу безусловной минимизации. Рассмотрим задачу минимизации функции двух переменных с учетом одного ограничения: минимизировать при ограничении . В соответствии с методом множителей Лагранжа исходная задача преобразуется в следующую: . Функция называется функцией Лагранжа, а - неизвестный коэффициент, который носит название множителя Лагранжа. Необходимые условия минимума функции Лагранжа могут быть записаны в следующем виде: Решениями этой системы трех уравнений являются значения в точке минимума функции Лагранжа. Однако, как нетрудно заметить, в точке минимума выполняется ограничение , а при этом минимум функции совпадает с минимумом функции . Действительно, при Пример. Минимизировать при ограничении . Используя функцию Лагранжа перейдем к задаче безусловной минимизации. Минимизировать . Приравняем компоненты градиента к нулю: Таким образом, минимум функции достигается в точке , следовательно, минимум функции при ограничении достигается в точке . Метод множителей Лагранжа можно распространить на случай функции переменных при наличии m ограничений в виде равенств. Рассмотрим задачу минимизации функции , где на пеерменную наложены ограничения . Функция Лагранжа принимает следующий вид , где - множители Лагранжа, то есть неизвестные параметры, которые необходимо определить. Приравнивая нулю частные производные функции по компонентам вектора , получаем систему уравнений с неизвестными: Ограничения в виде равенств дополнят систему недостающими уравнениями. Решение расширенной системы из уравнений определяет стационарную точку функции . Таким образом необходимые условия минимума функции при наличии ограничений-равенств можно записать в следующем виде: Ограничения в виде неравенств. Рассмотрим задачу нелинейного программирования, поставленную в следующем виде: минимизировать функцию при наличии ограничений . Ограничения в виде неравенств называются активными в точке , если и неактивными, если в точке выполняется строгое неравенство . В настоящее время нет метода, гарантирующего существование решения любой подобной задачи. Ограничения в виде неравенств могут быть преобразованы в ограничения в виде равенств путем добавления к каждому из них неотрицательной ослабляющей переменной : . Таким образом, задача сводится к минимизации функции при наличии ограничений в виде равенств. Испоьзуем для решения полученной задачи метод множителей Лагранжа. Сформируем функцию Лагранжа: . Необходимыми условиями существования минимума будут следующие: (1) (2) (3) Умножив последнее уравнение на получим , то есть (4). Уравнения 1,2,4 являются необходимыми условиями минимума при наличии ограничений. Уравнения 2 являются также повторной записью ограничивающих неравенств . Уравнение 3 означает, что либо , либо . Если , то и ограничение является активным и представляет собой ограничения в виде равенства. С другой стороны, если ограничение является строгим неравенством , то соответствующий множитель Лагранжа . Действительно, неактивные ограничения следует исключить из уравнений 4, так как они учтены в формулах 2. Есть также дополнительное условие, которое должно быть выполнено в точке минимума . Окончательно можно записать следующую систему необходимых условий минимума функции при наличии ограничений в виде неравенств. Эти условия известны как условия Куна-Таккера. Примеры: 1) 2) Общая задача нелинейного программирования Кун и Таккер обобщили метод множителей Лагранжа на случай общей задачи нелинейного программирования с ограничениями как в виде равенств, так и в виде неравенств: Минимизировать при ограничениях . . Условия Куна-Таккера,определяющие необходимые условия оптимальности для задачи нелинейного программирования, записываются в следующем виде: . (1) (2) (3) (4) (5) Пример. Минимизировать при ограничениях ; ; . Решение. Запишем задачу как общую задачу нелинейного программирования в принятых обозначениях : Вычислим градиенты функций: Условие (1) Куна-Таккера принимает вид откуда или Уравнения (4), известные как условия дополняющей нежесткости, принимают вид . Заметим, что на переменные и накладывается треюование неотрицательности – условие (9). Окончательно условия Куна-Таккера записываются в следующем виде: Лекция 7. Методы штрафных функций. Рассмотрим задачу нелинейного программирования следующего вида: Минимизировать , (1) при ограничениях , (2) (3) . (4) Предполагается, что для вектора , являющегося решением этой задачи, известно некоторое начальное приближение , возможно недопустимое, т.е. не удовлетворяющее соотношениям (1-4). С помощью штрафной функции исходная задача условной минимизации преобразуется в последовательность задач безусловной минимизации. Конкретные методы, основанные на указанной схеме, определяются видом штрафной функции, а также правилами пересчета штрафных параметров. В общем виде штрафная функция определяется выражением: , где - вектор штрафных параметров, - так называемый штраф, зависящий от и функций, задающих ограничения. Очевидно, любой метод, основанный на преобразовании задачи условной минимизации в задачу безусловной минимизации, может представлять интерес лишь при выполнении следующих требований: 1. Решения подзадач должны стремиться к решению исходной задачи; 2. Сложность минимизации должна быть того же порядка, что и для функции . Основные типы штрафов. а) Квадратичный штраф. Квадратичный штраф используется для учета ограничений-равенств и имеет вид . При минимизации этот штраф препятствует отклонению величины от нуля ( как в сторону положительных, так и в сторону отрицательных значений). Минимум штрафной функции приближается к точке при увеличении штрафного параметра . В пределе при имеем ; . Квадратический штраф обладает двумя положительными качествами: • функция непрерывна, • функция имеет непрерывные производные. б) Бесконечный барьер. В данном случае штрафная функция называется барьерной, поскольку штраф здесь как бы создает барьер из бесконечно больших значений функции по границе допустимой области. При допустимых значениях барьерная функция принимает нулевое значение, а в недопустимых точках барьер равен бесконечности. Строго говоря, машинная реализация бесконечных штрафов невозможна. В качестве бесконечности можно использовать большое число. Например , где - множество индексов нарушенных ограничений, т.е. . В данном случае штрафная функция разрывна на границе допустимой области в) Логарифмический штраф. Логарифмический штраф задается формуой Это штраф положителен при всех , таких, что , и отрицателен при . В данном случае вводится искусственное разделение точек допустимой области: внутренним точкам отдается предпочтение перед точками, расположенными близко к границе. Логарифмический штраф – это барьерная функция, не определенная в недопустимых точках (т.е. для таких , что ). Поэтому при попадании по ходу поиска в недопустимую область должна срабатывать специальная процедура, обеспечивающая возврат в область допустимых значений. Итерационный процесс начинается из допустимой начальной точки при положительном начальном значении (например, при или ). После решения каждой подзадачи параметр уменьшается и в пределе стремится к нулю. г) Обратная штрафная функция. Обратная штрафная функция имеет вид . Штраф, заданный обратной функцией, не имеет отрицательных значений в допустимой области. В допустимых точках вблизи границы значения штрафа положительны и быстро убывают при движении от границы внутрь допустимой области. Этот штраф, как и предыдущий, также является барьером. В этом случае также приходится бороться с появлением недопустимых точек, поскольку в недопустимых точках штраф принимает отрицательные значения. Итерации начинаются с начальной допустимой точки при положительном значении . В процессе вычислений стремится к нулю. д) Штраф типа квадратичной срезки. Обозначим срезку Тогда штраф типа квадратичной срезки будет иметь вид: . Штраф удобен тем, что функция определена и непрерывна всюду, причем недопустимые точки не создают дополнительных сложностей по сравнению с допустимыми, так как различие между ними лишь в том, что в допустимых и граничных точках штраф равен нулю. С другой стороны, точки минимума функции могут оказаться недопустимыми. Итерации производятся с положительным , после решения очередной задачи безусловной оптимизации увеличивается. Пример1. Минимизировать при ограничении . Используя квадратичный штраф введем штрафную функцию . Определим минимум полученной функции классическим методом. Запишем необходимые условия минимума функции : Находим координаты оптимальной точки в зависимости от : . Переходя в этом выражении к пределу, получаем: . Таким образом, метод сходится к точке , в которой . Численная реализация метода штрафных функций состоит в последовательном применении метода безусловной минимизации к функции , при значении изменяющихся от к . Посчитаем оптимальные точки функции при различных значениях . а) Имеем задачу минимизации функции . Минимум достигается в точке , . Заметим, что в вычисленной точке значение функции меньше оптимального из-за нарушения условия . Действительно, . b). Функция имеет минимум в точке . Значение функции . Изобразим линии уровня функции . Точка оптимума приближается к реальной, а отклонение функции от нуля заметно уменьшается: . По существу, коэффициент играет роль весового коэффициента, определяющего относительную значимость ограничения и целевой функции. с). . Точка оптимума , . Таким образом, при увеличении точка минимума смещается все больше в сторону действительно оптимальной точки. d) Таким образом, при в случае точного решения задачи мы получаем оптимальную точку с двумя верными знаками. Возникает вопрос: зачем тогда начинать поиск оптимальной точки со значения ? Не лучше ли начать прямо с ? Такое намерение наталкивается, однако, на ощутимые трудности, связанные с тем, что форма линий уровня функции зависит от . С ростом линии уровня функции становятся все более вытянутыми вдоль прямой , и поэтому сложность решения задачи безусловной минимизации резко возрастает. Поэтому предпочтительнее становится стратегия многошагового последовательного приближения к решению задачи. Проблема выбора рациональной последовательности значений штрафных коэффициентов является основной проблемой, влияющей на эффективность вычислительного процесса. Пример 2. Заменим в задаче 1 ограничение-равенство на ограничение-неравенство . При этом решение задачи остается прежним. Запишем штрафную функцию, используя штраф типа квадрата срезки. Имеем или в данном случае Необходимые условия существования минимума имеют вид: Откуда, в силу симметричности выражений следует, что . С учетом этого получаем . Проанализируем результат, полагая аргумент оператора срезки равным нулю, большим нуля и меньшим нуля. а) - противоречие. б) - противоречие. в), откуда . Переходим к пределу Сделанное предположение (в) не нарушается. При итерационном приближении к точке минимума при возрастающих значениях получим следующую последовательность точек : 1 10 100 4 3 2.59 2.5 Из решения видно, что при любом конечном полученная точка не входит в допустимую область, так как не выполняется неравенство . По этой причине метод, использующий штраф в виде квадрата срезки называется методом внешней точки. Траектория движения к решению задачи представляет собой отрезок прямой, соединяющей точку безусловного минимума функции с точкой ее условного минимума . Используем теперь применительно к этой же задаче логарифмический штраф , т.е. . Условия минимума функции В силу симметричности выражений . С учетом этого имеем , откуда . Один из корней дает координату искомой стационарной точки . Устремляя к нулю получаем в пределе . Координаты оптимальных точек при различных значениях : -1.8 1.5 2.34 2.48 2.5 100 10 1 0.1 Убеждаемся, что стационарные точки штрафной функции сходятся к при . При этом каждая стационарная точка является допустимой. Поэтому методы, использующие штрафы, в виде логарифмической функции называются методами внутренней точки. Приведенные примеры демонстрируют принципиальную возможность использования методов штрафных функций для решения задач условной оптимизации. Однако, применяя его, необходимо иметь в виду два обстоятельства: во-первых, сходимость метода зависит от степени вытянутости линий уровня штрафной функции; во-вторых, метод может быть эффективным лишь в том случае, если все подзадачи безусловной минимизации могут быть решены с достаточной степенью точности. Алгоритм метода штрафных функций Обозначим - параметр окончания одномерного поиска; - параметр окончания безусловной оптимизации; - параметр окончания работы алгоритма; - начальное приближение для ; - начальный вектор штрафных параметров; Лекция 8. Методы прямого поиска в задачах условной оптимизации В методах прямого поиска для отыскания точек оптимума используется только целевая функция и ограничения. Как и в задачах безусловной оптимизации, необходимость разработки этих методов связана с тем, что в технических приложениях часто приходится сталкиваться с задачами, в которых функции разрывны и недифференцируемы. Поскольку эти методы строятся на интуитивных соображениях, не подкрепленных строгой теорией, то их сходимость к оптимальному решению не гарантируется. В то же время, они позволяют получать достаточно хорошие ( но не обязательно оптимальные ) решения. Кроме того, в силу своей логической простоты эти методы легко реализуемы. Метод комплексов Метод комплексов представляет собой модификацию метода поиска по симплексу применительно к задачам условной оптимизации. Изменение коснулось двух основных положений: При реализации метода прямого поиска по симплексу симплекс преобразуется путем проектирования «худшей» точки вдоль прямой проходящей через центр тяжести остальных точек симплекса. В задачах с ограничениями новая точка может оказаться недопустимой. Тогда ее можно сдвинуть к центру тяжести, пока она не станет допустимой. -недопустимая точка, полученная в результате преобразований симплекса -новая точка, расположенная внутри допустимой области, получена перемещением точки. 1. При наличии ограничений затруднительно построение точек исходного симплекса, поскольку велика вероятность попадания их в недопустимую область. Автор метода Бокс предложил строить множество пробных точек случайным образом. Если заданы верхние и нижние границы изменения каждой переменной и последовательность псевдослучайных чисел , равномерно распределенных на отрезке , то координаты точки определяются с помощью формулы. Таким образом, для получения точки в -мерном пространстве требуется случайных чисел. Каждая полученная точка проверяется на допустимость и если какое-нибудь из ограничений не выполняется то она сдвигается к центру тяжести уже построенных точек до тех пор пока не получится допустимая точка. Общее число точек должно быть не меньше , но может быть и больше. После того как множество исходных точек построено его преобразование осуществляется следующим образом. Определяется точка с наихудшим значением целевой функции и отбрасывается. Новая точка получается путем отражения исключаемой точки через центр тяжести остальных точек. Если -исключаемая точка,-центр тяжести остальных точек, то новая точка определяется как . Параметр задает расстояние отражения : при имеет место равенство ; соответствует растяжению; соответствует сжатию. После замены «худшей» точки на новую возможны следующие ситуации: 1. Новая точка допустимая и значение целевой функции в ней лучше, чем в точке . В этом случае находим новую «худшую» точку и осуществляем операцию отражения. 2. Новая точка допустимая, но значение целевой функции в ней не лучше, чем в точке . Передвинем эту точку на половину расстояния до ранее найденного центра тяжести (иначе возможно зацикливание). Если то новый шаг будет выполнен в противоположном направлении и может привести к дальнейшему ухудшению значения функции. 3. Новая точка недопустимая. Передвинем точку на половину расстояния до ранее найденного центра тяжести. Очевидно, что при принятой стратегии поиска по мере приближения к оптимуму точки многогранника будут стягиваться к центру тяжести. Поэтому условием окончания процедуры будет достижение многогранником заданных малых размеров или получение достаточно малой разницы между значениями целевой функции в вершинах симплекса. Бокс провел численные эксперименты по описанному алгоритму и на основе их анализа рекомендует выбирать и . Бокс также рекомендует, если новая точка выходит за границы допустимых значений переменных, то соответствующую координату принимать равной граничному значению. Выбор больше единицы компенсирует сжатие комплекса, обусловленное сокращением в два раза расстояния до центра тяжести. Большое число вершин используется для предотвращения «уплощения» и вырождения комплекса, когда поиск ведется вблизи границы допустимой области. Пример движения вдоль границы допустимой области: Алгоритм метода комплексов Уровень 0: type точка: -мерный вектор; var комплекс из точек l: boolean. Begin (а) Случайным образом определить координаты точек комплекса; repat (б) Определить точку комплекса , имеющую худшее значение в целевой функции . (в) Отобразить точку , относительно центра тяжести остальных точек комплекса, получить новую, допустимую точку комплекса. (г) Проверить условия окончания вычислений, - присвоить значение истинности условия окончания. until ; end. Уровень 0 а 1: var n:integer; begin n:=0; repeat n:=n+1; (а) Случайным образом определить координаты n-ого вектора while -недопустимая точка do begin (б) найти центр тяжести уже определенных точек комплекса (в) переместить точку в направлении центра тяжести end. Замечание. Для выполнения процедуры 0 а 1 необходимо задать верхние и нижние границы значений всех переменных: 0 в 1 begin (а) Найти центр тяжести точек комплекса без учета точек ; (б) Найти новую точку ; while -недопустимая точка или do (в) (г) Включить точку в комплекс вместо точки ; end. 0 г 1 var l1,l2: boolean; f: integer; точка; begin end. Методы случайного поиска Выборки с уменьшением интервала В методе используются серии случайных выборок. Наилучшая точка каждой серии используется как начальная точка следующей серии. Точки каждой последующей серии выбираются из интервала меньшей величины. Задается - количество серий; - количество опытов в серии; - начальное допустимое решение; - оценка величины начального интервала; . - параметр уменьшения интервала . Алгоритм: Шаг 1. Для вычислить , где -случайная величина, равномерно распределенная на интервале . Шаг 2. Если - недопустимая точка и , повторить шаг 1. Если - допустимая точка, запомнить и . Если , найти среди всех допустимых точек точку с наименьшим значением и положить ее равной . Шаг 3. Уменьшить интервал, полагая . Шаг 4. Если , закончить вычисления. В противном случае, увеличить и продолжить вычисления, начиная с шага 1. Если положить , количество опытов в серии ; число серий . Начальный единичный интервал сводится к интервалу . Для этого требуется примерно испытаний. Таким образом, для простой задачи небольшой размерности, в которой каждая проверка допустимости и подсчет значений целевой функции требует не более секунды, общие затраты времени можно считать приемлемыми. Для более реальных задач описанный алгоритм может оказаться слишком дорогостоящим. Адаптивный алгоритм случайного поиска с переменным шагом Для повышения эффективности методов случайного поиска предлагаются эвристические алгоритмы, которые включают элементы методов спуска в общую схему поиска. В данном алгоритме случайные выборки используются для определения направления поиска. Длина шага изменяется в зависимости от результата поиска: если две последовательные итерации дают улучшение целевой функции, величина шага увеличивается в раз. Если же последовательных итераций не дают улучшения, то величина шага уменьшается в раз. Алгоритм. Даны параметры и начальная точка . Для определения условия окончания вычислений вводится минимальное значение шага . Рекомендуется выбрать . Уровень 0. Ввод ; {- величина шага} ; {- количество неудачных точек выбранных подряд} repeat (а) Найти случайным образом точку для которой . случайная точка найдена. If =true then Begin ; if then begin ; ; end else ; until 0 а 1 repeat (а) получить случайный вектор единичной длины; ; if then begin end; until or ; Комбинаторный эвристический алгоритм Алгоритм первоначально был разработан для решения задач проектирования машин и механизмов. Основная идея алгоритма состоит в разбиении интервалов значений каждой независимой переменной на участки дискретных значений, и реализации случайного поиска на полученной дискретной решетке. Непрерывная область значений переменных заменяется на узлы дискретной решетки. Алгоритм. Begin (а) Построить случайную допустимую точку и положить . Repeat (б) (Покоординатный спуск) Для каждой переменной провести оптимизацию по - ой переменной при фиксированных значениях остальных. Получить новую базовую точку и . Until улучшение функции не достигнуто. 0 б 1 for i=1 to N do «Покоординатный спуск» begin (а) Выбрать случайным образом возможные значения -ой переменной для нахождения дополнительных допустимых точек с лучшим значением целевой функции по сравнению с базовой точкой. (б) Провести упреждающий поиск. end; 0 б 1 в Упреждающий поиск (а) Для каждого из допустимых решений, найденных для переменной . Выбрать допустимых значений переменной . (б) Выбрать наилучшую из допустимых точек. Зафиксировать значение переменной , соответствующее этой точке, как оптимальное. Пояснения. а) Авторы алгоритма утверждают, что -т.е. число упреждающих точек, должно лежать между 3 и 5. б) Во всех случаях следует ограничивать количество попыток при поиске точек дающих улучшение целевой функции. Если точек получить не удается надо переходить к следующей переменной. Обсуждение методов прямого поиска Подготовка задачи к решению. Общая задача условной оптимизации содержит ограничения в виде равенств, неравенств, а также верхние и нижние границы значений переменных: Минимизировать При ограничениях Существенная проблема заключается в том, что алгоритмы методов прямого поиска работают только с допустимыми точками пространства переменных. Как мы убедились при рассмотрении методов прямого поиска, если задача содержит ограничения только в виде неравенств, то существуют эвристические приемы, позволяющие перевести пробную точку из недопустимой области в допустимую. Если же недопустимая точка, то оперируя лишь значениями функций, входящих в ограничения, трудно изменить координаты точки так, чтобы выполнилось ограничение равенства. Трудности получения допустимой точки в задачах с ограничениями в виде равенств приводят к тому, что все методы прямого поиска требуют, чтобы ограничения были заданы только в виде неравенств. Следовательно, ограничения в виде равенств должны быть явно или неявно исключены перед решением задачи. 1. Метод комплексов. Хотя метод комплексов не требует непрерывности функции, так как не используем значений производных, строго говоря, необходимо чтобы допускаемая область была выпуклой. Это условие оказывается существенным при нахождении центра тяжести, так как предполагается, что центр тяжести допускаемых точек также будет допускаемой точкой. Это может оказаться неверным, если допускаемая область невыпуклая. Аналогичная ситуация может возникнуть при сдвиге допустимой, но неудовлетворительной по значению целевой функции точки. Сдвинутая точка может оказаться недопустимой даже если центр тяжести- недопустимая точка. Следовательно, для невыпуклых областей метод комплексов расходится. Сходимость метода комплексов так же существенно замедляется, если пробные точки располагаются вдоль границы допустимой области. Поэтому используется специальный прием, при котором вычисления несколько раз прерываются по какому-либо критерию и затем алгоритм выполняется сначала из точки, имеющей наилучшее значение целевой функции. Хотя метод, вообще говоря, сходится медленно, на практике он широко используется в технических приложениях и дает хорошие результаты для выпуклых задач. 2. Метод случайного поиска. По имеющимся данным о вычислительных экспериментах, алгоритм случайного поиска целесообразно использовать либо для задач небольшой размерности, либо как вспомогательный прием для определения хорошей начальной точки. Известно, что любые процедуры случайного поиска, охватывающего большую часть допустимой области, существенно улучшают возможности обнаружения глобального оптимума, в случае многоэкстремальных задач. Из рассмотренных методов, адаптивные процедуры являются более эффективными, так как они позволяют использовать накопленную информацию.