Вычислительные методы



Скачать 143.99 Kb.
Дата24.12.2012
Размер143.99 Kb.
ТипДокументы
§4. Вычислительные методы.
Приведенный в предыдущем параграфе классический метод (метод множителей Лагранжа) можно использовать тогда, когда целевая функция и ограничения задачи НЛП обладают хорошими свойствами (гладкость, выпуклость и др.). В отсутствии такой возможности применяются приближенные методы. Они могут применятся и в тех случаях, когда задача (1)-(3) не имеет оптимального решения. Тогда решая обобщенную задачу НЛП приближенными методами, можно построить минимизирующую последовательность, сходящуюся к некоторому, практический приемлемому приближенному «оптимальному решению». Приближенные методы, как правило, являются прямыми методами, так как они решают непосредственно исходную экстремальную задачу. К непрямым методам относятся те, в которых решение исходной задачи получается путем решения другой задачи, к которой предварительно сводится исходная задача. Например, метод множителей Лагранжа является непрямым методом, так как решается задача, полученная из исходной с помощью необходимого условия минимума. В теории НЛП разработано большое число вычислительных методов, которые по тем или иным характеристикам могут быть разбиты на различные группы (классы). Ниже приводится краткие сведения о некоторых из них. Но часто такое разбиение носит условный характер, так как один и тот же метод может быть отнесен к разным группам. Например, методы проекции градиента и условного градиента могут считаться как градиентными методами, так и методами возможных направлений.

Задачи НЛП, решаемые путем сведения к более простым задачам



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

2) Задача дробно-линейного программирования

(33)

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

(34)

(35)

(36)

можно свести к задаче ЛП следующим образом, введем новые переменные y0,y1,…,yn:

(37)

В новых переменных задача (33)-(36) запишется:

(38)

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

(39)

gif" name="object8" align=absmiddle width=226 height=45> (40)

(41)

(42)

где (39) и (40) получены в результате умножения обеих частей (34) и (35) на y0 > 0; (41) получено из первого равенства (37) в результате исключения xj; (42) аналог условия (36).

Оптимальное решение задачи ЛП (37)-(41) в Rn+1 найдем применяя симплекс-метод, а решение исходной задачи (33)-(37) – по формуле .
3) Задача квадратичного программирования
(43)

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

(44)

(45)

где D=|| ij || - симметрическая n x n матрица, r=(r1,…,rn) - постоянный вектор, A=|| aij || - m x n матрица, b=(b1,…,bm) - постоянный вектор, можно свести к задаче ЛП. Здесь матрица D предполагается положительно определенной (отсюда следует выпуклость квадратичной формы F(x), а ограничения (44)-(45) являются линейными). Такой переход можно осуществить следующим образом. Сначала строим каноническую форму задачи (43)-(45), введя в ограничения (44) слабые переменные xn+1,…,xn+m. Тогда ограничения задачи запишутся (в координатной форме):

(46)

(47)

(48)

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

- условие стационарности:

(49)

- условие допустимости;

(50)

, (51)

- условие дополняющей нежесткости:

(52)

- условие неотрицательности:

(53)

Систему (49)-(53) можно решать двухфазным симплекс-методом (методом искусственного базиса), рассматривая (49) как целевую функцию, а (50)-(53) – как ограничения, с учетом того, что множители Лагранжа 1,…, n,1,…, n не должны все одновременно равняться нулю.

Замечание. При использовании двухфазного симплекс метода следует учитывать «нелинейность» ограничений (52), т.е. не включать в базисные одновременно переменные j и xj с одним и тем же индексом и переменные j и xn+i с одним и тем же индексом.
4) Элементарным (по своей идее) является метод сведения задачи с ограничениями-равенствами:

(54)

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

(55)

к задаче безусловной оптимизации (метод исключения). Из уравнений (55) исключается k переменных, например,



Подставляя найденные представления переменных x1,…,xk в целевую функцию (54), приходим к следующей задаче безусловной оптимизации относительно n-k переменных:



Этот метод наиболее приемлем в том случае, когда ограничения (55) линейны:

Ax=b
Итеративные вычислительные методы.
Рассмотрим задачу НЛП



Где X допустимое множество (см. §1). Итеративными называются методы (или алгоритмические отображения), которые при помощи заданной начальной точки x0  X генерируют последовательность допустимых точек x0,x1,…,xk,xk+1,… , последовательно приближающихся к оптимальному решению x* задачи (56). Переход от xk к xk+1 называется итерацией. Если за конечное число итераций метод (алгоритм) приводит к оптимальному решению, то он называется точным методом, в противном случае – приближенным методом. Обычно итерация строится по схеме



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

Эффективность итеративного метода оценивается следующими факторами:

1) Универсальностью;

2) Надежностью и точностью;

3) Чувствительностью к исходным данным и параметрам;

4) Затратами на вычисление;

5) Сходимостью и скоростью сходимости;

Об этих факторах более подробно можно прочитать в [1], с. 252-254.

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

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

(57)

где >0 называется точностью решения исходной задачи. При этом в качестве приближенного оптимального решения задачи (56) принимают . Важно отметить, что итеративные методы рассчитаны на применение ЭВМ. Желательным свойством итеративных процессов является свойство спуска:

f(x0)  f(x1) …  f(xk)  f(xk+1) …

Методы с таким свойством называются методами спуска. Различные методы 0-го, 1-го, 2-го и т.д. порядка, в зависимости от применения при вычислении направления и длины шага производных соответствующих порядков целевой функции. Методы 0-го порядка (когда производные не применяются), иногда называют методами поиска.

Итеративные методы для задач без ограничений (X = Rn) упрощаются тем, что отсутствует необходимость проверки допустимости итеративных точек (xk  X) на каждой итерации. Методы, генерирующие только допустимые точки (их xk  X следует xk+1  X), называют методами возможных направлений.

Наиболее простыми являются методы одномерной оптимизации, т.е. когда в (56) x  R1, а X = [a,b]. К таким методам относятся известные из курса анализа метода деления отрезка пополам, ломаных, касательных, парабол, покрытий. (см [2], с.9-69).

Непрерывную функцию f(x), x  R1, называют унимодальной на отрезке [a,b], если существуют точка x*  [a,b], что на отрезке [a,x*] функция f(x) убывает, а на отрезке [x*,b] - возрастает. Основное свойство унимодальных функций, используемое при поиске точек минимума, состоит в том, что вычисление любых двух значений f(x1), f(x2), x1  x2, x1,x2  [a,b] позволяет уменьшить интервал поиска точки минимума. Для решения задачи одномерной оптимизации с унимодальной целевой функцией применяется метод золотого сечения и метод чисел Фибоначчи (см. [2] с. 19-22, [3] с. 194-204, [6] с. 109-114). В идейном отношении (и при реализации на ЭВМ) наиболее простым методом отыскания глобального минимума является метод равномерного перебора. Для сходимости этого метода важно, чтобы целевая функция удовлетворяла условию Липшица ([6] с. 114-116).

Известно, что градиент f(x), как вектор, указывает направление возрастания функции f в точке x (любое достаточно малое перемещение из точки x в направлении вектора f(x) увеличивает значение функции f). Это замечательное свойство положено в основу многих вычислительных методов. Итеративные методы, в которых направление x определяется при помощи градиента f(x) (в задачах на максимум) и антиградиента -f(x) (в задачах на минимум), называются градиентными методами (см. [1] с. 302-305, [2] с. 260-299, [6] с. 120-122). К числу градиентных можно отнести метод Ньютона, в котором k = -f(x), k = [2f(xk)]-1, а также методы наискорейшего спуска (см. там же), в которых длина шага определяется в результате решения оптимизационной задачи в направлении антиградиента.

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

Если точка xk лежит на границе допустимой области X, то любой малый шаг k >0 в направлении антиградиента может привести к недопустимой точке (xk  X). Преодоление такого случая предусмотрено в методах возможных направлений (метод Зойтендейка, метод проекции градиента, метод условного градиента, выпуклый симплексный метод Зангвилла, [1] с. 371-466). Идея состоит в том, чтобы в граничной точке xk выбрать направление поиска, соответствующее минимально возможному, с учетом ограничений, углу с направлением антиградиента в этой точке.
Пример 8. Методом проекции градиента решить следующую задачу НЛП:



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



завершив вычисления при выполнении одного из условий:



На каждой итерации этого метода предусмотрена процедура возврата точки xk+1 = xk – kf(xk) в допустимое множество X, если только xk+1  X. Такой возврат производится посредством проектирования Pxk+1 на X: xk+1=Px(xk–kf(xk)). При этом длину шага можно выбрать различными способами. Например, если f(x) липшецева: ||f(x’) – f(x”)||  L||x ’- x”||, то полагают k =   (0;2/L).

Отметим, что вычисление проекции Px(y), yRn является самостоятельной задачей минимизации:



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



Решение: В качестве начальной точки возьмем x0 = (0;0.5)  X (здесь X={x  R2 | }). Так как



То полагаем k = =0.75, k=0,1,…

Шаг 1.



Так как (0.75;-0.25)  X, то x1 = (0.75;-0.25).

Требуемая точность не достигнута, так как ||x1 – x0|| = 1.06 > 0.01.

Шаг 2.



Поскольку точка (1.5;0.125) не принадлежит Х и учитывая то, что Х – замкнутый шар с радиусом r=1, получаем:



Требуемая точность не достигнута, так как ||x2 – x1|| = 0.298 > 0.01. И так далее. Требуемая точность получается на пятой итерации (шаге):

.

Таким образом, решение задачи найдено с точностью =0.01. Заметим, что точное решение данной задачи есть x*=(1,0), f(x*)=-1.
Пример 9. Методом условного градиента решить следующую задачу НЛП:



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



завершив вычисления при выполнении условия



Здесь f(x) выпуклая функция, а X = {x  R2 | } - прямоугольник (двумерный параллелепипед).

Пусть xkX, причем f(xk)0. Тогда в малой окрестности точки xk функция f(x) представима в виде:



и линейная функция fk(x)=<f(xk),x-xk>, является приближением разности f(x)-f(xk) с точностью до малой величины O(||x-xk||) в некоторой окрестности точки xk (по определению градиента).

Поставим вспомогательную задачу:

(57)

Пусть - решение этой задачи. Положим

.

В силу выпуклости множества Х, xkX. Длину шага можно выбрать различными способами. Например, где найдено из условия наискорейшего спуска по направлению :



Отметим, что (57) является, вообще говоря, задачей НЛП и поэтому может оказаться достаточно сложной. Ее решение упрощается, если допустимое множество Х исходной задачи задано линейными ограничениями, либо имеет вид замкнутого шара или n-мерного параллелепипеда. В последнем случае, т.е. если , известно, что

(58)

где - i-я компонента вектора xk.

Решение. В качестве начального приближения выберем точку x0=(0,0)X.

Шаг 1. Вычислим f(x0)=(-4,-2) и запишем задачу (57):

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

Эту задачу ЛП можно решить симплекс-методом. В данном случае проще использовать формулу (58). Тогда . Найдем 0. В данном случае



Из условия имеем . Поэтому 0=min{1;0.8}=0.8.

Вычислим . Требуемая точность не достигнута, так как . Переходим ко второму шагу. И так далее.

Ответ:

Векторы p1,…,pn называются сопряженными направлениями, если они линейно независимы и <2f(xk)pi,pj>=0 при ij. Заметим, что сопряженные направления определяются неоднозначно. Итерационные методы, использующие в качестве направлений последовательности сопряженных векторов, относятся к методам 2-го порядка и поэтому обладают большой точностью. В частности, если целевая функция квадратичная, то при помощи методов сопряженных направлений можно получить точку минимума за конечное число шагов. К таким методам относятся метод Дэвидона-Флетчера-Пауэлла, метод Флетчера и Ривса и метод Зангвилла ([1], с. 310-329).
Пример 10. Методом сопряженных направлений решить следующую задачу НЛП без ограничений:



Вычислим матрицу Гессе:



Построим два сопряженных направления p1 и p2. Положим p1=(1,0). Тогда должен удовлетворять равенству . В частности, можно выбрать . Тогда и p2=(1,2). Пусть минимизация начинается в точке x0=(-1/2,1). Тогда вдоль p1 получим точку x1=(1/2,1). Теперь минимизируя f(x) из точки x1 в направлении p2 получим x2=(1,2), которая является точкой глобального минимума.

Один из подходов к решению задачи НЛП (56) основан на замене этой задачи последовательностью задач безусловной минимизации:

(59)

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

В методе штрафных функций подбираются так, чтобы при больших l функция fl(x) из (59) мало отличалась от f(x) при xX, и быстро возрастала при удалении точки xX от допустимого множества X.

Последовательность функций {}, определенных в Rn и обладающих свойствами



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

Например, для задачи (1)-(3) положим:

(60)

где

,



Можно показать, что равенство (60) определяет последовательность штрафных функций допустимого множества Х, задаваемого соотношениями (2)-(3). Если последовательность решений задач (59)-(60) безусловной оптимизации сходится к пределу, то для достаточно больших l приближенное оптимальное решение задачи (1)-(3) полагают равным xl. Критерием остановки служит неравенство ||xl – xl/2||, >0,l - четное число.

Заметим, что для задачи (43)-(45) квадратичного программирования решения вспомогательной задачи (59) можно найти точно, применяя необходимые условия (а в случае выпуклости функции (43) и достаточные) вида (9).
Пример 11. Методом штрафных функций решить следующую задачу НЛП:



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



Так как целевая функция выпукла, а ограничения линейны, то решение xl вспомогательной задачи (59) для любого l=1,2,… может быть найдено точно из условия fl(xl)=0.

Решение. Предположим, что в точке xl – решение задачи (59), gi(xl)>0 для всех i=1,2,3,…. Тогда . Поэтому (см. (60))



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



находим



Так как g3(xl)<0, то предположение не подтвердилось. Теперь предположим, что



Тогда



Поэтому считаем, что



Отсюда находим

(61)

Легко проверить, что второе предположение подтверждается, и равенство (61) определяет точку безусловного минимума xl вспомогательной функции fl(x) из (59). Окончательно находим:



Отметим, что для решения вспомогательных задач (59) можно было использовать приближенные (напр. градиентные) методы. Тогда при требовании точности ||xl – xl/2||, >0,l, получаем:



В методе барьерных функций исходная задача (56) также сводится к последовательности безусловных задач оптимизации (59), но функция Фk(x) выбирается так, чтобы при больших k функции fk(x) из (59) мало отличались от f(x) при x  int X, а при приближении к границе Х эти функции неограниченно возрастали. Последовательность функций {Фk(x)}, определенных в int X, называется последовательностью барьерных функций множества Х, если выполняются условия:

1)

2) для любой последовательности , сходящейся к граничной точке Х.

Например, для задачи (1)-(2) положим:



где

или .

Можно показать, что эти равенства определяют последовательность барьерных функций. Для достаточно больших k полагают x=xk.
Пример 12. Методом барьерных функций решить следующую задачу НЛП с точностью =0.002.



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



Задачу (59) запишем в виде:



Решая ее, например, методом Ньютона (применение этого метода см. на следующем примере) при k=500 и k=1000, получим: x500=(0.6696;0.3319), x1000=(0.6682;0.3326). Так как ||x1000 - x500||=1.65*10-3<0.002, полагаем x= x1000, f(x)=0.6687.

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



с точностью =0.05.

Итерационная формула этого метода есть



т.е. направление определяется антиградиентом, а длина шага – обратной матрицей Гессе. Будем пользоваться критерием остановки .

В качестве начальной точки возьмем x0=(0.00;3.00). Вычислим поочередно





Отсюда находим



И так далее. Требуемая точность получается на 6-ом шаге. Поэтому



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

Похожие:

Вычислительные методы iconВычислительные методы и приемы
В данной главе представлены наиболее распространенные вычислительные методы, используемые для численного решения отдельных задач,...
Вычислительные методы iconУчебная программа Дисциплины б9 «Вычислительные методы» по направлению 010300 «Фундаментальная информатика и информационные технологии»
Дисциплины «Вычислительные методы» направлено на обучение студентов основам решения задач линейной алгебры, решения нелинейных алгебраических...
Вычислительные методы iconП. Т. Зубков Вычислительные методы математической физики
П. Т. Зубков. Вычислительные методы математической физики. Учебно-методический комплекс. Рабочая учебная программа для студентов...
Вычислительные методы iconМетоды вычислений и математическое обеспечение иэт, эл 12, 13, 14, 17-2003, эл 16-2003
Лекция Введение: основные этапы решения прикладных задач с использованием компьютеров, вычислительные задачи, методы, алгоритмы,...
Вычислительные методы iconРабочей программы дисциплины Вычислительные методы Место дисциплины в структуре ооп
Рунге-Кутта; численные методы решения интегральных уравнений второго рода; метод регуляризации решения интегральных уравнений первого...
Вычислительные методы iconРабочая программа учебной дисциплины " вычислительные методы компьютерного моделирования в механике" Цикл
Профили подготовки: Компьютерные технологии управления в робототехнике и мехатронике
Вычислительные методы iconУ истоков компьютерной революции
Несколько тысячелетий спустя, появились первые ручные вычислительные инструменты. А в наши дни сложнейшие вычислительные задачи,...
Вычислительные методы iconРеферат по предмету: «Основы информатики и программирования»
Несколько тысячелетий спустя появились первые ручные вычислительные инструменты. А в наши дни сложнейшие вычислительные задачи, как...
Вычислительные методы iconОтчет за 2009 год по выполнению проекта №89 «Эффективные вычислительные методы на последовательности сеток для решения задач математической физики»
Охватывает огромную территорию водостока и само русло, рельеф которых и данные по стоку должны формироваться с учетом спутниковых...
Вычислительные методы iconПрограмма учебной дисциплины «вычислительные машины, системы и сети» Направление подготовки
Вычислительные машины, системы и сети ” призвана познакомить студента, обучающегося по направлению 220700 “Автоматизация технологических...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org