Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 519748)
Консорциум Контекстум Информационная технология сбора цифрового контента
Уважаемые СТУДЕНТЫ и СОТРУДНИКИ ВУЗов, использующие нашу ЭБС. Рекомендуем использовать новую версию сайта.

Методы оптимизации (90,00 руб.)

0   0
АвторыБелоусова Елена Петровна, Смагина Тамара Ивановна
ИздательствоИздательский дом ВГУ
Страниц46
ID685297
АннотацияПособие написано по двум разделам курса "Методы оптимизации". Первый раздел относится к нелинейному программированию и содержит задачи оптимизации функций одной и нескольких переменных, как без ограничений, так и с ограничениями типа равенств. Второй раздел посвящен изучению вариационного исчисления.
Кому рекомендовано Рекомендовано студентам 4-го курса факультета ПММ, обучающихся по специальности 01.03.03 "Механика и математическое моделирование для направления "Прикладная математика и информатика".
Методы оптимизации [Электронный ресурс] / Е.П. Белоусова, Т.И. Смагина .— Воронеж : Издательский дом ВГУ, 2017 .— 46 с. — 46 с. — Режим доступа: https://rucont.ru/efd/685297

Предпросмотр (выдержки из произведения)

Методы_оптимизации.pdf
Стр.1
Стр.3
Стр.6
Стр.7
Стр.8
Стр.9
Стр.10
Методы_оптимизации.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МЕТОДЫ ОПТИМИЗАЦИИ Учебно-методическое пособие Составители: Е. П. Белоусова, Т. И. Смагина Воронеж Издательский дом ВГУ 2017
Стр.1
1. Конечномерная оптимизация (Математическое программирование) §1. Конечномерные задачи без ограничений Рассмотрим задачу f(x) → extr, x ∈ Rn. (1.1) 1. Необходимое условие экстремума первого порядка. Пусть f : En → R и имеет непрерывные частные производные ∂f/∂xi, i = 1, n. Точка x0 называется точкой локального максимума функции f, если существует окрестность B(x0, r) такая, что для всех x ∈ B(x0, r) выполнено неравенство f(x0)  f(x). Здесь B(x0, r) = {x ∈ En : x − x0 < r}. Теорема Ферма. Если x0 - точка локального экстремума дифференцируемой функции f, то ∂f/∂xi = 0 для всех i = 1, n. Или f (x0) = grad f(x0) = 0. Здесь grad f(x) - это вектор из частных производных функции f(x) по переменным x1, ..., xn. Точка x0 такая, что grad f(x0) = 0 называется стационарной. 2. Необходимое условие экстремума второго порядка. Достаточное условие. Пусть f дважды непрерывно дифференцируема. Разложим ее в ряд Тейлора в окрестности точки x0: f(x0 + h) = f(x0) + (f (x0), h) + 1/2(f (x0)h, h) + o( h 2). (1.2) Матрица f (x0) = (∂2f/∂xi∂xj)(x0) является симметричной. Симметричная матрица A называется положительно определенной [неотрицательно определенной], если для всех 0 = x ∈ Rn выполнено неравенство (Ax, x) > 0 [(Ax, x)  0]. 3
Стр.3
§2. Задачи с ограничениями типа равенств. Необходимые и достаточные условия экстремума. Пусть fk : En → R, k = 0,m - дважды дифференцируемые функции. Требуется найти экстремум функции f0(x) при ограничениях fk(x) = 0, k = 1,m, т.е. решить задачу f0 → extr, fk(x) = 0, k = 1, m. Построим функцию Лагранжа L(x, λ0, λ) = λ0f0(x) + где λ0 ∈ R, λ = (λ1, ..., λm) ∈ Em - множители Лагранжа. Задача на экстремум с ограничениями типа равенств сводится к задаче на m k=1 безусловную оптимизацию для функции Лагранжа. Теорема (принцип Лагранжа). Пусть x0 - точка локального экстремума в задаче (2.1) и функции f0, fk, k = 1,m – непрерывно дифференцируемы в окрестности точки x0. Тогда существует ненулевой вектор множителей Лагранжа (λ0, λ) = (λ0, λ1, ..., λm) такой, что для функции Лагранжа выполняется условие стационарности Lx(x0, λ) = 0 ⇔ λ0f 0(x) + Lλ(x0, λ0, λ) = 0 ⇔ fk(x0) = 0, k = 1, ..., m. m k=1 Замечание. Для определения x0, λ0, λ получаем систему из n+m уравнений, а неизвестных n+m+1. Поэтому каждой точке локального экстремума соответствует бесконечное множество наборов множителей Лагранжа. Если среди систем множителей Лагранжа, соответствующих точке локального экстремума, нет множителей с λ0 = 0, то такая точка называется точкой нормального экстремума. Для нормальной точки локального экстремума множители Лагранжа определяются однозначно. 6 λkf k(x0) = 0. (2.2) λkfk(x), (2.1)
Стр.6
Следует рассмотреть два случая: 1) λ0 = 0; обычно отсюда следует, что и λ = 0, т.е. этот случай не подходит; 2) λ0 = 0; тогда полагают λ0 = 1. Решая систему (2.2), находят все стационарные (подозрительные на экстремум) точки. Дальнейшее исследование проводят так же, как и в случае безусловного экстремума. Условия экстремума второго порядка связаны со знаком матрицы вторых производных Lxx функции Лагранжа. Теорема (необходимое условие минимума). Пусть выполнены следующие условия: 1) x0 - точка локального минимума в задаче (2.1); 2) функции fk(x), k = 1,m дважды непрерывно дифференцируемы в окрестности этой точки (условие гладкости); 3) градиенты f 1(x0), ..., f m(x0) линейно независимы, т.е dimL{f 1(x0), ..., f m(x0) = m} (условие регулярности). Оно эквивалентно тому, что λ0 = 0. Тогда существует набор множителей Лагранжа (λ0, λ) = (λ0, λ1, ..., λm) такой, что для функции Лагранжа задачи (2.1) выполняются условия стационарности Lx(x0, λ0, λ) = 0 ⇔ λ0f 0(x0) + m k=1 λkf k(x0) = 0, (2.3) Lλ(x0, λ0, λ) = 0 ⇔ fk(x0) = 0, k = 1, m, где Lx - вектор из частных производных функции Лагранжа по переменным x и неотрицательности: (Lxx(x0, λ0, λ)h, h)  0 ∀h : таких, что (f k(x0), h) = 0, k = 1,m (2.4), 7
Стр.7
где Lxx - матрица из вторых частных производных функции Лагранжа по переменным x. Теорема (достаточное условие минимума). Пусть существует точка x0, что выполнены условия 2) гладкости и 3) регулярности предыдущей теоремы и существует набор множителей Лагранжа (λ0, λ), что для функции Лагранжа задачи (2.2) выполняются условие стационарности: Lx(x0, λ0, λ) = 0 ⇔ λ0f 0(x0) + m k=1 λkf k(x0) = 0 k = 1,m; Lλ(x0, λ0, λ) = 0 ⇔ fk(x0) = 0, k = 1,m и условие положительности: (Lxx(x0, λ)h, h) > 0 ∀h = 0 : таких, что (f k(x), h) = 0, k = 1, m. Тогда x0 - точка локального минимума в задаче (2.2). Всякое замкнутое ограниченное множество в Rn является компактным, поэтому верна Теорема Вейерштрасса. Непрерывная функция на непустом ограниченном замкнутом множестве в Rn достигает абсолютных максимума и минимума. Следствие1. Если f(x) непрерывна на Rn и lim|x|→∞ = +∞ (lim|x|→∞ = −∞), то f достигает своего абсолютного минимума (максимума) на любом замкнутом подмножестве в Rn. Правило решения. Для решения задачи (2.2) с ограничениями типа равенств следует: 1) составить функцию Лагранжа L(x, λ0, λ) = λ0f0(x) + 8 m k=1 λkfk(x);
Стр.8
2) выписать условие стационарности функции Лагранжа Lx(x0, λ0, λ) = 0 ⇔ и ограничения - равенства fk(x) = 0, k = 1,m; 3) из полученной системы найти стационарные точки x0. Целесообразно проанализировать два случая: а)λ0 = 0. Данный вырожденный случай на практике случается достаточно m k=0 редко. В большинстве задач это предположение приводит к тривиальности всех множителей Лагранжа. В некоторых примерах удается сразу убедиться в линейной независимости градиентов ограничений при всех допустимых x. Тогда этот вариант рассматривать не надо. b)λ0 = 0. В этом случае удобно принять λ0 = 1. 4) Найденные стационарные точки исследуются на локальный экстремум с помощью достаточного условия. Иногда стоит проверить квадратичную форму Lxx на строгую знакоопределенность на всем пространстве Rn с помощью критерия Сильвестра и лишь затем (если это будет необходимо) выяснять вопрос о знаке Lxx на множестве, определяемом ограничениями задачи. 5) Если не выполняется достаточное условие, то надо проверить выполнение необходимого условия экстремума. Задача. Найти параметры цистерны, которая при заданной площади поверхности S имеет минимальный объём V . Если обозначить через x1 высоту, а через x2 радиус основания, то приходим к задаче V = πx2 при ограничении S = 2πx2 x2 1 + x2 2 + 2πx1x2. Пример 1. Решить задачу f0(x) = 4x1 + 3x2 → extr при ограничении 2 = 1. 9 2x1 → min λkf k(x0) = 0
Стр.9
Решение. Составим функцию Лагранжа L(x, λ0, λ) = λ0(4x1 + 3x2) + λ1(x2 1 + x2 2 − 1). Для нахождения стационарной точки выпишем необходимое условие  Lx1 Lx2 Lλ1 : x2 : 4λ0 + 2λ1x1 = 0 : 3λ0 + 2λ1x2 = 0 1 + x2 2 − 1 = 0. 1). Рассмотрим случай λ0 = 0. Тогда λ1x1 = 0 и λ1x2 = 0, откуда следует, что либо λ1 = 0 (чего не может быть), либо x1 = 0 и x2 = 0, чего также не может быть, ибо тогда не выполняется ограничение задачи. Таким образом, λ0 = 0 и можно положить λ0 = 1. Из системы находим, что λ1 = − 2 что x1 = ±4 A(4 5, 3 для точки B . Найдём матрицу вторых производных. Имеем 5) и B(−4 x1 и x1 = 4  4 + 2λ1x1 = 0 3 + 2λ1x2 = 0 3x2. Из ограничения задачи x2 5, −3 5). Множитель Лагранжа λ1 = −5 поэтому матрица Lxx < 0 в точке A и Lxx > 0 для точки B . Поэтому (4 Lxx =  2λ1 0 0 2λ1 , 5, 3 x4 5) ∈ loc max, а (−4 5, −3 5) ∈ loc min. 1 + x4 Пример 2. Решить задачу f0 = x2 2 = 1. 1 + x2 2 → extr при ограничении Решение. Составим функцию Лагранжа L(x, λ0, λ) = λ0(x2 1 + x2 10 1+x2 2 = 1 следует, 5 и x2 = ±3 5. Таким образом, получены две стационарные точки 2 для точки A и λ1 = 5 2 2) + λ1(x4 1 + x4 2).
Стр.10

Облако ключевых слов *


* - вычисляется автоматически