Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 2
Текст из файла (страница 2)
Глава 6 состоит из пяти параграфов, посвященных принципу Лагранжа для необходимых условий экстремума, возмущениям экстремальных задач, существованию решений, алгоритмам оптимизации. Отдельный пятый параграф посвящен решению конкретных задач. Э. М. Галеев, В. М. Тихиииров Глава 1 Экстремальиь1е задачи 5 1. Конечномерные задачи без ограничений В этом параграфе даются необходимые и достаточные условия экстремума функций одной и нескольких переменных. 1.1. Постановка задача Пусть |: К" — К вЂ” функция и действительных переменных, обладающая некоторой гладкостью. Под гладкостью мы понимаем определенную дифференцируемость функции. Если функция Г дифференцируема Ь раз в точке а, мы пишем у б Р"(х).
Гладкой конечномерной экстремальной задачей оез ограничений называется следующая задача: у (х) — ехгг. При решении задачи надо найти отыскать не только абсолютные (глобальные) экстремумы (минимумы и максимумы) функции, но и локальныее экстре м ум ы. Точка х является точкой локального минимума (максимума) функции у, если существует окрестность П, = (х ! !х — х! < е) точки й такая, что у(х) > гь(х) (Г(х) < г (й)) для любой точки х из этой окрестности При этом мы пишем а б !осш!и Г (х б 1осгпаху), а если речь идет о минимуме или максимуме, то пишем х б 1осех1гу.
1.2. Необходимые н досгаточныс условия экстремума 1.2.1. Функции одной переменной Теорема 1 (Ферма). Пусть Г: К вЂ” К вЂ” функции одного действительного переменного. Если х б 1осехгг г — точка локального экстремума функции г и г' б Р(а) дифференцируема в точке х, то у'(х) = О. 11, Конечиомериые задачи без ограничений Доказательство. По определению дифференцируемости У(х + й) = у(х) + Г (х)й + г(Л), т(Л) = о(й) = о(1)й при малых Ь. Значит, ~(й + л) — г» = (г" (а) + (1) ) ь.
Если бы у'(х) ~ О, го при Л достаточно близких к нулю, величина Г'(х)+о(1) имела бы знаку'(х), поскольку о(1) О при Л вЂ” О. Саможе й может принимать как положительные, так и отрицательные значения. Следовательно, разность Г(х + Л) — у(х) может быть как меньше, так и больше нуля. Это противоречит тому, что у(х + Л) — у(х) > О при х б 1оспнп у' и з (х + Ь) — у(х) < О при х б 1осшах у. Геометрически теорема Ферма утверждает, что в точке экстремума дифференцируемой функции касательная к ее графику горизонтальна.
Теорема 2. Пусть функция у б Р (х) дважды дифференцируема в точке й, Необходимые условия экстремума: если х б !оспин л — точка локального минимума функции /, то Г'(х) =- О, уь(х) > О. Достаточные условия экстремума: если Г'(й) = О, Ул(х» О, то а б !осгп!и у — точка локального минимума функции г. Доказательство. По формуле Тейлора у(й + ь) = Г(й) + 1'(с)л + -ун(й)л' + г(й), г(ь) = о(ь'). 2 Необходимость. Пусть х б 1осгп!и Г. Тогда, во-первых, по необходимому условию экстремума! порядка для функций одной переменной— теореме Ферма — у'(х) = О, во-вторых, У(х+ Л) — Г(х) > О при достаточно малых Ь.
Поэтому в силу формулы Тейлора у(х+ й) — у(х) = -ун(х)ь~+г(Л) > О (г(ь) = о(ь~)) 2 при малых Ь. Разделим обе части последнего неравенства на Л и устрез г(Ь) мим й к нулю. Поскольку — — О, то получим, что ун(х) > О.. Лз Достаточность. Пусть у'(х) = О, у "(х) > О.
Тогда по формуле Тейлора в силу условия т(Л) = о(ь~) еь !1(Л)! < еь~ ~ т(Л) > -ей~ для любого е > О при достаточно малых Л имеем: Г(а + Л) Г(й) = Гн(а)ь + (Ь) > ( — — )й > О 1 - 2 г (У) 2 при е < . Следовательно, х б 1осгпш Г '(х) 2 !О Глава 1. Экстремальнме задачи р'(й,) =о с=с =О. д1(й) дх, / д'1(й) ! г ! 1б=! (АЬ, Ь) > о)!Ь!!~ 'ч' Л 6 К". Для локального максимума неравенства имеют противоположный вил; 1л(й) < 0 и 1н(й) < 0 соответственно. В олномерном случае можно дать почти исчерпыяающий ответ на вопрос о том, является ли данная точка х локальным экстремумом или нет.
Теорема 3. Пусть функция 1 Е Р'(х) и раэ дифференцируема в точке х. Необходимые условия экстремума: если х Е !осппп (гпах) 1 — точка локального минимума (максилгума) функции 1, то лабо 1 (й) = ... 1!н1(х) = О, либо 1'(й) = " = 1" 0(й) = О, 10-'(й) > О (1<' !(К) < О) (1) при нгкотораи т: 2 < 2гп < и. Достаточные условия экстремума: если выполняетсл условие (1), то л Е !оспйп (гпах) 1 — точка локального минимума (максимума) функции 1. Доказательство. Пусть для определенности х Е 1осппп1.
По формуле Тейлора 1(й+") = Л~~, " + "(Л) г(Ь) = о(Ь") ( „-~ 0 при Ь - О), 1 (х) ь „ г(Л) Необходимость при и = ! следует из теоремы Ферма. Пусть далее и > 1. Тогда либо 1'(й) = ... = 1!"1(х) = О, либо 1'(х) = ... 10 0(й) = О, 1!0(х) ф О, ! < и. Значит, 1!'1(й), Поскольку й Е 1осппп 1, то 1(й + Л) — 1(й) = — Ы + т,(Л) > О при достаточно малых по модулю Ь. Так как 1!0(й) уг О, то отсюда следует, что ! — четно и 101(й) > О.
Достаточность. Пусть 1'(х) = ... = 10т '1(й) = О, 1 (й) ф О. Тогда по формуле Тейлора 1(х+Ь) — 1(й)= Ь +г,(Ь), — — ~0 при Ь- 0 1" '( ) (Ь) (2гп)! ' Льп Поскольку 10 1(х) ) О, то 1(х+ Л) — 1(х) > О при лостаточно малых Л, т. е. х Е !оспин 1. б 1.
Конечвомерные задачи без ограничений 1.2.2. Функции нескольких переменных Сформулируем необходимое условие экстремума ! порядка в конечномерной задаче без ограничений, являюшееся аналогом теоремы Ферма. 'Г орема 1. Если х = (хы...,йн) Е 1осехгг1 — точка локального экстремума функции и переченных 1(х~ х„) и функция 1 б Р(х) диффергнцируема в точке х, то 1'(х) = 0 ч=ь 01(х) д1(й) дх, дх„ Доказательство. Рассмотрим функцию одной переменной у(хг) = 1(йн...,й, нх;,х; н...,й„). Поскольку х = (й„...,х„) е !осехгг1, то х, Е 1осехггу. Кроме того !р Е Р(х;).
По необходимому условию экстремума для функций одной переменной — теореме Ферма Сформулируем необходимые и достаточные условие экстремума П порядка в конечномерной задаче без ограничений. Предварительно напомним, что второй производной функции нескольких переменных является симметричная матрица вторых производных а также приведем определения знакоопределенностей симметричных матриц. Матрица А называется неотрицательно определенной (А > О), если (АЬ,Ь) ) 0 ч Л Е К" синь ~~~ абЬ;Л! » )0 тг Л = (Л,,...,Ь„) 6 К". Матрица А называется паеолгитгльно определенной (А > 0), если (АЛ,Л) >О АЛЕК", ЛфО.
Матрица А называется строго пслолсителъно определенной, если сушествует а > 0 такое, что Аналогично опрелеляются неположительная и отрицательная матрицы. Отметим, что в конечномерном пространстве условие положительной определенности симметричной матрицы А эквивалентно условию строгой положительности матрицы А. В бссконечномерных пространствах зто не так (см. 1АТФ, с. 242!). !2 Глава 1. Экстремальные задачи Теорема 2. Пусть функция / Е 23~(х) дважды дифференцируема в точке х = (йц...,х„). Необходимые условия экстремума: если й Е 1осппп(|пах) / — точка локального минимума (максиму.на) функции /, то /'(У) = О, (/н(х)Ь,Ь) > О ((/л(х)Ь,Ь) < 0) Ч Ь Е К".
Достаточные условия экстремума: если /'р) = О, (/ь(Х)Ь,Ь) > О ((/н(Х)Ь,Ь) > О) у Ь б К", Ь 1Ь О, то х Е !оспин (|пах) / — точка локального минимума (максимума) функции /. Докаэатольстао. По формуле Тейлора У(х+ Ь) = У(х) + (У'(х) Ь) + -(/ь(Х)Ь Ь) +г(Ь) т(Ь) о(!Ь!з) Докажем теорему для случая минимума. Случай максимума аналогичен. Необходимость.
Поскольку х Е !оспин/, то, во-первых, по необходимому условию экстремума 1 порядка в конечномерной задаче без ограничений — аналогу теоремы Ферма /'(х) = О, во-вторых, /(х + ЛЬ) — У(х) > 0 при достаточно малых Л. Поэтому в силу формулы Тейлора Л /(х+ ЛЬ) — /(х) = — (/лЯЬ,Ь) + г(ЛЬ) > 0 (г(ЛЬ) = о(/Л!') ) при малых Л и фиксированном Ь. Разделим обе части последнего неравенства на Л и устремим Л к нулю. Поскольку г(ЛЬ)/Л вЂ” О, то 2 получим, что (г (х)Ь,У|) > 0 1|' Ь б К . Достаточность.
Так как / (х) = О, то по формуле Тейлора в силу выполненного условия (/н(х)Ь,Ь) > о!Ь! имеем: У(*+ Ь) — У(й) = -(/н(й)Ь,Ь) +.(Ь) > -!Ь!'+,(Ь) > О 2 2 при достаточно малых И, так как г(Ь) = о(!Ь!~). Следовательно, х б 1оспцп/. ь Замечааие. ДлЯ квадРатичных фУнкционалов Зг(х) = 2 а,зх,хз | |=| условие положительной (отрицательной) определенности матрицы А = г (х) = (азз), ., являетсн достаточным условием абсолютного минимума (максимума) функционала.
13 5 1. Конечиомериые задачи без о|3заничеинй 1.2.3. Критерий Сильвестра Знакоопределенность матрицы устанавливается с помошью критерия Сильвестра. Напомним, что последовательными главными минорами матрицы А / а|| " а|ь '~ называются определители А, ь =де! ~ аь, ... аы Главным минором Ач ц матрицы А называется определитель матрицы размера Ь х Ь, составленной из строк и столбцов с номерами / асц азгц ~ з|,, ..,зы Ац ь: = дез а|ни ... ач Ь Теорема. (9, с. 260). Пусть А — симметричная матрица. Тогда 1.
Матрица А положительно олределена (А > 0) тогда и только тогда, когда все ее носледовательные главные миноры аолохзительны, т. е. А|,ь >О, Ь=!,...,п. 2. Матрица А отрицалзельно определена (А < 0) тогда и только тогда, когда все ее последовательные главные миноры чередуют знак, начиная с отрицательного, т.
е. ( — 1)лбе|А| ь > О, Ь = 1,..., п. 3. Матрица А неотрицательно определена (А > О) тогда и только тогда, когда все ее главные миноры неотрицательны, |л.е. А„ь > О, 1<з| «... зь<п,й=!,...,п, 4. Матрица А ненололсительно определена (А < 0) тогда и только тогда, когда все ее главные миноры чередуют знак, начиная с неноложительного, т. е.
( — 1) А„;„> О, 1 < з, « ... зз < и, 1з = 1,..., зз. Замечание 1. Как будет показано ниже, положительность (неотрицательность) л|атрицы равносильна положительности (неотрицательности) всех собственных значений матрицы. Замечание 2. Отметим, что условие положительности последовательных главных миноров матрицы равносильно условию положительности всех главных миноров (см. [9, с. 260)).
Для условия неотрицательности это не так, т. е. из условия неотрицательности послеловательвых главных миноров не следует неотрицательность всех главных миноров ма~рицы и, следовательно, не следует неотрицательность матрицы. /о о'з Действительно, у матрицы А = ~ ! ) последовательные главные миноры равны нулю (А, = Ап — — 0), но она не является неотрицательной: (АЬ Ь) = ((О -Ьз) (Ь~ Ьз)) = -Ьзз < О пРи Ьз ~ О. 15 14 Глава 1. Экстремальяые задачи б 1. Кояечиомериые задачи без ограиичеиий 1.2.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
