lopt1 (1013489)

Файл №1013489 lopt1 (Лекционный курс)lopt1 (1013489)2017-06-17СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ЛЕКЦИИЛекция 1Раздел I. ТЕОРИЯ ОПТИМИЗАЦИИ1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИИ ОСНОВНЫЕ ПОЛОЖЕНИЯПостановка задачи поиска минимума функций содержит:• целевую функцию f ( x) , где x = ( x1 ,..., xn )T , определенную на n-мерном евклидовом пространстве R n . Ее значения характеризуют степень достижения цели, воимя которой поставлена или решается задача;• множество допустимых решений X ⊆ R n , среди элементов которого осуществляется поиск.Требуется найти такой вектор x ∗ из множества допустимых решений, которомусоответствует минимальное значение целевой функции на этом множестве:f ( x∗ ) = min f ( x) .(1.1)x ∈XЗ а м е ч а н и я.1.

Задача поиска максимума функции f ( x) сводится к задаче поиска минимума путем замены знака перед функцией на противоположный (рис. 1):f ( x∗ ) = max f ( x) = − min [ − f ( x) ] .x∈ Xx∈ Xff ( x∗ )f ( x)x∗x− f ( x)− f ( x∗ )Рис. 12. Задача поиска минимума и максимума целевой функции f ( x) называется задачей поиска экстремума: f ( x∗ ) = extr f ( x) .x ∈X53. Если множество допустимых решений X задается ограничениями (условиями),накладываемыми на вектор x , то решается задача поиска условного экстремума. ЕслиX = R n , т.е. ограничения (условия) на вектор x отсутствуют, решается задача поискабезусловного экстремума.4. Решением задачи поиска экстремума является пара ( x∗ , f ( x∗ )) , включающаяточку x ∗ и значение целевой функции в ней.5. Множество точек минимума (максимума) целевой функции f ( x) на множествеX обозначим X ∗ . Оно может содержать конечное числo точек (в том числе одну), бесконечное число точек или быть пустым.Определение 1.1.

Точка x∗ ∈ X называется точкой глобального (абсолютного) минимума функции f ( x) на множестве X , если функция достигает в этой точке своего наименьшего значения, т.е.f ( x∗ ) ≤ f ( x) ∀x ∈ X .Определение 1.2. Точка x ∗ ∈ X называется точкой локального (относительного)минимума функции f ( x) на множестве допустимых решений X , если существует ε > 0 ,такое, что если x ∈ X и x − x ∗ < ε , то f ( x∗ ) ≤ f ( x) .

Здесь x = x12 + x 22 +...+ x n2 –евклидова норма вектора x .З а м е ч а н и я.1. В определении 1.1 точка x ∗ сравнивается по величине функции со всеми точками из множества допустимых решений X , а в определении 1.2 – только с принадлежащими ее ε -окрестности (рис. 2).x2Xεx∗x1Рис. 22.

Если в определениях 1.1 и 1.2 знак неравенства ≤ заменить на ≥ , то получимопределения глобального (абсолютного) и локального (относительного) максимумов.3. Глобальный экстремум всегда является одновременно локальным, но не наоборот.6Определение 1.3. Поверхностью уровня функции f ( x) называется множество точек, в которых функция принимает постоянное значение, т.е.

f ( x) = const . Если n = 2 ,поверхность уровня изображается линией уровня на плоскости R 2 .Пример. Построить линии уровня функций:x1222а) f ( x) = x1 + x2 ; б) f ( x) =+ x22 ;4† Уравнения линий уровня имеют следующий вид:а) f ( x) = x12 + x22 = const = r 2 – уравнение окружностей с центром в точке (0, 0)Tирадиусом, равным r (рис.

3, а);x2б) f ( x) = 1 + x22 = const – уравнение эллипса. Если const = 1 , то a = 2 и b = 1 –4большая и малая полуоси (рис. 3, б) . „x2ff ( x) =x12+f ( x) = const = 42x221x2x12f ( x) = 0f ( x) = const = 1x1а)x2ff ( x) =x1242+ x22f ( x) = 41−42f ( x) = 0x2x1б)Рис. 374f ( x) = 1x1Определение 1.4. Градиентом ∇f ( x) непрерывно дифференцируемой функцииf ( x) в точке x называется вектор-столбец, элементами которого являются частные производные первого порядка, вычисленные в данной точке:⎛ ∂ f ( x) ⎞⎜⎟⎜ ∂ x1 ⎟⎜ ∂ f ( x) ⎟⎜⎟∇f ( x) = ⎜ ∂ x2 ⎟ .⎜⎟⎜⎟⎜ ∂ f ( x) ⎟⎜ ∂x ⎟n ⎠⎝Градиент функции направлен по нормали к поверхности уровня (см. определение1.3), т.е.

перпендикулярно к касательной плоскости, проведенной в точке x , в сторонунаибольшего возрастания функции в данной точке.Определение 1.5. Матрицей Гессе H ( x) дважды непрерывно дифференцируемойв точке x функции f ( x) называется матрица частных производных второго порядка, вычисленных в данной точке:⎛⎜⎜⎜⎜H ( x) = ⎜⎜⎜⎜⎜⎜⎝где hij =∂ 2 f ( x)∂x12∂ 2 f ( x)∂x2 ∂x12∂ f ( x)∂xn ∂x1∂ 2 f ( x) ⎞⎟∂x1∂xn ⎟⎟ ⎛ h11∂ 2 f ( x)∂ 2 f ( x) ⎟ ⎜h21∂x2 ∂xn ⎟ = ⎜∂x22⎟ ⎜⎟ ⎜⎟ ⎝ hn122∂ f ( x)∂ f ( x) ⎟…⎟∂xn ∂x2∂xn2 ⎠∂ 2 f ( x)∂x1∂x2h12h22hn 2h1n ⎞⎟h2n ⎟,⎟⎟hnn ⎠∂ 2 f ( x), i , j = 1,... , n .∂ xi ∂ x jЗ а м е ч а н и я.1. Матрица Гессе является симметрической размеров (n × n ) .2. Вместе с градиентом можно определить вектор антиградиента, равный по модулю вектору градиента, но противоположный по направлению.

Он указывает в сторонунаибольшего убывания функции в данной точке.3. С помощью градиента и матрицы Гессе, используя разложение в ряд Тейлора,приращение функции f ( x) в точке x может быть записано в формеΔf ( x) = f ( x + Δ x) − f ( x) = ∇f ( x)T Δ x +21 T2Δ x H ( x) Δ x + o ( Δ x ) ,2(1.2)где o ( Δ x ) – сумма всех членов разложения, имеющих порядок выше второго;Δ xT H ( x) Δ x – квадратичная форма.8Пример.

Для функции f ( x) = x12 + x24 вычислить градиент и найти матрицу Гессе вточках x 0 = (0, 0) , x 1 = (1,1) .TT† Согласно определениям 1.4 и 1.5 имеем:(∇f ( x) = 2 x1 , 4 x23)T0 ⎞⎛2, H ( x) = ⎜;⎜ 0 12 x 2 ⎟⎟2⎠⎝∇f ( x1 ) = ( 2, 4 )T⎛ 2 0⎞T∇f ( x 0 ) = ( 0, 0 ) , H ( x 0 ) = ⎜⎟;⎝0 0⎠⎛2 0 ⎞, H ( x1 ) = ⎜⎟. „⎝ 0 12 ⎠Определение 1.6. Квадратичная форма ΔxT H ( x) Δ x (а также соответствующая матрица Гессе H ( x) ) называется:• положительно определенной ( H ( x) > 0 ) , если для любого ненулевого Δ xвыполняется неравенство Δ xT H ( x) Δ x > 0 ;• отрицательно определенной ( H ( x) < 0 ) , если для любого ненулевогоΔxвыполняется неравенство Δ xT H ( x) Δ x < 0 ;• положительно полуопределенной ( H ( x) ≥ 0 ) , если для любого Δx выполняетсянеравенство Δ xT H ( x) Δ x ≥ 0 и имеется отличный от нуля вектор Δ x , для которого Δ xT H ( x) Δ x = 0 ;• отрицательно полуопределенной ( H ( x) ≤ 0 ) , если для любого Δ x выполняетсянеравенство Δ xT H ( x) Δ x ≤ 0 и имеется отличный от нуля вектор Δx , для которого Δ xT H ( x) Δ x = 0 ;x , что• неопределенной ( H (x ) >< 0 ) , если существуют такие векторы Δx , Δ ~выполняются неравенства Δ xT H ( x) Δ x > 0 , Δ xT H ( x) Δ x < 0 ;• тождественно равной нулю ( H ( x) ≡ 0 ) , если для любого Δx выполняетсяравенство Δ xT H ( x) Δ x = 0 .2.

НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ БЕЗУСЛОВНОГОЭКСТРЕМУМАПостановка задачиДана дважды непрерывно дифференцируемая функция f ( x) , определенная намножестве X = R n .Требуется исследовать функциюf ( x) на экстремум, т.е. определить точкиx ∗ ∈ R n ее локальных минимумов и максимумов на R n :f ( x∗ ) = min f ( x) ;x∈Rf ( x∗ ) = max f ( x) .nx∈R9n(2.1)Стратегия решения задачиНаходятся точки x ∗ локальных экстремумов с помощью необходимых условийпервого и второго порядка (порядок условий определяется порядком используемых производных), а также достаточных условий безусловного локального экстремума.

Вычисляются значения f ( x∗ ) функции в найденных точках локальных экстремумов.Утверждение 2.1 (необходимые условия экстремума первого порядка).Пусть x ∗ ∈ R n есть точка локального минимума (максимума) функции f ( x) намножестве R n и f ( x) дифференцируема в точке x ∗ . Тогда градиент функции f ( x)в точке x ∗ равен нулю, т.е.∇f ( x ∗ ) = 0(2.2)или∂ f ( x∗ )= 0,∂ xii = 1,... , n .(2.3)Определение 2.1. Точки x ∗ , удовлетворяющие условию (2.2) или (2.3), называютсястационарными.Утверждение 2.2 (необходимые условия экстремума второго порядка).Пусть точка x ∗ есть точка локального минимума (максимума) функции f ( x) намножестве R n и функция f ( x) дважды дифференцируема в этой точке. Тогда матрица Гессе H ( x∗ ) функции f ( x) , вычисленная в точке x ∗ , является положительно полуопределенной (отрицательно полуопределенной), т.е.H ( x∗ ) ≥ 0 ,(2.4)( H ( x∗ ) ≤ 0 ) .(2.5)Утверждение 2.3 (достаточные условия экстремума).Пусть функция f ( x) в точке x ∗ ∈ R n дважды дифференцируема, ее градиент равен нулю, а матрица Гессе является положительно определенной (отрицательно определенной), т.е.∇f ( x ∗ ) = 0 и H ( x ∗ ) > 0 ,(2.6)( H ( x∗ ) < 0 ) .(2.7)Тогда точка x ∗ есть точка локального минимума (максимума) функции f ( x) на множестве R n .10Определение 2.2.

Рассмотрим определитель матрицы Гессе H ( x∗ ) , вычисленнойв стационарной точкеdet H ( x∗ ) =1. Определители Δ1 = h11 ,h11h12h1nh21h22h2 nhn1hn 2hnnΔ2 =h11h12h21h22.h11h1n,..., Δ n =называютсяhn1hnnугловыми минорами.2. Определители m -го порядка ( m ≤ n ), получающиеся из определителя матрицыH ( x∗ ) вычеркиванием каких-либо ( n − m ) строк и ( n − m ) столбцов с одними и теми женомерами, называются главными минорами.Для проверки выполнения достаточных условий экстремума и необходимых условий второго порядка используются два способа.Первый способ (с помощью угловых и главных миноров – табл.

1).• Критерий проверки достаточных условий экстремума (критерий Сильвестра).Для того чтобы матрица Гессе H ( x∗ ) была положительно определенной( H ( x∗ ) > 0 ) и точка x ∗ являлась точкой локального минимума, необходимо и достаточно, чтобы знаки угловых миноров были строго положительны:Δ1 > 0 , Δ 2 > 0 ,..., Δ n > 0 .(2.8)Для того чтобы матрица Гессе H ( x ∗ ) была отрицательно определенной( H ( x ∗ ) < 0 ) и точка x ∗ являлась точкой локального максимума, необходимо и достаточно, чтобы знаки угловых миноров чередовались, начиная с отрицательного:Δ1 < 0 , Δ 2 > 0 , Δ 3 < 0 ,...,(−1)n Δ n> 0.(2.9)• Критерий проверки необходимых условий экстремума второго порядка.1. Для того чтобы матрица Гессе H ( x∗ ) была положительно полуопределенной( H ( x∗ ) ≥ 0 ) и точка x ∗ может быть являлась точкой локального минимума, необходимо и достаточно, чтобы все главные миноры определителя матрицы Гессе были неотрицательны.2.

Для того чтобы матрица Гессе H ( x∗ ) была отрицательно полуопределенной( H ( x∗ ) ≤ 0 ) и точка x ∗ может быть являлась точкой локального максимума, необходимо и достаточно, чтобы все главные миноры четного порядка были неотрицательны,а все главные миноры нечетного порядка – неположительны.11∗1п/п∗∇f ( x ) H ( x )Первый способТаблица 1Тип стационарной точки x ∗Локальный минимум10>0Δ1 > 0, Δ 2 > 0,..., Δ n > 020<030≥0Δ1 < 0, Δ 2 > 0,..., ( −1) Δ n > 0Все главные миноры определителяматрицы H ( x∗ ) неотрицательны40≤0Все главные миноры четногопорядка неотрицательны, а нечетного порядка неположительныМожет быть локальныйминимум, требуется дополнительное исследованиеМожет быть локальныймаксимум, требуется дополнительное исследование50=0Матрица Гессе состоит из нулевыхэлементовТребуется дополнительноеисследование60>0<Не выполняются условия п.

Характеристики

Тип файла
PDF-файл
Размер
306,8 Kb
Тип материала
Высшее учебное заведение

Тип файла PDF

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

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

Список файлов лекций

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6390
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее