шпоры методы оптимизации. Задача матго программирования (змп) заключ в нахождении min фии f ( X ), если. (1) Под реш змп понимают
 Скачать 1.38 Mb.
|
|
2) Мн-во решений задачи (1), (2) явл-ся выпуклым; 3) если ф-ия строго выпукла, то она может достичь своего min не более чем в одной точке. Док-во: 1) Пусть есть точка глобальн min ф-ии , т.е. окрестность этой точки , так что Пусть точка Соединим эти точки отрезком Т.к. мн-во Х явл-ся выпуклым , то при всех : при , след-но найдется такое значение что Поэтому что противоречит тому, что т. явл-ся точкой локальн min. 2) Мн-во - мн-во решений задачи Пусть мн-во состоит более чем из одной точки. Возьмем Рассм. Т.к.ф-ия -выпукла, то выполняется нер-во 3)Предположим сущ-ет точка Соединим точки и отрезком: мы нашли точку в которой что противоречит тому, что явл-ся точкой локального min. Т 2 (о ст-ной точке в-ой ф-ции): Каждая стационарная точка выпуклой ф-ции , определенная на выпуклом множестве Х, явл. ее точкой минимума. Док-во: Пусть стационарная точка ф-ции , т.е. Рассмотрим произвольную точку Для точек в силу выпуклости ф-ции выполняется:(3)Т.к. ф-ция дифференцируема, то приращение (из (3))=> .по св-ву неотр остатка точка минимума.. 23. Необходимые усл. минимума дифференцируемой ф-ции на выпуклом мн-ве, выраженные через скалярное произведение. Критерий минимума выпуклой дифференцируемой функции на выпуклом множестве, сформулированный через скалярное произведение. Замеч1.Если ф-ция дифференцируема, но не обязательно выпукла, то усл. может не выполняться в точке минимума ф-ции , т. к. возможна ситуация, когда точка принадлежит границе мн-ва X. Теор1. Пусть ф-ция непрерывно дифференцируема на выпуклом мн-ве X. Если точка явл. ее точкой минимума, то для всех выполняется нерав-во (1) Док – во. Пусть - точка минимума ф-ции . Тогда сущ., такое что для всех . Выберем произвольную точку и рассмотрим отрезок Т. к. мн-во X выпукло, то этот отрезок принадлежит мн-ву X и при малых . Для таких рассм. (2) Последнее выражение является неотрицательным, так как x* есть тока минимума. Но тогда как и в противном случае при достаточно малых приращение (3) изменит свой знак на противоположный. Теор. доказана. Следстивие 1.Если или ,то нер-во (1) превращается в равенство Следствие 2.Усл(2) можно записать в виде (3) Теор2. Для того, чтобы выпуклая, непрерывно дифференцируемая ф-ция , определенна на выпуклом, замкнутом мн-ве Х, достигала своего минимума в точке , необходимо и достаточно, чтобы выполнялось нерав-во Док-во: Необходимость следует из теор1. Докажем достаточность. Пусть точка x* такова, что выполнена усл. Возьмем произвольную точку и рассмотрим По св-ву неотрицательного остатка имеем Замечание 4.Форма (3) необходимого усл. минимума непрерывно дифференцируемой ф-ции на выпуклом замкнутом мн-ве используется для построения метода усл. градиента. 24.Задача проектирования на выпуклое и замкнутое множество. Свойства проекции. Примеры. Опр. Расстояние от точки до мн-ва определ. формулой.Ф-ция непр. по y. Опр. Проекцией точки y на мн-во X наз. такая точка , для кот. Задача нахождения точки pназ задачей проектирования точки y на мн-во X. Если решение задачи проектирования , то норма Задачу проектир. обычно заменяют равносильной задачей (1) Задача (1) предст. собой задачу min-ции квадратичной ф-ции Утв1. Если мн-во явл. Замкнутым и не пустым, то и если , то Док-во. Пусть . В противном сл. . Рассм. произв. точку и построим мн-во . Мн-во не явл. пустым, явл. замкнутым и огранич. Поэтому по теор. Вейерштрасса проекция точки y на Z. В силу постр. мн-ва Z:. Пусть , . Предп. противное. . Тогда . Рассм. отрезок, соед. точки yи p: . Найдется такое , что при . Рассм. расстояние След-но, p не явл. проекцией. Утв2. Если непустое, выпуклое и замкнутое, то ед. проекция Док-во. Пусть . Тогда очевидно, что , поэтому явл. ед. Рассм., когда . Предп., что более одной проекции , , Вектора не явл. коллинеарными. Действ-но, если , то . Если , то . Это противоречит тому, что .Рассм. . Нашли точку , такую , что противор., что -проекции. Замеч. Если мн-во не явл. выпуклым, то может сущ. две проекции. Рассм. примеры нахождения проекций точек на мн-ва для некот. конкр. мн-в 1) ; 2) ;;3) ; 4) Т.к. проекция в любой точке, не принадл. X, будет принадл. границе мн-ва X, то от данной задачи можно перейти к задаче min-ции ф-ции f(x) при ограничении . Т.к. c-ненулевой вектор, сост. классич. ф-цию Лагранжа.Система необх. усл:; 25.Критерий построения проекции на выпуклое замкнутое множество. Необходимые усл. минимума диф. ф-ции на выпуклом мн-ве, выраженные в терминах проекции точки на мн-во. Критерий минимума выпуклой диф. ф-ции на выпуклом мн-ве, сформулированный с помощью оператора проектирования. Теор1.Пусть непустое мн-во X явл. выпуклым и замкнутым. Тогда точка р явл. проекцией точки у на мн-во X только тогда, когда выполняется усл. для всех . Док-во. Рассм. ф-цию . Эта ф-ция явл. квадратичной, выпуклой. Мн-во X по усл. Тео. замкнуто и выпукло. Поэтому достигается в точке эта точка явл.единственной. Тогда по теореме о необходимых и достаточных условиях минимума выпуклой ф-ции на замкнутом, выпуклом мн-ве выполняется усл. для всех . Но в данном случае Тем самым теор. доказана. В следующих теоремах выясняется зависимость решения задачи математического программирования и решения задачи проектирования. Теор2. Пусть точка есть точка локального минимума ф-ции на множестве X. Функция предполагается непрерывно дифференцируемой, а мн-во X выпуклым и замкнутым. Тогда для произвольного справедливо равенство . Док-во. Пусть . Тогда выполняется усл.(1)Пусть . Преобразуем последнее равенство к виду и подставим в формулу (1). Получим . Тогда по теор1 заключаем, что . Теорема доказана. Теор3. Пусть ф-ция явл. выпуклой, непрерывно дифференцируемой, мн-во X выпуклым и замкнутым. Точка есть точка локального минимума для произвольного справедливо рав-во . Док-во. Необходимость следует из теоремы 2. Докажем достаточность. Пусть выполняется усл. . Тогда по теореме 1 имеем из чего следует и . Тогда по критерию локального минимума выпуклой ф-ции на замкнутом выпуклом мн-ве заключаем, что есть точка локального минимума ф-ции на мн-ве Х. Теорема доказана. 26.Теорема о седловой точке функции Лагранжа (достаточные условия оптимальности). Рассм.задачу (1), (2) где - заданное мн-во и ф-ии определены на . Для задачи (1), (2) рассмю нормированную ф-цию Лагранжа: (3)определенную на мн-ве (4) Опр. Точка наз. седловой точкой функции Лагранжа (3), в области , если Теорема1 (о седловой точке ф-ии Лагранжа) Пусть точка явлю седловой точкой ф-ции Лагранжа (3), тогда явлюрешение задачи (1)-(2). Док-во: 1.Покажем сначала, что в условия теоремы точка уд. ограничениям (2) задачи (1)-(2). Т.к. -седловая точка ф-ции Лагранжа, то выполняется нер-ва: (5) Рассмю левое из (5): (6) В нер-во (6) подставляем вып-ся огранич. рав-ва. Выберем некоторый индекс положим остальные . Подставим это в (6): выполняются ограничения неравенства. Точка , т.к. она является седловой точкой функции Лагранжа. Т.е. удовл-ет огр-ям задачи (1)-(2). 2.Покажем, что для значения выполняется условие дополнительной нежесткости, а имеено, если Предположим противное: пусть для некоторого индекса В нер-ве (6) положим , тогда получим последнее нер-во будет вып-ся для а не для что противоречит определению седловой точки. 3.Покажем, что точка - решение задачи (1)-(2). Рассмотрим правое из нер-в (5), из которого в силу условия дополнительной нежесткости Рассмотрим последнее нер-во для: Доказан 27. Критерий существования седловой точки функции Лагранжа для задачи выпуклого программирования. Рассм.задачу (1), (2) где -заданное мн-во и ф-ии определены на . Для задачи (1), (2) рассм. нормированную ф-ию Лагранжа: (3) определенную на мн-ве (4) Теор2 (Критерий сущ.седловой точки ф-ии Лагранжа для задачи выпуклого прогр-ния) Пусть в задаче (1)-(2) функции являются выпуклыми, т.е задача (1)-(2)-задачи выпуклого программирования, (-выпуклое мн-во) и функции явл. дифференцируемыми в точке Тогда точка явл.седловой точкой ф-ции Лагранжа тогда и только тогда, когда Док-во: (Необходимость). Пусть точка - седлова точка ф-ии Лагранжа, тогда Т.к. ф-ии диф-мы, то ф-ия Лагранжа диф-ма: Последнее нер-во разделим на , получим (5) Покажем, что для значения вып-ся условие доп-ной нежесткости, а именно, если Предположим противное: пусть для некоторого индекса В нер-ве (6) положим , тогда получим последнее нер-во будет вып-ся для а не для что противоречит определению седловой точки. Достаточность: Пусть вып-ся соотношения (5)-(6), покажем тогда, что точка явл-ся седловой точкой ф-ии Лагранжа. Т.к. ф-ии -выпуклые по условию теоремы, то ф-ия Лагранжа выпуклая по х. По св-ву неотр-ти остатка для выпуклой ф-ии вып-ся: т.е. правая точка из опр. седловой точки. Точка а из условия (6) отсюда следует правая часть нер-ва из определения седловой точки. Теорема доказана. 28.Определение двойственной задачи к задаче математического программирования. где заданное мн-во, ф-ции определены на мн-ве Переформулируем задачу (1) при помощи нормальной классической ф-ции Лагранжа: Ф-ция Лагранжа определяется на мн-ве . Переформулируем задачу (1) при помощи нормальной классической ф-ции Лагранжа: Ф-ция Лагранжа определена на мн-ве Рассм. Ф-цию Рассм. задачу . Точную нижнюю грань В силу зависимости ф-ии с задачей (1): В предположении, что и мн-во решений задачи (1) не пусто, т.е. Задача (3) то же будет иметь мн-во решений с тем же min значением. Аналогично с функцией (2) рассмотрим ф-цию которая будет определена на И рассм. задачу Задача (4) наз. двойственной к задаче (3) или к задаче (1). Переменные двойственные переменные, наз. основными. При подстановке задачи (1) предполаг., что ф-ия приним. Конечные значения на мн-ве , поэтому ф-ия . Однако определение ф-ии не исключает возможности принятия значений разных . Чтобы подчеркнуть конечность ф-ии говорят, что рассматривается задача (5) где Обозначим и через Теор Для имеет место нер-во (6) Док-во: По определению функции Если то Переходя в последнем нер-ве к точной нижней грани по мн-ву , получаем нер-во Остальные два нер-ва в (6) очевидны. Теорема доказана.29. Связь между двойственной и прямой задачами математического программирования. Имеется задача(1): Которую можно переформулировать в(2): (2) Рассм. задачу двойственную к (2). Пусть Двойственная задача имеет вид: Теор: Для им. место нер-во Док-во: По опр-ию ф-ии . Если То Переходя в последнем нер-ве к точной нижней грани по мн-ву, получаем нер-во . Остальные два нер-ва в (5) очевидны. Теорема доказана. Теорема. Если задачи (2) и (4) имеют решение, т.е. мн-во то ф-я Лагранжа имеет седловую точку на мн-ве и обратно, если имеет седловую точку, то задачи (2) и (4) имеют решение. Док-во.Необходимость.Пусть задачи (2) и (4) имеют решение, т.е. выполнено (5). Возьмем т. . Покажем, что т. седловая точка ф-ии Лагранжа. Рассм. значение Выполняется усл. седловой точки, т.к. т.е. Достаточность.Пусть ф-я Лагранжа имеет седловую точку, т.е. Т.о. , т.е. задача имеет решение. Следствие1.След. утв. равносильны: 1.Т. -седловая точка на. 2. Задачи (2) и (4) имеют решение, т.е. 3.Сущ. такие что 4. Справедливо равенство Следствие2. Если и - седловые точки ф-ии на , то точки и -седловые точки ф-ии Лагранжа, причем значения ф-ии во всех этих точках равны между собой. 30.Пример решения задачи оптимизации с помощью теории двойственности Для правильности нужно под каждым inf поставить и в место 2 систем поставить оду с 4 уравнениями. 31.Основные определения в задаче одномерной минимизации. Примеры. Рассмотрим задачу: Считаем, что принимает на Xконечные значения. Произвольное решение этой задачи будем обозначать ч/з , мн-во решений ч/з .Таким обр, . Опр. Посл-ть наз. минимизирующей для ф-ции на мн-ве X, если Из опр-ния и существования точной нижней грани следует, что минимизирующая последовательность всегда сущ Опр. Посл-ть сходится к мн-ву X, если , где ч/з обозначено расстояние от точки до мн-ва Замеч. Если мн-во не явл. пустым, то всегда сущ. минимизирующая посл-ность, сходящаяся к . Пример1: Пусть , мн-во X совпадает со всей числовой прямой . Здесь мн-во решений , и минимальное значение ф-ции тоже равно нулю. Посл-ть явл. минимизир. т.к., но к нулю не стремится при . Опр. Ф-ция наз. унимодальной на , если она непр. на этом отрезке и сущ. такие числа , такие что:
Если , функция наз. строго унимодальной. 32.Метод деления отрезка пополам решения задачи одномерной минимизации. Пусть -унимодальна. Решим задачу. Выберем 2 точки:, , где , являющаяся параметром метода, . Чем меньше значение тем больше точность. Заметим чтоточки и располагаются симметрично относительно середины отрезка и при малых значениях делят его практически пополам. Если , то полагаем Если, то полагаем В силу унимодальности отрезок имеет непустое пересечение с множеством решений задачи и длинна нового отрезка равна . Пусть найден отрезок , длина кот.. который имеет непустое пересечение с множеством . Вычисляем точки:, и значение ф-ции в них. Если , то полагаем Если, то полагаем Получим отрезок , который имеет непустое пересечение с мн-вом и его длина равна Процесс деления отрезка пополам продолж. до тех пор, пока не будет достигнута заданная точность, при этом будет проведено итераций. Так как каждое деление отрезка пополам требует двух вычислений значений ф-ции, то для достижения заданой точности требуется вычислений ф-ции. После определения отрезка в качестве точки минимума можно взять равное: если , если И значение даст приближенное значение . При этом погрешность решения, то есть отклонение приближенного решения от мн-а решений не превосходит величины . 33. Метод золотого сечения решения задачи одномерной минимизации. МЗС позволяет решить задачу с требуемой точностью при меньшем кол-ве вычислений значения функции. Опр. Золотым сечением отрезка наз деление отрезка на 2 неравные части так, что отношение длины меньшей части к длине большей равно отношению длины большей части к длине всего отрезка. Т-ки, кот. делят отрезок в золотом отношении Описание МЗС. Решаем задачу . Положим а1=а, b1=b и найдем точки х1 и х2, котор делят [a1;b1] в золотом сечении. Вычислим и . Если , то положим а2=а1, b2=x2, . Если , то а2=х1, b2=b1, . Длина построенного отрезка [a2;b2] равна и точка , кот. делит отрезок [a2;b2] в золотом отношении. Пусть на некотор. этапе найден отр-к , найдены т-ки х1, ,…, и вычислены значения , f(),…,f(). Длина отрезка . И на отрезке есть т-ка , кот. делит этот отрезок в ЗО и в кот. вычислено значение целевой функции. Определим следующ. т-ку по правилу . Предположим, что (). Вычислим знач. ф-ции в т-ке .Если выполняется неравенство , полагаем . Если , то , в результате получим отрезок , имеющий непустое пересечение с мн-вом решений задачи, длина кот. Если количество вычислений значений целевой ф-ции ничем не огранич., то процесс вычислений продолжается до тех пор, пока не будет выполнятся неравенство Если количество вычислений значений целевой ф-ции ничем огранич., то процесс вычислений заканчивается, когда будет выполнено заданное число итераций. В качестве точки минимума выбираем т-ку с вычисленным в ней значением целевой ф-ции. Погрешность этого метода: Замечание. Преимуществом МЗС явл. тот факт, что на каждой итерации знач. ф-ции вычисляется только один раз. Замечание. МЗС можно применять для нахождения минимума функции не являющейся унимодальной. Но в этом случае решение может находиться далеко от глобального минимума. 34. Обоснование метода ломаных решения задачи одномерной минимизации. Метод ломаных применяется для решения задачи (1), без требования унимодальности ф-ции f, но эти ф-ии должны уд. усл. Липшица. |