Метод линеаризации для задач условной оптимизации. Алгоритм Франка-Вульфа | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 7 марта, печатный экземпляр отправим 11 марта.

Опубликовать статью в журнале

Автор:

Рубрика: Математика

Опубликовано в Молодой учёный №3 (293) январь 2020 г.

Дата публикации: 19.01.2020

Статья просмотрена: 36 раз

Библиографическое описание:

Лобанов В. С. Метод линеаризации для задач условной оптимизации. Алгоритм Франка-Вульфа // Молодой ученый. — 2020. — №3. — С. 8-12. — URL https://moluch.ru/archive/293/66414/ (дата обращения: 24.02.2020).



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

Метод основан на разложении нелинейной функции общего вида в ряд Тейлора до членов первого порядка в окрестности некоторой точки

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

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

Непосредственное использование последовательности задач ЛП

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

Случай линейных ограничений

Задача НЛП с линейными ограничениями имеет следующий вид:

При ограничениях

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

Ясно, что задача вида:

При ограничениях

Представляет собой задачу ЛП и поэтому имеет оптимальное решение в допустимой угловой точке (при условии, что допустимая область ограничена). Весьма важен вопрос о соотношении между решением линеаризованной задачи и решением исходной задачи . Заметим, что при решении линеаризованной задачи получается единственное решение (если не принимать во внимание случай не единственности оптимума в задаче ЛП), тогда как исходная задача может иметь несколько локальных экстремумов. Выбор точки локального экстремума в близи зависит от выбора начальной точки линеаризации. Следовательно, при невыпуклой целевой функции нельзя быть уверенным в том, что найдено приближение к глобальному экстремуму. Однако даже в случае выпуклой функции нет гарантии, что точка хорошо «приближает» . Истинное решение может лежать внутри допустимой области, а точка должна быть угловой. Из этого следует, что и в случае выпуклой функции для получения хорошего приближенного решения необходима дополнительная корректировка .

Заметим, что в силу допустимости точек , имеет место неравенство

Следовательно, если воспользоваться формулой для , то получается следующее неравенство:

или

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

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

В результате решения задачи

Находится допустимая точка , такая, что

Поскольку величина вообще не равна нулю, полученная точка может служить точкой линеаризации для построения следующей аппроксимации. Решение последовательности задач ЛП и одномерный поиск продолжаются до тех пор, пока последовательные оптимумы , получаемые при помощи одномерного поиска, не станут достаточно близкими (т. е. расстояние между ними не станет меньше заранее выбранной малой величины).

Далее рассмотрим соответствующий алгоритм Франка-Вульфа.

Алгоритм Франка-Вульфа

Рассмотрим итерационный процесс:

Существует целевая функция , которую нужно максимизировать (минимизировать), с системой ограничений заданных линейно.

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

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

Составим новую линейную целевую функцию, которую нужно максимизировать (минимизировать).

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

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

Новое приближение находится следующим образом:

Где шаг, принадлежащий промежутку , который можно найти из уравнения

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

Условие выхода из итерационного процесса: или

, где

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

Рис. 1

Изображенный на рис. 1 трехступенчатый компрессор предназначен для сжатия газа, поступающего под давлением 1 атм. в количестве моль/ч, до давления 64 атм. Предполагается, что сжатие двустороннее и адиабатическое; после каждой его стадии газ охлаждается до начальной температуры Требуется выбрать значения давления на промежуточных стадиях процесса, потребление энергии.

Решение: Для двустороннего адиабатического сжатия с охлаждением до начальной температуры работа газа задается формулой

Где коэффициент Пуассона, универсальная газовая постоянная.

При трехступенчатом сжатии полная работа газа определяется формулой

Где , выходное давление на первой ступени, выходное давление на второй ступени.

Если для рассматриваемого газа , то при фиксированных и оптимальные давления и можно получить, решая следующую задачу:

(при этом требуется, чтобы выбранные давления монотонно увеличивались от входа к выходу).

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

Анализируя метод можно заметить, что при выборе шага мы решаем уравнение вида

Оно может быть не обязательно дифференцируемо. Могут существовать разрывы 1-го и 2-го рода. Если оптимальное решение итерационного процесса не удовлетворяет условия заказчика, то следует исследовать данное уравнение на -ом шаге на гладкость и непрерывность, тем самым повысить точность алгоритма Франка-Вульфа.

Рассмотрим график целевой функции на промежутке с учётом ограничений

Функция монотонно возрастающая и имеет точки перегиба. Это объясняет трудность программного вычисления «самого» оптимального случая.

Литература:

  1. Пшеничный Б. Н., Данилин Ю. М. Численные методы в экстремальных задачах. М.: Наука, 1975. — 320с.
  2. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432с.
  3. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975. 536с.
Основные термины (генерируются автоматически): допустимая область, целевая функция, одномерный поиск, задача, ограничение, исходная задача, итерационный процесс, линейное программирование, выпуклая функция, выходное давление.


Похожие статьи

Задачи линейного программирования в школьном курсе...

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

Итеративный алгоритм для задачи о назначении

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

Некоторые прикладные задачи целочисленного...

Областью допустимых решений исходной задачи без учета целочисленности является многоугольник ОАВСD (рис.2). Максимальное значение целевая функция

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

Задача о назначении с дополнительными работами...

В противном случае начинается итерационный процесс решения оптимизационных задач с двумя ограничениями – по одному ограничению из (1) и (2) и с целевой функцией, в которой из (3) присутствуют только переменные, которые имеются в выбранных ограничениях.

Декомпозиционный метод решения линейной трехиндексной...

В итерационном процессе решаются задачи с тремя ограничениями и одной связывающей переменной.

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

Планирование производственного процесса при нарушении...

Основные термины (генерируются автоматически): целевая функция, линейное

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

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

Оптимизация по условиям Куна — Таккера | Статья в журнале...

Линейная форма — также выпуклая функция. Поэтому целевая функция будет выпуклой. В этом случае необходимые условия Куна-Таккера являются

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

Применение метода линейного программирования для решения...

Задача линейного программирования заключается в изучении способов нахождения наибольшего или наименьшего значений некоторой линейной функции при наличии линейных ограничений [1, 2, 3]. Функция, наибольшее или наименьшее значение которой необходимо...

Решение интервальной задачи дробно-линейного...

. Задача (9)-(11) является задачей линейного программирования. Следовательно, ее решение можно найти соответствующими известными

В результате получаем максимальное значение целевой функции задачи 2 верхней граничной задачи исходной задачи (3), (4). Это значение...

Поиск решения как средство решения задач оптимизации...

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

Для решения задачи оптимизации необходимо на рабочем листе Excel создать таблицу исходных

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

Похожие статьи

Задачи линейного программирования в школьном курсе...

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

Итеративный алгоритм для задачи о назначении

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

Некоторые прикладные задачи целочисленного...

Областью допустимых решений исходной задачи без учета целочисленности является многоугольник ОАВСD (рис.2). Максимальное значение целевая функция

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

Задача о назначении с дополнительными работами...

В противном случае начинается итерационный процесс решения оптимизационных задач с двумя ограничениями – по одному ограничению из (1) и (2) и с целевой функцией, в которой из (3) присутствуют только переменные, которые имеются в выбранных ограничениях.

Декомпозиционный метод решения линейной трехиндексной...

В итерационном процессе решаются задачи с тремя ограничениями и одной связывающей переменной.

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

Планирование производственного процесса при нарушении...

Основные термины (генерируются автоматически): целевая функция, линейное

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

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

Оптимизация по условиям Куна — Таккера | Статья в журнале...

Линейная форма — также выпуклая функция. Поэтому целевая функция будет выпуклой. В этом случае необходимые условия Куна-Таккера являются

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

Применение метода линейного программирования для решения...

Задача линейного программирования заключается в изучении способов нахождения наибольшего или наименьшего значений некоторой линейной функции при наличии линейных ограничений [1, 2, 3]. Функция, наибольшее или наименьшее значение которой необходимо...

Решение интервальной задачи дробно-линейного...

. Задача (9)-(11) является задачей линейного программирования. Следовательно, ее решение можно найти соответствующими известными

В результате получаем максимальное значение целевой функции задачи 2 верхней граничной задачи исходной задачи (3), (4). Это значение...

Поиск решения как средство решения задач оптимизации...

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

Для решения задачи оптимизации необходимо на рабочем листе Excel создать таблицу исходных

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

Задать вопрос