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

Информация в данной статье относится к релизам программы MATLAB ранее 2016 года, и поэтому может содержать устаревшую информацию в связи с изменением функционала инструментов. С более актуальной информацией вы можете ознакомиться в разделе документация MATLAB на русском языке.

Автор материала - А.Г.Трифонов.

Содержание

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

2. Методы безусловной оптимизации

2.1. Численные методы безусловной оптимизации нулевого порядка

Основные определения

Классификация методов

Общая характеристика методов нулевого порядка

Метод прямого поиска (метод Хука-Дживса)

Метод деформируемого многогранника (метод Нелдера—Мида)

Метод вращающихся координат (метод Розенброка)

Метод параллельных касательных (метод Пауэлла)

2.2. Численные методы безусловной оптимизации первого порядка

Минимизация функций  многих переменных. Основные положения

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

Метод сопряженных градиентов

2.3. Численные методы безусловной оптимизации второго порядка

Особенности методов второго порядка

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

3. Методы условной оптимизации

3.1. Линейное программирование

3.2. Транспортная задача линейного программирования

Постановка задачи

Венгерский метод

Метод потенциалов

3.3. Прямые методы условной оптимизации

Основные определения

Метод проекции градиента

Комплексный метод Бокса

3.4. Методы штрафных функций

Основные определения

Методы внутренних штрафных функций

Методы внешних штрафных функций

Комбинированные алгоритмы штрафных функций

4. Динамическое программирование

Список литературы

 

Наверх

 

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

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

В настоящее время для решения оптимальных задач применяют в основном следующие методы: 

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

В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Названием “методы нелинейного программирования” объединяется большая группа численных методов, многие из которых приспособлены для решения оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся вычислительной машины и т.д. Ряд методов нелинейного программирования практически постоянно используется в сочетании с другими методами оптимизации, как, например, метод сканирования в динамическом программировании. Кроме того, эти методы служат основой построения систем автоматической оптимизации - оптимизаторов, непосредственно применяющихся для управления производственными процессами.

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

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

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

В таблице 1.1 [2] дана характеристика областей применения различных методов оптимизации, при этом за основу положена сравнительная оценка эффективности использования каждого метода для решения различных типов оптимальных задач. Классификация задач проведена по следующим признакам: 

• вид математического описания процесса; 
• тип ограничений на переменные процесса
• число переменных. 

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

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

ТАБЛИЦА 1.1. Области применения методов оптимизации
Вид описания процесса		Конечные уравнения						Дифференциальные уравнения
Тип ограничений на переменные		Нет		Равенства		Неравенства		Нет		Равенства		Неравенства
Число переменных п		?3	>3	?3	>3	?3	>3	?3	>3	?3	>3	?3	>3
ТТип метода	Методы классического анализа	1	2	4	4	4	4	3	4	4	4	4	4
	Множители Лагранжа	-	-	1	2	-	-	-	-	2	3	-	-
	Вариационное исчисление	-	-	-	-	-	-	2	3	2; 7	3; 7	-	-
	Динамическое программирование	1; 5	3; 5	1;5;7	3; 5; 7	1; 5	3; 5	2	3	3	3	3	3
	Принцип максимума	2; 5	1; 5	2; 5	2; 5	2; 5	2; 5	1	1	2	2	2	2
	Линейное программирование	-	-	-	2; 6	2; 6	1; 6	-	-	-	-	-	-
	Методы нелинейного программирования	2	1	2	.1	2	1	4	4	4	4	4	4
	Геометрическое программирование	2; 8	2; 8	-	-	2; 8	2; 8	-	-	-	-	-	-
Примечания:  1. Эффективное применение метода.  2. Используется. 3. Возможно применение.  4. Используется как вспомогательный метод. 5. Многостадийные процессы (размерность указывается для отдельной стадии).  6. Задачи с линейными критериями оптимальности и линейными ограничениями. 7. Используются множители Лагранжа.  8. Задачи с критериями и ограничениями в форме позиномов.

 

Наверх

 

2. Методы безусловной оптимизации

2.1. Численные методы безусловной оптимизации нулевого порядка

Основные определения

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

Вектор-строка получается путем применения операции транспонирования:

.

Оптимизируемую функцию f(x) называют целевой функцией или критерием оптимальности.

В дальнейшем без ограничения общности будем говорить о поиске минимального значения функции f(x) записывать эту задачу следующим образом:

f(x ) --> min.

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

Отметим, что задачу максимизации f(x) можно заменить эквивалентной ей задачей минимизации или наоборот. Рассмотрим это на примере функции одной переменной (Рис. 2.1). Если х* - точка минимума функции y = f(x), то для функции y =- f(x) она является точкой максимума, так как графики функций f(x) и - f(x), симметричны относительно оси абсцисс. Итак, минимум функции f(x) и максимум функции - f(x) достигаются при одном и том же значении переменной. Минимальное же значение функции f(x), равно максимальному значению функции - f(x), взятому с противоположным знаком, т.е. min f(x) =-max(f(x)).

Рассуждая аналогично, этот вывод нетрудно распространить на случай функции многих переменных. Если требуется заменить задачу минимизации функции f(x₁, …, x_n) задачей максимизации, то достаточно вместо отыскания минимума этой функции найти максимум функции f(x₁, …, x_n). Экстремальные значения этих функций достигаются при одних и тех же значениях переменных. Минимальное значение функции f(x₁, …, x_n) равно максимальному значению функции - f(x₁, …, x_n), взятому с обратным знаком, т.е. min f(x₁, …, x_n) =max f(x₁, …, x_n). Отмеченный факт позволяет в дальнейшем говорить только о задаче минимизации.

Рис. 2.1. Экстремум

В реальных условиях на переменные x_j, i=1, …. n, и некоторые функции g_i (х), h_i(х), характеризующие качественные свойства объекта, системы, процесса, могут быть наложены ограничения (условия) вида:

g_i (х) = 0, i=1, …. n,

h_i (х) <= 0, i=1, …. n,

a <= x <= b,

где

 ;

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

Каждая точка х в n-мерном пространстве переменных х₁, …, х_n, в которой выполняются ограничения, называется допустимой точкой задачи. Множество всех допустимых точек называют допустимой областью G. Решением задачи (оптимальной точкой) называют допустимую точку х*, в которой целевая функция f(х) достигает своего минимального значения.

Точка х* определяет глобальный минимум функции одной переменной f(x), заданной на числовой прямой Х , если x ^* X и f(x^*) < f(x) для всех x^*  X (Рис. 2.2, а). Точка х* называется точкой строгого глобального минимума, если это неравенство выполняется как строгое. Если же в выражении f(х*) <= f(x) равенство возможно при х, не равных  х*, то реализуется нестрогий минимум, а под решением в этом случае понимают множество х* = [x^*  X: f(x) = f(x^*)] (Рис. 2.2, б).

Рис. 2.2. Глобальный минимум. а - строгий, б - нестрогий

Точка х*  Х определяет локальный минимум функции f(x) на множестве Х , если при некотором достаточно малом e > 0 для всех х, не равных  х*, x  X, удовлетворяющих условию ¦х - х*¦<= e, выполняется неравенство f(х*) < f(х). Если неравенство строгое, то х* является точкой строгого локального минимума. Все определения для максимума функции получаются заменой знаков предыдущих неравенств на обратные. На Рис. 2.3 показаны экстремумы функции одной переменной f(х) на отрезке [a, b] . Здесь х₁, х₃, х₆ - точки локального максимума, а х₂, х₄ - локального минимума. В точке х₆ реализуется глобальный максимум, а в точке х₂ - глобальный минимум.

Рис. 2.3. Экстремумы функции

 

 

Наверх

 

Классификация методов

Возможны два подхода к решению задачи отыскания минимума функции многих переменных f(x) = f(x₁, ..., х_n) при отсутствии ограничений на диапазон изменения неизвестных. Первый подход лежит в основе косвенных методов оптимизации и сводит решение задачи оптимизации к решению системы нелинейных уравнений, являющихся следствием условий экстремума функции многих переменных. Как известно, эти условия определяют, что в точке экстремума х* все первые производные функции по независимым переменным равны нулю:

, i=1, …, n.

Эти условия образуют систему п нелинейных уравнений, среди решений которой находятся точки минимума. Вектор f’(х), составленный из первых производных функции по каждой переменной, т.е.

,

называют градиентом скалярной функции f(x). Как видно, в точке минимума градиент равен нулю.

Решение систем нелинейных уравнений - задача весьма сложная и трудоемкая. Вследствие этого на практике используют второй подход к минимизации функций, составляющий основу прямых методов. Суть их состоит в построении последовательности векторов х [0], х [1], …, х [n], таких, что f(х[0])> f(х [1])> f(х [n])>… В качестве начальной точки x[0] может быть выбрана произвольная точка, однако стремятся использовать всю имеющуюся информацию о поведении функции f(x), чтобы точка x[0] располагалась как можно ближе к точке минимума. Переход (итерация) от точки х [k] к точке х [k+1], k = 0, 1, 2, ..., состоит из двух этапов: 

1. 1. выбор направления движения из точки х [k];
   2. определение шага вдоль этого направления. 

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

Математически методы спуска описываются соотношением

x[k+1] = x[k] + a_kp[k], k = 0, 1, 2, ...,

где p[k] - вектор, определяющий направление спуска; a_k - длина шага. В координатной форме:

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

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

или функции

.

Здесь k - номер итерации; e, g - заданные величины точности решения задачи.

Методы поиска точки минимума называются детерминированными, если оба элемента перехода от х[k] к x[k+l] (направление движения и величина шага) выбираются однозначно по доступной в точке х [k] информации. Если же при переходе используется какой-либо случайный механизм, то алгоритм поиска называется случайным поиском минимума.

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

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

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

 

 

Наверх

 

Общая характеристика методов нулевого порядка

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

 

 

Наверх

 

Метод прямого поиска (метод Хука-Дживса)

Суть этого метода состоит в следующем. Задаются некоторой начальной точкой х[0]. Изменяя компоненты вектора х[0], обследуют окрестность данной точки, в результате чего находят направление, в котором происходит уменьшение минимизируемой функции f(x). В выбранном направлении осуществляют спуск до тех пор, пока значение функции уменьшается. После того как в данном направлении не удается найти точку с меньшим значением функции, уменьшают величину шага спуска. Если последовательные дробления шага не приводят к уменьшению функции, от выбранного направления спуска отказываются и осуществляют новое обследование окрестности и т. д.

Алгоритм метода прямого поиска состоит в следующем.

1. Задаются значениями координат х_i[0] , i = 1, ..., п , начальной точки х[0], вектором изменения координат D х в процессе обследования окрестности, наименьшим допустимым значением е компонентов D х.

2. Полагают, что х[0] является базисной точкой х^б, и вычисляют значение f(x^б).

3. Циклически изменяют каждую координату х^б_i, i = 1, ..., п , базисной точки х^б на величину ?х_i, i = 1, ..., п , т. е. х_i[k] = х^б +D х; х_i[k] = х^б_i - ?х_i. При этом вычисляют значения f(x[k]) и сравнивают их со значением f(x^б). Если f(x[k]) < f(x^б), то соответствующая координата х_i, i = 1, ..., п , приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней п-йкоординаты f(x[k]) < f(x^б), то переходят к п, 4. В противном случае - к п. 7.

4. Полагают, что х[k] является новой базисной точкой х^б , и вычисляют значение f(x^б).

5. Осуществляют спуск из точки х[k] > х_i[k+1] = 2х_i[k] - x^б , i = 1, ..., n , где x^б - координаты предыдущей базисной точки. Вычисляют значение f(x[k+1]).

6. Как и в п. 3, циклически изменяют каждую координату точки х[k+1], осуществляя сравнение соответствующих значений функции f(х) со значением f (х[k+1]), полученным в п. 5. После изменения последней координаты сравнивают соответствующее значение функции f(x[k]) со значением f(x^б), полученным в п. 4. Если f(x[k]) < f(x^б), то переходят к п. 4, в противном случае - к п. 3. При этом в качестве базисной используют последнюю из полученных базисных точек.

7. Сравнивают значения D х и е. Если D х < е, то вычисления прекращаются. В противном случае уменьшают значения Dх и переходят к п. 3.

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

Недостаток метода прямого поиска состоит в том, что в случае сильно вытянутых, изогнутых или обладающих острыми углами линий уровня целевой функции он может оказаться неспособным обеспечить продвижение к точке минимума. Действительно, в случаях, изображенных на Рис. 2.4, а и б, каким бы малым ни брать шаг в направлении х₁ или x₂ из точки х’ нельзя получить уменьшения значения целевой функции.

Рис. 2.4. Прямой поиск: невозможность продвижения к минимуму: а – С₁ > C₂ > C₃; б - С₁ > C₂

Напомним, что поверхностью уровня (на плоскости - линией уровня) является поверхность, получаемая приравниванием выражения функции f(х) некоторой постоянной величине С, т. е. f(х) = С . Во всех точках этой поверхности функция имеет одно и то же значение С. Давая величине С различные значения С₁, ..., С_n, получают ряд поверхностей, геометрически иллюстрирующих характер функции.

 

Наверх

 

Метод деформируемого многогранника (метод Нелдера—Мида)

Данный метод состоит в том, что для минимизации функции п переменных f(х) в n-мерном пространстве строится многогранник, содержащий (п + 1) вершину. Очевидно, что каждая вершина соответствует некоторому вектору х.Вычисляются значения целевой функции f(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершина х[h]. Через эту вершину и центр тяжести остальных вершин проводится проецирующая прямая, на которой находится точка х[q] с меньшим значением целевой функции, чем в вершине х[h] (Рис. 2.5). Затем исключается вершина х[h]. Из оставшихся вершин и точки x[q] строится новый многогранник, с которым повторяется описанная процедура. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода.

Рис. 2.5. Геометрическая интерпретация метода деформируемого многогранника

Введем следующие обозначения:

x[i, k] =(x₁[i, k], …, x_j[i, k], …, x_n[i, k])^T

где i = 1, ..., п + 1; k = 0, 1, ..., - i-я вершина многогранника на k-м этапе поиска; х[h, k] — вершина, в которой значение целевой функции максимально, т. е. f(х[h, k] = max{f(x[1, k]), …, f(x[n+1, k])}; х[l, k] - вершина, в которой значение целевой функции минимально, т. е. f(х[l, k]) =min {f(x[1, k]), …, f(x [n+1, k])}; х [п+2, k]- центр тяжести всех вершин, за исключением х[h, k]. Координаты центра тяжести вычисляются по формуле

Алгоритм метода деформируемого многогранника состоит в следующем.

1. Осуществляют проецирование точки х[h, k] через центр тяжести:

x[n+3, k] =x[n+2, k] + a(x[n+2, k] - x[h, k]) ,

где а > 0 - некоторая константа. Обычно а = 1.

2. Выполняют операцию растяжения вектора х[n+3, k] - х[n+2, k]:

x[n+4, k] =x[n+2, k] + g(x[n+3, k] - x[n+2, k]),

где g > 1 - коэффициент растяжения. Наиболее удовлетворительные результаты получают при 2,8 <= g <= 3.

Если f(x[n+4, k]) < f(х[l, k]), то х[h , k] заменяют на x[n+4, k] и продолжают вычисления с п. 1 при k = k + 1. В противном случае х[h, k] заменяют на х[n+3, k] и переходят к п. 1 при k = k + 1.

3. Если f(x[n+3, k]) > f(х[i, k]) для всех i, не равных  h, то сжимают вектор x[h, k] - x[n+2, k]:

x[n+5, k] =x[n+2, k] + b (х[h, k] – x[n+2, k] ), где b > 0 - коэффициент сжатия. Наиболее хорошие результаты получают при 0,4 <= b <= 0,6. 

Затем точку х[h, k] заменяют на х[n+5, k] и переходят к п. 1 при k = k+ 1.

4. Если f(x[n+3, k])> f(x[h, k]), то все векторы х[i, k] - х[l, k] . i= 1,..., п + 1, уменьшают в два раза:

x[i, k] = x[l, k] + 0,5(x[i, k] - x[l, k]) .

Затем переходят к п. 1 при k= k + 1.

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

,

где e = (е₁ ,..., е_n) - заданный вектор.

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

 

 

Наверх

 

Метод вращающихся координат (метод Розенброка)

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

Рис. 2.6. Геометрическая интерпретация метода Розенброка

Из начальной точки х[0] осуществляют спуск в точку х[1] по направлениям, параллельным координатным осям. На следующей итерации одна из осей должна проходить в направлении y₁ = х[1] - х[0], а другая - в направлении, перпендикулярном к у₁ . Спуск вдоль этих осей приводит в точку х[2] , что дает возможность построить новый вектор х[2] - х[1] и на его базе новую систему направлений поиска. В общем случае данный метод эффективен при минимизации овражных функций, так как результирующее направление поиска стремится расположиться вдоль оси оврага.

Алгоритм метода вращающихся координат состоит в следующем.

1. Обозначают через р₁[k], ..., р_n[k] направления координатных осей в некоторой точке х[k] (на к-й итерации). Выполняют пробный шаг h₁ вдоль оси р₁[k], т. е.

x[kl] = x[k] + h₁p₁[k].

Если при этом f(x[kl]) < f(x[k]), то шаг h умножают на величину b > 1;

Если f(x[kl]) > f(x[k]), - то на величину (-b), 0 < |b| < 1;

x[kl] = x[k] + b h₁p₁[k].

Полагая ?h₁ = а₁ .получают

x[kl] = x[k] + a₁p₁[k].

2. Из точки х[k1] выполняют шаг h₂ вдоль оси р₂[k]:

x[k2] = x[k] + a₁p₁[k] + h₂p₂[k].

Повторяют операцию п. 1, т. е.

x[k2] =x[k] + а₁р₁[k] +а₂p₂[k].

Эту процедуру выполняют для всех остальных координатных осей. На последнем шаге получают точку

х[kn] = х[k+1] = х[k] + .

3. Выбирают новые оси координат p₁[k+1], …, р_n[k+1]. В качестве первой оси принимается вектор

р₁[k+1] = x[k+l] - x[k].

Остальные оси строят ортогональными к первой оси с помощью процедуры ортогонализации Грама - Шмидта. Повторяют вычисления с п. 1 до удовлетворения условий сходимости.

Коэффициенты b подбираются эмпирически. Хорошие результаты дают значения b = - 0,5 при неудачных пробах (f(x[ki])> f(x[k])) и b = 3 при удачных пробах (f(x[ki]) < f(x[k])).

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

 

 

Наверх

 

Метод параллельных касательных (метод Пауэлла)

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

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

Рис. 2.7. Геометрическая интерпретация метода Пауэлла

Суть метода такова. Выбирается некоторая начальная точка х[0] и выполняется одномерный поиск вдоль произвольного направления, приводящий в точку х[1] . Затем выбирается точка х[2], не лежащая на прямой х[0] - х[1], и осуществляется одномерный поиск вдоль прямой, параллельной х[0] - х[1],. Полученная в результате точка х[3] вместе с точкой х[1] определяет направление x[1] - х[3] одномерного поиска, дающее точку минимума х^*. В случае квадратичной функции nпеременных оптимальное значение находится за п итераций. Поиск минимума при этом в конечном счете осуществляется во взаимно сопряженных направлениях. В случае неквадратичной целевой функции направления поиска оказываются сопряженными относительно матрицы Гессе. Алгоритм метода параллельных касательных состоит в следующем.

1. Задаются начальной точкой x[0]. За начальные направления поиска р[1], ..., р[0] принимают направления осей координат, т. е. р [i] = е[i], i = 1, ..., n (здесь e[i]= (0, ..., 0, 1, 0, … 0)^T).

2. Выполняют n одномерных поисков вдоль ортогональных направлений р[i] , i = 1, ..., п. При этом каждый следующий поиск производится из точки минимума, полученной на предыдущем шаге. Величина шага а_k находится из условия

f(x[k] + а_kр[k]) =  f(x[k] + ар[k]).

Полученный шаг определяет точку

х[k+1] = х[k] + а_kр[k] .

3. Выбирают новое направление p =-x[n] - х[0] и заменяют направления р[1], ..., р[n] на р[2], ..., р [n], р. Последним присваивают обозначения р[1], ..., р[n]

4. Осуществляют одномерный поиск вдоль направления р = р[n] = х[n] - х[0]. Заменяют х[0] на х[n+1] = х[n] + а_nр[п] и принимают эту точку за начальную точку х[0] для следующей итерации. Переходят к п. 1.

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

 

 

Наверх

 

2.2. Численные методы безусловной оптимизации первого порядка

Минимизация функций многих переменных. Основные положения

Градиентом дифференцируемой функции f(x) в точке х[0] называется n-мерный вектор f(x[0]), компоненты которого являются частными производными функции f(х), вычисленными в точке х[0], т. е.

f'(x[0]) = (дf(х[0])/дх₁, …, дf(х[0])/дх_n)^T.

Этот вектор перпендикулярен к плоскости, проведенной через точку х[0] , и касательной к поверхности уровня функции f(x), проходящей через точку х[0] .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С₀, С₁, ... , получим серию поверхностей, характеризующих ее топологию (Рис. 2.8).

Рис. 2.8. Градиент

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f’(х[0])), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Очевидно, что если нет дополнительной информации, то из начальной точки х[0] разумно перейти в точку х [1], лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р[k] антиградиент -f’(х[k]) в точке х[k], получаем итерационный процесс вида 

х[k+1] = x[k]-a_kf'(x[k]), а_k > 0; k=0, 1, 2, ...

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

x_i[k+1]=х_i[k] - a_kf(x[k])/x_i

i = 1, ..., n; k= 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x[k+l] - x[k] || <= e, либо выполнение условия малости градиента

|| f’(x[k+l]) || <= g,

Здесь e и g - заданные малые величины.

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

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

f(х[k+1]) = f(x[k] – a_kf’(x[k])) < f(x[k]).

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

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

 

Наверх

 

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

При использовании метода наискорейшего спуска на каждой итерации величина шага а_k выбирается из условия минимума функции f(x) в направлении спуска, т. е. 
f(x[k] –a_kf’(x[k])) = f(x[k] – af'(x[k])).

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
j(a) = f(x[k] - af'(x[k])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х[0].

2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f’(x[k]).

3. Определяется величина шага a_k, путем одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])).

4. Определяются координаты точки х[k+1]:

х_i[k+1] = x_i[k] – а_kf’_i(х[k]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a_kвыбирается путем минимизации по а функции ?(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0.Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj(a)/da = -f’(x[k+1]f’(x[k]) = 0.

Рис. 2.9. Геометрическая интерпретация метода наискорейшего спуска

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

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l_i, i =1, …, n, матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 2.10. Овражная функция

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

 

Наверх

 

Метод сопряженных градиентов

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

f(x) = (х, Нх) + (b, х) + а

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

По определению, два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером пхп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x[k]) в направление p[k], H-сопряженное с ранее найденными направлениями р[0], р[1], ..., р[k-1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р[k] вычисляют по формулам:

p[k] = -f’(x[k])+b_k-1p[k-l], k >= 1;

p[0] = -f’(x[0]).

Величины b_k-1 выбираются так, чтобы направления p[k], р[k-1] были H-сопряженными:

(p[k], Hp[k-1])= 0. 

В результате для квадратичной функции

,

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

x[k+l] =x[k] +a_kp[k],

где р[k] - направление спуска на k-м шаге; а_k - величина шага. Последняя выбирается из условия минимума функции f(х)по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:

f(х[k] + а_kр[k]) =  f(x[k] + ар [k]).

Для квадратичной функции

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.

1. В точке х[0] вычисляется p[0] = -f’(x[0]).

2. На k-м шаге по приведенным выше формулам определяются шаг а_k. и точка х[k+1].

3. Вычисляются величины f(x[k+1]) и f’(x[k+1]).

4. Если f’(x[k+1]) = 0, то точка х[k+1] является точкой минимума функции f(х). В противном случае определяется новое направление p[k+l] из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х[0] на х[п+1] , а вычисления заканчиваются при , где  - заданное число. При этом применяют следующую модификацию метода:

x[k+l] = x[k] +a_kp[k],

p[k] = -f’(x[k])+b_k-1p[k-l], k >= 1;

p[0] = -f’(x[0]);

f(х[k] + a_kp[k]) =  f(x[k] + ap[k];

.

Здесь I- множество индексов: I = {0, n, 2п, Зп, ...}, т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 2.11). Из заданной начальной точки х[0] осуществляется спуск в направлении р[0] = -f'(x[0]). В точке х[1] определяется вектор-градиент f'(x [1]). Поскольку х[1] является точкой минимума функции в направлении р[0], то f’(х[1]) ортогонален вектору р[0]. Затем отыскивается вектор р [1], H-сопряженный к р [0] . Далее отыскивается минимум функции вдоль направления р[1] и т. д.

Рис. 2.11. Траектория спуска в методе сопряженных градиентов

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

 

Наверх

 

2.3. Численные методы безусловной оптимизации второго порядка

Особенности методов второго порядка

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

Необходимым условием экстремума функции многих переменных f(x) в точке х* является равенство нулю ее градиента в этой точке:

f’(х^*)  0. 

Разложение f’(х) в окрестности точки х[k] в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее уравнение в виде

f'(x)  f’(x[k]) + f"(x[k]) (х - х[k])  0.

Здесь f"(x[k])  Н(х[k]) - матрица вторых производных (матрица Гессе) минимизируемой функции. Следовательно, итерационный процесс для построения последовательных приближений к решению задачи минимизации функции f(x)описывается выражением

x[k+l] x[k] - H^-1(x[k]) f’(x[k]) ,

где H^-1(x[k]) - обратная матрица для матрицы Гессе, а H^-1(x[k])f’(x[k])  р[k] - направление спуска.

Полученный метод минимизации называют методом Ньютона. Очевидно, что в данном методе величина шага вдоль направления р[k] полагается равной единице. Последовательность точек {х[k]}, получаемая в результате применения итерационного процесса, при определенных предположениях сходится к некоторой стационарной точке х* функции f(x). Если матрица Гессе Н(х*) положительно определена, точка х* будет точкой строгого локального минимума функции f(x).Последовательность x[k] сходится к точке х* только в том случае, когда матрица Гессе целевой функции положительно определена на каждой итерации.

Если функция f(x) является квадратичной, то, независимо от начального приближения х[0] и степени овражности, с помощью метода Ньютона ее минимум находится за один шаг. Это объясняется тем, что направление спуска р[k]  H^-1(x[k])f’(x[k]) в любых точках х[0] всегда совпадает с направлением в точку минимума х*. Если же функция f(x) не квадратичная, но выпуклая, метод Ньютона гарантирует ее монотонное убывание от итерации к итерации. При минимизации овражных функций скорость сходимости метода Ньютона более высока по сравнению с градиентными методами. В таком случае вектор р[k] не указывает направление в точку минимума функции f(x), однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент.

Существенным недостатком метода Ньютона является зависимость сходимости для невыпуклых функций от начального приближения х[0]. Если х[0] находится достаточно далеко от точки минимума, то метод может расходиться, т. е. при проведении итерации каждая следующая точка будет более удаленной от точки минимума, чем предыдущая. Сходимость метода, независимо от начального приближения, обеспечивается выбором не только направления спуска р[k]  H^-1(x[k])f’(x[k]), но и величины шага а вдоль этого направления. Соответствующий алгоритм называют методом Ньютона с регулировкой шага. Итерационный процесс в таком случае определяется выражением

x[k+l]  x[k] - a_kH^-1(x[k])f’(x[k]).

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

f(x[k] – a_k H^-1(x[k])f’(x[k])   (f(x[k] - aH^-1(x[k])f’(x[k])).

Вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить. В таких случаях в подпрограммах оптимизации полагается H^-1(x[k])  Е ,где Е — единичная матрица. Очевидно, что итерация при этом осуществляется по методу наискорейшего спуска.

 

Наверх

 

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

Алгоритм метода Ньютона состоит в следующем. 

1. В начальной точке х [0] вычисляется вектор

p[0]  - H^-1(x[0])f’([0]).

2. На k-й итерации определяются шаг а_k и точка х[k+1].

3. Вычисляется величина f(х[k+1]).

4. Проверяются условия выхода из подпрограммы, реализующей данный алгоритм. Эти условия аналогичны условиям выхода из подпрограммы при методе наискорейшего спуска. Если эти условия выполняются, осуществляется прекращение вычислений. В противном случае вычисляется новое направление

р[k+1]  –H^-1(x[k])f’([k])

и осуществляется переход к следующей итерации.

Количество вычислений на итерации методом Ньютона, как правило, значительно больше, чем в градиентных методах. Это объясняется необходимостью вычисления и обращения матрицы вторых производных целевой функции. Однако на получение решения с достаточно высокой степенью точности с помощью метода Ньютона обычно требуется намного меньше итераций, чем при использовании градиентных методов. В силу этого метод Ньютона существенно более эффективен. Он обладает сверхлинейной или квадратичной скоростью сходимости в зависимости от требований, которым удовлетворяет минимизируемая функция f(x). Тем не менее в некоторых задачах трудоемкость итерации методом Ньютона может оказаться очень большой за счет необходимости вычисления матрицы вторых производных минимизируемой функции, что потребует затрат значительного количества машинного времени.

В ряде случаев целесообразно комбинированное использование градиентных методов и метода Ньютона. В начале процесса минимизации, когда точка х[0] находится далеко от точки экстремума х*, можно применять какой-либо вариант градиентных методов. Далее, при уменьшении скорости сходимости градиентного метода можно перейти к методу Ньютона.

3. Методы условной оптимизации

 

Наверх

 

3.1. Линейное программирование

Под линейным программированием понимается раздел теории экстремальных задач, в котором изучаются задач и минимизации (или максимизации) линейных функций на множествах, задаваемых системами линейных равенств и неравенств. В общем случае задача линейного программирования формулируется следующим образом. Найти вектор х* (x*₁, ..., х*_n), определяющий максимум (минимум) линейной форме

f(x)  с₁x₁ + с₂x₂+...+с_nx_n

при ограничениях:

a₁₁x₁ + … a_1nx_n  b₁;

. . . . . . . . . . . . . . . . . . .

a_m1x₁ + … a_mnx_n  b_m;

a_m+1x₁+… a_m+1,nx_n  b_m+1;

. . . . . . . . . . . . . . . . . . .

a_kx₁ + … a_knx_n  b_m;

a_k+1 x₁ + … a_k+1nx_n  b_m;

 

a_m+1x₁ + … a_m+1,nx_n  b_m+1;

. . . . . . . . . . . . . . . . . .

a_lx₁ + … a_lnx_n  b_l;

x_i  0; i  1, …, n.

Каждое из условий-неравенств определяет полупространство, ограниченное гиперплоскостью. Пересечение полупространств образует выпуклый п-мерный многогранник Q. Условия равенства выделяют из n-мерного пространства (п-l) -мерную плоскость, пересечение которой с областью Q дает выпуклый (n-l) -мерный многогранник G. Экстремальное значение линейной формы (если оно существует) достигается в некоторой вершине многогранника. При вырождении оно может достигаться во всех точках ребра или грани многогранника. В силу изложенного для решения задачу линейного программирования теоретически достаточно вычислить значения функции в вершинах многогранника и найти среди этих значений наибольшее или наименьшее. Однако в практических задачах количество вершин области G настолько велико, что просмотр их даже с использованием ЭВМ невозможен. Поэтому разработаны специальные численные методы решения задач линейного программирования, которые ориентируются в основном на две формы записи задач. Каноническая форма задачи линейного программирования:

f(x)  с₁х₁ + ...+ с_nx_n > max(min);

a₁₁x₁ +… a_1nx_n  b₁;

. . . . . . . . . . . . . . . . . .

a_mx₁ +… a_mnx_n  b_m;

x_i  0; i  1, …, n.

или в матричной форме:

(с, х) > max(min);

Ax  b,

х  0.

Здесь А  (а_ij) - (mхn) - матрица условий. Ее столбцы (a_1j, ..., а_mj)^T , j  1, ..., п, называются векторами условий. Вектор b  (b₁, ..., b_m)^T носит название вектора правых частей, а с  (с₁, …, с_n) - вектора коэффициентов линейной формы.

Задача линейного программирования с однотипными условиями

f(x)  с₁х₁ + ...+ с_nx_n > max(min);

a₁₁x₁ +… a_1nx_n  b₁;

. . . . . . . . . . . . . . . . . .

a_mx₁ +…a_mnx_n  b_m;

или в матричной форме:

(с, х) > max(min);

Ax  b,

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

 

Переход к эквивалентной системе неравенств.

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

a₁₁x₁ +…a_1nx_n  b₁;

можно заменить условием

-a₁₁x₁ +…-a_1nx_n  -b₁.

 

Переход от ограничения-неравенства к равенству

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

a₁x₁ +…a_nx_n  b.

эквивалентно двум ограничениям:

-a₁₁x₁+…-a_1nx_n+x_n+1  b; x_n+1  b₁.

 

Представление ограничения-равенства парой неравенств.

Ограничение

a_lx₁ +… a_nx_n  b;

можно представить парой условий:

a₁₁x₁ +… a_1nx_n b₁.

a₁₁x₁ +…-a_1nx_n  -b₁.

 

Переход к неотрицательным переменным

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

x_i  x_n+2 - x_n+1, x_n+1  0; x_n+2  0.

 

Переход от переменных, ограниченных снизу, к неотрицательным переменным

Если переменная ограничена снизу х_i  b_i то, заменив ее по формуле х_i  у_i + b_i переходим к задаче с неотрицательной переменной у_i  0.

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

Идея этого метода состоит в следующем. Отыскиваются некоторая вершина многогранника G и все ребра, выходящие из этой вершины. Далее перемещаются вдоль того из ребер, по которому функция убывает (при поиске минимума), и попадают в следующую вершину. Находят выходящие из нее ребра и повторяют процесс. Когда приходят в такую вершину, в которой вдоль всех выходящих из нее ребер функция возрастает, то минимум найден. Отметим, что, выбирая одно ребро, исключают из рассмотрения вершины, лежащие на остальных траекториях. В результате количество рассматриваемых вершин резко сокращается и оказывается посильным для ЭВМ. Симплекс-метод весьма эффективен и широко применяется для решения задач линейного программирования.

 

Наверх

 

3.2. Транспортная задача линейного программирования

 

Постановка задачи

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта.A_i в пункт В_j, i  1, …, m; j  1, ..., n. Предположим, что

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

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что

, i  1, …, m.

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

, j  1, …, n

Объемы перевозок - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:

x_ij  0, i  1, ..., m; j  1, ..., n.

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

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

, i  1, ..., m.

Введение этого условия приводит к открытой транспортной модели.

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

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

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

 

 

Наверх

 

Венгерский метод

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

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X₀  (x_ij[0])_m,n, элементы которой неотрицательны и удовлетворяют неравенствам:

, i  1, …, m;

, j  1, …, m.

Если эти условия являются равенствами, то матрица Х_o - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Х_k  (x_ij[0])_m,n. Близость этой матрицы к решению задачи характеризует число D_k — суммарная невязка матрицы Х_k:

.

В результате первой итерации строится матрица Х_l, состоящая из неотрицательных элементов. При этом D_l  D₀. Если D_l  0, то Х_l - оптимальное решение задачи. Если D_l  0, то переходят к следующей итерации. Они проводятся до тех пор, пока D_k при некотором k не станет равным нулю. Соответствующая матрица Х_k является решением транспортной задачи. 

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D₀/2 (D₀ - суммарная невязка подготовительного этапа).

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

 

 

Наверх

 

Метод потенциалов

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам А_iсоответствуют числа u_i, пунктам B_j - числа v_j. Они выбираются таким образом, чтобы их разность на k-й итерации была равна С_ij - стоимости перевозки единицы продукции между пунктами А_i и В_j:

v_j[k] – u_i[k]  C_ij, i  1, ..., m; j 1, …, п.

Если разность предварительных потенциалов для каждой пары пунктов А_i, В_j не превосходит С_ij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

 

Наверх

 

3.3. Прямые методы условной оптимизации

Основные определения

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x)n-мерного векторного аргументах (в дальнейшем без ограничения общности будут рассматриваться задачи поиска минимального значения функции):

f(x) -> min

при ограничениях:

g_i(x)  0, i  1, ..., k;

h_j(x)  0, j  1, .., m;

a  x  b.

Здесь x, a, b — векторы-столбцы:

, , 

Оптимизируемую функцию f(x) называют целевой функцией. Каждая точка x в n-мерном пространстве переменных x₁, ..., х, в которой выполняются ограничения задачи, называется допустимой точкой задачи. Множество всех допустимых точек называется допустимой областью G . Будем считать, что это множество не пусто. Решением задачи считается допустимая точка х*, в которой целевая функция f(х) достигает своего минимального значения. Вектор х* называют оптимальным. Если целевая функция f(x) и ограничения задачи представляют собой линейные функции независимых переменных х₁, ..., х_n, то соответствующая задача является задачей линейного программировании, в противном случае - задачей нелинейного программирования. В дальнейшем будем полагать, что функции f(x), g(x), i  1, ..., k , h_j(x), j  1, …, m, - непрерывные и дифференцируемые.

В общем случае численные методы решения задач нелинейного программирования можно разделить на прямые и непрямые. Прямые методы оперируют непосредственно с исходными задачами оптимизации и генерируют последовательности точек {x[k]}, таких, что f(х[k+1])  f(x[k]). В силу этого такие методы часто называют методами спуска. Математически переход на некотором k-м шаге (k.  0, 1, 2, ...) от точки х[k] к точке x[k+1] можно записать в следующем виде:

x[k+l]  x[k] + a_kp[k],

где р[k] — вектор, определяющий направление спуска; а_k — длина шага вдоль данного направления. При этом в одних алгоритмах прямых методов точки х[k] выбираются так, чтобы для них выполнялись все ограничения задачи, в других эти ограничения могут нарушаться на некоторых или всех итерациях. Таким образом, в прямых методах при выборе направления спуска ограничения, определяющие допустимую область G, учитываются в явном виде.

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

Рассмотрим некоторые алгоритмы прямых методов.

 

 

Наверх

 

Метод проекции градиента

Рассмотрим данный метод применительно к задаче оптимизации с ограничениями-неравенствами. В качестве начальной выбирается некоторая точка допустимой области G. Если х[0] - внутренняя точка множества G (Рис. 3.1), то рассматриваемый метод является обычным градиентным методом:

x[k+l]  x[k] –a_kf’(x[k]), k  0, 1, 2, ...,

где 

градиент целевой функции f(х) в точке x[k].

После выхода на границу области G в некоторой граничной точке х[k] , k  0, 1, 2,..., движение в направлении антиградиента -f’(х[k]) может вывести за пределы допустимого множества (см. Рис. 3.1). Поэтому антиградиент проецируется на линейное многообразие М, аппроксимирующее участок границы в окрестности точки х[k]. Двигаясь в направлении проекции вектора -f'(x[k]) на многообразие М, отыскивают новую точку х[k+1], в которой f(х[k+1])  f(x[k]), принимают х[k+1] за исходное приближение и продолжают процесс. Проведем более подробный анализ данной процедуры.

Рис. 3.1. Геометрическая интерпретация метода проекции градиента

В точке х[k] часть ограничений-неравенств удовлетворяется как равенство:

h_i(x)  0, j  1, ..., l; l  m.

Такие ограничения называют активными.

Обозначим через J набор индексов j(1  j  l) этих ограничений. Их уравнения соответствуют гиперповерхностям, образующим границу области G в окрестности точки х[k] . В общем случае эта граница является нелинейной (см. рис. 3.1). Ограничения h_j(x), j  J, аппроксимируются гиперплоскостями, касательными к ним в точке х[k]:

Полученные гиперплоскости ограничивают некоторый многогранник М, аппроксимирующий допустимую область G в окрестности точки х[k] (см. Рис. 3.1).

Проекция р[k] антиградиента -f'(x[k]) на многогранник вычисляется по формуле

p[k]  P[-f’(x[k])].

Здесь Р - оператор ортогонального проектирования, определяемый выражением

Р  E – A^T(AA^T)^-1A,

где Е - единичная матрица размеров п; А - матрица размеров lхn . Она образуется транспонированными векторами-градиентами а_j, j  1, ..., l, активных ограничений. Далее осуществляется спуск в выбранном направлении:

x[k+1]  x[k] + a_kp[k].

Можно показать, что точка х[k+1] является решением задачи минимизации функции f(х) в области G тогда и только тогда, когда Р[-f’(x[k])]  0,

т. е, и u  (u₁, ..., u_l)  (A^TA)^-1A^T(-f’(х[k]))  0.

Эти условия означают, что антиградиент (-f’(х[k])) целевой функции является линейной комбинацией с неотрицательными коэффициентами градиентов ограничений h_j(x)  0.

В соответствии с изложенным алгоритм метода проекции градиента состоит из следующих операций.

1. В точке х[k] определяется направление спуска р[k].

2. Находится величина шага а_k.

3. Определяется новое приближение х[k+1].

Рассмотрим детально каждую из этих операций.

1. Определение направления спуска состоит в следующем. Пусть найдена некоторая точка х[k]  G и известен набор активных ограничений h_i(х[k])  0, j  J. На основании данной информации вычисляют (-f’(х[k])) и определяют проекцию Р[-f’(х[k])]. При этом возможны два случая:

а) Р[-f’(х[k])] не равна 0. В качестве направления спуска р[k] принимают полученную проекцию;

б) Р[-f’(х[k])]  0, т. е. .

Данное выражение представляет собой систему из п уравнений для определения коэффициентов и_j. Если все и_j  0, j J, то в соответствии с вышеизложенным точка х[k] является решением задачи. Если же некоторый компонент и_q  0, то соответствующий ему градиент выводится из матрицы А и порождается новая проецирующая матрица Р. Она определит новое направление спуска.

2. Для определения величины шага а_k целевая функция минимизируется по направлению р[k] при условии соблюдения ограничений задачи с установленной точностью. Последняя задается введением некоторого положительного числа e. Считают, что точка х удовлетворяет условиям задачи с заданной точностью, если h_i(х)  e, j  1, ..., m. Величина шага а_kопределяется решением задачи вида:

f(x[k] + ар[k]) > min;

h_j(x[k] + ар[k])  e, j  1, ..., m.

3. Определение нового приближения состоит в следующем. Очередная точка вычисляется по формуле

x[k+1]  x[k] + а_kр[k].

Признаком сходимости является стремление к нулю векторов р[k]. Рассмотренный метод является в некотором смысле аналогом градиентных методов для решения задач на безусловный экстремум, и ему свойствен их недостаток - медленная сходимость.

 

 

Наверх

 

Комплексный метод Бокса

Этот метод представляет модификацию метода деформируемого многогранника и предназначен для решения задачи нелинейного программирования с ограничениями-неравенствами. Для минимизации функции n переменных f(x) в n-мерном пространстве строят многогранники, содержащие q  п+1 вершин. Эти многогранники называют комплексами,что и определило наименование метода.

Введем следующие обозначения:

х[j, k]  (х₁[j, k], …, х_i[j, k], …, х_n[j, k])^T,

где j  1, ..., q; k  0, 1, 2, ... - j-я вершина комплекса на k-м этапе поиска;

х[h, k] - вершина, в которой значение целевой функции максимально, т. е. f(x[h, k])  max{f(x[l, k]), ..., f(x[q, k])}; x[h, k]- центр тяжести всех вершин, за исключением х[h, k] . Координаты центра тяжести вычисляются по формуле

, i  l, ..., n.

Алгоритм комплексного поиска состоит в следующем. В качестве первой вершины начального комплекса выбирается некоторая допустимая точка х[1, 0]. Координаты остальных q-1 вершин комплекса определяются соотношением

х_j[j, 0]  а_i + r_i(b_i - a_i), i  1, ..., п; j  2, ..., q.

Здесь а_i, b_i - соответственно нижнее и верхнее ограничения на переменную х_i', r_i - псевдослучайные числа, равномерно распределенные на интервале [0, 1]. Полученные таким образом точки удовлетворяют ограничениям а  х  b , однако ограничения h_j(x)  0 могут быть нарушены. В этом случае недопустимая точка заменяется новой, лежащей в середине отрезка, соединяющего недопустимую точку с центром тяжести выбранных допустимых вершин. Данная операция повторяется до тех пор, пока не будут выполнены все ограничения задачи. Далее, как и в методе деформируемого многогранника, на каждой итерации заменяется вершина х[h, k], в которой значение целевой функции имеет наибольшую величину. Для этого х[h, k] отражается относительно центра тяжести х[l, k] остальных вершин комплекса. Точка х[р, k], заменяющая вершину х[h, k], определяется по формуле

x[p, k]  (a+1)х[l, k] + ax[h, k],

где а  0 - некоторая константа, называемая коэффициентом отражения. Наиболее удовлетворительные результаты дает значение а  1,3. При этом новые вершины комплекса отыскиваются за небольшое количество шагов, а значения целевой функции уменьшаются достаточно быстро.

Если f(x[р, k])  f(x[h, k]), то новая вершина оказывается худшей вершиной комплекса, В этом случае коэффициент ауменьшается в два раза. Если в результате отражения нарушается какое-либо из ограничений, то соответствующая переменная просто возвращается внутрь нарушенного ограничения. Если при отражении нарушаются ограничения h_j(x)  0. то коэффициент а каждый раз уменьшается вдвое до тех пор, пока точка х[р, k] не станет допустимой. Вычисления заканчиваются, если значения целевой функции мало меняются в течение пяти последовательных итераций: |f(х[l, k+1]) – f(х [l, k])|  e, k  1, ..., 5, где e   - заданная константа. В этом случае центр тяжести комплекса считают решением задачи нелинейного программирования.

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

 

Выбор начальной точки допустимой области

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

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

J₁  {j|h_j() 0, j  1, …, m};

J₂  {j|h_j() 0, j  1, …, m};

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

h_j(х)  0, j  J₁;

h_j(х) - z  0, j  J₂;

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

,

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

h(x)  0, j  1, …, m.

Следовательно, минимальное значение z меньше нуля. В силу этого после конечного числа шагов некоторого прямого алгоритма будут получены x[0], z, такие, что z  0, и условия задачи удовлетворяются. Точка х[0] и принимается в качестве начальной для исходной задачи нелинейного программирования.

 

Наверх

 

3.4. Методы штрафных функций

Основные определения

Методы штрафных функций относятся к группе непрямых методов решения задач нелинейного программирования:

f(x) -> min;

g_i(x)  0, i  1, ..., k;

h_j(x)  0, j  1, ..., m;

a  x  b.

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

F(x,a)  f(x) +Ф(х, а).

Здесь f(x) - целевая функция задачи оптимизации; Ф(х, а) - “штрафная” функция; параметр а  0. Точку безусловного минимума функции F(x, a) будем обозначать через х(а).

В зависимости от вида Ф(х, а) различают методы внутренних штрафных, или барьерных, функций и методы внешних штрафных функций.

 

Наверх

 

Методы внутренних штрафных функций

Эти методы применяются для решения задач нелинейного программирования с ограничениями-неравенствами. В рассматриваемых методах функции Ф(x, а) подбирают такими, чтобы их значения неограниченно возрастали при приближении к границе допустимой области G (Рис. 3.2). Иными словами, приближение к границе “штрафуется” резким увеличением значения функции F(x, а). На границе G построен “барьер”, препятствующий нарушению ограничении в процессе безусловной минимизации F(x, a). Поиск минимума вспомогательной функции F(x, а) необходимо начинать с внутренней точки области G . При этом в процессе оптимизации траектория спуска никогда не выйдет за пределы допустимой области. Все перечисленные особенности функции Ф (х, а) определили наименование рассматриваемой группы методов.

Рис. 3.2. Внутренняя штрафная функция

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

Здесь dG -граница области G.

Общий вид внутренней штрафной функции

,

где j _j - непрерывные дифференцируемые функции, определяемые ограничениями-неравенствами исходной задачи нелинейного программирования. Вспомогательная функция F(x, а) при этом имеет форму

.

Она определена в области G и неограниченно возрастает, если h_j(х) -> 0 для некоторого j. В качестве внутренних штрафных функций используют, например, такие:

; .

Алгоритм метода внутренних штрафных функций состоит в следующем. В качестве начальной точки х[0] выбирается произвольная внутренняя точка области G. Задается некоторая монотонно убывающая сходящаяся к нулю последовательность {a_k}, k  1, 2, ..., положительных чисел. Для первого элемента а₁ этой последовательности решается задача безусловной минимизации функции F(x, а), в результате чего определяется точка х(а₁). Эта точка используется в качестве начальной для решения задачи поиска минимума функции F(x, а₂), где а₂  а₁, и т. д. Таким образом, решается последовательность задач безусловной минимизации функций F(х, а_k), k  1, 2, ..., причем решение предыдущей задачи х(а_k) используется в качестве начальной точки для поиска последующего вектора х(а_k+1). Последовательность полученных таким образом точек х(а_k) сходится к оптимальному решению исходной задачи - локальному минимуму х*.Вычисления прекращают при выполнении условий:

|f(x[k]) - f(x[k-l])|  e;

||x[k] - x[k-l]||  b;

Здесь e, b - заданные числа, определяющие точность вычислений.

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

1) ;

2)  и монотонно убывает;

3)

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

 

Наверх

 

Методы внешних штрафных функций

Данные методы применяются для решения задачи оптимизации в общей постановке, т. е. при наличии как ограничений-неравенств, так и ограничений-равенств. В рассматриваемых методах функции Ф(х, а) выбирают такими, что их значения равны нулю внутри и на границе допустимой области G, а вне ее -положительны и возрастают тем больше, чем сильнее нарушаются ограничения (Рис. 3.3). Таким образом, здесь “штрафуется” удаление от допустимой области G.

Рис. 3.3. Внешняя штрафная функция

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

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

,

где j_j, f _j - функции, определяемые соответственно ограничениями-равенствами и неравенствами исходной задачи нелинейного программирования. Вспомогательная функция F(х, а) при этом имеет форму

Одна из применяемых внешних штрафных функций имеет вид

Здесь

Алгоритм метода внешних штрафных функций формулируется так же, как и алгоритм метода внутренних штрафных функций, и обладает аналогичными свойствами. Однако в этом случае не требуется, чтобы начальная точка х[0]  G , а последовательность {a_k}, k  1, 2, ..., положительных чисел должна быть монотонно возрастающей.

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

 

 

Наверх

 

Комбинированные алгоритмы штрафных функций

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

F(x, а)  f(х) + Ф(х, а) + f (х, а) . 

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

.

В качестве начальной точки выбирается вектор х[0] , удовлетворяющий условиям h_j(х)  0, j  1 ,..., m.Последовательность {a_k} , k  1, 2,..., положительных чисел является монотонно убывающей и сходящейся к нулю.

 

Выбор начальной точки допустимой области

В данном случае задача состоит в поиске точки, удовлетворяющей строгим неравенствам h_i(х)  0, j  1, ..., т. Рассмотрим два множества индексов:

J₁  {j¦h_j  0, j  1, …, m}

J₂  {j¦h_j  0, j  1, …, m}

Поиск внутренней точки должен состоять в том, чтобы перейти от точки  к новой точке , в которой удовлетворяются некоторые из ограничений множества J₂. При этом ни одно из условий множества J₁ не должно нарушаться. Затем необходимо перейти от точки  к другой точке, и так далее до тех пор, пока не будут удовлетворены все ограничения. Эта процедура реализуется минимизацией функции

,

где V(x) - внутренняя штрафная функция одного из видов, представленных выше, относительно ограничений из множества J₁. Последовательность {а_k}, k  1, 2, ..., сходится к нулю. В процессе минимизации производится проверка знаков функций h_j, j  J₂. Как только какое-либо из этих ограничений удовлетворяется, оно переводится во второе слагаемое, т.е. формируется соответствующая штрафная функция V(х). Минимизация полученной в результате новой функции W(x, а.) осуществляется из последней найденной точки х[k].

 

Наверх

 

4. Динамическое программирование

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

Рис. 4.1. Многостадийный процесс

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

x_k⁽ⁱ⁾  j _k⁽ⁱ⁾(x₁^(i-1), …, x_m^(i-1), u₁⁽ⁱ⁾, …, u_r⁽ⁱ⁾),

k  1, ..., m; i  1, ..., N,

связывающей выходные параметры i-й стадии x_k⁽ⁱ⁾ с выходными параметрами предыдущей стадии x_k^(i-1) и управлением и_l⁽ⁱ⁾ (l  1, ..., r), используемым на i-й стадии.

Систему уравнений удобно также представить в векторной форме

x⁽ⁱ⁾  j ⁽ⁱ⁾(x⁽ⁱ-1)_, u⁽ⁱ⁾),

причем x⁽ⁱ⁾ вектор совокупности переменных состояния (или выход) i-й стадии;

x⁽ⁱ⁾  (x₁⁽ⁱ⁾, x₂⁽ⁱ⁾, …, x_m⁽ⁱ⁾),

a u⁽ⁱ⁾ - вектор совокупности управляющих воздействий (управление) на i-й стадии:

u⁽ⁱ⁾  (u₁⁽ⁱ⁾, u₂⁽ⁱ⁾, …, u_r⁽ⁱ⁾).

Размерности векторов состояния x⁽ⁱ⁾ и управления и u⁽ⁱ⁾ в общем случае могут быть различными для разных стадий процесса. Однако далее, не нарушая общности, можно принять, что размерности m и r векторов состояния и управления для всех стадий процесса одинаковы.

В реальных процессах на значения переменных состояния x⁽ⁱ⁾ и управляющих воздействий u⁽ⁱ⁾ могут быть наложены ограничения, определяющие диапазон изменения или взаимосвязь указанных переменных. Математически это находит выражение в появлении дополнительных условий в виде равенств или неравенств

F_j(x⁽1), …, x^(N), u⁽¹⁾, …, u^(N)),

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

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

,

Смысл записи заключается в том, что значения переменных x⁽ⁱ⁾ и u⁽ⁱ⁾ принадлежат к допустимым областям их изменения Х и U, ограниченным соответствующими соотношениями.

Предполагается, что эффективность каждой стадии процесса оценивается некоторой скалярной величиной

r_i  r_i^*(x⁽ⁱ⁾, u⁽ⁱ⁾).

заданной в виде функции от переменных состояния стадии x⁽ⁱ⁾ и принятого на ней управления u⁽ⁱ⁾.

С учетом математического описания стадии функциональная зависимость эффективности может быть представлена также как

r_i  r_i(x⁽ⁱ-1), u⁽ⁱ⁾).

т. е. как функция состояния входа x^(i-1) на i-й стадии и используемого на ней управления u⁽ⁱ⁾

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

Естественно, что значение критерия оптимальности R_N зависит от совокупности u⁽ⁱ⁾_N управляющих воздействий на всех стадиях процесса, которые представляет собой набор значений векторов u⁽ⁱ⁾ для всех стадий:

u_N  (u⁽1), u⁽2), …, u^(N)).

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

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

  (u_опт⁽1), u_опт⁽2), …, u_опт^(N)),

для которой критерий оптимальности r_n принимает в зависимости от постановки оптимальной задачи максимальное или минимальное значение.

 

Принцип оптимальности

В основу метода динамического программирования положен принцип оптимальности, который в переложении для много-, стадийного процесса может быть сформулирован следующим образом. Оптимальная стратегия обладает тем свойством, что каковы бы ни были начальное состояние x⁽⁰⁾ многостадийного процесса и управление на первой стадииu⁽¹⁾, последующие управления на всех стадиях u⁽ⁱ⁾ (i  2, ..., N) должны составлять оптимальную стратегию и_N-1относительно состояния x⁽1) первой стадии, определяемого начальным состоянием процесса x⁽⁰⁾ и управлением на первой стадии u⁽1).

В приведенной формулировке принципа оптимальности под оптимальной стратегией и_N-1 понимается стратегия управления многостадийным процессом, включающим N-1 последних стадий исходного процесса, придающая критерию

оптимальное значение.

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

Таким образом, если известна оптимальная стратегия управления и_N-1 для любого возможного состояния x⁽1) первой стадии N-стадийного процесса, то уже не составляет труда выбрать оптимальное управление и на первой стадии u_опт⁽¹⁾, поскольку на последующих стадиях оно определяется только состоянием выхода первой стадии:

и_N-1  и_N-1 (x⁽1)).

Процедура применения принципа оптимальности для оптимизации N-стадийного процесса, очевидно, должна начинаться с последней стадии процесса, для которой не существует последующих стадий, могущих повлиять согласно принципу оптимальности на выбор управления u_опт^(N) на этой стадии. После того как оптимальное управление u_опт^(N) найдено для всех возможных состояний входа последней стадии x^(N-1)  X, можно приступить к определению оптимального управления для предыдущей (N-1)-стадии, для которой оптимальная стратегия управления на последующих стадиях (т. е. на последней N-й стадии) известна, и т. д.

В результате может быть найдена оптимальная стратегия управления для всего многостадийного процесса, являющаяся функцией начального состояния процесса u_N^(x(0)). Если начальное состояние x⁽0) известно (задано или выбрано из условия оптимума критерия R), то его значение определяет оптимальные управления для всех стадий процесса.

 

Наверх

 

Список литературы

1. Аоки М. Ведение в методы оптимизации. М.: Наука. 1977. 344с.
2. Бояринов А.И., Кафаров В.В. Методы оптимизации в химической технологии. М.: Химия. 1975. 576с.
3. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. - M.: Наука, 1969. - 382с.
4. Фурунжиев Р.И., Бабушкин Ф.М., Варавко В.В. Применение математических методов и ЭВМ: Практикум. Мн.: Выш.шк. 1988. 191с.