Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Московский государственный авиационный институт

Кафедра прикладной информатики

Лекции

“МЕТОДЫ ОПТИМИЗАЦИИ ”

Содержание

1. Основные понятия

- понятие САПР

- процесс оптимизации

2. Методы одномерной оптимизации

- аналитический способ

- численный способ

3. Методы одномерного поиска

- метод “золотого сечения”

4. Одномерная оптимизация с использованием производных

- метод деление интервала пополам

- метод Ньютона (метод касательной)

5. Безусловная опртимизация

6. Квадратичная аппроксимация (или квадратичное приращение)

7. Методы прямого поиска

- приемущества

- недостатки

8. Метод координатного спуска

9. Градиентные методы

- метод наискорейшего спуска

- анализ метода

- метод Ньютона

- недостатки метода Ньютона

10. Задачи оптимизации с ограничениями - разностями (ЗОР)

- метод исключения

- метод множителей Лагранжа

11. Нелинейное программирование (НЛП)

- методы решения НЛП

12. Задачи линейного программирования (ЛП)

1. Основные понятия

Понятие САПР

САПР - система автоматизированного проектирования. Проектирование сложный процесс, направленный на разработку отдельного объекта.

Способ уменьшения время проектирования - уменьшение числа разработчиков.

Система - совокупность людей, задач и программ, которые взаимосвязаны друг с другом.

Оптимизация - от латинского слова «оптимус» - наилучший - поиск наилучшего, поиск наилучшего проектного изделия.

Процесс оптимизации

Имеется задача. Для решения задачи нужно формализовать объект и представить его в виде математической модели.

Модели:

- физические;

- геометрические (фотография, рисунок);

- математические.

Математическая модель, та которая определена с помощью математических формализмов. Математическая модель не является точной, а является идеализацией. Модель характеризуется параметрами, которые могут быть и числовыми . Их часть может характеризовать состояние объекта - параметры состояния , а другие могут относиться к процессу проектирования - переменные проектирования .

Определение параметров состояния - задача моделирования. Определение переменных проектирования - задачи проектирования или задачи оптимизации.

Допустим имеются 2 переменные . Задавая конкретные значения получаем точку.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Плоскость множества возможных вариантов, на нее могут быть наложены ограничения.

Отображение множества - целевая функция позволяет формировать критерий для сравнения различных решений.

2 вида задач оптимизации:

- максимизации;

- минимизации.

Для оптимизационного решения задачи требуется:

1. Сформулировать задачу;

2. Построить математическую модель (определить множество переменных);

3. Определить ограничения на возможные решения;

4. Определить целевую функцию. Далее применим формальные математические методы, позволяющие найти решения.

2. Методы одномерной оптимизации

Постановка: требуется оптимизировать х (формальная постановка)

- функция одной переменной

- целевая функция.

Решение: найти х, при котором принимает оптимальное значение.

2 варианта:

- минимизировать - задача минимизации;

- максимизировать - задача максимизации.

Рассмотрим случай минимизации

2 способа:

- аналитический

- численный

В аналитическом задается в виде формулы, в численном задается в виде черного ящика, на входе подается х, на выходе значение целевой функции в этой точке.

Пусть функция определена в некоторой области S (), в случае одномерной оптимизации S - интервал :

1. точка называется глобальным минимумом, если для

2. точка называется строгим глобальным минимумом, если для

3. точка называется локальным минимумом, если для

4. точка называется строгим локальным минимумом, если для

Следствие: любая точка глобального минимума является локальным минимумом, обратное не верно.

Аналитический способ нахождения локального минимума.

- дифференцируема

- необходимое условие точки локального минимума.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Численные методы

Пусть функция задана на интервале , при этом существует такая точка , что на - монотонно убывает, а на - монотонно возрастает, то функция унимодальная.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

а b

Если из того что следует, что , то функция называется монотонно возрастающей. Если из того что следует, что , то функция называется монотонно убывающей.

3. Методы одномерного поиска

Разобьем и вычислим значение функции в каждой точке.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

искомый минимум

В результате остается интервал меньшего размера, к которому применяется тот же метод, и находим еще один интервал, в конце находим интервал с заведомо нужной точкой.

Интервал неопределенности - интервал, в котором заведомо находится точка минимума. Наиболее эффективное разбиение - двумя точками на 3 равных отрезка.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1)

2)

- после выполнения n шагов сокращение исходного интервала

- точность с которой надо найти решение задачи.

N=2n, где n - число шагов, N - число вычислений (мера эффективности данного решения).

Метод золотого сечения

Точки должны быть расположены на равном расстоянии.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

; ; ;

; - золотое сечение.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

а

- величина сокращения на каждом шаге

число итераций растет как логарифм функции.

4. Одномерная оптимизация с использованием производных

. Пусть целевая функция дифференцируема .

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

точка локального минимума

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

точка локального максимума

Деление пополам

Имеется хотя бы 1 корень. Выбираем любую точку и смотрим какой знак она имеет, такой знак нам и искать. Выбираем точку приблизительно в середине интервала, исследуя значения в 3-х можно отбросить половину интервала.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Метод Ньютона (метод касательной)

В случае если известна производная, то выбираем - начальное приближение.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Допустим, что точка достаточно близка к корню функции и примерно себя ведет линейно не отклоняется. Проведем касательную и находим точку ближе чем , и повторяем до .

Для метода Ньютона необходимо:

- функция должна иметь производную;

- точка должна быть взята близко к корню;

- функция изменяется близко к линейной функции.

;

- уравнение касательной;

.

Если , то вычисления можно прекратить и считать что нужный нам корень - условие прекращения поиска. (Е - значение корня с некоторой точностью).

В методе Ньютона каждя его итерация удваивает количество значащих цифр. Если все условия выполнены, то эти методы удваивают (ускоряют) количество значащих цифр:

;

Представим что линейная функция, то метод Ньютона позволяет найти ее корень за 1-у итерацию. Целевая функция представляет собой квадратичную зависимость следовательно метод Ньютона позволяет найти минимум или максимум квадратичной функции за 1-у итерацию.

Замена функции на касательную, называется - линейная аппроксимация, и ее применение к целевой функции парабола в точке приближения.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

f(x)

Замена заданной зависимости квадратичной зависимостью, называется - квадратичной аппроксимацией. Метод Ньютона основан на замене заданной зависимости более простой зависимостью.

5. Безусловная оптимизация

Целевая функция зависит от нескольких переменных f(х₁, х₂, …, х_n) min. Т.к. нет дополнительных условий накладывающихся на переменные - безусловная оптимизация.

Функции 2-х переменных

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

f(x_1,x₂)

Условия определяющие точку минимума - необходимо проанализировать поведение функции в некоторой точке.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Часто под окрестностью подразумевают шар.

Рассмотрим вспомогательное построение:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

линейное векторное x₃ пространство (х₁,х₂,х₃)

Скалярное произведение векторов , где - длина вектора (норма вектора), - угол между векторами.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Допустим, что: ,

Тогда: ;

Допустим, что имеется 2 вектора:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Чтобы задать направление, мы задаем вектор.

Нормируем вектор

Нормированный вектор имеет тоже самое направление, но , длина.

Допустим, что задан нормированный вектор .

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Скалярное произведение равно 0, тогда года прямой.

Возвращаемся к функции 2-х переменных:

Отбрасываем члены , приращение будет более точным.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Вектор - формула Тейлора.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Мы рассматриваем как изменяется точка вдоль данного направления.

Функция становится функцией одной переменной.

- скалярная величина.

- производная по направлению (вдоль данного направления)

- направление ряда равное направлению grad ( 0).

grad - вектор, в сторону которого функция изменяется более быстро.

Антиградиент - grad направленный в другую сторону (-grad).

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

х₂

Необходимое условие:

- локальный минимум (или максимум). Точки локального экстремума.

Допустим что мы совершаем малое перемещение . В каком случае (в точке) будет: * больше, чем заданная: тогда, когда угол - острый .

* - если под прямым углом, то не изменяется;

* - если под тупым углом, то приводит к уменьшению функции.

1.

строим поверхности

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

z

2. Идет построение в плоскости х₁ и х₂. Берут точку - определяющую значение аргумента. Находят точку в которой функция имеет тоже самое значение, в результате получаем линию в которой функция имеет постоянное значение - изолиния (линия уровня).

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Вектор grad составляет прямой угол с изолинией.

Вернемся к формуле:

5. Квадратичная аппроксимация (или квадратичное приращение)

Линейное отображение:

- линейное отображение, если:

1. свойство аддитивности - ;

2. свойство однородности -

Линейное отображение можно задать матрицей:



Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

; ;

п - основная формула

отображение

2 задачи:

решение системы уравнений

и обратное отображение - найти х

А^-1 - обратное отображение;

следовательно строки матрицы ортогональны столбцам

другой матрицы

нахождение собственных значений

Используя матрицу можно найти более сложную функцию : - квадратичная форма.

- функция нескольких переменных .

Рассмотрим подробнее.

Есть матрица:

- квадратичная форма

А и А^/ определяют одну и ту же квадратичную форму следовательно значения этой формы не однозначно. Если по заданной квадратичной форме найдем симметрию, то она будет однозначная.

;

;

Без ограничения общности можно считать, что матрица определяющая квадратичную форму является симметричной.

Вернемся к квадратичной форме:

Рассмотрим функцию 2-го порядка:

Допустим, что , матрица диагональная.

1.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Эллипсы

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Эллиптический парабалоид

2.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

3.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Гиперболы

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Седло

Допустим, что . Тогда вся картина просто повернется на некоторый угол по оси Z.

Рассмотрим п-мерный случай.

Квадратичная форма называется положительно определенной областью если она не отрицательная.

1. , причем обращается в ноль, в том случае если х = 0 (). Этот случай соответствует эллиптическому параболоиду.

2. , .

3. Знаконеопределенность.

соответствует п-мерному эллиптическому гиперболоиду (п-мерное седло)

Рассмотрим 2-мерное пространство:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Если квадратная матрица называется положительно определенной, то и матрица положительно определенной.

Рассмотрим разложение функции 2-х переменных в ряд Тейлора:

квадратичная матрица задается матрицей Н

матрица составленная из членов 2-го порядка

- матрица симметрична

Матрица Н - матрица Гесса.

- определение матрицы Гесса

Если матрица (матрица Гесса) в точке локального экстремума положительно определена, то это точка - локального минимума, если матрица отрицательно определена, то это точка - локального максимума, а если не определена - седловые точки.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Локальный max или min Седловая точка

Минимизируем:

Найти частные производные:

1. (grad = 0);

2.

Эта система позволяет найти все точки экстремума:

Допустим, что . Надо составить функцию второго порядка и подставить и посмотреть их.

Необходимые условия - помогают охарактеризовать искомую точку:

1. grad f = 0

2.

Н 0 - локальный минимум;

Н 0 - локальный максимум;

Н - не определена - седловая точка.

Для поиска используют численные методы.

Постановка:

Требуется , где х - вектор - т.к. нет ограничений задача безусловной оптимизации.

Есть черный ящик, который по заданным значениям х позволяет вычислить значение функции.

6. Методы прямого поиска

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Должны задать начальное приближение точки х₀;

- некоторое приближение полученное после к - итераций;

вычислить значение точки в окрестности точки ;

Из данных точек выбрать точку в которой функция принимает наименьшее значение, выбираем ее и строим вокруг нее окрестность.

Выбираем точку где хуже. В окрестности существующей точки выбираем точку с меньшим значением, опять в ее окрестности есть точки с меньшим значением и т.д.

В таком виде этот метод не эффективен.

Пример:

Шаг по х1 берем больше, а по х2 - сохраняем. Поскольку мы свободны в выборе точек, то можно менять шаг и направление.

Методы:

1. Хука-Дживса;

2. Нелдера-Мида (используется п-1 угольник)

Преимущества метода прямого поиска:

1. простота;

2. не нужны производные.

Недостатки:

1. плохая сходимость;

2. применим для небольшого числа переменных.

п 1020

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

2п точек:

в случае 2-х переменных - 4 точки;

в случае 3-х переменных - 6 точек.

Этот метод применим в простых случаях, когда эти недостатки себя не проявляют.

8. Метод координатного спуска

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Существует приближенная точка минимума. Минимизируя функцию по направлению к х1, на прямой используется любой метод одномерной минимизируют, х2 - фиксируют. Далее выполняют одномерную оптимизацию по х2, фиксируя х1.

Этот процесс повторяют до тех пор пока следующая точка не окажется близка к точке приближения.

9. Градиентные методы

Метод наискорейшего спуска

Рассмотрим grad целевой функции.

Движение по направлению вектора под острым углом будет приводить к уменьшению целевой функции, а движение против направления функции к увеличению целевой функции. Разумно за направление движения принять сам вектор - grad f.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Для выбора расстояния нужно применить метод одномерной оптимизации. Прекратить поиск, когда величина grad f станет достаточно малой. Этот метод гарантирует, что найдена либо точка локального минимума, либо седловая точка.

Анализ метода

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рассмотрим целевую функцию, которая является квадратичной функцией, точка локального минимума совпадает с точкой начала координат.

Пусть мы выбрали начальное приближение.

Отыскивая наименьшее значение по направлению траектории (наименьшее значение там где происходит касание grad f линии уровня).

В случае когда масштаб выбирается следующим образом (линии уровня вытянуты).

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Траектория

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Если линии уровня - окружности, то приходим сразу в точку локального минимума.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Метод Ньютона

1. - один постоянный член любой точки данной функции является оптимальным - тривиальный случай;

2. линейная функция (двучлен)

(возможно бесконечное уменьшение и увеличение)

1 и 2 не подходят для оптимизации

трехчлен

;

без ограничения общности можно положить что матрица q - симметричная

Разложим функцию в ряд Тейлора (должно быть 3 члена). Чтобы найти линейный член квадратичной функции, надо взять grad.

;

; С = 0

Найдем матрицу Гесса (матрица вторых частных производных)

элемент матрицы Гесса является элементом функции Q. (все частные производные высших порядков равны 0).

Функция экстремальна, если grad в данной точке равен 0, следовательно условие экстремальности - система.

Необходимое условие оптимальности:

Если решение данной системы существует и оно единственное (совместная система).

Если решение данной системы существует и оно единственное, т.е. если Q знакоопределена, то существует решение и оно единственное.

Если имеем квадратичную функцию и матрица положительно определена, то линии уровня - эллипсы.

Собственные значения определяют оси эллипсов.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Чтобы определить координаты точки локального минимума, нужно решить систему .

Пусть f(x) - произвольная функция и надо найти точку локального минимума. Разложим функцию в ряд Тейлора в окрестности точки.

Пусть функция не квадратичная, эллипсы примерно отражают кривизну линий уровня и находятся в окрестности точки . В окрестности точки находим приближение и заменяем эту функцию квадратичной функцией, которая получается из разложения в ряд Тейлора. Далее решаем задачу минимизации.

Находим точку минимума и рассматриваем эту точку как следующее приближение и т.д.

Для нахождения точки минимума квадратичной функции (зависит от )необходимо решить систему:

Окончательно следующее приближение .

- формула Ньютона

(обобщение формулы минимизации одной переменной)

Выполнение метода останавливается когда , т.е. когда очень мало. Для получения практической точности достаточно выполнить 4 итерации метода Ньютона.

Если f - хороша, то метод Ньютона подходит, если f - квадратичная функция, то метод Ньютона приводит к минимальной точке за 1 шаг, из любой точки.

Недостатки:

1. на каждом шаге итерации надо находить решение системы ;

2. С ростом числа итераций Н - разрежается, т.е. большое число членов становится равными 0.

Все формулы безусловной минимизации можно записать в общую схему:

1. выбор направления;

2. выбор шага.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

- приближение в точке локального минимума, чтобы приблизиться к искомой точке. Мы должны выбрать направление, в конце получим локальную линию.

Допустим, требуется f(x)min; - начальное приближение; - текущее приближение

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

а) выбор направления ;

б) движение вдоль выбранного направления

10. Задачи оптимизации с ограничениями - разностями (ЗОР)

Пример:

Функции заданы аналитическим выражением можно разрешить относительно одной из переменных можно исключить из f и , подставив вместо нее :

автоматизированный проектирование аппроксимация оптимизация

Тогда, - задача безусловной оптимизации. Находим вычисляем

Метод исключения

Численное решение:

точка min должна лежать на прямой.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

В каждый момент линия уровня будет касаться прямой эта точка и является точкой

условного локального min. Если в окрестности заданной точки, удовлетворяющей

всем значениям равенства, значение функции больше, чем в точке, то эта точка - есть точка условного локального min.

Пример:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Если (a₁x)=b

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Допустим,

Прямая будет проходить через некоторую точку удовлетворяющую условию и

Для n переменных , Ax=b

Рассмотрим i-ое ограничение:

,

- задан x - все вектора, лежащие . Они и составляют гиперплоскость.

При добавлении еще одного условия, уменьшаются размерности. В конечном итоге получится пространство n-m.

Для двух переменных возможно 2 случая:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

В случае 2 это не точка минимума, а седловая точка.

Рассмотрим точку 3-х переменных:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Ограничение - плоскость, следовательно, все допустимые точки на плоскости.

Если угол grad не равен 90 градусам следовательно можно двигаться дальше. На плоскости существует направление, которое будет составлять острый угол с - grad, и двигаясь в этом направлении можно уменьшить значение f.

Если -grad f перпендикулярен плоскости эта точка может быть точкой минимума.

Пусть существует 2 ограничения:

Рассмотрим опять случай 3-х переменных:

Точка минимума должна принадлежать пересечению плоскостей.

Необходимое условие - вектор антиградиента должен составлять угол 90 градусов с прямой пересечения плоскостей.

Для п-мерного случая имеется п переменных следовательно рассматривая каждое ограничение, получаем п-1 гиперплоскость следовательно рассмотрев т ограничений получим п-т гиперплоскость (т<п).

все ограничения независимы

Если вектор grad (п-мерный) будет ортогонален п-т - пространству.

Допустим имеется п-1 пространство, п-мерный вектор может принадлежать ему или нет. Пусть вектор не принадлежит данному подпространству следовательно его можно разложить на 2 вектора - один который принадлежит подпространству, и второй который ортогонален данному. Ортогональное дополнение - вектора, которые ортогональны данному подпространству.

В 3D - пространстве, если подпространство равно 1 следовательно ортогональное дополнение равно 2.

В п-т-мерном подпространстве ортогональное дополнение имеет размерность т.

Необходимое условие: Если мы находим точку, где вектор градиента принадлежит ортогональному дополнению к пространству, заданному ограничениями - равенствами, то эта точка может быть точкой локального минимума.

Пусть есть 2 плоскости. Если записать систему ограничений равенств следующим образом:

где

Т.о. вектора порождают ортогональное дополнение. Существующие могут быть выбраны в качестве базиса ортогонального дополнения следовательно градиент принадлежит ортогональному дополнению:

т.е. линейная комбинация базисных векторов.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

- множители Лагранжа.

Рассмотрим матрицу , в ней - столбцы.

это условие может быть использовано для численного решения задачи оптимизации с ограничивающими уравнениями.

Пример:

Если найдем такие вектора х и , для которых эти условия выполняются то точка может быть точкой локального минимума.

Рассмотрим случай когда система ограничений - равенств нелинейная:

Если функции дифференцируемы, то в окрестности точки минимума они будут вести себя как линейные.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

следовательно в окрестности точки локального минимума эта зависимость линейная следовательно получается система вида:

, где

следовательно необходимое условие локального минимума:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

- множители Лагранжа.

- точка может быть искомой в задаче

- множители Лагранжа.

Обозначения для скалярного произведения ;

;

Необходимое условие точки локального минимума исходное задание с ограничениями представляет собой необходимое условие точки локального экстремума для функции Лагранжа.

Метод множителей Лагранжа

Применяется для нахождения точки локального минимума для точек исходной задачи . Экстремальными точками локального минимума являются седловые.

Пример:

Найти расстояние от точки до прямой в 3-х мерном пространстве.

Плоскость :

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Пересечение плоскостей - линия



5 условий дают систему линейных уравнений

11. Нелинейное программирование (НЛП)

- заданные функции нелинейные

НЛП

Рассмотрим

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Пример:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

В случае системы неравенств пересечение всех областей. Если g > 0, то ограничение неравенства - неактивно (точку можно смещать).

Если точка точно на границе, то говорят, что ограничение активно.

Рассмотрим случай:

Если , то граница проходит не через начало координат.

Необходимые условия:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Если локальный минимум внутри допустимой области, то ;

2. Если точка локального минимума точно на границе, то , точка является точкой локального, если и

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

В общем случае:

а) ;

б) ;

в) Если , то . Если , то . Т.е. . Условие дополняющей нежесткости.

Все 3 условия в совокупности называются условиями Куна-Таккера (условия оптимальности первого порядка).



Ограничения неравенства

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Можно записать и так:

Поскольку постановка задачи

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Основные результаты:

Область п-мерного пространства называется выпуклой если вместе с 2-ми точками, она содержит весь отрезок, соединяющий эти 2 точки.

Пример:

Функция нескольких переменных называется выпуклой если ее матрица Гесса положительно определена.

;

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Если мы рассматриваем неравенство , то данное неравенство определяет выпуклую область.

Th: Пусть дана задача НЛП, если целевая функция этой задачи - выпуклая, и область целевых решений так же выпукла, то локальный оптимум совпадает с ее глобальным оптимумом задачи (задачи выпуклого программирования).

1 случай - когда все ограничительные неравенства являются не активными.

2 случай - когда точка лежит на границе.

Методы решения НЛП

Нулевого порядка - поисковые методы (безусловные ориентиры похожи на это). Используется только значение целевой функции (Z).

Первого порядка - аналогичны градиентным методам. Условно градиентные методы. Используется и Z и вектор градиента (grad Z).

Второго порядка. Ньютоновские методы. Они являются специальными вариантами методов Ньютона для оптимизации. Используется Z, grad Z и матрица Гесса (Н)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

(**)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1 случай - вектор grad направлен по нормали;

2 случай - идет под углом (надо спроецировать поверхность следовательно она будет показывать направление)

Если мы внутри, двигаемся как в (*), а далее (**). Это более эффективный метод.

Рассмотреть отрезок, это может дать нам еще один отрезок.

12. Задачи линейного программирования (ЛП)

- стандартная форма задачи ЛП

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

В общем случае, если , то допустимая область представляющая собой многогранник в пространстве.

В случае - многогранник, имеющий неполную размерность.

Допустим, имеется некоторое выпуклое множество. Тогда в любой граничной точке этого множества, всегда можно провести опорную гиперплоскость, т.е. такую гиперплоскость которая имеет с множеством только одну общую точку, и все множество находится по одну сторону от гиперплоскости.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Если -grad является нормалью к гиперплоскости и плоскость не опорная, то можно двигаться под острым углом к -grad, тем самым улучшая значение функции. Такое движение невозможно, если антиградиент определяет опорную плоскость. Следовательно в этом случае это точка локального минимума, который является и глобальным.

Геометрически, чтобы найти точку локального минимума, необходимо найти такую вершину глобального множества, что плоскость которая является нормальной к антиградиенту является опорной.

Рассмотрим , т - ограничений равенств, п - число переменных.

Первые m столбцов линейно независимы. , .

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

A = B N m

Базисная матрица

, - столбцы матрицы

- базисные переменные

Тогда систему ограничений равенств можно записать

;

;

Для В существует обратная матрица ;

Если для данного базиса зафиксируем не базисные переменные в нуле, то получим точку, которая является вершиной многогранника.

Вершины многогранника множества характеризуемые тем, что небазисные переменные равны 0.

Что делать если вершина не точка оптимума.

Рассмотрим целевую функцию:

d - показывает суммарное влияние небазисных переменных на целевую функцию

d₀ - множители Лагранжа или относительные оценки небазисных переменных.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Точка будет точкой оптимума, если все .

Если имеется один отрицательный коэффициент.

следовательно можно увеличить , тогда целевая функция начнет улучшаться.

, если , то дальше увеличивать нельзя и меняются местами.

Размещено на Allbest.ru

...