7.2. Множители Лагранжа. Методы оптимизации некрасова м г

7.2. Множители Лагранжа | Решение задач по математике и другим предмета

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

Для начала рассмотрим случай для функции двух переменных.

Определение. Условным экстремумом функции Z=F(X, Y) называется экстремум этой функции, достигнутый при условии, что переменные X и Y связаны уравнением (X, Y)=0 (уравнение связи).

Отыскание условного экстремума можно свести к исследованию на обычный экстремум так называемой функции Лагранжа U=F(X, Y)+(X, Y), где  - неопределенный постоянный множитель.

Необходимые условия экстремума функции Лагранжа имеют вид

Из этой системы из трех уравнений можно найти неизвестные X, Y, .

Для того, чтобы найти наибольшее и наименьшее значения функции в замкнутой области, надо:

1) найти стационарные точки, расположенные в данной области, и вычислить значения функции в этих точках;

2) найти наибольшее и наименьшее значения функции на линиях, образующих границу области;

3) из всех найденных значений выбрать наибольшее и наименьшее.

Рассмотрим задачу минимизации функции N переменных с учетом одного ограничения в виде равенства:

Минимизировать F(X1, X2, …, XN)

При ограничениях h2(X1, X2, …,XN) = 0

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:

Минимизировать L(X; V) = F(X) – Vh2(X).

Функция L(X; V) называется функцией Лагранжа, V – неизвестная постоянная, которая носит название Множителя Лагранжа. На знак V никаких требований не накладывается.

Пусть при заданном значении V = V0 безусловный минимум функции L(X; V) по X достигается в точке X = X0 и X0 удовлетворяет уравнению h2(X0) = 0. Тогда X0 минимизирует F(X1, X2, …, XN) с учетом h2(X1, X2, …,XN) = 0, поскольку для всех значений X, удовлетворяющих h2(X1, X2, …,XN) = 0, h2(X) = 0 И Min L(X; V) = Min F(X).

Необходимо подобрать значение V = V0 таким образом, чтобы координата точки безусловного минимума X0 удовлетворяла равенству h2(X1, X2, …,XN) = 0. Это можно сделать, если, рассматривая V как переменную, найти безусловный минимум функции L(X; V) = F(X) – Vh2(X) в виде функции V, а затем выбрать значение V, при котором выполняется равенство h2(X1, X2, …,XN) = 0.

Пример 66. Минимизировать

При ограничении

Решение. Соответствующая задача безусловной оптимизации записывается в следующем виде:

Минимизировать

Приравняв две компоненты градиента L к нулю, получим

Для того чтобы проверить, соответствует ли стационарная точка X0 Минимуму, вычислим элементы матрицы Гессе функции L(X; V), рассматриваемой как функция Х,

Которая оказывается положительно определенной. Это означает, что L(X; V) – выпуклая функция Х. Следовательно, координаты определяют точку Глобального минимума. Оптимальное значение V находится путем подстановки значений в уравнение 2х1 + х2 = 2, откуда 2V +V/2 = 2 или V0 = 4/5. Таким образом, условный минимум достигается при

При решении задачи из Примера 66 мы рассматривали L(X; V) как функцию двух переменных Х1 и Х2 и, кроме того, предполагали, что значение параметра V выбрано так, чтобы выполнялось ограничение. Если же решение системы

В виде явных функций V получить нельзя, то значения X и V находятся путем решения следующей системы, состоящей из N + 1 уравнений с N + 1 неизвестными:

Для нахождения всех возможных решений данной системы можно использовать численные методы поиска. Для каждого из решений (X0; V0) следует вычислить элементы матрицы Гессе функции L, рассматриваемой как функция Х, и выяснить, является ли эта Матрица положительно определенной (локальный минимум) или отрицательно определенной (локальный максимум).

Пример 67. Минимизировать

При ограничении

Решение.

Эта система трех уравнений с тремя неизвестными имеет два решения:

Матрица Гессе функции L(X; V), рассматриваемой как функция Х, равна

Вычислив элементы матрицы H для каждого из двух решений, находим, что матрица

положительна определена,

А матрица отрицательно определена.

Следовательно, (X(2); V2) соответствует максимуму функции L, рассматриваемой как функция Х; оптимальное решение

Заметим, что (X(1); V1) соответствует минимуму L.

Здесь необходимо подчеркнуть, что если мы рассмотрим L как функцию трех переменных, а именно переменных х1, х2 и V, то точки (X(1); V1) и (X(2); V2) не окажутся точками минимума или максимума L как функции X и V. На самом деле они являются Седловыми точками функции L(X; V).

Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств. Рассмотрим общую задачу, в которой требуется

Минимизировать F(X)

При ограничениях Hk(X) = 0, K = 1, 2, …, K.

Функция Лагранжа принимает следующий вид:

Здесь V1, V2, …, Vk – множители Лагранжа, т. е. неизвестные параметры, значения которых необходимо определить. Приравнивая частные производные L по Х к нулю, получаем следующую систему N уравнений с N неизвестными:

Если найти решение приведенной выше системы в виде функций вектора V оказывается затруднительным, то можно расширить систему путем включения в нее ограничений в виде равенств

Решение расширенной системы, состоящей из N + K уравнений с N + K неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция Х, подобно тому, как это было проделано в случае задачи с одним ограничением.

Для некоторых задач расширенная система N + K уравнений с N + K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что на практике такие задачи встречаются достаточно редко.

< Предыдущая Следующая >

matica.org.ua

6.2. Метод наискорейшего спуска | Решение задач по математике и другим

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

В текущей точке вычисляется Grad F(X), и затем в направлении градиента ищется Min F(X). Практически это может быть осуществлено любым методом одномерной оптимизации (поиск по одному направлению – направление градиента), наиболее часто используется сканирование до первого локального минимума по направлению Grad F(X).

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

В ряде случаев можно повысить скорость выхода в район оптимума предъявлением невысоких требований к точности поиска Min по направлению (задается величиной H – шагом поиска по направлению). Условием окончания может являться малость модуля градиента функции F(X): |Grad F(X)| < . Можно также использовать и малость приращений по переменным в результате шага, но только в том случае, если на данном шаге мы «проскочили» оптимум, иначе может оказаться, что малость шага обусловлена не близостью к оптимуму, а малостью коэффициента пропорциональности шага H.

В ряде случаев используют уменьшение шага поиска оптимума по направлению после каждой смены направления. Условием окончания поиска в этом случае является достижение заданной малой величины шага.

Метод наискорейшего спуска отличается от градиентного спуска способом определения величины Hk, которая находится из условия:

(*)

Такой выбор Hk Обеспечивает максимально возможное уменьшение функции F(X) вдоль направления ее антиградиента В точке Х(K).

Таким образом, для определения Hk на каждом шаге метода наискорейшего спуска решается одномерная задача минимизации функции ФK(H), для чего можно использовать рассмотренные выше методы одномерной оптимизации.

Пример 64. Минимизировать функцию методом наискорейшего спуска, завершив вычисления при , I = 1, 2.

Решение. Найдем частные производные:

1-й шаг. Положим Х(0) = (0, 0), тогда

Функцию Ф0(H) находим, используя соотношение (*). Для нахождения точки минимума функции Ф0(H) используем метод Пауэлла. Поскольку шаг H изменяется в пределах 0 < H < 1, то за первоначальное значение примем H = 0, а H = 0.5. Таким образом находим H0 = 0.22.

Значит, Х(1) =(0, 0) – 0.22(1, 1) = (-0.22, -0.22).

Вычислим значение производных: F(-0.22, -0.22) = (0.204, -0.236). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

2-й шаг. Составим функцию:

Снова используем метод Пауэлла, полагая H = 0 и H = 0.5, Находим h2 = 0.32.

Значит, Х(2) =(-0.22,-0.22) – 0.32(0.204, -0.236) = (-0.2853, -0.1445).

Вычислим значение производных: F(-0.2853, -0.1445) = (0.08, 0.0726). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

3-й шаг. Составим функцию:

Используем метод Пауэлла, полагая H = 0 и H = 0.5, Находим h3 = 0.24.

Значит, Х(3) =(-0.2853-0.240.08, -0.1445-0.240.0726) = (-0.3045, -0.1619).

Вычислим значение производных: F(х(3)) = (0.0182, -0.0205). Условия завершения поиска выполняются, поэтому требуемая точность достигнута и

Пример 65. Минимизировать функцию F(X, Y) = X3+2Y2-3X-4Y, методом градиентного спуска с дроблением шага, завершив вычисления при

Решение. Найдем частные производные:

1-й шаг. Положим Х(0) = (0, 0), тогда

Значит, Х(1) =(0, 0) – 0.281(-3, -4) = (0.843, 1.124).

Вычислим значение производных: F(х(1)) = (-0.8681, 0.496). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

2-й шаг. Составим функцию:

Снова используем метод Пауэлла, полагая H = 0 и H = 0.5, Находим h2 = 0.2121.

Значит, Х(2) =(0.833+0.21210.8681, 1.124-0.21210.496) = (1.0171, 1.0188).

Вычислим значение производных: F( х(2)) = (0.1035, 0.0752). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

3-й шаг. Составим функцию:

Используем метод Пауэлла, полагая H = 0 и H = 0.5, Находим h3 = 0.2196.

Значит, Х(3) =(1.0171-0.21960.1035, 1.0188-0.21960.0752) = (0.9944, 1.002).

Вычислим значение производных: F(х(3)) = (-0.0335, 0.008). Условия завершения поиска выполняются, поэтому требуемая точность достигнута и

Вопросы к главе 6

Метод градиента

1. Что называется градиентом функции двух переменных?

2. Как оценивается эффективность поиска градиентным методом?

3. Какой алгоритм коррекции шага предпочтительнее вблизи оптимума?

4. Почему в районе оптимума величина шага х убывает при использовании

Алгоритма ?

5. Исходя из определения Gradf(X) как вектора, указывающего направление

Возрастания функции, что лучше искать: Min или Max?

Метод наискорейшего спуска

1. В чем основные отличия метода наискорейшего спуска от метода градиента?

2. По какому направлению осуществляется поиск из каждой текущей точки при

Поиске Minf(X)?

3. Как вычисляется градиент F(X) в методе наискорейшего спуска?

4. Каковы условия окончания поиска?

5. Можно ли методом наискорейшего спуска найти Maxf(X)?

< Предыдущая Следующая >

matica.org.ua

4.7. Метод Пауэлла | Решение задач по математике и другим предметам!!!

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

Алгоритм метода Пауэлла:

Шаг 1. Вычислить

Шаг 2. Вычислить F(X1) и F(X2).

Шаг 3. Если F(X1) > F(X2), положить Если Положить .

Шаг 4. Вычислить F(X3) и найти

Шаг 5. По трем точкам Х1, х2, х3 Вычислить, Используя формулу оценивания квадратичной аппроксимации:

Шаг 6. Проверка на окончание поиска.

А) является ли разность достаточно малой?

Б) является ли разность достаточно малой?

Если оба условия выполняются, закончить поиск. В противном случае перейти к шагу 7.

Шаг 7. Выбрать «наилучшую» точку () и две точки по обе стороны от нее. Обозначить эти точки в естественном порядке и перейти к шагу 4.

Заметим, что при первой реализации шага 5 границы интервала, содержащего точку минимума, не обязательно оказываются установленными. При этом полученная точка может находиться за точкой Х3 . Поэтому следует провести после шага 5 дополнительную проверку и в случае, когда точка находится слишком далеко от Х3, заменить точкой, координата которой вычисляется с учетом заранее установленной длины шага.

Пример 22. Минимизировать функцию F(X) = 2X2 + (16/X).

Решение. Пусть начальная точка X1 = 1 и длина шага X = 1. Для проверки на окончание поиска используются следующие параметры сходимости:

Итерация 1.

Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Шаг 5. Используя метод параболической аппроксимации, находим

Шаг 6. Проверка на окончание поиска:

Следовательно, продолжаем поиск.

Шаг 7. Выбираем «наилучшую» точку, и точки, их окружающие. Обозначаем эти точки в естественном порядке Переходим к итерации 2, которая начинается с шага 4.

Итерация 2.

Шаг 4.

Шаг 5.

Шаг 6. Проверка на окончание поиска:

Следовательно, продолжаем поиск.

Шаг 7. Выбираем «наилучшую» точку, и точки, их окружающие. Обозначаем эти точки в естественном порядке Переходим к итерации 3, которая начинается с шага 4.

Итерация 3.

Шаг 4.

Шаг 5.

Шаг 6. Проверка на окончание поиска:

Точность достигнута. Следовательно, поиск закончен.

Получили

Пример 23. Найти минимальное значение F* и точку минимума Х* функции . Точку Х* Найти с точностью =0,05.

Решение. Пусть начальная точка X1 =3 и длина шага X = 1. Для проверки на окончание поиска используются следующие параметры сходимости:

Итерация 1.

Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Шаг 5. Используя метод параболической аппроксимации, находим

Шаг 6. Проверка на окончание поиска:

Так как пункт А) Не выполняется, то продолжаем поиск.

Итерация 2.

Шаг 4.

Шаг 5.

Шаг 6. Проверка на окончание поиска:

Следовательно, продолжаем поиск.

Итерация 3.

Шаг 4.

Шаг 5.

Шаг 6. Проверка на окончание поиска:

Продолжаем поиск.

Шаг 7. Выбираем «наилучшую» точку, и точки, их окружающие. Обозначаем эти точки в естественном порядке Переходим к итерации 4, которая начинается с шага 4.

Итерация 4.

Шаг 4.

Шаг 5.

Шаг 6. Проверка на окончание поиска:

Условия окончания поиска выполняются, следовательно, вычисления заканчиваем.

Получили

Пример 24. НАйти точку минимума Х* функции с точностью =0,05.

Решение. Пусть начальная точка X1 = 0,5 и длина шага X = 0,2. Для проверки на окончание поиска используются следующие параметры сходимости:

Итерация 1.

Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Шаг 5. Используя метод параболической аппроксимации, находим

Шаг 6. Проверка на окончание поиска:

Так как пункт А) Не выполняется, то продолжаем поиск.

Итерация 2.

Шаг 4.

Шаг 5.

Шаг 6. Проверка на окончание поиска:

Условия окончания поиска выполняются, следовательно, вычисления заканчиваем.

Получили

< Предыдущая Следующая >

matica.org.ua

Некрасова, Марина Геннадьевна - Методы оптимизации и теория управления : учебное пособие

Поиск по определенным полям

Чтобы сузить результаты поисковой выдачи, можно уточнить запрос, указав поля, по которым производить поиск. Список полей представлен выше. Например:

author:иванов

Можно искать по нескольким полям одновременно:

author:иванов title:исследование

Логически операторы

По умолчанию используется оператор AND. Оператор AND означает, что документ должен соответствовать всем элементам в группе:

исследование разработка

author:иванов title:разработка

оператор OR означает, что документ должен соответствовать одному из значений в группе:

исследование OR разработка

author:иванов OR title:разработка

оператор NOT исключает документы, содержащие данный элемент:

исследование NOT разработка

author:иванов NOT title:разработка

Тип поиска

При написании запроса можно указывать способ, по которому фраза будет искаться. Поддерживается четыре метода: поиск с учетом морфологии, без морфологии, поиск префикса, поиск фразы. По-умолчанию, поиск производится с учетом морфологии. Для поиска без морфологии, перед словами в фразе достаточно поставить знак "доллар":

$исследование $развития

Для поиска префикса нужно поставить звездочку после запроса:

исследование*

Для поиска фразы нужно заключить запрос в двойные кавычки:

"исследование и разработка"

Поиск по синонимам

Для включения в результаты поиска синонимов слова нужно поставить решётку "#" перед словом или перед выражением в скобках. В применении к одному слову для него будет найдено до трёх синонимов. В применении к выражению в скобках к каждому слову будет добавлен синоним, если он был найден. Не сочетается с поиском без морфологии, поиском по префиксу или поиском по фразе.

#исследование

Группировка

Для того, чтобы сгруппировать поисковые фразы нужно использовать скобки. Это позволяет управлять булевой логикой запроса. Например, нужно составить запрос: найти документы у которых автор Иванов или Петров, и заглавие содержит слова исследование или разработка:

author:(иванов OR петров) title:(исследование OR разработка)

Приблизительный поиск слова

Для приблизительного поиска нужно поставить тильду "~" в конце слова из фразы. Например:

бром~

При поиске будут найдены такие слова, как "бром", "ром", "пром" и т.д. Можно дополнительно указать максимальное количество возможных правок: 0, 1 или 2. Например:

бром~1

По умолчанию допускается 2 правки.

Критерий близости

Для поиска по критерию близости, нужно поставить тильду "~" в конце фразы. Например, для того, чтобы найти документы со словами исследование и разработка в пределах 2 слов, используйте следующий запрос:

"исследование разработка"~2

Релевантность выражений

Для изменения релевантности отдельных выражений в поиске используйте знак "^" в конце выражения, после чего укажите уровень релевантности этого выражения по отношению к остальным. Чем выше уровень, тем более релевантно данное выражение. Например, в данном выражении слово "исследование" в четыре раза релевантнее слова "разработка":

исследование^4 разработка

По умолчанию, уровень равен 1. Допустимые значения - положительное вещественное число.

Поиск в интервале

Для указания интервала, в котором должно находиться значение какого-то поля, следует указать в скобках граничные значения, разделенные оператором TO. Будет произведена лексикографическая сортировка.

author:[Иванов TO Петров]

Будут возвращены результаты с автором, начиная от Иванова и заканчивая Петровым, Иванов и Петров будут включены в результат.

author:{Иванов TO Петров}

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

search.rsl.ru