🗊Презентация Нелинейное программирование

Нелинейное Программирование

Типовые примеры применения Типовые примеры применения Графическое изображение Виды задач нелинейного программирования Безусловная оптимизация с одной переменной Безусловная оптимизация с несколькими переменными Условие Каруша-Куна-Таккера (ККТ) для оптимизации с ограничениями Квадратичное программирование Сепарабельное программирование Выпуклое программирование Невыпуклое программирование Выводы

Задачи планирования характеризуются нелинейностью  Задачи планирования характеризуются нелинейностью  необходимо решать такие нелинейные задачи. Задача нелинейного программирования: найти x = (x1, x2, . . . , xn) так, чтобы Максимизировать f(x), Согласно gi(x) ≤ bi : i = 1, 2,. . . , М, и х ≥ 0, f(x), gi(х), заданная функция с n переменными решения.

Не существует универсального алгоритма для решения каждой конкретной задачи этого формата. Не существует универсального алгоритма для решения каждой конкретной задачи этого формата. Особые случаи решаются путем различных предположений. Рассмотрим типовые приложения и основные идеи решения некоторых важных типов задач нелинейного программирования.

Типовые примеры Задача о комбинации продуктов при эластичности цен Транспортная задачи с оптовыми скидками на транспортные расходы Выбор портфеля активов с ценными бумагами в зоне риска

Графическое Изображение

Видов задач нелинейного программирования Безусловная оптимизация Оптимизация с линейными ограничениями  Выпуклое программирование Сепарабельное программирование  Невыпуклое программирование  Геометрическое программирование  Дробное программированию Задача комплиментарности

Один алгоритм не может решить все эти различные типы задач. Поэтому были разработаны алгоритмы для различных классов (определенных типов) нелинейного программирования. Один алгоритм не может решить все эти различные типы задач. Поэтому были разработаны алгоритмы для различных классов (определенных типов) нелинейного программирования.

Безусловная Оптимизация с одной переменной Одномерная процедура поиска

Безусловная оптимизация с несколькими переменными Процедура градиентного поиска

Условие Каруша-Куна-Таккера (ККТ) для оптимизации с ограничениями квадратичное программирование

Квадратичное программирование ККТ условия для квадратичного программирования Измененный симплекс-метод Правило ограниченного доступа

Сепарабельное программирование Переформулировка задачи как задача линейного программирования

Выпуклое программирование Алгоритм последовательной линейной аппроксимации (Франка-Вульфа)

Невыпуклое програмирование

Графическое Представление с 1 или 2 переменными может быть представлено ​​графически. (пример о стекольном заводе для линейного программирования). Если 2-е и 3-е функциональные ограничения заменены одним нелинейным ограничением: - Оптимальное решение все еще остается ​​(x1, x2) = (2, 6) на границы области допустимых значений, но оно не допустимое решение угловой точки(УГД). УГД решение возможно, но с другой целевой функцией: (Z=3x1 + x2). - Если целевая функция нелинейная:

Пример стекольного завода Пример стекольного завода с нелинейным ограничением

Пример о стекольном заводе с исходной областью допустимых значений с нелинейной целевой функцией: Пример о стекольном заводе с исходной областью допустимых значений с нелинейной целевой функцией:

Оптимальным решением является (8/3, 5)оно лежит на границе области допустимых значений (Z = 857), геометрическое область точек с Z = 857 пересекает область допустимых значений именно в этой точке, в то время как геометрическая область точек с любым большим Z вообще не пересекает область допустимых значений). Оптимальным решением является (8/3, 5)оно лежит на границе области допустимых значений (Z = 857), геометрическое область точек с Z = 857 пересекает область допустимых значений именно в этой точке, в то время как геометрическая область точек с любым большим Z вообще не пересекает область допустимых значений). если Оптимальное решением является (x1, x2) = (3, 3), оно лежит внутри границы области допустимых значений. (Решение остается оптимальным, так как оно является безусловным абсолютным максимумом, и если оно удовлетворяет ограничениям, то оно является оптимальным и для задачи с ограничениями).

Пример о стекольном заводе с исходной областью допустимых значений с другой нелинейной целевой функцией: Пример о стекольном заводе с исходной областью допустимых значений с другой нелинейной целевой функцией:

Общий алгоритм должен рассмотреть все решения в области допустимых значений, а не только на ее границе. Локальный максимум не обязательно должен быть глобальным максимумом (общее оптимальное решение). Например, рассмотрим функцию с одной переменной построенную в пределах 0 ≤ х ≤ 5  функция имеет 3 локальных максимума, х = 0, 2, 4, но только Общий алгоритм должен рассмотреть все решения в области допустимых значений, а не только на ее границе. Локальный максимум не обязательно должен быть глобальным максимумом (общее оптимальное решение). Например, рассмотрим функцию с одной переменной построенную в пределах 0 ≤ х ≤ 5  функция имеет 3 локальных максимума, х = 0, 2, 4, но только X = 4 - глобальный максимум. (локальные минимумы в х = 1, 3, 5, но только х = 5 является глобальным минимумом). Нелинейные алгоритмы программирования не в состоянии различать локальный максимум и глобальный максимум (за исключением нахождения другого лучшего локального максимума). Важно знать условия, при которых любой локальный максимум гарантированно будет глобальным максимумом в области допустимых значений .

Максимизация обычной (дважды дифференцируемой) функции с одной переменной f(x)) без каких-либо ограничений, когда Максимизация обычной (дважды дифференцируемой) функции с одной переменной f(x)) без каких-либо ограничений, когда                для всех x  функция всегда изогнута вниз: вогнутая функция. Если ≤ заменены ≥  функция всегда изогнута вверх: выпуклая функция. (Линейная функция как вогнутые, так и выпуклые). Функция не является ни вогнутой, ни выпуклой, если изгибы вверх и вниз чередуется между собой. Функции со множеством переменных характеризуются как вогнутые или выпуклые, если всегда изогнуты вниз или вверх. Проверка: для функции с более двух переменных (функция состоит из суммы более мелких функций с одной или двумя переменными каждая).

Если каждая меньшая функция = вогнутая  Если каждая меньшая функция = вогнутая                             = общая функция вогнута. Если каждая меньшая функция = выпуклая                             = общая функция выпуклая. Сумма 2 небольших функций (в квадратных скобках).                   функция x1  вогнутая, потому что ее вторая производная отрицательна.                       функции x2 и x3  вогнутые, потому что обе меньших функции вогнуты.

Задача нелинейного программирования не имеет ограничений: Целевая функция = вогнутая гарантирует, что локальный максимум = глобальный максимум. Задача нелинейного программирования не имеет ограничений: Целевая функция = вогнутая гарантирует, что локальный максимум = глобальный максимум. Целевая функция = выпуклая гарантирует, что локальный минимум = глобальный минимум. Если есть ограничения  еще одно условие обеспечивает эту гарантию. Область допустимых значений = выпуклое множество (множество точек, где для каждой пары точек в области, весь отрезок линии, соединяющей их, также лежит в области) область допустимых значений для задачи о стекольном заводе = выпуклое множество. Область допустимых значений для любой задачи линейного программирования = выпуклое множество. Область допустимых значений на рис. является выпуклым множеством.

Область допустимых значений для задач нелинейного программирования = выпуклое множество, где все gi(х) = выпуклые функции [для ограничения gi(х) ≤ bi]. g1(х) = x1 (линейная функция автоматически и вогнутая и выпуклая) и Область допустимых значений для задач нелинейного программирования = выпуклое множество, где все gi(х) = выпуклые функции [для ограничения gi(х) ≤ bi]. g1(х) = x1 (линейная функция автоматически и вогнутая и выпуклая) и ( и = выпуклые функции  их сумма = выпуклая функция). Эти две выпуклые gi(х) приводят к области допустимых значений, которая явлвется выпуклым множеством. Когда только одна из этих gi(х) = вогнутая функция. Нелинейные ограничения заменяются на

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

вогнутая функция, так как обе вогнутая функция, так как обе              и = вогнутые функции. Новая область допустимых значений ≠ выпуклое множество (оно содержит пары точек (0, 7) и (4, 3), и часть отрезка, соединяющего эти две точки не находится в области допустимых значений). Нет гарантии, что локальный максимум = глобальному максимуму. Два локальных максимума, (0, 7) и (4, 3), но только (0, 7) = глобальный максимум  чтобы гарантировать, что локальный максимум = глобальному максимуму для задачи нелинейного программирования с ограничениями gi(х) ≤ bi (i = 1, 2, ..., т) и х ≥ 0, целевая функция f(x) должна быть вогнутой и каждая gi(х) должна быть выпуклой функцией (так называемое выпуклое программирование).

Виды задач нелинейного программирования Один алгоритм не может решить все эти различные типы задач. Поэтому были разработаны алгоритмы для отдельных классов (определенных типов) нелинейного программирования.

Безусловная оптимизация: Безусловная оптимизация: Нет ограничений Цель: Максимизировать F(x): x = (x1, x2, ..., хn). Решение: х = х* является оптимальным, когда F(x) дифференцируема функция: :х = х*, j = 1, 2,…, n. Когда f(x) вогнутая функция (достаточное условие). Решение для х* сводится к решению системы n уравнений полученных заданием n частных производных = 0. Для нелинейной функции f(x) эти уравнения также нелинейны  трудно решить аналитически. Процедуры поиска значения х, описанные для n =1 и n > 1, играют важную роль в решении многих типов задач, где существуют ограничения.

Алгоритмы задач с ограничениями сосредоточены на варианте неограниченный задачи на каждой итерации. Когда xj имеет ограничение неотрицательности Алгоритмы задач с ограничениями сосредоточены на варианте неограниченный задачи на каждой итерации. Когда xj имеет ограничение неотрицательности xj ≥ 0, необходимое и достаточное условие меняется на:   для каждого такого j, показанного на рис., где оптимальное решение задачи с одной переменной при х = 0, и даже производной отрицательно, а не равно 0. Вогнутая функция, которая следует максимизировать согласно условию неотрицательности, если имеет производные ≤ 0 при х = 0 это является необходимым и достаточным условием для х = 0 оптимальным. Задача с ограничениями неотрицательности, но без функциональных ограничений (частный случай m = 0) - следующий класс задач.

Линейно ограниченная оптимизация: Линейно ограниченная оптимизация: gi(х) линейная функции с ограничениями, f(x) целевая функция нелинейна. Задача упрощается если имеем одну нелинейную функцию, с областью допустимых значений линейного программирования. Разработаны специальные алгоритмы, основанные на расширенном симплекс-методе для учета нелинейной целевой функции (особый случай: квадратичное программирование). Квадратичное программирование: линейные ограничения, f(x) квадратичная целевая функция. Отличие от линейного программирования: некоторые слагаемые в целевой функции включают квадрат переменной или произведение двух переменных.

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

Расширенный симплекс-метод используется там, где F(x) вогнутая функция. Расширенный симплекс-метод используется там, где F(x) вогнутая функция. Квадратичное программирование очень важно: его формулировка естественно возникает во многих приложениях (Выбор портфеля активов с рисковыми ценными бумагами). Общим подходом к решению общих линейно ограниченных задач оптимизации является решение последовательности аппроксимаций квадратичного программирования.

Выпуклое программирование: Выпуклое программирование: Широкий класс задач, который включает все предыдущие типы (как частный случай), где f(x) вогнутая функция. Предположения: 1. f(x) является вогнутой функцией. 2. Каждый gi(х) является выпуклой функцией. Этого достаточно, чтобы обеспечить то, что локальный максимум = глобальному максимуму. Необходимыми и достаточными условиями для такого оптимального решения являются естественное обобщение условий для безусловной оптимизации и ее расширения, чтобы включить ограничения неотрицательности.

Сепарабельное программирование: Сепарабельное программирование: Особый случай выпуклого программирования с дополнительным предположением: 3. Все f(x) и gi(х) – сепарабельные функции. Сепарабельные функции = каждое слагаемое включает только одну переменную, поэтому функцию можно разделить на сумму функций с отдельными переменными: каждая fj(xj) функция включает только слагаемые, содержащие только xj. В линейном программировании сепарабельное программирование удовлетворяет предположению аддитивности, но не предположению пропорциональности (для нелинейных функций).

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

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

Геометрическое программирование: Геометрическое программирование: В применении нелинейного программирования для инженерных задач проектирования, целевая функция и функции ограничений примут вид: Где для i = 1, 2,. . . , n. ci и aij представляют физические константы, xj переменные проектирования. Функции не является ни выпуклой, ни вогнутой методы выпуклого программирования не могут быть применены к этим задачам геометрического программирования.

Важный случай может быть преобразован в эквивалентную задачу выпуклого программирования (где коэффициенты ci в каждой функции строго положительны)  функции здесь - обобщенные положительные многочлены (posynomials), целевая функция будет минимизироваться. Эквивалентная задача выпуклого программирования с переменными решения y1,y2,... ,yn, полученная заданием для j = 1, 2, ... , n. по всей исходной модели, так что могут быть применены алгоритмы выпуклого программирования. Разработаны альтернативные процедуры решения для решения этих полиноминальных проблем программирования, а также для других типов задач геометрического программирования. Важный случай может быть преобразован в эквивалентную задачу выпуклого программирования (где коэффициенты ci в каждой функции строго положительны)  функции здесь - обобщенные положительные многочлены (posynomials), целевая функция будет минимизироваться. Эквивалентная задача выпуклого программирования с переменными решения y1,y2,... ,yn, полученная заданием для j = 1, 2, ... , n. по всей исходной модели, так что могут быть применены алгоритмы выпуклого программирования. Разработаны альтернативные процедуры решения для решения этих полиноминальных проблем программирования, а также для других типов задач геометрического программирования.

Дробное программирования: Дробное программирования: Целевая функция в форме дроби максимизировать Такие задачи возникают при максимизации отношения произведенного товара на количество затраченных человеко-часов (производительность) или прибыли на израсходованный капитал (доходность), или ожидаемого значения к стандартному отклонению меры производительности для инвестиционного портфеля (доходность/риск). Разработаны некоторые специальные процедуры решения для определенных форм f1(х) и f2(х).

Решение проблемы дробного программирования – преобразовать ее в стандартный тип аналогичной задачи, для которых уже существуют эффективные процедуры решения. f(x) дробно-линейных форм программирования Решение проблемы дробного программирования – преобразовать ее в стандартный тип аналогичной задачи, для которых уже существуют эффективные процедуры решения. f(x) дробно-линейных форм программирования где c, d - векторы строки, х - вектор-столбец, c0, d0 скаляры. Функции ограничений gi(х) линейные, поэтому ограничения в матричной форме: Ax ≤ B и x ≥ 0.

При дополнительных предположениях, трансформируем к эквивалентной задаче линейного программирования, задавая и При дополнительных предположениях, трансформируем к эквивалентной задаче линейного программирования, задавая и таким образом, что х = у/т  Максимизировать Z = cy + c0t, Согласно Ay - bt ≤ 0,                       dy + d0t = 1, и у ≥ 0, T ≥ 0, Что может быть решено симплекс-методом. Такие же преобразования используются для преобразования задач дробного программирования с вогнутыми f1(х), f2(х), gi(х) в эквивалентные задачи выпуклого программирования.

Задача дополнительности Задача дополнительности Решение некоторых задач нелинейного программирования может быть сведено к решению задач дополнительности. С учетом переменных w1, w2,. . . , wp и z1, z2,…, zp, задача дополнительности в том, чтобы найти подходящее решение для набора ограничений w = F(z), w ≥ 0, z ≥ 0 Которое удовлетворяет ограничению взаимодополняемости

w и z = векторы-столбцы, F = заданная вектор-функция, T обозначает транспонирование. Задача не имеет целевую функцию, так что это не полноценная задача нелинейного программирования (задача дополнительности) из-за дополнительных отношений, которые либо w и z = векторы-столбцы, F = заданная вектор-функция, T обозначает транспонирование. Задача не имеет целевую функцию, так что это не полноценная задача нелинейного программирования (задача дополнительности) из-за дополнительных отношений, которые либо wi = 0 или zi = 0 (или оба) для каждого i = 1, 2, ... , p. Важным частным случаем является линейная задача дополнительности:   F(z) = q + Мz, где q = заданный вектор столбец и M = P x P заданная матрица. Эффективные алгоритмы, разработанные для решения этой проблемы при соответствующих предположениях о свойствах матрицы M. Один тип включает в себя поворот из одного базисного допустимого решения (BF) к другому, как симплекс-метод для линейного программирования. Задачи взаимодополняемости находят применение в нелинейном программировании, теории игр, экономических задачах равновесия и инженерных задачах равновесия.

Одной Переменной Безусловной Оптимизации Безусловной оптимизации с одной переменной х (N = 1), где дифференцируемой функции (х) до максимума вогнутой  необходимым и достаточным условием для конкретного решения х = х*, чтобы быть оптимальным (глобального максимума) находится на х = х* Как на рис. Это уравнение может быть решена явно в X *, или, если F(x) не простая функция, поэтому производная не только линейной или квадратичной функцией, уравнение не может быть решена аналитически.Одномерного поиска процедура обеспечивает простой способ решения проблемы численно. Одномерные Процедура поиска Одномерного поиска процедура находит последовательность решения суда, который приводит к оптимальному решению. На каждой итерации, вы начинаете с текущим решением суда проводить систематический поиск, который завершается путем выявления новых улучшенное решение суда.

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

Если наклон (производная) положительное или отрицательное решение в суде указывает, является ли улучшение лежит к правой или левой  если производная в конкретное значение х положительно  х* должна быть > х (см. рис), так что эта х становится нижней границей решения суда должны быть рассмотрены позже. Если производная отрицательна  x*, должны быть <x, поэтому x станет верхняя граница. Определение обе границы, каждое новое решение суда выбран границы между текущим предусматривает новые жесткие связанный одного типа, сужая тем самым область поиска. Как правило выбора каждого пробного раствора Таким образом, результирующая последовательность проб решения должны сходиться к х*. На практике, то есть с продолжающимися последовательности, пока расстояние между границ не достаточно мал, что следующее решение суда должно быть в пределах заранее оговоренного ошибке допуска x*. Обрабатывать данные: Если наклон (производная) положительное или отрицательное решение в суде указывает, является ли улучшение лежит к правой или левой  если производная в конкретное значение х положительно  х* должна быть > х (см. рис), так что эта х становится нижней границей решения суда должны быть рассмотрены позже. Если производная отрицательна  x*, должны быть <x, поэтому x станет верхняя граница. Определение обе границы, каждое новое решение суда выбран границы между текущим предусматривает новые жесткие связанный одного типа, сужая тем самым область поиска. Как правило выбора каждого пробного раствора Таким образом, результирующая последовательность проб решения должны сходиться к х*. На практике, то есть с продолжающимися последовательности, пока расстояние между границ не достаточно мал, что следующее решение суда должно быть в пределах заранее оговоренного ошибке допуска x*. Обрабатывать данные:

Для выбора каждого нового решения суда, который используется процедурой является серединой правило (так называемый план поиска Больцано), который выбирает середину между двумя текущие границы. Для выбора каждого нового решения суда, который используется процедурой является серединой правило (так называемый план поиска Больцано), который выбирает середину между двумя текущие границы. Резюме: Одномерные процедуру поиска. Инициализации: Выбрать є. Найти начальные и осмотр (или найти любое значение х, при котором производная положительна, а затем отрицательный). Выберите исходный раствор суда

Итерация: Итерация: 1. Оценка при х = х'. 2. Если ≥ 0, сброс = х'. 3. Если ≤ 0, сброс = х'. 4. Выберите новый. Правила остановки: Если , таким образом, что новый x’ должен быть в є из х*, остановиться. В противном случае выполните другой итерации.

Пример: Предположим, что функция, которая будет максимальным: , А на рис. Пример: Предположим, что функция, которая будет максимальным: , А на рис. Первых двух производных:   Вторая производная отлична от положительной везде, f(x) является вогнутой функцией, поэтому одномерного поиска процедура может быть применена безопасно найти свой глобальный максимум (при условии, глобальный максимум существует). Быстрый осмотр этой функции (даже без построения ее графика, как показано на рис.) Показывает, что f(x) является положительным для малых положительных значений х, но это негативно для х < 0 или х > 2.

Одномерные Пример процедуры поиска. Одномерные Пример процедуры поиска.

Одномерного поиска процедура подачи заявок Одномерного поиска процедура подачи заявок

 = 0, = 2, используются в качестве исходных границ, с их средней точке х = 1, а начальное решение суда. Пусть є = 0,01 быть ошибки терпимости x* в правила остановки, так что окончательное  = 0, = 2, используются в качестве исходных границ, с их средней точке х = 1, а начальное решение суда. Пусть є = 0,01 быть ошибки терпимости x* в правила остановки, так что окончательное                ≤ 0,02 с окончательным х’ в середине. 1D-поисковый процедура дает последовательность результаты представлены в табл. [Таблица включает как функция и производные величины, где производное оценивали при испытании решение сгенерировано предшествующих итерации алгоритма не нужно вычислить f(x) вообще и что она нужна только для расчета производной достаточно далеко, чтобы определить его знак] , сделать вывод, что                       х* ≈ 0,836, 0.828125 < х* < 0,84375.

Многомерных Безусловной Оптимизации: Многомерных Безусловной Оптимизации: Максимизация вогнутой функции f(х) несколько переменных x (​​x1, x2, ..., хn), когда нет никаких ограничений на возможные значения. Необходимые и достаточные условия оптимальности, дается система уравнений, установив соответствующие частные производные = 0, не может быть решена аналитически, поэтому численная процедура поиска должна быть использована. Как предыдущую процедуру поиска 1D быть продлен до этой многогранной проблемы? Стоимость обыкновенных производных используется для выбора одного из всего двух возможных направлений (увеличение или уменьшение x), в котором, чтобы перейти от текущего решения суда к следующему.

Цель: достичь точки, где эта производная = 0. Есть бесчисленное множество возможных направлений, в которых для перемещения, соответствуют возможно пропорциональное соотношение, при котором соответствующие переменные могут быть изменены. Достигнув точки, где все частные производные = 0  расширения 1D процедуру поиска требует использования значений частных производных, чтобы выбрать определенное направление, в котором двигаться (включает в себя использование градиента целевой функции). Потому что цельовой функции f(х) предполагается дифференцируемой, он обладает градиент , в каждой точке х. Цель: достичь точки, где эта производная = 0. Есть бесчисленное множество возможных направлений, в которых для перемещения, соответствуют возможно пропорциональное соотношение, при котором соответствующие переменные могут быть изменены. Достигнув точки, где все частные производные = 0  расширения 1D процедуру поиска требует использования значений частных производных, чтобы выбрать определенное направление, в котором двигаться (включает в себя использование градиента целевой функции). Потому что цельовой функции f(х) предполагается дифференцируемой, он обладает градиент , в каждой точке х.

Градиент в конкретной точке х = х‘ является вектором, элементами которого являются частные производные от х = х', так что при х = х'. Значение градиента в том, что (бесконечно малых) изменение х, который максимизирует скорость, с которой f(x) увеличивает это изменение, которое пропорционально . Геометрически направление градиента имеет направленный отрезок (стрелка) от координат (0, 0, ..., 0) до точки ( , ..., ), где оценивается в xj = xj‘  скорость, с которой f(х) возрастает, если максимальна (бесконечно малых) изменений x в направлении градиента . Градиент в конкретной точке х = х‘ является вектором, элементами которого являются частные производные от х = х', так что при х = х'. Значение градиента в том, что (бесконечно малых) изменение х, который максимизирует скорость, с которой f(x) увеличивает это изменение, которое пропорционально . Геометрически направление градиента имеет направленный отрезок (стрелка) от координат (0, 0, ..., 0) до точки ( , ..., ), где оценивается в xj = xj‘  скорость, с которой f(х) возрастает, если максимальна (бесконечно малых) изменений x в направлении градиента . Цель: найти максимально допустимое решение f(x), казалось бы целесообразно пытаться двигаться в направлении градиента как можно больше.

Процедура Градиент Поиск: Процедура Градиент Поиск: Текущая проблема не имеет ограничений, градиент предполагает, что эффективная процедура поиска должна продолжать двигаться в направлении градиента, пока не достигнет оптимального решения х*, где f(x*) = 0. Это не практично изменить x непрерывно в направлении, потому что это ряд изменений потребует непрерывной переоценке и изменению пути направления  лучше было бы продолжать двигаться в фиксированном направлении от текущего решения суда, не останавливаясь, пока f(х) не перестает расти.

Остановка точка будет следующее решение суда, поэтому градиент затем будут пересчитаны, чтобы определить новое направление. При таком подходе каждая итерация включает в себя изменение текущего х решение суда следующим образом: сброс , где t* является положительным значением т, которая максимизирует , то есть Остановка точка будет следующее решение суда, поэтому градиент затем будут пересчитаны, чтобы определить новое направление. При таком подходе каждая итерация включает в себя изменение текущего х решение суда следующим образом: сброс , где t* является положительным значением т, которая максимизирует , то есть [ f(x)= , где , j = 1, 2,. . . , n, и что эти выражения для xj включает только константы и t, поэтому f(x) становится функцией только одной переменной t]

Итераций этой процедуры поиска градиента продолжаются до = 0 в небольших толерантности, т.е. до : j= 1, 2, . . . , n Итераций этой процедуры поиска градиента продолжаются до = 0 в небольших толерантности, т.е. до : j= 1, 2, . . . , n Чтобы подняться на вершину холма, близорукие, не может видеть вершину холма, чтобы идти непосредственно в этом направлении. Когда стоит на месте, землю вокруг ног хорошо видно, чтобы определить направление, в котором холме наклонной вверх наиболее резко  ходить в прямую линию. Во время прогулки, состоянии сказать, когда прекращении прохождения (ноль склона в направлении). Предполагая, что холм вогнута, градиентной процедуры поиска можно использовать для восхождения к началу эффективно. 2-переменной проблема, где (x1, x2) представляет координаты (без учета высоты) текущего местоположения. Функция f(x1, x2) дает холм высотой в (x1, x2). Начало каждой итерации в текущем положении (текущее решение суда), определяя направление [в (x1, x2) система координат], в которой холм наклонной вверх наиболее резко (направление градиента) в этой точке.

Тогда начните ходьбу в этом фиксированном направлении и продолжаться, пока продолжают расти. Остановка на новое место суда (решение), когда холм становится уровень в направлении, в котором готовятся сделать еще один итерации в другом направлении. Продолжить этих итераций, после зигзагообразные пути в гору, пока не дойдете до суда месте, где наклон = 0 во всех направлениях. Хилл Тогда начните ходьбу в этом фиксированном направлении и продолжаться, пока продолжают расти. Остановка на новое место суда (решение), когда холм становится уровень в направлении, в котором готовятся сделать еще один итерации в другом направлении. Продолжить этих итераций, после зигзагообразные пути в гору, пока не дойдете до суда месте, где наклон = 0 во всех направлениях. Хилл [f(x1, x2)] вогнута, то вершину холма. Найти t*, значения t, которая максимизирует f в направлении градиента, на каждой итерации. х и имеют фиксированные значения для максимизации, и f(x) вогнута  проблема максимизации вогнутой функции одной переменной t. Решаемые 1D процедура поиска (где начальная нижняя граница t не может быть отрицательным из-за t ≥ 0 ограничение). Если е простую функцию, то можно получить аналитическое решение, установив производную по t = 0 и решение.

Резюме градиентной процедуры поиска: Резюме градиентной процедуры поиска: Инициализации: выбрать и любой начальной х решение суда. К первым правилом остановки. Итерация: 1. Экспресс в зависимости от т путем установки                                                : j=1, 2, . . . , n, а затем Подставляя эти выражения в f(x). 2. Используйте одномерных процедура поиска (или исчисление), чтобы найти t = t*, которая максимизирует над : t ≥ 0. 3. Сброс . Затем перейдите на правило остановки. Правила остановки: Оценка при х = х'. Убедитесь в том,                          для всех j = 1, 2,. . . , n. Если да, то остановится с текущими х по желанию приближении оптимального решения х*. В противном случае выполните другой итерации.

Пример: с двумя переменными проблема: Пример: с двумя переменными проблема: Развернуть . Таким образом,   F (X) вогнута. Градиент процедуру поиска: X = (0, 0) выбран в качестве начального решения суда. Соответствующие частными производными = 0 и 2, градиент в этой точке:  начать первой итерации, комплект: x1 = 0 + T (0) = 0,                                                           x2 = 0 + T (2) = 2т, а затем подставить эти выражения в F (X), чтобы получить   потому что   и   следует, что , t* = 1/4,

 Сброс х '= (0, 0) + 1/4 (0, 2) = 0, 1/2.  Сброс х '= (0, 0) + 1/4 (0, 2) = 0, 1/2. Для этого нового решения суда, градиент                                        Для второй итерации, установите х = (0, 1/2) + т (1, 0) = (т, 1/2), так                                                                              потому что   и   затем t = 1/2, так Сброс Организация таблицы, которая суммирует 2 предшествующих итераций. На каждой итерации, 2-й столбец показывает текущее решение суда, и правая колонка показывает возможного нового решения суда, которое затем осуществляется вниз в 2 колонки для следующей итерации. Четвёртое Заголовки столбцов дает выражения для xj в терминах т, которые должны быть заменены в f(x) с получением указанного в пятой колонке. Продолжая таким образом, последующие решения процесс будет (1/2, 3/4), (3/4, 3/4), (3/4, 7/8), (7/8, 7/8), ... , Как на фиг. Потому что эти точки сходятся к х* = (1, 1), это решение является оптимальным решением, так как подтверждается тем, что

Поскольку этот сходящейся последовательности проб решения никогда не достигает своего предела, процедура останавливается где-то (в зависимости от) немного ниже (1, 1) в качестве окончательного приближения x*. Как видно из рис. предлагает, градиент зигзаги процедуру поиска оптимального решения, а не двигаться по прямой линии. Некоторые модификации разработанной методики, ускоряющих движение к оптимальному решению, приняв этот зигзаг поведения во внимание. Если f(x) не были вогнутая функция, процедура поиска градиент все равно бы сходятся к локальному максимуму . Только смена описания процедуры в этом случае является то, что t* Теперь будет соответствовать первый локальный максимум как t увеличивается от 0. Если целью было свести к минимуму f(x) вместо этого, одно изменение в процедуре будет двигаться в противоположном направлении градиента на каждой итерации. Правило для получения следующей точке будет Reset . Только другие изменения в том, что t* теперь будет неотрицательным значением t, что сводит к минимуму, то есть . Поскольку этот сходящейся последовательности проб решения никогда не достигает своего предела, процедура останавливается где-то (в зависимости от) немного ниже (1, 1) в качестве окончательного приближения x*. Как видно из рис. предлагает, градиент зигзаги процедуру поиска оптимального решения, а не двигаться по прямой линии. Некоторые модификации разработанной методики, ускоряющих движение к оптимальному решению, приняв этот зигзаг поведения во внимание. Если f(x) не были вогнутая функция, процедура поиска градиент все равно бы сходятся к локальному максимуму . Только смена описания процедуры в этом случае является то, что t* Теперь будет соответствовать первый локальный максимум как t увеличивается от 0. Если целью было свести к минимуму f(x) вместо этого, одно изменение в процедуре будет двигаться в противоположном направлении градиента на каждой итерации. Правило для получения следующей точке будет Reset . Только другие изменения в том, что t* теперь будет неотрицательным значением t, что сводит к минимуму, то есть .

Иллюстрация процедуры поиска, когда градиент Иллюстрация процедуры поиска, когда градиент

Каруша-Куна-Таккера (ККТ) условия Условной оптимизации Как распознать оптимальное решение для задачи нелинейного программирования (с дифференцируемых функций). Каковы необходимые и достаточные условия, такие решения должны выполняться? Эти условия для безусловной оптимизации, сведенные в 1-ых двух строках таблицы. Эти условия для небольшого расширения оптимизации без ограничений, где только ограничения неотрицательности ограничения, показанный на 3-й строке таблицы. Как указано в последнем ряду, условия общем случае Karush-Куна-Таккера (или ККТ условиях). Теорема. Предположим, что f(x), g1(х), g2(х),. . . , gm(х) дифференцируемы функции, удовлетворяющие некоторым условиям регулярности.

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

Тогда х* = (x1*, x2*, ..., хn*) Тогда х* = (x1*, x2*, ..., хn*) может быть оптимальным решением для задачи нелинейного программирования, только если существуют т номерами U1, U2,. . . , Гм, что все следующие условия удовлетворены ККТ: Оба условия 2 и 4 требует, чтобы произведение двух величин = 0  каждого из этих условий действительно говорит, что по крайней мере один из двух величин должна быть равна нулю. Условие 4 могут быть объединены с условием 3 выразить их в другую эквивалентную форму в качестве                                                           i =  1, 2, . . . , m.

Условие 2 могут быть объединены с условием 1 в качестве Условие 2 могут быть объединены с условием 1 в качестве При m = 0 (без функциональных ограничений), это суммирование выпадает и сложенном состоянии (1, 2) сводится к состоянии приведены в таблице 3-й ряд. Для m > 0, каждый член в суммирование изменяет m = 0 условие включения эффекта соответствующие функциональные ограничения. В условиях 1, 2, 4 и 6, интерфейса, соответствующих двойственных переменных линейного программирования, и они имеют сопоставимые экономическую интерпретацию. Ui возникла в математический вывод как множителей Лагранжа. Условия 3 и 5 Убедитесь, что решение целесообразности. Другие условия устранить большинство возможных решений качестве возможных кандидатов на оптимальное решение. Удовлетворение этих условий не гарантирует, что решение является оптимальным. Правой колонке таблицы некоторых дополнительных предположениях выпуклости Для получения этой гарантии как обобщение теоремы. Следствие. f(x) является вогнутой функцией и g1(х), g2(х),…, gm (х) являются выпуклыми функциями (выпуклого программирования), где все эти функции удовлетворяют условиям регулярности. Тогда х* = (x1*, x2*, ..., хn*) является оптимальным решением, если и только если все условия теоремы выполнены.

Пример: с двумя переменными задачи нелинейного программирования: Пример: с двумя переменными задачи нелинейного программирования: Развернуть, подлежат 2x1 + x2 ≤ 3 И x1 ≥ 0, x2 ≥ 0, где LN является натуральный логарифм.  m = 1 (один функциональной связи) и g1(х) = 2x1 + x2, поэтому g1(х) является выпуклым. Кроме того, он может быть легко проверено, что f(x) вогнута. Следствие относится, так что любое решение, удовлетворяющее условиям ККТ будет оптимальным решением. Применение формулы, приведенные в теореме дает следующие условия ККТ для этого примера:

Шаги в решении ККТ условия для этого примера: Шаги в решении ККТ условия для этого примера: 1. u1 ≥ 1, из условия 1 (j = 2). x1 ≥ 0, из условия 5. 2. Таким образом, <0. 3. Поэтому x1 = 0, из условия 2 (j = 1). 4. u1 ≠ 0 следует, что 2x1 + x2 - 3 = 0, из условия 4. 5. Шаги 3 и 4 следует, что x2 = 3. 6. x2 ≠ 0 следует, что u1 = 1, из условия 2 (j = 2). 7. Условия не нарушены x1 = 0, x2 = 3, u1 = 1.  такое число u1 = 1 такие, что x1 = 0, x2 = 3, u1 = 1 удовлетворяют всем условиям  x* = (0, 3) является оптимальным решением этой проблемы. Прогресс решить ККТ условия отличаются от одной проблемы к другой. Когда логика не очевидна, полезно рассмотреть отдельно различные случаи, когда каждая XJ и пользовательский интерфейс указанные быть либо = 0 или> 0, а затем не пытается каждом случае, пока один приводит к решению. В этом примере имеются восемь таких случаях соответствующий 8 комбинаций x1 = 0 в сравнении с x1> 0, x2 = 0 против x2> 0, u1 = 0, в зависимости от u1> 0. Каждый случай приводит к более простым заявлением и анализ условий.

Следующий случай: x1 = 0, x2 = 0, u1 = 0  ККТ Условия: Следующий случай: x1 = 0, x2 = 0, u1 = 0  ККТ Условия:                                                            Противоречие. 3. 0 + 0 ≤ 3. (Все другие условия являются избыточными.) Другие три случая, когда u1 = 0 также дать немедленную противоречий таким же образом, так что ни одно решение не доступно. Случай x1 = 0, x2> 0, u1 = 0 противоречит условиям 1 (= 1), 1 (у = 2) и 2 (у = 2). Случай x1> 0, x2 = 0, u1 = 0 противоречит условиям 1 (= 1), 2 (= 1) и 1 (у = 2). Случай x1> 0, x2> 0, u1 = 0 противоречит условиям 1 (= 1), 2 (= 1), 1 (у = 2) и 2 (у = 2). Случай x1> 0, x2> 0, u1> 0 позволяет удалять эти ненулевые множители из условий 2 (= 1), 2 (у = 2) и 4, который затем позволяет удалить условия 1 (= 1), 1 (у = 2) и 3 как излишним, как представлено следующее. ККТ условий случая x1> 0, x2> 0, u1> 0 1 (у = 1). 2 (у = 2). 1 - u1 = 0.

4. 2x1 + x2 - 3 = 0. (Все другие условия являются избыточными.) 4. 2x1 + x2 - 3 = 0. (Все другие условия являются избыточными.) Таким образом, U1 1, поэтому x1 1 2, что противоречит x1 0. Теперь предположим, что дело x1 0, x2 0, u1 0 пробуется следующий. ККТ условий случая x1 = 0, x2> 0, u1> 0 1 (у = 1). 2 (у = 2). 1 - u1 = 0. 5. 0 + x2 - 3 = 0. (Все другие условия являются избыточными.) Поэтому x1 = 0, x2 = 3, u1 = 1. Найдя решение, мы знаем, что никаких дополнительных случаев не нужно считаться. Для более сложных задач, невозможно, для получения оптимального решения непосредственно от ККТ условиях. Тем не менее, эти условия еще дать ценные подсказки относительно личности оптимального решения, и они также позволяют проверить, является ли предлагаемое решение может быть оптимальным. Там также много ценных косвенного применения ККТ условиях.

Одно из этих приложений возникает двойственность в теории, развитой для нелинейного программирования параллельных теории двойственности в линейном программировании. Для любого ограниченного задачи максимизации (прямая задача), ККТ условия могут быть использованы для определения тесно связана двойственная задача, которая задаче условной минимизации. Переменные в двойственной задачи состоят как из интерфейса множителей Лагранжа (I = 1,2, ..., т) и первичных переменных XJ (J = 1,2, ..., N). Частный случай, когда исходная задача является задачей линейного программирования, переменные XJ выпадают из двойственной задачи, и она становится знакомым двойственной задачи линейного программирования (UI переменных здесь соответствуют Yi переменных). Когда прямая задача выпуклого программирования является проблемой, можно установить связь между основной задачи и двойственной задачи аналогичны линейного программирования. Например, сильным свойством двойственности, в котором говорится, что оптимальная значений целевой функции двух задач совпадают, имеет место и здесь. Значения щ переменных в оптимальное решение для двойной проблема может снова быть интерпретированы как тень цены, то есть, они дают скорость, с которой оптимальное значение целевой функции для прямой задачи может быть увеличена (слегка) увеличение правой стороне соответствующего ограничения. Теория двойственности нелинейного программирования является сложная тема. Одно из этих приложений возникает двойственность в теории, развитой для нелинейного программирования параллельных теории двойственности в линейном программировании. Для любого ограниченного задачи максимизации (прямая задача), ККТ условия могут быть использованы для определения тесно связана двойственная задача, которая задаче условной минимизации. Переменные в двойственной задачи состоят как из интерфейса множителей Лагранжа (I = 1,2, ..., т) и первичных переменных XJ (J = 1,2, ..., N). Частный случай, когда исходная задача является задачей линейного программирования, переменные XJ выпадают из двойственной задачи, и она становится знакомым двойственной задачи линейного программирования (UI переменных здесь соответствуют Yi переменных). Когда прямая задача выпуклого программирования является проблемой, можно установить связь между основной задачи и двойственной задачи аналогичны линейного программирования. Например, сильным свойством двойственности, в котором говорится, что оптимальная значений целевой функции двух задач совпадают, имеет место и здесь. Значения щ переменных в оптимальное решение для двойной проблема может снова быть интерпретированы как тень цены, то есть, они дают скорость, с которой оптимальное значение целевой функции для прямой задачи может быть увеличена (слегка) увеличение правой стороне соответствующего ограничения. Теория двойственности нелинейного программирования является сложная тема.