Элементы теории выпуклых множеств и функций

Лекция № 2 Элементы теории выпуклых множеств и функций. 2.1. Выпуклые множества. Выпуклый анализ в настоящее время является обширным разделом математики, начало которому было положено в работах немецкого математика и физика Германа Минковского (1864-1909). Рассмотрим некоторые понятия и факты, которые будут использоваться в следующих разделах. Будем предполагать, что рассматриваются элементы и множества из пространства конечной размерности. Пусть и – два элемента из . Тогда множество , - * называется отрезком , ( -в ) + . Отрезок может быть записан в иной форме: ( Геометрически это выглядит так: при Когда ) при «пробегает» значения от нуля до единицы, . «пробегает» по всему отрезку. Рис. 3 (а) Определение 2.1 Непустое множество называется выпуклым множеством, если для любых двух элементов и из соединяющий их отрезок , , т.е. , - Пустое множество считается выпуклым по определению. Определение иллюстрируется рисунком: ( ) Рис. 3 (б) Примеры выпуклого и невыпуклого множества Операция пересечения, примененная к совокупности (конечной или бесконечной) выпуклых множеств, не нарушает выпуклости. Операция объединения может ее нарушить. Можно ввести операции сложения множеств и умножения их на действительное число. * + * + ( ) Операции сложения, умножения на число, вычитание не нарушают выпуклости (докажем позднее). Множество K называется конусом (с вершиной в точке O), если Конус не обязательно является выпуклым множеством. Задания : Пусть выпуклые множества. Доказать выпуклость множеств: ⋂ ∑ * Множество : { ∑ + для } и ; ( ) ∑ { ∑ } называется линейной оболочкой (доказать ее выпуклость) Разберем пример 1 Пусть множеств): выпуклые множества. Доказать выпуклость множества (пересечение ⋂ Пусть (каждому, для ), следовательно принадлежит пересечению множеств. ⋂ Но т.к. все выпуклы, то ( для любого I, следовательно ) ( ) ⋂ Что доказывает выпуклость множества – пересечения Остальные примеры доказать самостоятельно. Определение 2.2 Функция Q, определенная на выпуклом множестве , выпуклой (выпуклой вниз) на , если ( ( ) ) ( ) ( ) ( ) ) ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) называется Если при тех же условиях выполняется ( ( то функция называется вогнутой (выпуклой вверх) Если ( ( ) ( ) ) то функция называется строго выпуклой, а если ( ( ) ) то функция называется строго вогнутой. геометрически означает, что для всякого отрезка , ) проходит нестрого ниже включенного в , график этого отрезка ( соответствующей хорды, опирающейся на ( ) и ( ) Выпуклость функции Q на -, Рис. 4 (а) Рис. 4 (б) Если функция Q является аффинной, т.е. ( ) , то она одновременно и выпукла и вогнута. Критерий выпуклости дифференцируемой функции ( ) На открытом выпуклом множестве функция ( )выпукла тогда и только тогда, когда ( ) ( ) ( ( ) ) Неравенство означает, что график (поверхность) функции всюду проходит нестрого выше ее линейного приближения (касательной гиперплоскости), построенного по измерениям функции Q и ее градиента в произвольной точке из D. Рис.5 (а) Рис.5 (б) Критерий выпуклости для дважды непрерывно дифференцируемой функции ( ) Пусть Q определена на открытом выпуклом множестве D. Q выпукла на D тогда и только тогда, когда матрица Гессе (обозначим ее неотрицательно определена на D, т.е. и произвольного вектора d : ( ) ( ) В силу непрерывности вторых частных производных матрица Гессе будет симметричной. Получим матрицу Гессе для функции: Q= ( ) ( ( ) ) Если гессиан функции Q всюду в D положительно определен, функция будет строго выпукла на D. Обратное неверно. Например, строго выпукла в , а ее вторая производная в нуле равна нулю. Характер знакоопределенности симметрической матрицы определяется по знаку квадратичной формы для . Если знак может быть различен для разных d, то матрицу называют знаконеопределенной. Критерий Сильвестра позволяет взаимно однозначно связать положительную определенность матрицы A с положительностью ее главных миноров а отрицательную определенность – с чередованием их знаков, начиная с отрицательного: Если значения некоторых из миноров обратились в ноль, критерий неприменим. Например, из того, что не следует неотрицательность матрицы. ● Рассмотрим пример: является ли выпуклой функция? Составим матрицу Гессе: ( ) . ( Исследуем ее главные миноры: / ) | | Матрица Гессе положительно определена. Следовательно, функция Q является выпуклой. Лекция № 3. Условия оптимальности в задачах математического программирования. Теория и примеры. Рассмотрим задачу о нахождении допустимых значений , при которых функция ( ) достигает минимума в области: ( ) { ( ) } Запишем эту задачу в виде: * ( ) + Предполагается, что минимум существует. Будем рассматривать решения двух типов: глобально-оптимальные, когда ( ) ( ) и локально – оптимальные, когда существует такая окрестность ( ) точки для которой: , ( ) значение ( ) точки ) ( ) (т.е. это выполняется для любого Всюду ниже функции ( ) достаточно гладкими. ( ) ( из окрестности ) будем считать Для задач, не обладающих выпуклостью, необходимые условия наличия в точке локального минимума дает теорема Каруша-Куна- Таккера. Теорема. Для того, чтобы точка была локальным минимумом рассматриваемой задачи необходимо выполнение группы условий: 1.Точка допустимость; 2. ( нетривиальность; ) 3. ( 4. ( ) 5. ( ) ) ∑ неотрицательность; ( ) ∑ ( )- разложимость; условия дополняющей нежесткости. Ограничения - неравенства, обращающиеся в ноль в точке активными в этой точке. называют ( ) Для множества номеров активных в точке специальное обозначение - ( ) неравенств удобно ввести Разберем содержательный смысл условий дополняющей нежесткости. Из условия (5) следует, что для неактивных в точке неравенств выполняется Следовательно, неактивные ограничения не входят в условие разложимости (4) и не влияют на выполнение условий оптимальности. Фактически в условии (4) суммирование выполняется только по номерам ( ) Заметим, что для задач без ограничений-равенств аналогичную теорему обычно называют теоремой Куна – Таккера (при этом все, что связано с равенствами, из условий теоремы следует исключить), а для задач без ограничений –неравенств – теоремой Лагранжа. В последнем случае первая из сумм в правой части условия разложимости отсутствует, а условия 3 и 5 - неотрицательности и дополняющей нежесткости - вообще не нужны, требования нетривиальности запишется в виде: ( ) Если ввести функцию Лагранжа, записав ее с использованием векторных обозначений: ( ) ( ) ( ( )) ( ( )) то условие разложимости (4) можно представить как условие стационарности функции Лагранжа: ( ) Если функции выпуклы (вниз), ограничения – равенства либо отсутствуют, либо линейны, функция ( ) выпукла (вниз), то такая задача называется выпуклой. В выпуклой задаче математического программирования все локальные минимумы являются глобальными. При этом условия теоремы Каруша – Куна - Таккера будут не только необходимыми, но и достаточными условиями, определяющими точку глобального минимума . Задача 3.1 Найти минимум функции ( ) при ограничениях: Приготовим задачу к решению по теореме К-К-Т Запишем ограничения по-другому: Найдем градиенты: ( ) ( ) ( ) ( ) Решение задачи состоит в переборе активных ограничений и проверке условий теоремы. Пусть множество активных ограничений – пустое множество: ( ) Запишем условие разложимости: { Проверим выполнение ограничений в этой точке Ограничения выполняются в данной точке. Возьмем в качестве активного одно из нарушенных ограничений, например (объяснение по рисунку). Запишем условие разложимости: ( ) * + . ( ) ∑ ( ) ∑ ( ( ) ) ) ( ) ( ( ) ( ) ( ) ( { ) Последним приписывается активное ограничение. Самое главное – выполнено условие неотрицательности Проверим выполнение неравенств Легко проверить, что ограничения выполняются в данной точке. Теперь проверим функцию на выпуклость Найдем частные производные Составим матрицу Гессе: ( ) ( ( Исследуем ее главные миноры: ) | | ) Функция ( ) является выпуклой функцией. Все ограничения линейны (они одновременно выпуклы и вогнуты). Задача является выпуклой. В выпуклой задаче математического программирования все локальные минимумы являются глобальными. При этом условия теоремы Каруша – Куна - Таккера будут не только необходимыми, но и достаточными условиями, определяющими точку глобального минимума . Точкой минимума является точка Другие линии уровня с большим С «войдут в область», но т.к. мы ищем минимум функции, нас интересует линия наименьшего С, которая «коснется» области. Лекция № 7. Вычислительные методы математического программирования. В общем случае задача математического программирования представима в виде: { ( ) ( ) { } ( ) } (7.1) где множество простой геометрической структуры, например { или } Вычислительный метод должен строить для задачи (7.1) оценку решения (приближенное решение) – интервальную или точечную. Вычислительный метод (или алгоритм) решения задачи строится исходя из имеющейся априорной информации о свойствах функций. 7.1. Методы поиска минимума унимодальной функции. Пусть унимодальная функция на отрезке [ ] Эта функция должна иметь на этом отрезке единственный глобальный ] а на [ ] строго минимум (обозначим его ) и строго убывать на [ возрастать. При применении вычислительного метода испытания включают только измерения значений функции. Для проверки унимодальности функции ( ) на практике обычно используют следующие критерии: 1.Если функция ( ) дифференцируема на отрезке [ не убывает на этом отрезке, то ( ) унимодальна на [ 2. Если функция ( ) дважды дифференцируема на [ ( ) [ ] то ( ) унимодальна на [ и производная ] ] ]и ] Пример 7.1. Показать, что функция ( ) ] унимодальна на отрезке [ Найдем ( ) ( ) ( ) Корни полученного квадратного трехчлена ( ) Используя второй критерий унимодальности, получаем, что ( ) унимодальна ]. на отрезке [ 1.Пусть некоторым методом точках: проведено N измерений значений функции в с результатами : ( где под Тогда ) ( ) { } понимается номер испытания с наименьшим значением. [ ( ) ( ) ] испытания в этих точках не проводятся. Данный интервал является оценкой решения. Если отрезок разбивается на n равных частей: ( ) ( ) , То этот метод поиска минимума называется методом перебора. Эффективность выполненных измерений можно оценить длиной интервала. Пример 7.2. Найти минимальной значение и точку минимума функции ( ) на отрезке [ ] Проверим функцию на унимодальность: ( ) ( ) √ ( ) ( √ ) На отрезке [ ] Разобьем отрезок [ точках деления. унимодальна. ( ) ] 1,5 1,55 1,6 ( ) -89,4 -90,2 91,2 10 равных частей, вычислим значения функции в 1,65 1,7 1,75 1,8 1,85 1.9 1.95 2 -91,8 -91,9 -91,4 -90,5 -89,4 -88,0 92,08 92,12 Из таблицы находим 2.Метод дихотомии – неоптимальный последовательный метод. Это простой последовательный метод, позволяющий сокращать интервал поиска в два раза с использованием двух новых измерений. Первое измерение не приводит к сокращению интервала. Описание алгоритма a) задать точность решения; b) положить ( ) c) пока ) ) ( ) ( ) d) вычислить Используя измерения функции в трех точках зависимости от того, какое из трех значений новые значения: ( ) в наименьшее , установить Если наименьшее было Если наименьшее было Если наименьшее было Вернуться на пункт с) ) полученный интервал принять в качестве интервальной оценки решения. Рис. 7.1. Гарантированная эффективность метода дихотомии за N измерений: ( ) N всегда нечетно. 3.Метод золотого сечения. Рассмотрим метод, который для очередного сжатия интервала поиска использует только одно новое измерение (кроме начального этапа, требующего проведения сразу двух измерений). Новые значения используются более рационально, чем в методе дихотомии. Деление отрезка на две неравные части происходит так, что отношение длины всего отрезка к длине большей его части равно отношению длины большей части к длине меньшей части. Такое деление называется золотым сечение этого отрезка. Золотое сечение отрезка [ ] осуществляется двумя точками [ ( ( ) ( ) )( ) ( ) ] √ √ Итак, отрезок будет разделен в отношении Точки относительно середины отрезка (доказать самостоятельно). симметричны Рис. 7.2. Описание алгоритма: а) Задать точность решения; b) провести измерение в точке построить новую точку ( ( ) ) c) пока выполнять пункт d), d) провести измерение в новой точке ( ( )и ( ) ) и запомнить результат ) Если , то положить новую точку ( Иначе, если новую точку положить ( и выбрать ) ( на рис. 7.3. k=0) и выбрать ) (для этого случая рисунок сделать самостоятельно). (Т.е. и в первом, и во втором случае перешли к новому отрезку [ этом отрезке – точки ] и на вернуться к пункту с) е) полученный интервал принять в качестве интервальной оценки решения Осталось доказать (для случая ) , что новая точка ] в отношении золотого сечения (точку новый отрезок [ ( ) мы и находили в отношении золотого сечения). делит Докажем это (для простоты) для первого и второго отрезка. Т.е в начале рассмотрим отрезок [ ( Для случая ] на котором находятся точки: ) ( ) находим новый отрезок и новые точки: ( Докажем, что делит новый отрезок [ ) ] в отношении золотого сечения Надо доказать, что Все длины отрезков выразим через длину большого отрезка ( ( ) ( ) ) ( ( ) )( ( ) )( ( ) )( ) Получили соотношение, которое соответствует золотому сечению. Именно такое мы получали, когда начали исследовать золотое сечение. Значит, точка делит новый отрезок [ ] в отношении золотого сечения. В случае решите самостоятельно, какое утверждение «про золотое сечение» надо доказать. Домашнее задание. ]. Показать, что является 1.Пусть точки точки золотого отрезка [ ] а второй точкой золотого сечения отрезка [ первой точкой золотого ]. сечения отрезка [ 2. Пусть точки точки золотого отрезка [ справедливо равенство ][ ] отрезков [ ]. Доказать, что Найти длины 3. Доказать унимодальность функции ( ) [ ]. Сделать два шага методом дихотомии. 4. Доказать унимодальность функции ( ) ( ) [ Сделать один шаг методом золотого сечения, получить новый отрезок. Рис. 7.3. ] Лекция №8 Вычислительные методы математического программирования 8.1 Методы поиска локального минимума в задачах без функциональных ограничений { ( ) } - это задача без ограничений. Функция, как правило, должна характеризоваться лишь гладкостью некоторого порядка. Обычно в таких задачах используется принцип «локального спуска» к минимуму, заключающийся в том, что должно обеспечиваться существенное убывание значений целевой функции: ( ) ( ) Существенное убывание должно обеспечивать сходимость к локальнооптимальному решению. Рис. 9.1 Будем задавать начальную точку поиска . Несмотря на неограниченность области поиска, всегда будем предполагать, что локальный минимум в задаче существует и начальная точка для применяемого численного метода находится в области его притяжения. 8.2. Метод Ньютона Данный метод является классическим методом второго порядка , использует локальные квадратичные аппроксимации функций. Концептуально важен, как основа построения высоко эффективных методов. Рассмотрим произвольную дважды непрерывно дифференцируемую функцию. Пусть в точке для ( ) измерены значения: ( ) ( ) матрица Гессе – матрица вторых производных: ( ) Для функции трех переменных матрица Гессе имеет вид: ( ) ( ) Для функции двух переменных матрица Гессе имеет вид: ( ) ( ) Построим локальную квадратичную аппроксимацию целевой функции: ( ) ( ) ( ) ( ) Вспомним формулу Тейлора для функции двух переменных в окрестности точки ( ) ( ) (( ( ( ) ( ) ) ( ( ( ( ) )( ( ) ) ( ) ) ) ) ) На самом деле – это разложение функции ( ) по формуле Тейлора в окрестности точки , и берутся в формуле слагаемые не выше второй степени (квадратичные). Распишем это подробно для второго слагаемого в формуле для ( ) ( ) ( ) ( ) ( ( ) (( ) ) ( ): ) ( ) ( ) ( ) ( ( ) ( ) ( ( ) ) ) это линейные слагаемые формулы Тейлора. Квадратичные слагаемые задаются формулой: ( ) ( ) Это нужно проверить самостоятельно сравнить с формулой Тейлора. Возвращаемся к методу Ньютона. Условие, определяющее стационарную точку ̅ аппроксимации вид: ( ̅) ( ̅ ( ) имеет ) Если принять точку ̅ за точку очередного испытания Ньютона: , то получим метод ( ) ( ) Умножим обе части равенства на матрицу, обратную к матрице Гессе в точке ) : слева, т.е. на матрицу ( ( ) ( ( ) ) ( ( ) ) (9.1) ( Направление ( ) ) Получается из антиградиента за счет домножения на него обратной матрицы к матрице Гессе. ( ) Метод Ньютона размещает точку нового испытания текущей квадратичной аппроксимации. в стационарной точке Для квадратичной функции ( ) при невырожденности матрицы Гессе метод Ньютона приходить за один шаг в стационарную точку функции ( ) Рассмотрим простую интерпретацию метода Ньютона для функции одной переменной. Тогда соотношение (9.1) принимает вид: ( ) (9.2) Представим итерационный процесс на плоскости Стационарной точке функции ( ) будет соответствовать корень производной ( ) а соотношение (9.2) можно интерпретировать как метод касательных для поиска корня уравнения ( ) III КУРС. II. Условия оптимальности в задачах математического программирования. Лекция № 1. Необходимые сведения из математического анализа. Этот материал мы повторяли в конце предыдущего семестра. Но мы рассматривали функции двух переменных. Но теперь мы рассмотрим эти вопросы на более высоком уровне – будем изучать функции произвольного, но конечного числа переменных. Целью этого раздела является изучение условий, определяющих точку экстремума в задачах с ограничениями: ( ) ( ) * ( ) ( } ) ) – ограничения – неравенства ( ) – ограничения – равенства ( (1.1) Функции достаточно гладкие. Пример такой задачи: 1. Вектор – градиент и его геометрический смысл. Обозначим вектор – градиент ( ) ( ) ( ) ( ) Геометрическое место точек , для которых ( ) . Это поверхность, которая называется поверхностью равного уровня. ( ). На поверхности равного уровня Пусть она проходит через точку . Тогда ( ). выполняется: ( ) Если функция ( ) дифференцируема в точке , то ( ) ( ) ∑ ( ) ( ) (‖ ‖) (разложение функции по формуле Тейлора) С использованием векторной формы записи: ∑ ( ) Используя эти равенства и равенство ( ( ) ( ) ( ( ) ), получаем: ) ( ) ( ( ( ) ( ) ) (‖ ) ‖) (‖ ( ) ‖) Это представление поверхности равного уровня. Отбрасывая последний нелинейный (малый) член суммы, имеем линейную аппроксимацию поверхности в окрестности : ( ( ) ) ( ) Получили уравнение касательной гиперплоскости в точке . Видим, что вектор ортогонален к ней. Вектор градиента локально ортогонален также поверхности равного уровня функции в точке (рис.1) Рис.1 2.Производная по направлению. Пусть ) нормированным (| | – вектор направления. Считаем его По определению ( ( ) ( - производная по направлению. ) ) | ( ) Производная по направлению может существовать и при отсутствии дифференцируемости Q в точке . Например не дифференцируемая функция ( ) | | в точке имеет производные по направлениям и эти производные равны 1. Получим выражение для производной по направлению в случае дифференцируемости функции в точке ( ( ) ) ( ( ) ) ( | |) ( ) ( ( ) ) Множество направлений строгого локального убывания функции есть открытое полупространство (рис. 2) * ( ( с границей, ортогональной ( ). Поскольку ( ( ) )| | | ( ) ) |( ) ) + при , -, то при ( ) ( ) – направление скорейшего локального роста функции, т.к. ему соответствует а - ( ) (антиградиент) – направление скорейшего локального убывания, т.к. ему соответствует . Рис. 2 3. Условие экстремума первого порядка при отсутствии ограничений. Рассмотрим задачу поиска минимума функции ( ) Теорема Ферма. Если и Q дифференцируема в точке - локальный минимум функции Q в , то ( Доказательство. Пусть это не так и направлении ) . ( ) . Рассмотрим точки, смещенные от в ( ( | ) | | )| Из дифференцируемости следует, что ( ( ) ( ) ( ( ) ) при любых достаточно мылах ( ) ( ) ) ( ) | ( ) | ( )| ( ) ( ) . Это противоречит локальной оптимальности точки ( ) Замечание. Условие является необходимым не только для локального минимума, но и для локального максимума. Доказательство теоремы Ферма опирается на возможность смещения из точки в любом направлении в силу отсутствия ограничений. При наличии ограничений точки, в которых ( ) могут выходить из допустимой области. Тогда применяется несколько другой алгоритм нахождения максимума или минимума функции 4. Функция Лагранжа. В общем случае задачи (1.1) (задача с ограничениями) условия экстремума удобно записывать через функцию Лагранжа. Для этой задачи она имеет вид: ( ) ( ) ∑ ( ) ∑ (1.2) Если ограничений - неравенств в задаче нет, то сумма ( ) ∑ исчезает. Q Задача с ограничениями – равенствами имеет вид : ( ) ( ) * ( } ) – ограничения – равенства Для нее функция Лагранжа: ( ) ( ) (1.3) ∑ (1.2* ) Лагранж рассматривал именно задачу (1.3) и функцию вида (1.2*). 5. Необходимые условия оптимальности в задаче с равенствами. Теорема Лагранжа. Пусть в задаче с равенствами (1.3) функции Q и дифференцируемы в окрестности точки , их производные непрерывны в точке . Тогда, чтобы была локальным экстремумом (минимумом или максимумом), необходимо существование , при котором для функции Лагранжа (1.2*) выполняется условие стационарности по совокупности переменных в точке ( ) ( ) (1.4) Если расписать это равенство, т.е. разделить дифференцирование по ( ) ( ) ( и по , получаем: ∑ ) h( ) (1.4* ) Это равенство эквивалентно записывается в виде системы условий: { ( ) ( ∑ ( ) ) (1.4**) ( ) Заметим, что условие (1.4) выглядит так же, как условие в теореме Ферма, но оно записывается для функции Лагранжа. Т.е. теорема Ферма рассматривается в расширенном пространстве Система (1.4**) – полная система уравнений относительно ( ). При этом первое условие в системе означает линейную зависимость векторов ( ) ( ) ( ) ( ) а второе условие в системе означает допустимость точки, т.е. что ограничения - равенства в точке ( ) выполняются. Эту теорему примем без доказательства, но будем использовать при решении задач для нахождения минимума или максимума функции, если при этом в задаче заданы ограничения - равенства. Лекция № 5. Условия оптимальности в задачах математического программирования. Теория и примеры. Рассмотрим задачу: Найти проекцию произвольной точки ( * Введем функцию ( ) ) на множество D + ( ) ( ) Расстояние между двумя точками находится «немного» по другой формуле: ( ) √( ) ( ) ) и минимум функции ( ) находятся в одной и той же Но минимум функции ( ) –квадрат расстояния между точками. точке. Значительно легче изучать функцию ( Действительно, минимум этой функции достигается в точке ( ), но при этом ( минимально расстояние до точки ( ), для которой ) . А это и есть проекция ( ) на множество D. Проекция точки на множество – это ближайшая к данной точке ) которая связана с точка множества. Поэтому мы ищем минимум функции ( расстоянием между точками. Сформулируем задачу по- другому: найти минимум функции ( при ограничениях ) ( ) , где ( ( ) ) произвольная точка плоскости. Рис 5.1 Запишем ограничения в нужном виде для решения задачи: ( ) ( ( ) Найдем градиент функции ( ( ) ) ) ( ( ( ) ) ) ) находится внутри области D, т.е не лежит ни на одном 1.Пусть проекция точки ( ограничении. Это значит, что множество активных ограничений – пустое множество. Тогда { ( ( ) ) Это значит, что проекцией точки является сама точка. Это происходит, когда точка ( ) находится внутри области D (Рис. 5.1) 2.Пусть проекция лежит на прямой ( . Тогда это ограничение является активным. ) Условие разложимости запишется: ( { ( ) ) Последним приписали активное ограничение. Выразим через из первых двух уравнений и подставим в третье уравнение: { Получаем { Чтобы точка ( ) была проекцией, т.е. доставляла минимум функции, необходимо, чтобы выполнялись два условия - точка должна удовлетворять второму ограничению и . Распишем эти ограничения. ) Это неравенство «противоположно» неравенству ( которое выделяет ( ), область определения задачи, т.е. точка которую мы проектируем, лежит ниже ) прямой ( . Точка ( ( ) должна удовлетворять второму ограничению. ) ( ) ( ) Это приводит к неравенству: Точка ( )лежит ниже прямой ниже прямой Эти прямые взаимно перпендикулярны, т.к перпендикулярны их нормальные векторы, и проходят через точку (1, 3) ̅̅̅* + ̅̅̅̅* +( ̅̅̅̅) Следовательно, эти прямые задают область Итак, если проектируемая точка лежит в ( , то ее проекция попадает на прямую ) 3. Пусть проекция лежит на прямой активным. ( . Тогда это ограничение является ) Условие разложимости запишется: { ( ( ) ) Последним приписали активное ограничение. Выразим через из первых двух уравнений и подставим в третье уравнение: { ( ) Получаем { Чтобы точка ( ) была проекцией, т.е. доставляла минимум функции, необходимо, чтобы выполнялись два условия - точка должна удовлетворять первому ограничению и . Распишем эти ограничения. Это неравенство «противоположно» неравенству ) мы проектируем, лежит ниже прямой ( Точка ( ( . ) ) должна удовлетворять первому ограничению. т.е. точка ( ), которую ( ) ( ) ( ) Это приводит к неравенству: Точка ( )лежит выше прямой ниже прямой Эти прямые взаимно перпендикулярны, т.к перпендикулярны их нормальные векторы, и проходят через точку (1, 3) ̅̅̅* + ̅̅̅̅* ̅̅̅̅) +( Следовательно, эти прямые задают область Итак, если проектируемая точка лежит в ( , то ее проекция попадает на прямую ) 4. Пусть проекция лежит на пересечении прямых Т.е. в точке ( ( ) и ( ) ) Тогда оба ограничения являются активными. Условие разложимости запишется: { ( ( ) ) Последние два уравнения – активные ограничения. Решение – точка ( ) Подставим в первые два уравнения: { ( ( ) ) Самостоятельно решить систему, найти (выразить через Показать, что если проекцией точки ( области между двумя прямыми ) является точка ( и Самостоятельно показать, что задача является выпуклой. ) и из условия ) ( )лежит в Лекция № 6. Условия оптимальности в задачах математического программирования. Теория и примеры. Задача 6.1 Найти проекцию произвольной точки плоскости ) на прямоугольник ( . Рис. 6.1 Расстояние между двумя точками находится «немного» по другой формуле: ( ) √( ) ( ) Проекция точки на множество – это ближайшая к данной точке точка множества. Введем функцию ( ) ( ) ( ) ) и минимум функции ( ) находятся в одной и той же Но минимум функции ( ) – квадрат расстояния между точками. точке. Значительно легче изучать функцию ( Сформулируем задачу по- другому: найти минимум функции ( ) при ограничениях ( ) ( , где ( ) произвольная точка плоскости. ) Запишем ограничения в нужном виде для решения задачи: ( ) ( ) ( ( ) ) ( ) ( ) ( ) Найдем градиент функции ( ( ) ) ( ( ( ) ) ) ) находится внутри области D, т.е не лежит ни на одном 1.Пусть проекция точки ( ограничении. Это значит, что множество активных ограничений – пустое множество. Тогда { ( ( ) ) Это значит, что проекцией точки является сама точка. Это происходит, когда точка ( ) находится внутри области D. 2. Пусть проекция лежит на прямой ( ) является активным. (как показано на рисунке). Тогда ограничение Условие разложимости запишется: ( ( { ( ( ( ) ) ) ( ) ) ) Последним приписали активное ограничение. Решим систему. Найдем ) задана). точка ( ( (видим это на рисунке, : известно, т.к. ) Получилась точка ( ) Чтобы точка ( ) была проекцией, т.е. доставляла минимум функции, необходимо, чтобы выполнялись два условия - точка должна удовлетворять всем оставшимся ограничениям и . Распишем эти ограничения. ( ) ( ) ( ) это неравенство выполняется всегда по условию задачи. ( ) Чтобы выполнялось необходимо Итак, чтобы проекция точки «падала» на прямую ) расположению точки ( , должны выполняться условия по Именно такое расположение мы видим на рисунке. 3. Пусть проекция лежит на прямых ( ) ( ограничения (как показано на рисунке). Тогда являются активным. ) Условие разложимости запишется: ( { ( ( ( ( ) ) ) ( ) ( ) ) ) Последними приписали активные ограничения. Найдем . ( ) ( ) Последние условия указывают, где должна быть расположена точка ( рисунке), чтобы проекция лежала на прямых Удовлетворяет ли точка ( ) (видим это на . ) остальным ограничениям? ( ) ( ) Эти неравенства выполняются всегда. Самостоятельно доказать выпуклость задачи. Задача 6.2. (Невыпуклая задача) ( ) * + Допустимая область задана линейными ограничениями, эти функции – ограничения выпуклы. Составим матрицу Гессе: ( ) ( ( ) ) Поскольку главные миноры матрицы обращаются в нули, то по критерию Сильвестра нельзя выяснить знакоопределенность матрицы. Поэтому мы не можем утверждать, что функция является выпуклой. Поэтому условия К.- К. – Т. не будут являться достаточными, а будут лишь необходимыми условиями локального минимума. Поскольку условия оптимальности лишь необходимы, сначала следует доказать существование минимума в этой задаче. Если решение существует, то придется отыскивать все точки, где эти условия выполняются, и затем, сравнивая значения функции в этих точках, определить глобальный минимум. Исключим из ограничений, используя Тогда задача примет вид: ( ) * + В пространстве переменных матрица вторых производных имеет вид: ( ) ( ) Не можем утверждать, что является положительно определенной. Функция не имеет конечных безусловных минимумов (самостоятельно покажите это). Проведем исследование. Область D неограниченна. Изучим поведение функции вдоль ( ) параллельным границам области. Рассмотрим вектор прямых ) направленный вдоль этих прямых. Функция ( ) ) положительную вторую производную. направлению вектора ̅ ( ̅ ( ( ) ( )( имеет по )( ) Отсюда и из квадратичного вида функции следует существование конечного минимума в задаче, поскольку на бесконечности функция будет возрастать равномерно по параметру С. Пусть активным ограничением является ( ) ( ( ) Разложение будет иметь вид: ( ) { ( ) ) { Удовлетворяет ли точка ( В точке ( - 0, 25. ( ) ограничению номер 2 : ( ) ( ) ) может быть минимум функции. Значение функции в этой точке равно (Точка А на рисунке 6.2.). Пусть активным ограничением является ) ( ) ( ) ( ) Разложение будет иметь вид: ( ) ( ) { { Удовлетворяет ли точка ( ) Проверим. ( В точке ( ) ограничению номер 1: ( ) ) может быть минимум функции. Значение функции в этой точке ( ) Следовательно, глобальный минимум вспомогательной задачи достигается в точке ( ) А для исходной задачи – в точке На рисунке (6.2.) это точка B Рис. 6.2. Практическое занятие №4 Глава II. Условия оптимальности в задачах математического программирования Нахождение минимума выпуклой функции по теореме К.-К.-Т. Задача 4.1. Найти минимум функции ( ) ( ) ( ) При ограничениях Начертить на плоскости вид области решения задачи. В угловых точках построить векторы( ). Используя геометрическую трактовку градиенты, а также вектор антиградиент условий К.- К.- Т. определить, может ли точка глобального минимума располагаться в одной из вершин? Сделать предположения о точке локального минимума. Поверить по теореме К.К.-Т. 1.Запишем ограничения в нужном для решения виде и вычислим их векторы – градиенты, а ( ) также вектор антиградиент ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ( ) Теперь сделаем рисунок ( ( ( ) ) ) ) Найдем точки пересечения ограничений- вершины четырехугольника Точка A - ( ) пересекается с ( ) { A (3,5; 2,5) Вычислим координаты антиградиента в точке A ( Точка B - ( ) ) пересекается с ( ( ( ( ) ) ) ( ) ) { B (1,33; 4,67) Вычислим координаты антиградиента в точке B ( ) ( ( ( ) ) ) ( ) Точка C - ( ) пересекается с ( ) { C(0,8; 4,4) Вычислим координаты антиградиента в точке C ( Точка D - ( ) ) пересекается с ( ( ( ( ) ) ) ( ) ) { D(2,33; 1,33) Вычислим координаты антиградиента в точке D ( ) ( ( ( ) ) ) ( ) В вершинах построим векторы - антиградиенты и конус направлений убывания функции. При этом вектор можно «сжать» во сколько угодно раз. Направление вектора не изменится. Если конус в точке пересекается с областью D, то точка не может быть минимумом функции. Это происходит во всех точках – вершинах задачи (показать самостоятельно). Значит, ни одна угловая точка не может быть точкой экстремума. 2. Решим теперь задачу по К.-К.-Т. Пусть множество активных ограничений – пустое множество. ( ) ( ( { ) ) { Назовем эту точку O(3,5;4). Видим, что точка лежит за пределами области . Убедимся в этом аналитически. Проверим, выполняются ли ограничения в этой точке. ( ) ( ( ( ) ) ) Видим, что нарушается ограничение Введем его в число активных. Кроме того, мы можем заметить, что линии уровня функции – эллипсы с центром симметрии в точке O(3,5;4). Чем «шире» эллипс, тем большему значению функции он соответствует. Первый эллипс, который подойдет к области решения задачи коснется ограничения ( ) ( ) ( ) { Назовем эту точку M (2,5;3,5) Проверим, удовлетворяет ли точка остальным ограничениям ( ( ) ) ( ) Исследуем задачу на выпуклость. Ограничения – неравенства линейны, следовательно, выпуклы. Найдем матрицу Гессе для функции: Составим матрицу Гессе: ( ) ( ( Исследуем ее главные миноры: ) ) | | Матрица положительно определена. Для выпуклости дважды непрерывно дифференцируемой функции ( ) необходимо и достаточно неотрицательной определенности этой матрицы, то ( ) выпукла в . Условия К.-К.-Т. будут необходимыми и достаточными условиями, определяющими решение задачи. Домашнее задание. Задача 4.2. Проверить выполнение условий К.-К.-Т. в точках : ( Для задачи: ( ) При ограничениях : ) ( ) (√ ) ( ) ( ) Практическое занятие №5 Глава II. Условия оптимальности в задачах математического программирования Нахождение минимума выпуклой функции по теореме К.-К.-Т. Задача 5.1. ( ) При ограничениях: Как изменится решение, если добавить ограничение - равенство ? 1.Запишем ограничения в нужном для решения виде и вычислим их векторы – ( ) градиенты, а также вектор антиградиент ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( Теперь сделаем рисунок на плоскости ) Рис. 5.1. Решим теперь задачу по К.-К.-Т. Пусть множество активных ограничений – пустое множество. ( ) { { Сложим 1-е и 2-е уравнения, получим: Из второго уравнения Итак, получили точку: . Назовем ее точка A Проверим, принадлежит ли точка области решения задачи ( ( ) ( ) ) ! ! ( ) Т.е. нарушены ограничения 2 и 3. Введем эти ограничения в число активных ( ) * + ( ) ( ) ( ) ( ); { Последние два равенства – активные ограничения. Из этих равенств найдем Из третьего равенства: Получим два равенства для нахождения { Итак: Проверим, удовлетворяет ли точка ( ( ) ограничениям 1 и 4 ) ( ) Проверим, является ли задача выпуклой. ( ) ( ( ) ) | | | | Функции – ограничения являются линейными, т.е выпуклы. Матрица Гессе ) положительно определена. Для этой выпуклой задачи точка B( является точкой минимума. 2.Добавим ограничение – равенство Тогда можно исключить переменную из всех выражений. ( ) ( ) ( ) Ограничения задачи останутся прежними: Преобразуем функцию: ( ) Запишем ограничения, как функции двух переменных: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) Проверим задачу на выпуклость: ( ) ( ( ) ) Исследуем ее главные миноры: | | Матрица положительно определена. Для выпуклости дважды непрерывно дифференцируемой функции ( ) необходимо и достаточно неотрицательной определенности этой матрицы, то ( ) выпукла в . Условия К.-К.-Т. будут необходимыми и достаточными условиями, определяющими решение задачи. Ограничения линейны, т.е. выпуклы. Пусть множество активных ограничений – пустое множество. ( ) ( ) { Решаем систему, получаем Проверим, удовлетворяются ли ограничения. Видим по графику, что в этой точке не выполняются ограничения 2 и 3 Проверим аналитически: ( ) ( ) Возьмем эти ограничения за активные: ( ) ( ) ( ) { Последние два равенства – активные ограничения. Система для нахождения : ( ) { Обосновать самостоятельно, что это точка минимума. Проверить, что выполняются ограничения 1 и 4. Найти минимальное значение функции в первой задаче и во второй (минимумы будут разные!) Домашнее задание. Найти проекцию произвольной точки плоскости на прямоугольник . Рис. 5.2 Сделать для параллелепипеда и трехмерной точки. ( ) Практическое занятие №6 Глава II. Условия оптимальности в задачах математического программирования Нахождение минимума функции по теореме К.-К.-Т Задача 6.1. Решить задачу определения глобальных минимумов функции Q при ограничениях: Q  x12  x 22  16 x1  20  x 2  164 при ограничениях x1  x2  8  0;  0,5  x12  x2  4  0; x1  0; x2  0 1.Запишем ограничения в нужном для решения виде и вычислим их векторы – градиенты, а также вектор антиградиент ( ) ( ( ( ) ( ) ) ) ( ( ( ) Теперь сделаем рисунок на плоскости Рис.6.1 ( ) ( ) ) ( ) ) 2.Решим теперь задачу по К.-К.-Т. Пусть множество активных ограничений – пустое множество. ( ) { Получили точку Назовем ее точка А. Проверим, принадлежит ли точка области решения задачи ( ( ( ) ) ) ( ) Т.е. нарушенo ограничение 1 . 3.Введем это ограничение в число активных ( ) { } ) ( ) ( ) ( { Последнее равенство – активное ограничение. Для решения системы выразим из первого и второго уравнений через и подставим в третье уравнение { Получили точку, обозначим ее B. Проверим, выполняются ли в этой точке остальные ограничения. ( ( ) ) ( ) В точке B выполнены необходимые условия минимума, но т.к. задача не является выпуклой, могут быть и другие точки, подозрительные на экстремум. Покажем, что задача не является выпуклой. Функция - ограничение ( не является выпуклой. ) ( ) Главные миноры не являются положительными Функция не является выпуклой. Все остальные ограничения – линейны, значит – выпуклы. Проверьте, что функция цели Q  x12  x 22  16 x1  20  x 2  164 является выпуклой, и тем не менее, в целом, задача не является выпуклой. Значит, надо проверять другие точки на выполнение достаточных условий теоремы. Возьмем другие активные ограничения, например 1 и 3, ( ) { } ( ) ( ) ( ) ( ) { Последние два равенства – активные ограничения. Решаем систему: Это говорит о том, что ограничение №3 надо выводить из числа активных. А такой вариант у нас уже был. В общем случае в невыпуклой задаче требуется большой перебор различных вариантов активных ограничений. Попробуйте, например, взять в качестве активных ограничения 2 и 3 и посмотрите, почему необходимые условия минимума по т. К.- К.-Т. не будут выполняться. Если найдутся еще точки, в которых выполняются необходимые условия теоремы, то надо вычислить значения функции во всех таких точках и выбрать из них наименьшее. Но в данной задаче мы можем сделать выводы из геометрических соображений. Линии уровня функции – окружности с центром в точке в точке А (8, 10). Чем больше радиус окружности, тем большему значению функции она соответствует. Окружность с «наименьшим» значением функции, коснется заданной области в точке B (3,5) Через другие точки, которые расположены на границах, пройдут окружности большего радиуса, которые не могут давать минимум данной функции. Задача 6.2. С использованием теоремы К.-К.-Т. доказать, что из всех треугольников с общим углом при вершине и заданной суммой длин боковых сторон равнобедренный треугольник имеет наименьшее основание. Пусть угол при вершине треугольника равен , а длины боковых сторон равны Тогда по теореме косинусов основание треугольника равно Надо найти минимум функции при ограничениях: Запишем ограничения в нужном для решения виде, найдем градиенты: ( ( ) ( ) ( ) ( ) ) ( ) ( ) Проверим задачу на выпуклость. Ограничения - равенства и ограничения неравенства линейны, следовательно, выпуклы. Проверим функцию ( ) Главные миноры: В треугольнике не может быть такого угла. Следовательно, функция выпукла и задача является выпуклой. Пусть множество активных ограничений-неравенств является пустым множеством, но ограничение-равенство обязательно входит в разложение: ( ) ( ) { Вычтем из первого уравнения второе, получим: ( ) ( ( )( ) ( ) ) ( ( ) ) Итак, получили точку ( ) В этой точке выполняются все ограничения неравенства. По свойству нетривиальности теоремы К. – К.-Т. множитель ( ) т.к. должен быть отличен от нуля, Следовательно, точка удовлетворяет всем необходимым условиям теоремы К.-К.-Т. Из выпуклости задачи следует, что эти условия являются еще и достаточными. Рис. 6.2 Домашнее задание 6.3. Известно, что город, который необходимо спроектировать, имеет форму треугольника, площадь которого фиксирована и равна S. Каждый вечер город обходит по периметру стражник. Определить, какими должны быть стороны треугольника, для того, чтобы расстояние, которое он преодолевает, было минимальным. 6.4. Найти глобальный минимум в задаче (  ) x12  x22  2  x1  2  x2  2; x  D  D  x  R 2 : x1  x2  1, x12  x22  1, x1  0,5, x2  0,5 6.5 Даны две параллельные прямые и точка А между ними, лежащая на расстоянии a одной прямой и на расстоянии bот другой прямой. Точка А служит вершиной прямых углов прямоугольных треугольников, две другие вершины которых лежат на каждой из параллельных прямых. Какой из треугольников имеет наименьшую площадь?