Многомерные задачи оптимизации.

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

Min дифференциальной функции многих переменных

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

(9.1)

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

Свели задачу к минимуму ц.ф.

- полная поверхность контейнера.

Решение: В соответствии с (9.1) получим систему

Отсюда

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

Этот метод можно использовать лишь для дифференциальной ц.ф.

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

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

Для решения подобной задачи в области проектирования G можно дискретное множество точек (узлов) путем разбиения интервалов изменения параметров на части с шагами соответственно.

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

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

Пусть требуется найти наименьшее значение ц.ф.

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

(9.2)

где - некоторый шаг.

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

Действительно, пусть

Тогда с ростом функция возрастает, а (9.2) определяет движение в сторону уменьшения .

Значение можно найти иначе:

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

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

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

Или

Или

Близость ц.ф.

(9.3)

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

Для случая n=2

Ц.ф.

Описывает некоторую поверхность в трех мерном пространстве.

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

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

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

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

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

, - единичные векторы в направлении координатных осей.

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

Методы, основанные на выборе пути оптимизации с помощью градиента, называется градиентными.

Идея метода градиентного спуска:

Выбираем некоторую начальную точку

, ,

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

Делаем шаг в направлении, обратном градиентному

В результате приходим в точку :

Значение функции ;

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

Повторяем процедуру в новой точке: вычисляем grad и снова делаем шаг в обратном к нему направлении:

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

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



Недостаток метода градиентного спуска.

Такой же, как у метода покоординатного спуска: при существовании оврагов на поверхности сходимость метода очень медленная.

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

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

i=1,…,n

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

Один из таких методов – метод наискорейшего спуска.

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

Ищем min функции:

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

Для случая ц.ф. двух переменных z=f(x,y):

1. 
   gradz касательной к линии уровня в данной точке.
   
2. 
   в точке, в которой достигается min ц.ф. вдоль направления, производная ц.ф. по этому направлению обращается в 0.
   

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

Задачи с ограничениями.

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

Например, Метод штрафных функций.

Сущность метода:

Пусть - ц.ф., для которой необходимо найти min m в ограниченной области

Заменяем данную задачу задачей безусловного минимума

,

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

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

В частности, если существуют ограничения неравенства вида

(j=1,…,J),

то в качестве штрафной можно взять функцию, которая:

1) = 0 во всех точках пространства проектирования, удовлетворяющих заданным ограниченным неравенствам.

2. 
   в тех точках, в которых эти неравенства не выполняются.
   

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

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

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

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

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

В этом случае точка достаточно близка к границе области В и с необходимой точностью описывает оптимальные значения проектных параметров. Если точка min находится внутри области D, то искомый результат будет получен сразу после 1-го шага, т.к. в данном случае =0.

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

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

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

Найти значения переменных , которые:

1. 
   удовлетворяют системе линейных уравнений:
   

(9.3)

2)являются не отрицательными

(9.4)
3)обеспечивают наименьшее значение линейной и ц.ф.

= (9.5)

Существует решение системы уравнений (9.3), удовлетворяющее системе неравенств (9.4), называется допустимым решением.

Допустимое решение, которое минимизирует и ц.ф. (9.5), называется оптимальным решением.

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

Автобаза обслуживает 3 овощных магазина, причём товар доставляется в магазин из 2-х плодоовощных баз. Нужно спланировать перевозки так, чтобы их общая стоимость была min.

Зададим исходные данные: Ежедневно вывозится с первой базы 12 т товара, со второй – 15 т. При этом завозится в первый магазин 8 т, во второй – 9 т, в третий – 10 т. Стоимость перевозки 1 т товара (в рубл.) с баз в магазины см. в табл.:

База	Магазин
	1	2	3
1	8	11	9
2	10	7	12

Решение: Обозначим через - количество товара, который нужно доставить с 1-й базы соответственно в 1-й, 2-й, 3-й магазины; через - количество товара, который нужно доставить со 2-й базы в те же магазины. Эти значения в соответствии с исходными данными должны удовлетворять следующим условиям:


(9.6)

Первые два уравнения описывают количество товара, вывозимое с 1-й и 2-й баз, а три последних - количество товара, завозимое в каждый магазин.

К данной системе уравнений необходимо добавить систему неравенств (9.7),

которая означает, что товар обратно из магазинов на базы не вывозится.

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

(9.8)

Таким образом, мы имеем типичную задачу линейного программирования: Найти оптимальные значения проектных параметров , удовлетворяющих условиям (9.6)-(9.7) и min общую стоимость перевозок (9.8).

Анализируем систему (9.6): первые 4 уравнения независимы, 5-е можно получить путём сложения 1-го и 2-го и вычитания из этой суммы 3-го и 4-го. Фактически имеем систему:

Число неизвестных больше числа уравнений, поэтому выразим через все остальные неизвестные:

(9.9)

Так как в соответствии с (9.7) все проектные параметры должны быть неотрицательны, то с учётом (9.9) получим следующую систему неравенств:

(9.10)

Эта система неравенств описывает все допустимые решения рассматриваемой задачи. Среди всех допустимых значений свободных параметров необходимо найти оптимальные, min ц.ф. f.

Формула (9.8) с учётом (9.9) примет вид

(9.11)

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

Очевидно, стоимость перевозок будет min, если величина примет наибольшее значение в рамках сделанного ограничения ().

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

В этом смысле минимальная общая стоимость перевозок равна 229 р.

Числа

указывают

количество

товара в

тоннах.