XIV Аттетков и др. Методы оптимизации (1081420), страница 14
Текст из файла (страница 14)
Если же 7'(х„) ф О, то в случае Я 1"'(я:„) < 0 можно отбросить отрезок [х, х2) и продолжать описанным выше способом поиск точки минимума на отрезке (хс, х,], и наоборот. После каждого приближения правильность вычислений подтверждается уменьшением минимального значения многочлена по сравнению с его минимальным значением на предыдущем шаге. Вычисления можно прекратить, когда длина интервала неопределенности, в котором гарантированно находится искомая точка х„, станет меньше заданной наибольшей допустимой величины е,.
Пример 2.7. Рассмотрим ту же функцию 7'(х) = хз + 16/х, что и в примерах 2.4 и 2.6, и найдем точку ее минимума х„на отрезке (хм х2) = (1; 4). Вычисляем (с = 12, )з = 20 и по формуле с"'(х) = 2х — 16ссхз получаем Д = — 14, Д = 7.
Используя (2.31), находим х = — 10, ш = Я98 - 14,0712, сс — 0,3677 и х, = хс + р,(хз — хс) — 2,1031. Так как 1"'(х,) — 0,5888 ) О, то поиск точки х, продолжаем на отрезке (х~, хя ), где хс — — хс = 1 и х2 — — х, = 2,1031, причем с0 с0 О) О) У(хз ) — 12,0308, После аналогичных вычислений имеем х0~ = 0,1303, сл® = — 2,9333, 1с0~ = 0,8342, х~ ~ = х~ ~ + р0~(х(1).
— х~ ~) = 1,9202, Тс(хс ~) — 0,4990 < 0 и Т" (хс )) — 12,0196. Теперь искомая точка 60 (1) х„находится в интервале (х,х ), где х =х„-1,9202 и х2 = х„= 2,1031. В итоге аналогичной серии вычислений получаем хссО - — 0,0939, сл~2~ = 0,5501, 1с~з~ = 0,.4365, х~ ) = 2,0000. Итак, пришли к значению х, у которого четыре верных -(2) знака после запятой совпадают с точным значением х, = 2 (см. пример 2.4). Вопросы и зада зи Вопросы и задачи 2.1. Имеет ли функция ?(х) = хе ' экстремум в интервале (О, 3)'? Если имеет, .то в какой точке? Имеет ли она минимум в том же интервале, минимум на отрезке [О, 3], и если да, то в какой точке? 2.2. Проверьте, являются ли унимодальными следующие функции: а) ?'[х) = х" — 2х — 1 на отрезках [О, 2], [1,5, 2]: б) ?'[х) = ]]х — 1] — 1[ па отрезках [ — 3, 3], [ — 3, 1], [1, 3], [О, 2].
2.3. Имеются утверждения относительно функции ?'(х), определенной на отрезке [а,!4]: а) ?'[х) возрастает; б) у(х) не убывает; в) ?[х) имеет локальный минимум на интервале (а,б) в некоторой точке х„; г) Лх Е (а, Ь): ~'(х) = 0; д) Лх е (а, Ь): ?о(х) не существует; е) ?'(х) > 0 на отрезке [а, Ь]; ж) Ле > 0: ['(х) < 0 при х1 — е < х < х1 и ?"(х) > 0 при Х4 <Х <Х4+Е; з) Лх е (а, Ь); ? п(х) = 0:, и) ~п(х) =О, х б (а, Ь), Какие из указанных утверждений вытекают из перечисленных? 2.4. Имеет ли функция х а1п —, х~О; 4 У(х) = О, х=О., минимум в точке х = О, выполняется ли в этой точке необходи- мое, достаточное условия экстремума? 2.5.
Для каких унимодальных функций метод золотого сечения приводит к цели за меньшее количество итераций, чем метод Ньютона? 94 2. МЕТОДЪ| ОДНОМЕРНОЙ МИНИМИЗАЦИИ 2.6. Какой из методов: золотого сечения, Ньютона, кубической интерполяции — окажется более эффективным, если производные вычисляются приближенно через разность значений функции в близких точках? 2.7. Минимизируйте функции )~ ) ~ 1)4 ~ ) ~ 1)2 на отрезке [ — 2, 3] с помощью метода золотого сечения. 2.8. Минимизируйте функцию 1(х) =хагс18х — — 1п(1+х ) 1 2 на отрезке ~ — 6, 6] методом Ньютона. Выбирая различные начальные приближения, найдите какое-либо значение хщ при котором метод начнет расходиться. 2.9. Минимизируйте функцию Т"(х) = (х — 1)4 на отрезке ~0,5, 2] и функцик> д(х) = хв1п(1/х) на отрезке ~0,2, 1] методами дихотомии и золотого сечения, а также с помощью оптимального последовательного поиска, градиентного метода и метода Ньютона.
Сравните эти методы. 3. МИНИМИЗАЦИЯ НЫН~~ЛЫ~ ~~» НАЦИЙ Широкий класс задач математического программирования связан с минимизацией выпуклых функиий многих переменных, определенных на выпуклом множестве. Такие задачи относят к задачам выпуклого программирования. В этой главе рассмотрены основные свойства выпуклых множеств и функций и описаны некоторые методы минимизации выпуклой целевой функции в случае, когда на область изменения параметров оптимизации не наложено ограничений.
3.1. Выпуклые множества Пусть с. †. — конечномерное линейное пространство и х1, х~ — произвольные элементы в я.. Множество Е с а. вида Е = 1х Е Е: х = Лх'+ (1 — Л)хг, Л б [О, Ц с Ц будем называть отпрезком с концами х' и хг и обозначать ~х', х"1. Определение 3.1. Подмножество й линейного пространства я".
называют выпуклым множестпвом, если оно вместе с любыми двумя точками х1, х~ Е й содержит и отрезок ~х~, х~), т.е. для любых х1, х~ Е й и Л Е ~0, Ц выполняется соотношение Лх1+ (1 — Л)хз е й. Пустое множество считаем выпуклым по определению. Пример 3.1. а.
Линейное подпространство 'Н в линейном пространстве,б является выпуклым множеством. В самом деле, для любых элементов х, х Е 'Н линейному подпространству Н, согласно определению, принадлежит и любы линейная комби- 96 3. МИНИЪЗИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ нация о1х +озх этих элементов. В частности, это верно и 1 2 при о1 = Л, а2 = 1 — Л, где Л б [О, Ц.
б. Отрезок Е = [х', х2) в линейном пространстве ь". является выпуклым множеством. '1тобы показать это, выберем две точки у, у2 Е Е. Тогда, согласно определеник1 отрезка, существуют такие значения 11, 12 Е [О, Ц, что у = 11х + (1 — 21)х ~ у =12х + (1 — 12)х Пусть Л Е [О, Ц выбрано произвольно. Тогда Лу + (1 — Л)у = Л(й1х~ + (1 — 11)х~) + + (1 — Л)(12х + (1 — 12)х ) = (Л11+ (1 — Л)Ь2)х1+ + (Л(1 — Х1) + (1 — Л) (1 — Х2) ) х . Положив 131 = Л11+ (1 — Л)12 и )32 = Л(1 — ~1) + (1 — Л)(1 — й2), нетрудно показать, что 131 ) О, .Д2 > 0 и Д1 + 132 = 1. Таким образом, О <,31 ( 1, )32 = 1 — )31 и Лу1 + (1 — Л) у 2 = ~31 х ~ + (1 —,31 ) х 2 Е Е.
Отметим, что одноточечное множество, как частный случай отрезка, является выпуклым множеством. в. Рассмотрим систему линейных алгебраических уравнений (СЛАУ) Ах = Ь, где А матрица размера п2 х и, х матрица-столбец высоты в, составленная из неизвестных системы, а Ь -- матрица-столбец высоты т, составленная из правых частей уравнений. Множество решений рассматриваемой системы есть подмножество линейного арифметического пространства К". Это подмножество является выпуклым. В самом деле, если х' и х2 решения рассматриваемой системы, а Л Е [О, Ц, то в силу свойств решений СЛАУ (или свойств матричных операций) А(Лх' + (1 — Л) х2) = ЛАх' + (1 — Л) Ахз = ЛЬ+ (1 — Л) Ь = Ь, т.е.
столбец Лх'+ (1 — Л)х2 является решением СЛАУ Ах = Ь. Рассмотренному примеру можно придать более широкое толкование. Допустим, что А .- линейный оператор, действу- ЗЛ. Выпуклые множества 97 ющий в линейном пространстве ь". Тогда прообраз А 1(у) = = (х Е,б: Ах = у) произвольного элемента у Е ь" есть выпуклое множество в ь. Доказательство этого аналогично тому, которое было проведено для множества решений С,ЛАУ. Подмножество Е в линейном пространстве,С назовем аффинным мноеообразием, если оно вместе с любыми своими элементами х' и х~ содержит и любую их линейную комби~ац ю вида Лх'+ (1 — Л)х~, де Л Е 2 — юбое ~~с~о.
Яс~о, что аффинное многообразие частный случай выпуклого множества. Нетрудно показать, что множество решений СЛАУ, а также прообраз А '(у) элемента у для линейного оператора А являются аффинными многообразиями. Другой способ получения аффинного многообразия образовать множество хо+ Н = (у е к,: у = х~+ уп, у е Н), где х —.- произвольный элемент в,С, а 'Н С ь" произвольное линейное подпространство. Это множество является аффинным многообразием. Действительно, если х ., х Е хе + 'Н, то х' = х" + р', где у' Е 'Н, 1= 1, 2. Поэтому для любого числа Л Лх'+ (1 — Л)х~ = Л(х" +у')+(1 — Л)(х~+у ) = = х~+ (Лу~ + (1 — Л)у ) Е х~ +'Н.
Отметим без доказательства, что лкабое аффинное многообразие может быть представлено в виде х" +'Н. Поэтому в йп понятие аффинного многообразия равнозначно т-мерной плосношпи. Пример 3.2. Пусть к. нормированное пространство. Тогда любое множество Е вида Е = 1х Е ь": ~~х — хе~~ < т1, где ~~х(~ норма элемента х в б, является выпуклым. Докажем это. Для любых элементов х1, х~ Е Е и любого числа Л Е (О, 1] имеем // (Л '+ (1 — Л) ') — '/! = /! Л( ' — ') + (1 — Л) (.
' - ') /! < < Л~!х — х ~~+ (1 — Л)~!х — х ~~ < Лг+(1 — Л)а = г. т.е. Лх +(1 — Л)хэ Е Е. з. минОмизлиия вып,. кдых егнкций Пример 3.3. Пусть ь" — - евклидово пространство., в котором скалярное произведение элементов х и у будем обозначать 1х, у). Для любого вектора, а Е ь" и любого числа с Е К множество Е = (х Е ь": (х, а) = с1 является аффинным многообразием и, в частности, выпуклым множеством. Чтобы показать это, выберем произвольные элементы х1, х~ Е Е и число Л Е К. Тогда (х', а) = (х~, а) = с. Следовательно, с учетом свойств скалярного произведения 1Лх~+ (1 — Л)х~, а) = = Л (х~, а) + (1 — Л) (х~,.
а) = Лс+(1 — Л)с = с., Л 1+(1 — Л) заЕ, Множество Е указанного вида в дальнейшем будем называть еиперплосностъю. Отметим, что термин „гиперплоскость' в Бз означает плоскость, а в К .. прямую. Нетрудно показать, что множество Е = 1х Е,б: (х, а) < с1 выпуклое, но аффинным многообразием не является. Это утверждение остается в силе, если в определении множества Е знак „<" заменить знаком „>': по существу, это равносильно замене вектора а вектором — а. Утверждение также будет справедливым, если знак неравенства заменить строгим неравенством.
Множество .Е в дальнейшем будем называть полу- пространством. Пусть х', ..., хл — произвольные элементы в линейном пространстве ь. Их линейную комбинацию Л1х1+... + Льхь назовем выпунлой комбинацией, если все коэффициенты Ль г = 1, Й, неотрицательны, а их сумма равна единице, т.е. ь Л, = 1. Отметим, что линейная комбинация Лх1+ (1 — Л)х~, в=1 участвующая в определении отрезка, при Л е [О, 1] является выпуклой.
Теорема 3.1. Для того чтобы множество Е С ь" было выпуклым, необходимо и достаточно, чтобы любая выпуклая комбинация элементов Е принадлежала этому множеству. 99 3.1. Выпуклые множества ~ Достаточность утверждения теоремы очевидна, и мы остановимся на доказательстве его необходимости, следуя методу математической индукции по количеству слагаемых в выпуклой комбинации. Пусть множество Е С к". выпукло.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
