1. Математическая модель объекта и ее свойства

1.Математическая модель объекта и ее свойства.

Сущность методологии состоит в замене исходного объекта его "образом" — математической моделью — и дальнейшем изучении модели с помощью реализуемых на компьютерах вычислительно-логических алгоритмов.

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

Рис. 1.1.

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

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

На третьем этапе создаются программы, "переводящие" модель и алгоритм на доступный компьютеру язык. К ним также предъявляются требования экономичности и адаптивности. Их можно назвать "электронным" эквивалентом изучаемого объекта, уже пригодным для непосредственного испытания на "экспериментальной установке" — компьютере.
2.Понятие критерия оптимальности и функции цели.

Критерии оптимальности

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

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

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

Рассмотрим более подробно требования, которые должны предъявляться к критерию оптимальности.

1. Критерий оптимальности должен выражаться количественно.

2. Критерий оптимальности должен быть единственным.

3. Критерий оптимальности должен отражать наиболее существенные стороны процесса.

4. Желательно чтобы критерий оптимальности имел ясный физический смысл и легко рассчитывался.

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

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

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

.

Рис.1. Оптимизируемый объект

– выходы объекта; – контролируемые входные параметры; – регулируемые входные параметры (управляющие параметры); – неконтролируемые воздействия;

Так как , то при фиксированных можно записать:

.

При этом всякое изменение значений управляющих параметров двояко сказывается на величине R:

• 
  прямо, так как управляющие параметры непосредственно входят в выражение критерия оптимизации;
  
• 
  косвенно – через изменение выходных параметров процесса, которые зависят от управляющих.
  

Если же случайные возмущения достаточно велики и их необходимо учитывать, то следует применять экспериментально-статистические методы, которые позволят получить модель объекта в виде функции, которая справедлива только для изученной локальной области и критерий оптимальности примет вид:
.
В принципе, для оптимизации вместо математической модели можно использовать и сам объект, однако оптимизация опытным путем имеет ряд существенных недостатков:

а) необходим реальный объект;

б) необходимо изменять технологический режим в значительных пределах, что не всегда возможно;

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

В задачах оптимизации различают простые и сложные критерии оптимизации.

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

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

3.Основные задачи оптимизации.

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

Итак, для решения задачи оптимизации необходимо:

а) составить математическую модель объекта оптимизации

,

б) выбрать критерий оптимальности и составить целевую функцию

,

в) установить возможные ограничения, которые должны накладываться на переменные;

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

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

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

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

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

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

Задачи с нелинейной целевой функцией и линейными ограничениями иногда называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если f(x) – квадратичная функция, то мы имеем дело с задачей квадратичного программирования; если f(x) есть отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т.д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку специфические особенности тех или иных задач играют важную роль при разработке методов их решения.

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

Оптимизация:

Дискретная:

Целочисленное программирование;

Стохастическое программирование.

Непрерывная:

Безусловная:	Условная:
Глобальная оптимизация; Дифференцируемая оптимизация; Недифференцируемая оптимизация.	Линейное программирование; Нелинейные задачи; Стохастическое программирование.

4.Одномерная оптимизация. Метод общего поиска. Унимодальные функции. Метод деления интервала пополам.

ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ

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

Общий поиск:

Пусть требуется найти минимум функции f(x) на некотором интервале [a,b]. Если о функции f(x) на этом интервале никакой дополнительной информации неизвестно, то для поиска минимума на [a,b] можно присенить простейший метод перебора, или, иначе, общего поиска.

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

Обычно говорят о дроблении интервала неопределенности, которое характеризуется коэффициентом α. Разделив интервал неопределенности на n равных частей, получим n+1 узел. Тогда _. При этом необходимо вычислить N=n+1 раза.

Следовательно,

(2.1)

Чтобы получить значение потребуется вычислить функцию в 201 точке, а при =0.001 N=2001.

Ясно, что эффективность этого метода с уменьшением интервала неопределенности быстро падает.

Унимодальные функции

Более эффективные методы можно построить, если предположить, что исследуемая функция имеет в рассматриваемом интервале только один минимум. Более точно: предположим, что в интервале [a, b] имеется единственное значение такое, что – минимум на [a, b] и что строго убывает для и строго возрастает для . Такая функция называется унимодальной.
Для ее графика имеются три различные формы:


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

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

Метод деления интервала пополам

Разделим интервал [a, b] на две равные части, а затем каждую из частей еще на две равные части.

Это первый этап поиска минимума. На нем после пяти вычислений функции (два – на краях и три – внутри интервала [a, b]) интервал неопределенности сужается вдвое, то есть на этом этапе . Новый интервал неопределенности снова разделим пополам, а затем каждую половину снова пополам. Теперь значения функции по краям и в его середине уже известны. Поэтому для завершения поиска на этом этапе требуется вычислить только два значения функции, после чего интервал неопределенности снова уменьшится вдвое. Это преимущество рассмотренного метода сохранится и в дальнейшем.

После N вычислений функции коэффициент дробления интервала составляет

(2.2)

Здесь N=5,7,9,…, так как интервал неопределенности, начиная со второго этапа, уменьшается только после двух вычислений функции. Из (2.1),(2.2) видно, что метод деления пополам эффективнее, чем общий поиск.

5. Унимодальные функции. Метод «золотого сечения»

Более эффективные методы можно построить, если предположить, что исследуемая функция имеет в рассматриваемом интервале только один минимум. Более точно: предположим, что в интервале [a, b] имеется единственное значение такое, что–минимумна [a, b] и что строго убывает для и строго возрастает для . Такая функция называется унимодальной. Для ее графика имеются три различные формы:

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

Из предположения унимодальности следует, что для любых точек интервала [a, b], таких, что < справедливо<.Аналогично, если <, то >. Обратно, если < и>, то , а если <, то .

Будем считать исследуемую функцию унимодальной. Более эффективный метод нахождения минимума функции является деление интервала на неравные части. Вычислим функцию на концах отрезка [a, b] и положим . Вычислим функцию в двух внутренних точках . Сравним все значения функции и выберем среди них наименьшее. Если наименьшим оказалось f(x₃). Следовательно, минимум находиться в одном из прилегающих к нему отрезков либо на отрезке [x1,x3], либо [x3,x4]. Поэтому отрезок [x4,x2] можно отбросить и оставить отрезок [x1,x4].

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

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

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

6. Метод Свенна для поиска отрезка, содержащего точку минимума

Метод Свенна – это эвристический метод, который определяет интервал неопределенности, содержащий точку минимума. Пусть требуется найти минимум функции f(x) не на отрезке, а на всей оси х. Берем функцию f(x), которая унимодальна. Выберем некоторое начальное приближение x0 и сделаем из него шаг некоторой длины h: x1 = x0 + h. Если f(x1)>f(x0), то изменим направление шага и положим x1= x0 + h. Пусть теперь f(x1 )n)n-1). В рассматриваемом примере f(x4)>f(x3), следовательно минимум унимодальной функции лежит на отрезке [x4,x3] и его можно найти одним из методов, основанном на уменьшении интервала(метод общего поиска, деления отрезка пополам, золотого сечения).

Главное достоинство методов поиска отрезка, содержащего точку минимума состоит в том, что они основаны на вычислении только значений функции и, следовательно, не требуют вычисления производных. Но также есть и недостаток - скорость их сходимости невелика. Метод Свенна только значения функции f(x). Этот метод называется методом 0-го порядка.
7. Одномерная оптимизация. Метод Ньютона-Рафсона

Рассмотрим функцию f(x). Если предположить, что функция f(x) дифференцируема, то существуют методы, использующие производные. Методы, использующие вторую производную, называются методами 2-го порядка. Пусть f(x) дважды дифференцируема. Необходимым условием min функции является =0, где x*- минимум функции. А чтобы x* было именно min достаточно выполнения условия >0. Будем решать уравнение =0. Зададим некоторое начальное приближение x_k, построим квадратическую модель функции с помощью разложения в этой точки функции в ряд Тейлора. Получаем:

Если , то будет иметь единственную стационарную точку. Найти ее можно, для чего приравняем :.

Решим это уравнение относительно х и полученное решение запишем в виде x_k+1, как очередное приближение к min, т.е.

(*). Функцию (*) можно получить по-другому, если применить метод касательной, т.е. численный метод нахождения 0 функции g(0) =0, а g(x)=, тогда . Рассмотренный метод обычно называют методом Ньютона/ Ньютона – Рафсона.

Однако у метода есть недостатки: 1.Уравнение =0 может определить не только min, но и max.

2.Модельная функцияможет сильно отличаться от оптимизируемойи шаг

может оказаться слишком большим:

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

<, если оно выполняется, то переходим к следующему шагу и т.д. Если же >, а < 0, то должна первоначально уменьшится в направлении от к (это следует из квадратичной модели). Поэтому следующую точку можно найти, дробя шаг в обратном направлении, например, положив . Из основной формулы метода видно, что выражение отрицательное тогда и только тогда, когда > 0. Это гарантия существования подходящего направления шага, направленного в сторону минимума. С другой стороны, если<0 и >0, то первоначально увеличивается, поэтому шаг нужно сделать в противоположном направлении. Критерии останова для данного метода <ε, где ε - заданная точность.

8. Одномерная оптимизация. Квазиньютоновский метод.

Для нахождения минимума функции f(x) используют модифицированный метод Ньютона – квазиньютоновский метод. Этот метод не использует вычисления производных, все действия выполняются с помощью вычисления функции. Производные находят с помощью аппроксимации. Для начала выберем начальное приближение и малый шаг h. Будем изначально рассматривать три точки . Аппроксимируем производные:

, а вторая производная, следовательно, равна:

.

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

.

Метод имеет такие же недостатки: 1.Уравнение =0 может определить не только min, но и max.

2.Модельная функцияможет сильно отличаться от оптимизируемойи шаг

может оказаться слишком большим:

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

<, если оно выполняется, то переходим к следующему шагу и т.д. Если же >, а < 0, то должна первоначально уменьшится в направлении от к (это следует из квадратичной модели). Поэтому следующую точку можно найти, дробя шаг в обратном направлении, например, положив . Из основной формулы метода видно, что выражение отрицательное тогда и только тогда, когда > 0. Это гарантия существования подходящего направления шага, направленного в сторону минимума. С другой стороны, если<0 и >0, то первоначально увеличивается, поэтому шаг нужно сделать в противоположном направлении. Критерии останова для данного метода <ε, где ε - заданная точность.

9. Многомерная оптимизация. Рельеф функции. Метод покоординатного спуска.

Изложим этот метод на примере функций трех переменных F(x, y, z). Выберем нулевое приближение, x₀, y₀, z₀. Фиксируем значение двух координат y=y₀, z=z₀. Тогда функция будет зависеть только от одной переменной x; обозначим ее через f₁(x)=F(x, y₀, z₀). Используя какой-либо способ нахождения минимума функции одной переменной, отыщем минимум функции f₁(x) и обозначим его через x₁. Мы сделали шаг из точки (x₀, y₀, z₀) в точку (x₁, y₀, z₀) по направлению, параллельному оси x; значение функции на этом шаге уменьшилось. Теперь из новой точки сделаем спуск по направлению, параллельному оси y, то есть рассмотрим функцию f₂(y)=F(x₁, y₀, z₀), найдем ее минимум и обозначим его через y₁. Второй шаг приводит нас в точку (x₁, y₁, z₀). Из этой точки делаем третий шаг – спуск параллельно оси z и находим минимум функции f₃(z)=F(x₁, y₁, z₀). Приход в точку (x₁, y₁, z₁) завершает цикл спусков или первую итерацию. Далее будем повторять циклы. На каждом спуске функция не возрастает, и при этом значение функции ограничено снизу ее значением в минимуме F^*=F(x^*, y^*, z^*). Следовательно, итерации сходятся к некоторому пределу . Будет ли здесь иметь место равенство, то есть, сойдутся ли спуски к минимуму, зависит от функции и выбора нулевого приближения.

Геометрическая иллюстрация будет следующей: будем двигаться по выбранному направлению, по некоторой прямой в плоскости XY.

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

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

Рельеф функции

Понятие "рельеф функции" удобно рассмотреть на примере функции двух переменных z=F(x, y). Эта функция описывает некоторую поверхность в трехмерном пространстве с координатами x, y, z. Задача F(x, y)->min означает поиск низшей точки этой поверхности.

Как в топографии, изобразим рельеф этой поверхности линиями уровня. Проведем равностоящие плоскости z=const и найдем линии их пересечения с поверхностью F(x, y). Проекции этих линий на плоскость XY называют линиями уровня. Направление убывания функции будем указывать штрихами рядом с линиями уровня. По виду линий уровня условно выделим три типа рельефа: котловинный, овражный и неупорядоченный.

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

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

10. Метод оврагов Случайный поиск

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

Теперь выберем другую точку  не слишком далеко от первой. Из нее также сделаем спуск и попадем в некоторую точку . Эта точка тоже лежит вблизи дна оврага. Проведем через точку  и  на дне оврага прямую – приблизительную линию дна оврага, передвинемся по этой линии в сторону убывания функции и выберем новую точку  на этой прямой, на расстоянии h от точки r₁. Величина h называется овражным шагом и для каждой функции подбирается в ходе расчета.

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

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

Случайный поиск

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

Действительно, пусть  и диаметр котловины около минимума составляет 10% от пределов изменения каждой координаты. Тогда объем этой котловины составляет  часть объема n- мерного параллелепипеда. Уже при числе переменных  практически ни одна точка в котловину не попадет.

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

11. Многомерная оптимизация. Градиентный метод. Метод наискорейшего спуска.

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

 или

Где – норма градиента и, соответственно,– единичный вектор.

(В качестве нормы вектора u можно выбрать так-называемую Гауссову норму .)

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

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

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

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

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

Найдем точку  из условия минимума квадратичной модели. Необходимым условием этого минимума будет . Имеем:

и это приводит к следующему алгоритму:

на каждой итерации k решить систему уравнений

, относительно  и положить  (4.7)

Этот алгоритм называется методом Ньютона. Положительной стороной метода Ньютона является то, что если  достаточно близко к точке локального минимума  функции f(х) с невырожденной матрицей Гессе , то, как можно доказать,  является положительно определенной и последовательность , генерируемая алгоритмом Ньютона будет сходиться к минимуму  (и скорость сходимости будет q-квадратичной).

К недостаткам метода относятся:

1. 
   Метод не сходится глобально, то есть требует достаточно хорошее начальное приближение ;
   
2. 
   Требует аналитическое задание первых и вторых производных;
   
3. 
   На каждом шаге необходимо решать систему уравнений (4.7);
   
4. 
   В методе Ньютона нет ничего, что удерживало бы его от продвижения в сторону максимума или седловой точки, где  тоже равен нулю.
   

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

Вообще говоря, метод Ньютона не обладает высокой надежностью.

13. Метод Марквардта

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

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

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

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

В соответствии с методом Марквардта, направление поиска  определяется равенством

(1), а новая точка  задается формулой .

В системе (1) I – единичная матрица, – матрица Гессе, .

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

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

Таким образом, большим значением  соответствует направление поиска

то есть направление наискорейшего спуска.

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

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

Приведем теперь алгоритм метода:

1. 
   Задать  – начальное приближение к , M-максимально допустимое количество итераций и – параметр сходимости.
   
2. 
   Положить .
   
3. 
   Вычислить .
   
4. 
   Проверить ||||. Можно взять |||| = . Если да, то перейти к п.11.
   
5. 
   Проверить ? Если да, то перейти к п.11.
   
6. 
   Вычислить шаг , решив систему .
   
7. 
   Положить .
   
8. 
   Проверить: . Если да, то перейти к п.9, иначе к п.10.
   
9. 
   Положить ,. Перейти к п.3.
   
10. 
    Положить . Перейти к п.6.
    
11. 
    Вывод результатов: , k
    

14. Задачи с ограничениями. Поиск оптимума в задачах с ограничениями типа равенств. Метод неопределенных множителей Лагранжа.

Рассмотрим задачу:

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

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

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной минимизации:

Функция называется функцией Лагранжа. Здесь – множитель Лагранжа.

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

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

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

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

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

Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств: , .

Функция Лагранжа принимает вид .

Здесь – множители Лагранжа, то есть неизвестные параметры, значения которых нужно определить. Приравнивая частные производные L по нулю, получаем следующую систему.

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

. Решение расширенной системы, состоящей из N+K уравнений с N+K неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции Лагранжа, рассматриваемой как функция от x.

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

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

Рассмотрим задачу условной оптимизации или нелинейного программирования
, которая имеет ограничения:

, ,. (
Говорят, что точка x соответствует допустимому решению задачи нелинейного программирования, если для нее выполняются все ограничения.
Предполагается, что для вектора x^*, являющегося решением задачи нелинейного программирования, известно некоторое начальное приближение x⁰ , возможно недопустимое. В методах штрафных функция строится последовательность точек x^m, m=0,1,...,M, которая начинается с заданной точки x⁰ и заканчивается точкой x^M, дающая наилучшее приближение к x^* среди всех точек построенной последовательности. В качестве x^m берутся точки решения вспомогательной задачи безусловной минимизации, полученной с помощью преобразования исходной целевой функции с помощью штрафных функций. В этих методах исходная задача условной оптимизации преобразуется в последовательность задач безусловной оптимизации.

Методы штрафных функций классифицируются в соответствии со способами учета ограничений-неравенств. В зависимости от того, являются ли элементы последовательности x^m допустимыми или недопустимыми точками, говорят о методах внутренней и внешней точки соответственно. Если последовательность x^m содержит точки обоих типов, метод называют смешанным.
Основная идея метода штрафных функций заключается в следующем. Строят вспомогательную функцию , такую, что приближенное решение основной задачи получается в результате решения последовательности задач безусловной минимизации функции .
В методе внешних штрафных функций функции H, G выбираются таким образом, чтобы они становились отличными от нуля (положительными) при нарушении соответствующего ограничения. А так как мы минимизируем вспомогательную функцию, то движение в сторону нарушения становится невыгодным. Внутри допустимой области в данном методе функции H и G должны быть равны нулю. Например, для ограничений неравенств G_j(g_i(x))→0, при g_i(x))→0⁺ .
Приближенное решение задачи получается в результате решения последовательности задач минимизации вспомогательной функции при r_j,l_k→∞,j=1,...,J, k=1,...,K. Соответствующие методы называют методами внешней точки.

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

В методе барьерных функций функции H, G выбираются отличными от нуля в допустимой области и такими, чтобы при приближении к границе допустимой области (изнутри) они возрастали, препятствуя выходу при поиске за границу области. В этом случае эти функции должны быть малыми (положительными или отрицательными) внутри допустимой области и большими положительными вблизи границы (внутри области). Например, для ограничений неравенств , G_j(g_i(x))→∞, при g_i(x))→0^-.
Такие методы называют еще методами внутренней точки. В алгоритмах, использующих функции штрафа данного типа, требуют, чтобы в процессе поиска точка x всегда оставалась внутренней точкой допустимой области. Приближенное решение поставленной задачи получается в результате решения последовательности задач минимизации при r_j,l_k→∞,j=1,...,J, k=1,...,K.
Для ограничений-равенств при выборе функций штрафов обычно требуют, чтобы H_k(h_k(x))→0 , при h_k(x)→0.

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

Последовательность действий при реализации методов штрафных функций или барьерных функций выглядит следующим образом:
1. На основании задачи (5.4-5.7) строим функцию (5.8). Выбираем начальной приближение x и начальные значения коэффициентов штрафа r_j,l_k, число итераций, точность безусловной оптимизации, точность соблюдения ограничений и т.д.
2. Решаем задачу минимизации вспомогательной функции.
3. Если полученное решение не удовлетворяет системе ограничений в случае использования метода штрафных функций, то увеличиваем значения коэффициентов штрафа и снова решаем эту задачу. В случае метода барьерных функций значения коэффициентов уменьшаются, чтобы можно было получить решение на границе.
4. Процесс прекращается, если найденное решение удовлетворяет системе ограничений с определенной точностью.

16. Поиск оптимума в задачах с ограничениями. Метод факторов.

Своеобразным и очень эффективным методом штрафов является метод факторов (или множителей), который основан на штрафе типа "квадрат срезки" для ограничений-неравенств.
Такой штраф определяется следующим образом , где срезка t определяется так:
Этот штраф внешний и стационарные точки функции Q(x,R) могут оказаться недопустимыми. С другой стороны, недопустимые точки не создают в данном случае дополнительных сложностей по сравнению с допустимыми. Различие между ними состоит лишь в том, что в допустимых точках штраф равен нулю.
В методе факторов на каждой итерации производится безусловная минимизация функции

, где R - постоянный весовой коэффициент, а угловые скобки обозначают операцию срезки. Параметры (факторы) σ_j и ì_k осуществляют сдвиг штрафных слагаемых. Компоненты векторов σ и ì меняются по ходу вычислений, однако в процессе решения каждой вспомогательной безусловной задачи оба эти вектора остаются постоянными. Начальные значения факторов σ и ì можно выбрать нулевыми. Обозначим через x^m точку минимума функции , используемой на m-ой итерации.
При переходе к (m+1)-й итерации факторы пересчитываются по формулам
, .
Формулы пересчета таковы, что в результате сдвига при переходе к новой подзадаче штраф за нарушение ограничений возрастает, и вследствие этого точки x^m приближаются к допустимой области.
Для контроля сходимости метода используют последовательности x^m, σ^m , ì^m , f(x^m ), g(x^m ), h(x^m). Прекращение основного процесса происходит, когда члены, по крайней мере, одной из этих последовательностей, перестают изменяться при пересчете факторов и последующей безусловной минимизации. Заметим, что величина положительного параметра R влияет на свойства метода, но конструктивного алгоритма его выбора не существует.


17. Линейное программирование. Постановка задач. Основная (каноническая) задача и сведение к ней произвольной задачи.

Постановка задачи. Основная задача линейного программирования состоит в следующем. Задана система

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

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

Таким образом, будем рассматривать случай .

Каждую задача линейного программирования можно свести к форме основной задачи. Для этого нужно: 1. Уметь сводить задачу максимизации к задаче минимизации.

2. Уметь переходить от ограничений, заданных в виде неравенств, к эквивалентным им ограничениям-равенствам.

1. Форма F достигает наибольшей величины при тех же самых значениях неизвестных , при которых форма F₁=-F достигает наименьшей величины. Следовательно, максимизация формы F равносильна минимизации формы F₁=-F. Тем самым задача максимизации сводится к задаче минимизации.

2. Допустим теперь, что среди ограничений задачи имеется некоторое неравенство. Его всегда можно записать в виде .(*)

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

18. Линейное программирование. Преобразование основной задачи к основной задаче ЛП с ограничениями-неравенствами (форма А).

Рассмотрим систему ограничений-равенств основной задачи

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

(**)

Полученная система эквивалентна системе основной задачи.

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

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

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

Для свободных неизвестных также записываем ограничения и переходим к системе

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

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

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

19. Линейное программирование. Геометрическое решение двумерных задач. Основная теорема о решении задачи ЛП.

Основная задача линейного программирования состоит в следующем. Задана система

(6.10)
m линейных алгебраических уравнений с n неизвестными x₁,...,x_n и линейная форма относительно этих же неизвестных:

F = c₁x₁ + ... + c_nx_n. (6.11)
Условия в системе (10) могут быть заданы также в форме неравенств.
Требуется среди всех неотрицательных решений системы (10) выбрать такое, при котором форма F принимает наименьшее значение (минимизируется).

Определение: Система (6.10) называется системой ограничений данной задачи.

Сами равенства (6.10) называются ограничениями-равенствами. Отметим, что кроме ограничений-равенств в основу задач входят также ограничения-неравенства x₁≥0,...,x_n≥0

Определение: Всякое неотрицательное решение x₁⁽⁰⁾,...,x_n⁽⁰⁾(x_i⁽⁰⁾≥0; i=1,...,n) системы (6.10) назовем допустимым. Допустимое решение часто называют планом задачи линейного программирования.

Геометрическое решение двумерных задач 

Геометрический смысл основной задачи линейного программирования становится предельно прозрачным, если перейти от нее к эквивалентной ей задаче с ограничениями-неравенствами, то есть  к задаче (А):

Дана система

                                                            

содержащая n= k = r линейных неравенств относительно k неизвестных x₁,...,x_k, и линейная форма

                                                                  

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

Будем рассматривать двумерный случай, то есть в системе и линейной форме присутствуют только x1 и x2.

Введем на плоскости прямоугольную декартову систему координат x₁Ox₂. Известно, что геометрическое место точек на плоскости, координаты которых удовлетворяют системе линейных неравенств, образует выпуклый многоугольник. Этот многоугольник называется многоугольником решений данной системы неравенств. Стороны этого многоугольника располагаются на прямых, уравнения которых получаются, если в неравенствах системы знаки неравенств заменить точными равенствами. Сам же этот многоугольник есть пересечение полуплоскостей, на которые делит плоскость каждая из указанных прямых.

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

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

Далее рассмотрим линейную форму, запишем её в следующем виде:

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

Например

С1 > С2 > С3

Вектор g показывает направление уменьшения линейной формы, что для нашей задачи является нужным направлением. Задача теперь сводится к тому, чтобы найти линию с минимальным С в рамках найденной области. То есть будем сдвигать линию линейной формы по направлению g, пока линия еще находится в допустимой области. В нашем случае процесс остановится, когда линия будет проходить через точку Q, так как при дальнейшем смещении линии выйдет из приемлемой области. Получаем, что решением будет значения x1 и x2 в точке Q.

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

Выпуклая комбинация – линейная комбинация с неотрицательными коэффициентами.