УМК (1013374), страница 5

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

Текст из файла (страница 5)

Еслив этой точке d 2 L( x ∗ , λ ∗ ) > 0 ( d 2 L( x ∗ , λ ∗ ) < 0 ) для всех ненулевых dx ∈ R n таких, чтоdg j ( x*) = 0 , j = 1, … , m и j ∈ J a , λ∗j > 0 ( λ∗j < 0 );dg j ( x*) ≤ 0 , j ∈ J a , λ∗j = 0 ,то точка x ∗ является точкой локального минимума (максимума) в задаче (3.16).24Пример 3. Найти условный экстремум в задачеf ( x) = x12 + x 22 → extr ,g1 ( x) = x1 − 1 = 0 ,g 2 ( x) = x1 + x 2 − 2 ≤ 0 .† 1. Составим обобщенную функцию Лагранжа:L ( x, λ 0 , λ ) = λ 0 ( x12 + x 22 ) + λ 1 ( x1 − 1) + λ 2 ( x1 + x 2 − 2) .2.

Выпишем необходимые условия экстремума первого порядка:а)∂ L (x , λ 0 , λ )∂ x1= 2λ 0 x1 + λ1 + λ 2 = 0 ,∂ L (x , λ 0 , λ )∂ x2= 2λ 0 x 2 + λ 2 = 0 ;б) x1 − 1 = 0, x1 + x 2 − 2 ≤ 0 ;в) λ 2 ≥ 0 (для минимума), λ 2 ≤ 0 (для максимума);г) λ 2 ( x1 + x 2 − 2) = 0 .3.

Решим систему для двух случаев.Первый случай: λ 0 = 0 , тогда λ1 = 0 и λ 2 = 0 , что противоречит утверждению3.8.Второй случай: λ 0 ≠ 0 . Поделив уравнения приведенной в п. 2 системы на λ 0 иλλзаменив 1 на λ1 и 2 на λ 2 , условие «a» запишем в видеλ0λ0∂ L (x , λ )= 2 x1 + λ1 + λ 2 = 0 ,∂ x1∂ L (x , λ )= 2x 2 + λ 2 = 0 .∂ x2Остальные соотношения сохранят свой вид.Рассмотрим 2 p − m = 2 варианта удовлетворения условия «г» дополняющей нежесткости:1) λ 2 = 0 , тогда x 2 = 0 .

Из ограничения следует, что x1 = 1 , а из условия «a»λ1 = −2 . Имеем условно-стационарную точку A : x1∗ = 1, x 2∗ = 0, λ∗1 = −2, λ∗2 = 0 ,вкоторой удовлетворяются необходимые условия и минимума, и максимума;2) λ 2 ≠ 0 , тогда x1 + x 2 − 2 = 0, 2 x1 + λ 1 + λ 2 = 0, 2 x 2 + λ 2 = 0, x1 − 1 = 0 . По-лучаем условно-стационарную точку B: x1∗ = 1, x 2∗ = 1, λ∗1 = 0, λ∗2 = −2 < 0 , в которойудовлетворяются необходимые условия максимума.254. Проверим выполнение достаточных условий экстремума.Исследуем точку A . Ограничение-неравенство не является активным. Поэтомуl = 1 < n = 2 и достаточные условия первого порядка не выполняются.

Проверим условия второго порядка: d 2 L (A ) = 2dx12 + 2dx 22 . Так как ограничение g 2 ( x ) ≤ 0 в точке Aпассивно, то dg1 ( A ) = dx1 = 0 и d 2 L ( A ) = 2dx 22 > 0 при dx 2 ≠ 0 . Следовательно, в точкеA – условный локальный минимум.x2g1 ( x) = 02f ( x) = 1B21 Ax1g 2 ( x) = 0f ( x) = 2XРис. 4Исследуем точку B. Ограничениеg 2 ( x) ≤ 0является активным, поэтомуl = 2 = n = 2 .

Так как λ ∗2 = −2 < 0 , то в точке B выполняются достаточные условия максимума первого порядка и она является точкой локального максимума. Из методическихсоображений проверим достаточные условия второго порядка: d 2 L (B ) = 2dx12 + 2dx 22 . Вточке B ограничение g 2 ( x) = 0 активно: dg1 (B ) = dx1 = 0 , dg 2 (B ) = dx1 + dx 2 = 0 . Отсюда dx1 = dx 2 = 0 и d 2 L (B ) = 0 . Поэтому требуется дополнительное исследование. Нарис. 4 видно, что в точке B – условный локальный максимум, поскольку при приближении к этой точке вдоль множества X функция возрастает, а при движении от нее – убывает. Это подтверждает сделанный ранее вывод.5.

Значения функции в точках экстремума: f ( A ) = 1, f (B ) = 2 . „26Лекция 34. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМАПринципы построения численных методов. Применение необходимых и достаточных условий безусловного экстремума эффективно для решения ограниченного числапримеров, в которых вытекающие из условий соотношения имеют аналитическое решение. Для решения большинства практических задач они не могут быть рекомендованы последующим причинам:• целевая функция f ( x) может не иметь непрерывных производных до второго порядка включительно;• использование необходимого условия первого порядка связано с решением системы n в общем случае нелинейных алгебраических уравнений, что представляет собой самостоятельную задачу, трудоемкость решения которой сравнима с трудоемкостью численного решения поставленной задачи поиска экстремума;• возможны случаи, когда о целевой функции известно лишь то, что ее значениеможет быть вычислено с нужной точностью, а сама функция задана неявно.Подавляющее большинство численных методов оптимизации относится к классуитерационных, т.е.

порождающих последовательность точек в соответствии с предписанным набором правил, включающим критерий окончания. При заданной начальной точкеx 0 методы генерируют последовательность x 0 , x 1 , x 2 ,... Преобразование точки x k вx k +1 представляет собой итерацию.Для определенности рассмотрим задачу поиска безусловного локального минимума:f ( x ∗ ) = min f ( x) .x∈R nЧисленное решение задачи безусловной оптимизации, как правило, связано с построениемпоследовательности{x }kf ( x k +1 ) < f ( x k ) , k = 0,1,… .точек,обладающихсвойством{ }Общее правило построения последовательности x k имеет видx k +1 = x k + t k d k ,k = 0,1,… ,где точка x 0 – начальная точка поиска; d k – приемлемое направление перехода из точки x k в точку x k +1 , обеспечивающее выполнение условия убывания функции и называемое направлением спуска; t k – величина шага.Начальная точка поиска x 0 задается, исходя из физического содержания решаемойзадачи и наличия априорной информации о положении точек экстремума.Классификация численных методов поиска безусловного экстремума.

В зависимости от наивысшего порядка частных производных функции f ( x) , используемых дляформирования d k и t k , численные методы решения задачи безусловной минимизациипринято делить на три группы:27• методы нулевого порядка, использующие только информацию о значениифункции f ( x) ;• методы первого порядка, использующие информацию о первых производныхфункции f ( x) ;• методы второго порядка, требующие для своей реализации знания вторых производных функции f ( x) .МЕТОДЫ НУЛЕВОГО ПОРЯДКАА. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИПостановка задачи. Тpебуется найти безусловный минимум функции f ( x) однойпеpеменной, т.е.

такую точку x ∗ ∈ R , чтоf ( x*) = min f ( x) .x∈RПоставленная задача одномерной минимизации может быть решена с помощьюнеобходимых и достаточных условий безусловного экстремума. Однако проблема полуdf ( x )чения решения уравнения= 0 может оказаться весьма сложной.

Более того, вdxпрактических задачах функция f (x ) может быть не задана в аналитическом виде иличасто неизвестно, является ли она дифференцируемой. Поэтому получение численногорешения поставленной задачи является важным для приложений.З а м е ч а н и я.1. Для методов одномеpной минимизации типично задание апpиоpной инфоpмациио положении точки минимума с помощью начального интервала неопpеделенностиL0 = [a0 , b0 ] . Пpедполагается, что точка минимума x * пpинадлежит интеpвалу L0 , но ееточное значение неизвестно.2. Большинство известных методов одномеpной минимизации пpименяется длякласса унимодальных функций.Опpеделение.

Функция f ( x) называется унимодальной на интеpвале L0 = [a0 , b0 ] ,если она достигает глобального минимума на [a0 , b0 ] в единственной точке x ∗ , пpичемслева от x ∗ эта функция строго убывает, а справа от x ∗ – стpого возpастает.3. Методы одномеpной минимизации шиpоко пpименяются в методах пеpвого ивтоpого поpядков для нахождения оптимальной величины шага. Пpи этом левая гpаницаначального интеpвала неопpеделенности, как правило, совпадает с началом кооpдинат,т.е. a0 = 0 .Стpатегия поиска включает в себя тpи этапа:1. Выбоp начального интеpвала неопpеделенности.

Гpаницы a0 , b0 интеpваладолжны быть такими, чтобы функция f ( x) была унимодальной.2. Уменьшение интеpвала неопpеделенности.283. Пpовеpку условия окончания. Поиск заканчивается, когда длина текущегоинтеpвала неопpеделенности [a k , bk ] оказывается меньше установленной величины.Ответом является множество точек, пpинадлежащих последнему интеpвалунеопpеделенности, сpеди котоpых каким-либо обpазом выбиpается pешение задачи x ∗ .В некотоpых методах заранее задается или находится количество N вычисленийфункции. В этом случае пpодолжительность поиска огpаничена.А1.

Метод дихотомииСтратегия поискаЗадаются начальный интеpвал неопpеделенности и тpебуемая точность. Алгоpитмопиpается на анализ значений функции в двух точках (см. pис. 1). Для их нахождения текущий интеpвал неопpеделенности делится пополам и в обе стоpоны от сеpедины откладывается поε, где ε – малое положительное число. Условия окончания пpоцесса поис2ка стандаpтные: поиск заканчивается, когда длина текущего интеpвала неопpеделенностиоказывается меньше установленной величины.АлгоpитмШаг 1.

Задать начальный интеpвал неопpеделенности L0 = [a0 , b0 ] , ε > 0 – малоечисло, l > 0 – точность.Шаг 2. Положить k = 0 .a + bk − εa + bk + ε, f (yk ) , zk = k, f (z k ) .Шаг 3. Вычислить y k = k22Шаг 4. Сpавнить f ( y k ) с f (z k ) :а) если f ( y k ) ≤ f (z k ) , положить ak +1 = ak , bk +1 = z k (pис. 1, а) и пеpейти к шагу5;б) если f ( y k ) > f (z k ) , положить ak +1 = y k , bk +1 = bk (pис.

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

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

Список файлов книги

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