Главная » Просмотр файлов » XIV Аттетков и др. Методы оптимизации

XIV Аттетков и др. Методы оптимизации (1081420), страница 22

Файл №1081420 XIV Аттетков и др. Методы оптимизации (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска) 22 страницаXIV Аттетков и др. Методы оптимизации (1081420) страница 222018-01-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Такова, например, функция Дх) = е одного действительного переменного. Вторая производная этой функции положительна: 1 "(х) = е 1 Поэтому она является строго выпуклой. В то жс время функция )'(х) возрастающая и не имеет точек локального минимума, т.е.

она не достигает наименьшего значения. 3.6. Примеры минимизации квадратичных функций Использование необходимого и достаточного условий локального минимума выпуклой функции рассмотрим на примсрах минимизации квадратичных функций.,Любая квадратичная функция Дх) может быть представлена в виде суммы 1(х) = Ях, х) + (с., х) квадратичной (Ях, х) и линейной (с, х) форм, при этом матрица Гессе Н(х) этой функции постоянна и связана с матрицей С,) квадратичной формы соотношением Н=2Я. З.б. Приьсвры минимизации каадрахичн сх функций 143 Рассмотрим квадратичную функцию ~(х) = — (Нх, х) + (с, х) 1 (3.37) с положительно определенной матрицей Гессе Н порядка н и фиксированным вектором с Е ас". Градиент этой функции равен 8тас1~(х) = Нх+ с.

(3.38) )'(х*) = — — (НН 'с, Н 'с)+ (с., Н 'с) = — (с, Н 'с). (3.39) * 1 1 2 2 Отметим, что если матрица Н квадратичной функции не является положительно определенной, то она может быть вырожденной. В этом случае либо функция не имеет стационарных точек, либо стационарных точек бесконечно много. Пример 3.15.

Исследуем на минимум функцию ~(хм хе) = , 2 . 2 = х, + 2хс хе + 4хх Рассматриваемая функция представляет собой квадратичную функцию с матрицей Гессе Так как матрица Н положительно определена, то она имеет обратную матрицу Н '. Иэ необходимого условия 8гас1~(х') = = О локального минимума функции с учетом (3.38) находим, что функция имеет единственнукь стационарную точку х' = = — Н сс. Рассматриваемая функция сильно выпуклая на вьилуклом множестве Б'." (см. пример 3.13). Значит, эта функция строго вьтуклаа (см. 3.5).

Поэтому, согласно теоремам 3.14 и 3.15, необходимое условие локального минимума является и достаточным условием. В стационарной точке х* функция (3.37) принимает значение 144 з. минимизлция выпуклых г ункций Нетрудно проверить (например, с помощью критерия Сильвестра), что матрица Н положительно определенная. Значит, функция имеет единственную стационарную точку х* = = — Н ~ с = — Н ~0 = О, в которой принимает наименыпее значение. ПРимеР 3.16. КваДРатичнаЯ фУнкцил ((хмхз) = хз~+ 2х~ хз также представляет собой квадратичную форму и имеет матрицу Гессе УХ = 2 ( Эта матрица знаконеопределенная, но является невырожденной. Поэтому функция имеет единственную стационарную точку х* = — Н '0 = О.

Но поскольку функция не выпуклая (матрица не является неотрицательно определенной), делать какие-либо заключения о наличии экстремума в точке х' нельзя. И действительно, точка 0 не является ни точкой локального минимума, ни точкой локального максимума, так как ее матрица Гессе в этой точке знаконеопределенная (Ч). Нетрудно убедиться, приведя квадратичную форму к каноническому виду, что график рассматриваемой функции представляет собой гиперболический параболоид с седловой точкой (О, 0).

Функция ~р(1) = ~(8,0) = Р (сечение функции ~(х~.,хз) при хз = 0) имеет при ~ = 0 строгий локальный минимум, в то время как функция ф(8) = ((г,— 1) = — 1 (сечение функции ~(хм хз) при х~ = — хя) при 1 = 0 имеет строгий локальный максимум. Пример 3.17. Квадратичную функцию ('(хмхз) = х~~ + +2х~хз+х~~ можно записать в виде ((хмхэ) = (х~+хз) . От- 2 сюда сразу следует, что она достигает наименьшего значения, равного нулю, в каждой точке прямой х~ + хя = О. Матрица Гессе этой функции имеет вид Я=2( 3.6.

Привары иииимиааиии каадратичн ~х функций 145 и является неотрицательно определенной. Значит, функция вы- пуклая, а каждая стационарная точка является точкой наи- меньшего значения функции. Необходимое условие локального минимума приводит к системс уравнений 2х~+2хз =О, 2х1+ 2хз = О, из которой заключаем, что стационарной является любая точка вида (1, — 1), 1Е и, т.е. точка, лежащая на прямой х~ +хе = О. ПРиведЯ квадРатичнУю фоРмУ Дх~,.хз) = (х~ + хг)з к каноническому виду, легко убедиться, что график функции представляет собой параболический цилиндр [ПЦ. Пример 3.18.

Квадратичная функция ~(х1;х2) — бх~ 4х~ха + 3хз + 4ч 5(х~ + 2хз) + 22 (3.40) (3.41) ~(х) = (Ах, х) + (Ь, х) + с, где х=(хм х2) ЕК, А=, Ь=, с=22. Матрица А положительно определенная, так как имеет угловые миноры Ь~ = 6 ) 0 и Ьз = 6 3 — ( — 2) = 14 ) О. Значит, рассматриваемая функция сильно выпуклая в 2 и имеет единственную стационарную точку х*, являющуюся точкой наименьшего далее используется в качестве базовой при сравнительном анализе различных численных методов безусловной минимизации и выявлении достоинств и недостатков их вычислительных свойств.

Поэтому представляет интерес подробное аналитическое исследование свойств этой функции. Функцию ~(хм хе) можно представить в виде 3. МИНИМИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ 146 значения. Эту точку можно найти по формуле х* = — Н 'Ь, где Н = 2А — матрица Гессе функции. Так как 14 2 6 то 28 2 6 8тГ5 — 2тГ5 В этой точке функция принимает значение ('(ж*) = — 28. Приведем квадратичную форму (Аж, а) функции к каноническому виду. Для этого найдем собственные значения матрицы А, составив ес характеристическое уравнение с1е1(А — Л7) = = О, где 1 - единичная матрица второго порядка. В данном случае это уравнение имеет вид 6 — Л вЂ” 2 — 2 3 — Л Раскрывая определитель в левой части уравнения, получаем (6 — Л)(3 — Л) — 4 = О, или Лт — 9Л + 14 = О. Это квадратное уравнение имеет корни Л1 = 2 и Лз = 7, которые и являются собственными значениями матрицы А.

Поскольку собственные значения различны, а матрица А симметрическая, то соответствующие этим собственным значениям собственные векторы ортогональны [Ъ ). Координаты собственных векторов найдем, решая СЛАУ (А — Л1)е = О, которая при Л = Л1 = 2 и Л = Лз = 7 сводится к соответствующим системам 4:с1 — 2хз = О, — 2т1+из =О, < — и1 — 2из = О, — 2т1 — 4из = О. т Решением первой системы является вектор (1 2), а второй т вектор ( — 2 1) . Нормируя эти векторы, получаем единичные т т векторы е', = (1~ъ'5 2/ъ 5) и е~ = ( — 2/ь'5 1/Л), образующие в Кз ортонормированный базис. В этом базисе матрицей 3.6.

Примеры минимизации каадратичн ~х Функций 147 квадратичной формы является диагональная матрица Л с диагональными элементами, совпадазощими с собственными значениями, а квадратичная форма (Аж, т) примет канонический вид (Лр, у) = Л1у2+ Л2у2~ = 291~ + 7у2~, у = (у1., у2). Координаты собственных векторов е1 и е2, записанные по столбцам, формируют матрицу перехода Г к новому, каноническому базису, которая в данном случае имеет вид 1 2 Я Д 1 (1 — 2 Я~2 1 чгз Д Поскольку матрица Г определяет переход от одного ортонормированного базиса к другому, она является ортогональной ~1Ч]. Поэтому обратнук1 матрицу У ' можно найти с помощью т транспонирования: Г = Г .

С помощью матрицы перехода можно найти координаты вектора Ь в новом базисе по формуле Ь' = Г 1Ь, что в рассматриваемом случае дает Таким образом, квадратичная функция в новой системе координат принимает вид 71(У1,у2) = 2у, + 7р2+20у1 + 22. С помощью выделения полных квадратов проводим дальнейшее упрощение вида функции: 71(д1,р2) = 21у1+5) +7р2 — 28, или Яз1,з2) = 2з12+ 7з22 — 28, где з~ = р1+ 5 и з2 = у2. Из найденного представления функции вытекает, что график рассматриваемой функции представляет собой эллиптический параболоид ~П1). 148 з. минОмиздиия выпукдых оъ'нкций Преобразование функции проведено за два шага: сначала переход к переменным у1, у2, а затем — к переменным 21, Формулы связи исходных переменных х1, х2 с конечными переменными 21 и 22 имеют вид 21 — 222 Х1 = — Л., Л 221 + 22 х2 = — 2Л.

1/5 Началом конечной системы координат является точка 01, которая в исходной системе координат имеет координаты х1 = — 1/5, х2 = — 2ъ'5. Все три системы координат покаРис. З.З заны на рис. 3.3. Линиями уровня функции /(х1, х2) являются подобные эллипсы (см. рис. 3.3). Найдем, нэпример, уравнение линии уровня, проходящей через точку хв = ( — 2, 1). Подстановка координат этой точки в (3.40) дает значение функции /(хв) = 57.

Следовательно, эта точка расположена на линии уровня /(хбх2) = 57. Переходя к конечной системе координат 012122, получаем уравнение /(21, я2) = 22~~ + 7222 — 28 = 57, или 2 2 1 2 85/2 85/7 Таким образом, искомая линия уровня эллипс с полуосями а = ~,~85/2 - 6,52 и 6 = /85/7 - 3,48. Найденная линия уровня показана на рис. 3.3 жирной линией. 3.7. Минимизация позиномов В прикладных задачах минимизации целевая функция часто имеет вид ев (3.42) у1х) = )' с~рг (х) ~ г=-1 149 3.7.

Минимизация цозииоиов с, > О, 1 = 1, т, а функции р~х) =П:" з=-1 13.43) а,у Е Б', 1= 1, т, у =1, и, определены на множестве К" =((хм ...х„)ЕК":х,>О, 1=1,п) точек с положительными координатами. Функцию вида 13.42) называют позиномом. Почином при определенных значениях показателей степени а,. может не быть вьиуняой функцией.

Однако с помощью замены переменных х:=е~", у=1,п, 13.44) он преобразуется в выпуклую функцию в Кп. Это показано в примере 3.9. Там же показано, что эта функция является строго выпуклой функцией в том случае, когда матрица А = (и,:) имеет ранг, равный и.

Поскольку функция уф,...,С„) выпукла в 1~", ли>бая точка ее локального минимума является точкой наименьшего значения функции 1см. теорему 3.14). Более того, так как эта функция дифференцируема в яС", множество ее точек наименьшего значения совпадает с множеством стационарных точек 1см.

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

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

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

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