Основы теории оптимизации; постановка и решение задачи

1 1.ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ 1.1.ПОСТАНОВКА И РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В наиболее общем смысле теория оптимизации представляет собой совокупность фундаментальных математических результатов и численных методов, ориентированных на нахождение наилучшего варианта из множества возможных альтернатив без их полного перебора и оценивания. Постановка любой задачи оптимизации включает в себя 4 этапа. 1)Установление границ подлежащей оптимизации системы Здесь под системой понимается некая изолированная часть реального мира – например, промышленная установка, предприятие и т.д. Чтобы выделить изучаемую систему из внешней среды, важно четко определить ее границы и зафиксировать на некотором заранее выбранном уровне представления ее взаимосвязи с внешней средой. 2)Выбор характеристического критерия Характеристический критерий представляет собой скалярную меру “качества” решения. Наилучшему решению задачи оптимизации обязательно отвечает оптимальное, т.е. максимальное или минимальное, значение критерия. В прикладных задачах характеристический критерий часто имеет экономический или технологический характер, например, им может быть величина прибыли предприятия или масса, т.е. задача может состоять в максимизации прибыли или минимизации массы двигателя. 3)Выбор независимых переменных, используемых для определения характеристик системы и идентификации вариантов решения Необходимо разделить переменные на те, значения которых могут изменяться в достаточно широком диапазоне и те, значения которых фиксированы и определяются внешними факторами. Первые являются независимыми переменными, а вторые – параметрами задачи. Важно, что выбор определенного набора независимых переменных в конкретной прикладной задаче почти всегда представляет собой компромисс между стремлением учесть все переменные, которые влияют на функционирование системы, и стремлением выбрать только те из них, чье влияние на выбранный характеристический критерий наиболее существенно. Последнее стремление продиктовано необходимостью разумного упрощения задачи. 4)Построение математической модели системы Модель системы описывает взаимосвязь между переменными и отражает степень их влияния на характеристический критерий. В самом общем представлении структура модели в технике включает основные уравнения материальных и энергетических балансов, соотношения, связанные с проектными решениями, а также уравнения, описывающие физические процессы, протекающие в системе. Эти уравнения обычно дополняются неравенствами, определяющими области допустимых значений переменных. 2 Решение оптимизационной задачи – это приемлемый набор значений независимых переменных, которому отвечает оптимальное значение характеристического критерия. 1.2. СТРУКТУРА ОПТИМИЗАЦИОННЫХ ЗАДАЧ Несмотря на то, что прикладные задачи оптимизации относятся к различным областям практической деятельности и представляют различные системы, они имеют общую форму. Все эти задачи можно охарактеризовать как задачи минимизации вещественнозначной функции f (x) с ограничениями на ее N -мерный векторный аргумент x . Общий вид задачи условной оптимизации Минимизировать f ( x) : R N → R1 при ограничениях hk (x) = 0 , k = 1...K (1.1) g j ( x) ≥ 0 , (1.2) j = 1...J xiL ≤ xi ≤ xiR , i = 1...I (1.3) Здесь f (x) - целевая функция задачи, уравнения hk (x) = 0 – называются ограничениями в виде равенств, а неравенства g j ( x) ≥ 0 – ограничениями в виде неравенств. Предполагается, что все функции в задаче вещественнозначны, а число ограничений конечно. Задачи оптимизации можно классифицировать в соответствии с видом функций f (x ) , g (x) и h(x) , а также размерностью вектора x . Если ограничения (1.1) – (1.3) отсутствуют, то это задача безусловной оптимизации. Такие задачи с N = 1 называются задачами одномерной оптимизации, при N > 1 – многомерной безусловной оптимизации. Если в задаче оптимизации функции hk (x) и g j (x) линейны, то это задача с линейными ограничениями. При этом целевая функция может быть как линейной, так и нелинейной. Задача условной оптимизации, в которой все функции линейны, называется задачей линейного программирования (ЛП). Если при этом координаты вектора x должны принимать только целые значения, то задача называется задачей целочисленного программирования (ЦЛП). Задачи с нелинейными целевой функцией и/или ограничениями называются задачами нелинейного программирования (НЛП). 3 2.ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ Задача оптимизации без ограничений, в которой характеристический критерий задан функцией одного аргумента, относится к наиболее простому и распространенному виду оптимизационных задач. 2.1. СВОЙСТВА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ С точки зрения применения методов оптимизации наиболее важными из свойств функции одной переменной являются непрерывность, монотонность и униминимальность. Монотонность функции. Функция f (x) является монотонно возрастающей, если для любых x1 и x 2 из области определения функции, таких, что x1 ≤ x 2 , выполняется f ( x1 ) ≤ f ( x 2 ) . Если же для любых x1 и x 2 из области определения функции, таких, что x1 ≤ x 2 , выполняется f ( x1 ) ≥ f ( x 2 ) , то f (x) является монотонно убывающей. Униминимальность. Функция f(x) называется униминимальной на отрезке [ a, b ] , если существует такая точка x* ∈ [a, b] , что для ∀x1 , x2 ∈ [a, b] , x1 < x 2 , выполняются: f ( x1 ) > f ( x 2 ) , если x2 < x * ; f ( x1 ) < f ( x 2 ) , если x* < x1 . f(x) [ a x * x1 x2 ] b x Для непрерывных целевых функций данное свойство означает наличие единственного локального минимума – в точке x * , который является и глобальным минимумом. Рассматриваемые далее методы одномерного поиска используют свойство униминимальности целевой функции в предположении, что отрезок локализации минимума [a,b] определен. 2.2. МЕТОД ПОИСКА ОТРЕЗКА ЛОКАЛИЗАЦИИ МИНИМУМА Построим итеративный конечношаговый процесс для определения отрезка [a,b], содержащего x * . Априори выбираются начальная точка x ( 0 ) и положительный шаг ∆ > 0 . Вычисляется новая точка x (1) = x ( 0 ) + ∆ и сравниваются соответствующие значения целевой функции. Рассмотрим три возможные ситуации. f(x) f(x) x ( 0) x (1) x ( 2 ) а) f(x) x ( 2 ) x ( 0) x (1) x x (0) x (1) x b) c) Рис. 2.1. (1) (0) В случае а) имеем f ( x ) < f ( x ) и продолжаем генерировать новые точки x ( k +1) из x ( k ) по x 4 правилу: x ( k +1) = x ( k ) + 2 k ⋅ ∆ , ∆ > 0 . (2.1) Генерацию точек следует продолжать вплоть до значения k+1, для которого впервые выполнится цепочка неравенств f ( x ( k −1) ) > f ( x ( k ) ) < f ( x ( k +1) ) . (2.2) В силу униминимальности f(x) ясно, что x * ∈ [ x ( k −1) , x ( k +1) ] , а значит можно положить a = x ( k −1) , b = x ( k +1) . В случае b) имеем f ( x (1) ) > f ( x ( 0 ) ) , и следует генерировать новые точки по формуле x ( k +1) = x ( k ) − 2 k ⋅ ∆ , (2.3) также вплоть до значения k+1, при которых впервые выполняется (3.2), и затем положить a = x ( k +1) , b = x ( k −1) . В редком на практике случае с) можно сразу положить a = x ( 0 ) , b = x (1) . Далее рассмотрим методы сокращения найденного отрезка локализации минимума и оценки x*. 2.3.МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА. СХЕМА СОКРАЩЕНИЯ ОТРЕЗКА. В отличие от метода пассивного поиска, методы последовательного поиска на каждом k-ом шаге используют информацию о значении функции f(x), вычисленном на (k-1)-ом шаге. Это позволяет строить более эффективные, т.е. быстрее сходящиеся к x*, методы одномерного поиска. Среди методов последовательного поиска с линейной скоростью сходимости рассмотрим метод дихотомии и метод “золотого сечения”. Оба метода используют для сокращения отрезка локализации минимума следующую схему. Пусть f (x ) униминимальна на [a, b] и достигает минимума в точке x * . Рассмотрим точки x (1) и x (2) : a < x (1) < x (2) < b . Сравнение f ( x (1) ) и f ( x (2) ) позволяет сократить отрезок [a, b]: Результаты сравнения Новый отрезок локализации минимума 1 f ( x (1) ) > f ( x (2) ) [x (1) , b] 2 f ( x (1) ) < f ( x (2) ) [a, x (2) ] 3 f ( x (1) ) = f ( x (2) ) [x (1) , x (2) ] Замечание. На практике схема обычно упрощается до двух “ветвей”: Результаты сравнения Новый отрезок локализации минимума 1 f ( x (1) ) > f ( x (2) ) [x (1) , b] 2 f ( x (1) ) ≤ f ( x (2) ) [a, x (2) ] Отрезок локализации минимума сокращается до тех пор, пока его длина не уменьшится до достаточно малых размеров. Принципиальная разница между использующими эту схему методами дихотомии и “золотого сечения” – в расположении точек x (1) и x ( 2 ) . 2.3.1.Метод дихотомии Пусть f(x) – унимодальная функция, имеющая минимум в точке x* ∈ [a, b] . Выберем первые две точки x (1) и x ( 2 ) внутри [a, b] 1 1 x (1) = (a + b) − δ , x ( 2 ) = (a + b) + δ , (2.4) 2 2 где δ > 0 – малое число. 5 Первый шаг поиска заканчивается проверкой условия окончания поиска: 1 (длина отрезка локализации минимума) ≤ ε , (2.5) 2 где ε > 0 - априори задаваемая точность вычисления x*. В случае выполнения (2.5) поиск x*, равной соответственно 1 1 x* = (a + x ( 2) ) или x* = ( x (1) + b) , (2.6) 2 2 окончен. Если условие (2.5) не выполнено, то в соответствии с описанной выше схемой сокращения выбирается новый отрезок локализации минимума: [a, b] = [a, x ( 2) ] или [a, b] = [ x (1) , b] . Затем внутри полученного отрезка по формулам (2.4) вычисляются новые точки x (1) и x ( 2 ) , выполняется сравнение f ( x (1) ) и f ( x ( 2) ) и т.д. Заметим, что длина отрезка локализации минимума после первого сокращения исходного [a, b] составит 1 LM 1 = (b − a ) + δ , (2.7) 2 а после k-го шага LM k −1 LM k = +δ 2 или, что тоже самое b − a 2k − 1 LM k = k + k −1 δ , (2.8) 2 2 где a и b – границы исходного отрезка. Теоретически, соответствующим выбором δ величину LM k можно сделать сколь угодно b−a близкой к . При программной реализации чрезмерное уменьшение δ приводит к 2k негативным последствиям, связанным с потерей чувствительности: f ( x (1) ) = f ( x (2) ) . 2.3.2.Метод “золотого сечения” Его отличие от метода дихотомии состоит в ином, более эффективном расположении точек внутри отрезка локализации минимума. Вначале рассмотрим симметричное расположение двух пробных точек на исходном отрезке локализации минимума [0,1] . 1 −τ τ 1 Рис.2.2. Расположение точек в методе золотого сечения Точка τ делит отрезок [0,1] на части, отношение длин которых равно τ 1 −τ . Обе пробные точки находятся от удаленных границ на расстояние τ . Следовательно после сравнения значений целевой функции, длина оставшегося отрезка будет однозначно равна τ (Рис.2.3). 1 −τ τ 1 −τ τ 1 а) б) Рис.2.3. Сокращенный отрезок локализации минимума 6 с оставшейся внутренней точкой Рассмотрим случай а). Внутри нового отрезка [0,τ ] осталась пробная точка 1 − τ . Потребуем, чтобы эта точка делила новый отрезок на части с прежним отношением длин τ 1 −τ : (1 − τ ) − 0 τ 1 −τ τ = = , ⇒ τ − (1 − τ ) 1 − τ 2τ − 1 1 − τ отсюда (1 − τ ) 2 = (2τ − 1)τ ; 1 − 2τ + τ 2 = 2τ 2 − τ ; τ 2 + τ − 1 = 0 . 5 −1 = 0,61803... 2 τ 0,6180 ≈ ≈ 1.618 называется “золотым”. Сечение отрезка в отношении 1 − τ 0.3820 Очевидно, что достаточно добавить симметрично к точке 1 − τ относительно центра отрезка [0,τ ] вторую пробную точку, чтобы вновь прийти к исходной (Рис.3.2) схеме расположения пробных точек, но уже внутри сокращенного отрезка локализации минимума. Важность полученного результата состоит в следующем. 1.Расположив внутри начального отрезка локализации минимума [0,1] пробные точки Положительное решение составляет τ = 1 − τ ( 0.3820 ) и τ ( 0.6180 ), где τ = 5 −1 , и сократив отрезок после сравнения значений 2 функции в них, на каждой из последующих итераций следует использовать оставшуюся внутри отрезка “старую” пробную точку. Для очередного сокращения отрезка к ней добавляется одна новая точка. Т.е. на 2-й, 3-й и прочих итерациях по сути необходима лишь одна дополнительная оценка значения функции в точке. 2.Длина отрезка локализации минимума на каждой итерации сокращается в τ раз. Это почти максимально возможное сокращение при реализации изложенной идеи экономии вычислений. Реализация метода “золотого сечения” на практике подразумевает “золотое” сечение начальными точками произвольного отрезка локализации минимума [ a, b] : x (1) = a + (1 − τ )(b − a ) , x ( 2 ) = a + τ (b − a ) . (2.9) Указанные свойства делают метод “золотого сечения” одной из наиболее эффективных процедур надежного последовательного поиска. 2.3.3. Методы полиномиальной аппроксимации. Среди методов последовательного поиска важное место занимают методы полиномиальной аппроксимации. Они менее надежны, чем методы дихотомии и “золотого сечения”, но обладают большей скоростью сходимости. Идея их довольно проста: по нескольким известным значениям независимой переменной и значениям целевой функции в них строится аппроксимирующая функция, точку минимума которой легко определить аналитически. Эта точка выступает в качестве текущей оценки истинного решения. Теоретически качество этой оценки может быть повышено двумя способами: уменьшением интервала аппроксимации и увеличением степени аппроксимирующего полинома. Первый способ в случае унимодальной функции сложности не представляет. Использование же полиномов высоких степеней на практике неэффективно. Замечания: 1. При некоторых обычно выполняемых условиях методы с полиномиальной аппроксимацией сходятся со сверхлинейной скоростью. 2. Если аппроксимирующая функция ϕ (x ) плохо описывает поведение f(x) в достаточно 7 представительной окрестности, то точка x̂ минимума ϕ (x ) будет плохой оценкой решения. В частности, в случае f(x) ϕ (x ) x* x3 xˆ x Рис.2.3 точка x̂ окажется за пределами отрезка локализации минимума [ x1 , x3 ] , не говоря уже о случае, x1 x2 f(x) x1 x2 x3 x* x ϕ (x ) Рис.2.4 когда у ϕ (x ) просто не будет ограниченного минимума 3. Повышение надежности методов полиномиальной аппроксимации приводит к значительному усложнению численных алгоритмов поиска и, как правило, потере сверхлинейной сходимости. 8 3. ВВЕДЕНИЕ В МНОГОМЕРНУЮ БЕЗУСЛОВНУЮ ОПТИМИЗАЦИЮ. Пусть требуется найти минимум функции f(x) нескольких аргументов f ( x) → min , x ∈ R n (т.е. x = ( x1 , x2 , ..., xn ), xi ∈ R ). (3.1) Существующие численные методы решения этой задачи основаны на точном или приближенном вычислении значений функции f(x) в некоторых генерируемых ими точках x . Последовательность точек x ( 0) , x (1) , x ( 2) ,... и соответствующих им значений функции f ( x ( 0 ) ), f ( x (1) ), f ( x ( 2) ),... позволяет строить приближение к решению задачи (3.1) – искомой точке минимума x * или, если такая точка не единственна, – к множеству точек минимума. Каждый алгоритм генерирует последовательность точек x ( 0) , x (1) , x ( 2) ,... , в соответствии с пассивной или последовательной стратегией поиска. При пассивной стратегии все точки x ( 0) , x (1) , x ( 2) ,..., x ( l ) выбираются одновременно до начала вычислений значений функции. При этом число точек l конечно. Последовательной стратегии соответствуют алгоритмы минимизации, в которых точки x ( 0 ) , x (1) , ... вычисляются поочередно, при этом выбор точки x ( i +1) обусловлен информацией о поведении функции f(x) в предшествующих точках x ( 0 ) , x (1) ,..., x ( i ) или, по крайней мере, в точке x (i ) . Пассивная стратегия применяется, как правило, в особых случаях и имеет ряд существенных недостатков по сравнению с последовательной. Главный из них – значительно больший объем вычислений при поиске точки минимума с заданной точностью, одинаковой для обеих стратегий. Однако в случае многоэкстремальных задач применение пассивной стратегии целесообразно. В основе последовательной стратегии лежит итерационная схема следующего вида: x ( k +1) = x ( k ) + α k p ( k ) , α k ∈ R1 , α k > 0; p ( k ) ∈ R n ; k=0,1,2,… (3.2) где k – номер итерации. Конкретный численный метод оптимизации определяется выбором начальной точки x 0 и правилами вычисления векторов p (k ) и чисел α k . В формуле (3.2) вектор p (k ) определяет направление минимизации функции f(x) на (k+1)-ом шаге (итерации), а коэффициент α k определяет длину шага в этом направлении. Введем понятие векторной нормы. Векторная норма – это функция • , сопоставляющая каждому вектору v ∈ R n действительное неотрицательное число. Векторная норма должна удовлетворять условиям: 1) v ≥ 0 , причем v = 0 только если v = 0 , т.е. v = (0, ..., 0) ; 2) αv =| α | v ; 3) v + w ≤ v + w , для любых векторов v, w ∈ R n и чисел α ∈ R1 . Наиболее распространена Евклидова норма v 2 = v12 + v22 + ... + vn2 . Заметим, что при p ( k ) ≠ 1 длина отрезка, соединяющего точки x ( k +1) и x ( k ) , конечно, не равна α k . 9 Классификация методов оптимизации в основном определяется:
правилом вычисления вектора направления p (k ) ;
использованием информации о первых и вторых частных производных функции f(x);
способом вычисления α k . Различают три основные группы методов многомерной безусловной оптимизации:
использующие только значения f(x) и называемые методами прямого поиска (методы нулевого порядка);
использующие значения функции f(x) и ее первых производных и называемые градиентными методами (методы первого порядка);
использующие значения функции f(x) и ее первых и вторых производных, называемые ньютоновскими методами (методы второго порядка). Использование итерационной схемы (3.2) для решения задачи минимизации f(x) предполагает, что направление p (k ) на каждом шаге k=0,1,2,… определяется так, чтобы обеспечить выполнение цепочки неравенств f ( x ( 0) ) > f ( x (1) ) > ... > f ( x ( k ) ) > ... (3.3) (k ) Определение: Метод оптимизации, вычисляющий последовательность точек x , k=0,1,2,…, удовлетворяющих условию (3.3), называется методом спуска. Определение: Направление p k , удовлетворяющее соотношению f ( x k + α k p k ) < f ( x k ) для любого α k >0, k=0,1,… называется направлением спуска или приемлемым направлением минимизации. (4.4) 10 4. ВВЕДЕНИЕ В МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ. 4.1. ПРИНЦИПИАЛЬНАЯ МОДЕЛЬНАЯ СХЕМА МЕТОДОВ. Пусть целевая функция f(x) имеет непрерывные первые g(x) и вторые G(x) частные производные для всех x ∈ R n . Для решения задач безусловной минимизации гладких функций f(x) будем строить методы спуска f ( x k ) > f ( x k +1 ) , k = 0, 1, 2, ... , (4.1) с использованием вектора g(x) и матрицы G(x), опираясь на итерационную схему пересчета координат x k +1 = x k + α k p k , (4.2) где α k > 0 - шаг в направлении спуска p k . Все методы первого и второго порядка могут быть описаны следующей принципиальной модельной схемой: имея текущее приближение x k искомой точки x * , на очередной итерации выполнить шаги: шаг 1. Используя f ( x k ) , g ( x k ) и (или) G ( x k ) , вычислить приемлемое направление поиска p k . шаг 2. Используя p k , вычислить шаг α k , обеспечивающий выполнение неравенства f (x k + α k p k ) < f (x k ) шаг 3. Проверить выполнение условия останова метода и, если оно выполнено, прекратить поиск, взяв x k в качестве искомого решения x * . шаг 4. Положить x k +1 = x k + α k p k , k = k + 1 и перейти на шаг 1. Наиболее сложным шагом модельной схемы и в теоретическом, и в практическом плане, является шаг 1. Это объясняется наличием целого ряда требований, которым должен удовлетворять вектор направления поиска p k . Наиболее важное из них: g ( x k ), p k < 0 . (4.3) На шаге 2 схемы решается задача одномерной минимизации с аргументом α k . 4.2.МЕТОДЫ ПЕРВОГО ПОРЯДКА. ГРАДИЕНТНЫЕ МЕТОДЫ. 4.2.1.Итерационная схема градиентных методов. Определение: Метод минимизации непрерывно дифференцируемой функции f (x) , в котором направление поиска определяется антиградиентом p k = − f ′( x k ) = − g ( x k ), k = 0, 1, 2, ... (4.4) называется градиентным методом. В общем случае градиентному методу соответствует итерационная схема:  x k +1 = x k + α k (− g ( x k )) = x k − α k g ( x k ), (4.5)  α > , k = , 1 , 2 ,... k  4.2.2.Оптимальный градиентный метод. Недостатки трех рассмотренных выше модификаций градиентного метода в значительной мере устраняются при использовании оптимального градиентного метода или, иначе, метода наискорейшего спуска Коши, которому соответствует следующая итерационная схема:  x k +1 = x k − α k g ( x k ), k = 0,1,2,... (4.6)  α = arg min f ( x k − α ⋅ g ( x k )).  k α >0 Отметим, что в понятие оптимальности здесь вкладывается только тот смысл, что 11 выбираемая в соответствии с методом точка x k +1 , лежащая на прямой αg ( x k ) , является на этой прямой точкой минимума функции f (x ) . Движение к точке минимума функции f (x ) в оптимальном градиентном методе производится зигзагообразно, причем последовательные направления поиска, например, p k −1 = x k − x k −1 и p k = x k +1 − x k , при точном определении α k −1 и α k являются ортогональными или p k −1 , p k = 0 (4.7) Рисунок иллюстрирует это для двумерного случая квадратичной функции. x2 x4 p x0 3 p x 2 3 p1 p x x2 x x0 2 1 x1 а) x1 б) Рис.4.1. 4.3. МЕТОДЫ ВТОРОГО ПОРЯДКА. МЕТОД НЬЮТОНА. Направление поиска (− g ( x k )) , соответствующее градиентным методам, можно интерпретировать как следствие линейной аппроксимации целевой функции. Использование квадратичной аппроксимации позволяет получить семейство методов, существенно более эффективных, чем градиентные. Локальное сходство любой гладкой функции f(x) с квадратичной позволяют использовать полученные результаты для предсказания поведения функции f(x) в окрестности ее стационарной точки x * по значениям собственных чисел матрицы Гессе G ( x*) . Например, если одно из них окажется близким к нулю, то можно ожидать, что при движении из x * вдоль соответствующего собственного вектора функции f(x) будет почти постоянной. Метод Ньютона. Метод Ньютона – первый в истории оптимизации метод, основанный на квадратичной аппроксимации минимизируемой функции. Название “метод Ньютона” закрепилось за применением рекуррентного соотношения x k +1 = x k − G −1 ( x k ) g ( x k ) , (4.8) при условии, что существует обратная матрица G −1 ( x k ) . С определенной точки зрения метод Ньютона можно трактовать как градиентный метод, у которого вектор-градиент модифицирован вторыми частными производными функции. Рассмотрим случай, когда минимизируемая функция f ( x) является квадратичной вида 1 f ( x) = h, x + Gx, x , (4.9) 2 где G - положительно определенная матрица. Исходя из произвольной начальной точки x 0 и используя выражение (4.8), получим x1 = x 0 − G −1 (h + Gx 0 ) = −G −1 h . (4.10) 1 Точка x является точкой минимума функции f (x ) . Следовательно, точка минимума 12 квадратичной функции найдена за один шаг из произвольной начальной точки. Пример:  f ( x) = ( x1 − 5) 2 + q( x2 − 3) 2 , q > 0 .  x10 = x20 = 0.  Вычислим f ′( x 0 ) и G −1 : f1′( x 0 ) = (2 x1 − 10) x = x0 = −10   − 10  1 1  f ′( x 0 ) =   f 2′( x ) = 2q( x2 − 3) | x = x0 = −6q  − 6 q   2 2  0  f11′′ ( x 0 ) = 2, f 12′′ = 0 2 0  1 / 2  → G −1 =    G =  f 21′′ = 0, f 22′′ = 2q   0 2q   0 1 / 2q  Поэтому  x11   0  1 / 2 0  − 10   5   1  =   −    =   . x   2   0   0 1 / 2q  − 6q   3  Несмотря на столь сильное свойство метода Ньютона в отношении квадратичной функции, попытка применить его без какой либо модификации к произвольной функции неквадратичного типа почти наверняка обречена на провал, поскольку в этом случае его шаги единичной длины в направлениях − G −1 ( x k ) g ( x k ) могут не только не приводить к точке минимума, но даже вызвать f ( x k +1 ) > f ( x k ) . Поэтому используется модификация метода вида x k +1 = x k − α k G −1 ( x k ) g ( x k ) , (4.11) где α k определяется одномерным поиском в направлении G −1 ( x k ) g ( x k ) , называемая “методом Ньютона-Рафсона”. При применении метода Ньютона, а предпочтительнее – метода Ньютона-Рафсона, необходимо иметь в виду следующее: 1. уравнения (4.8) и (4.11) требуют вычисления и обращения матрицы Гессе на каждом шаге метода, что составляет основную часть вычислений; 2. в задаче минимизации произвольной квадратичной функции с положительно определенной матрицей вторых частных производных, метод Ньютона дает решение за 1 итерацию независимо от выбора начальной точки x 0 ; 3. метод Ньютона может работать плохо или совсем отказать, если используемые в нем квадратичные приближения функции f (x ) будут неверно описывать поведение функции f (x ) вне малых окрестностей опорных точек x k . 13 5. МЕТОДЫ ШТРАФНЫХ И БАРЬЕРНЫХ ФУНКЦИЙ 5.1. МЕТОД ПРЕОБРАЗОВАНИЯ Пусть дана функция f i ( x) ≥ 0, i = 1, m и f ( x ) : R n → R1 , n > 1 , а также функции ограничений f i ( x) = 0, i = m + 1, p ( p − m < n ), определяющие множество n допустимых решений D ⊂ R . Рассмотрим задачу условной многомерной минимизации: минимизировать f (x ) при ограничениях f i ( x) ≥ 0, i = 1, m f i ( x) = 0, i = m + 1, p . Методом преобразования называется любой способ решения задачи условной минимизации целевой функции сведением ее к одной или нескольким задачам безусловной минимизации некоторых вспомогательных функций. Основоположником методов преобразования является Р. Курант, предложивший в 1943 г. использовать штрафную вспомогательную функцию для решения простых физических задач движения в ограниченной области. К задачам математического программирования этот подход начал применяться, примерно, с 1955 г. Общий вид вспомогательной функции для задачи условной минимизации: F ( x, r ) = f ( x) + Φ ( f i ( x), r ) , где r – параметр штрафа, а Φ – вещественнозначная функция, “штрафующее воздействие” которой регулируется с помощью r . Точку безусловного локального минимума F ( x, r ) по x обозначим x(r ) . Различные методы преобразования отличаются друг от друга выбором Φ и способом задания r , позволяющим найти решение задачи условной минимизации путем безусловной минимизации F ( x, r ) по x . Традиционный подход состоит в том, чтобы задать Φ и последовательность {r k } так, k чтобы точки x ( r ) существовали, их можно было бы найти каким-либо из методов k безусловной минимизации и x ( r ) → x * при k → +∞ . Методы такого типа, по Фиакко и Мак-Кормику, называют методами последовательной безусловной минимизации. Эти методы распадаются на два класса. Первый класс составляют методы барьерных функций, также называемые методами внутренней точки. Для этих методов характерен поиск решения внутри множества допустимых решений D . Второй класс составляют методы штрафных функций или, иначе, методы внешней точки, n использующие также недопустимые точки x ∈ R \ D . 5.2. МЕТОД ШТРАФНЫХ ФУНКЦИЙ Метод штрафных функций сводит решение задачи условной минимизации целевой функции f (x) к решению последовательности задач безусловной минимизации вспомогательной функции: F ( x, r ) = f ( x ) + P ( x, r ) , n где P( x, r ) – штрафная функция (penalty function), определенная на всем пространстве R . По построению P( x, r ) принимает нулевое значение на множестве допустимых решений D , а вне D – положительные значения, возрастающие с увеличением невязок ограничений. Общий вид штрафной функции: 14 m P( x, r ) = r[∑ψ i ( f i ( x )) + i =1 где r > 0 , а функции p ∑ψ i ( f i ( x))] , i = m +1 ψ i (t ), i = 1, m и ψ i (t ), i = m + 1, p определены и непрерывны при 1 любом t ∈ R . Функции ψ i (t ), i = 1, m выполнялось: (для ограничений-неравенств) конструируются так, чтобы ψ i (t ) → +∞ при t → −∞  , ψ i (t ) = 0 при t ≥ 0 а функции ψ i (t ), i = m + 1, p (для ограничений-равенств) по построению таковы, что: ψ i (t ) → +∞ при t → ±∞  . ψ i (t ) = 0 при t = 0 Наиболее часто применяются: ψ i ( f i ( x)) = (min(0, f i ( x))) 2 (рис. 1 а)) вместе с ψ i ( f i ( x )) = ( f i ( x )) 2 (рис. 5.1 б)) а) б) Рис. 5.1 или ψ i ( f i ( x)) = − min(0, f i ( x)) (рис. 2 а)) вместе с ψ i ( f i ( x)) = f i ( x) (рис.5.2 б)). а) б) Рис. 5.2 0 T Алгоритм метода штрафных функций требует задания начальной точки x = ( x1 , ..., xn ) , начального значения параметра штрафа r > 0 и коэффициента также параметра точности поиска ε > 0 . Алгоритм 1 Шаг 1. Положить k = 0 . Шаг 2. Составить вспомогательную функцию m F ( x, r k ) = f ( x) + r k [∑ψ i ( f i ( x )) + i =1 p z > 1 для его умножения, а ∑ψ i ( f i ( x))] . i = m +1 15 k k k Шаг 3. Начиная из точки x , найти точку x ( r ) безусловного минимума функции F ( x, r ) по x : F ( x(r k ), r k ) = minn F ( x, r k ) . x∈R Шаг 4. Вычислить штраф m P( x(r ), r ) = r [∑ψ i ( f i ( x (r ))) + k k k k i =1 p ∑ψ i ( f i ( x(r k )))] . i = m +1 Шаг 5. Проверить выполнение критерия останова: k k если P ( x( r ), r ) < ε , то перейти на шаг 6; иначе положить r k +1 = zr k , x k +1 = x (r k ), k = k + 1 , перейти на шаг 2. k Шаг 6. Положить x* ≅ x( r ) и закончить поиск. Замечание. Наиболее часто выбираются r = 0.01, 0.1 или 1 и z ∈ [4, 10] . 5.3. МЕТОД БАРЬЕРНЫХ ФУНКЦИЙ Метод барьерных функций сводит решение задачи условной минимизации целевой функции f (x) к решению последовательности задач безусловной минимизации вспомогательной функции: F ( x, r ) = f ( x ) + B ( x, r ) , где B( x, r ) – барьерная функция (barrier function), определенная лишь внутри множества допустимых решений D , т.е. на множестве D0 = {x | f i ( x) > 0, i = 1, m} . B( x, r ) такова, чтобы на границе допустимого множества построить барьер, препятствующий нарушению ограничений в процессе безусловной минимизации F ( x, r ) по x , и чтобы точки x (r ) с изменением r по некоторому правилу приближались к x * изнутри D (т.е. в D0 ). Отметим, что D0 должно быть не пусто – это исключает возможность применения метода барьерных функций для решения задач с ограничениями-равенствами Общий вид барьерной функции: f i ( x) = 0, i = m + 1, p . m B( x, r ) = r ∑ ϕ i ( f i ( x )) , i =1 где r > 0 , а функции ϕi (t ) – непрерывные при t > 0 функции, причем ϕ i (t ) → +∞ при t → +0 . 16 Наиболее часто применяются:
обратная функция барьера Кэрролла (1961) (рис. 5.3 а)) ϕ i ( f i ( x)) =
1 ; f i ( x) логарифмическая функция барьера Фриша (1955) (рис. 5.3 б)) ϕ i ( f i ( x)) = − ln( f i ( x)) . а) Алгоритм x = ( x10 , ..., метода б) Рис. 5.3 функций требует барьерных задания xn0 )T начальной точки ∈ D0 , начального значения параметра штрафа r > 0 и коэффициента 0 < z < 1 для его уменьшения, а также параметра точности поиска ε > 0 . Алгоритм 2 Шаг 1. Положить k = 0 . Шаг 2. Составить вспомогательную функцию m F ( x, r k ) = f ( x ) + r k ∑ ϕ i ( f i ( x)) . i =1 k k k Шаг 3. Начиная из точки x , найти точку x ( r ) безусловного минимума функции F ( x, r ) по x с проверкой принадлежности текущей точки множеству D0 : F ( x( r k ), r k ) = min F ( x, r k ) . x∈D0 Шаг 4. Вычислить k k B( x( r ), r ) = r k m ∑ ϕ i ( f i ( x(r k ))) . i =1 Шаг 5. Проверить выполнение критерия останова: k k если | B ( x( r ), r ) |< ε , то перейти на шаг 6; иначе положить r k +1 = zr k , x k +1 = x ( r k ), k = k + 1 , перейти на шаг 2. k Шаг 6. Положить x* ≅ x( r ) и закончить поиск. Замечание. Наиболее часто выбираются r = 1, 10 или 100 и z = 1 1 1 или . , 10 12 16