Материал: Исследование оптимизационных задач электроснабжения электрифицированных железных дорог

                                                                                           (2.6)

имеет вид, показанный на рис. 2.1.

Рис. 4.1. Нелинейная целевая функция  и ее представление линиями равного уровня

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

                                                                                       (2.7)

Полученные замкнутые кривые Z = const называются линиями равного уровня целевой функции Z. Напомним, что для линейной задачи линии равного уровня Z=const представляли собой прямые линии (рис. 2.2).

Таким образом, нелинейную функцию двух переменных Z(х1, х2) можно представить в двумерной плоскости х1, х2 линиями равного уровня Z=const. Эти концентрические линии стягиваются в точку с координатами х10 и х20, являющуюся минимумом целевой функции Z.

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

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

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

Как и в случае линейной задачи, система ограничений (4.2) образует в пространстве переменных х1, и х2 область  допустимых значений переменных. В общем случае эта область представляет собой замкнутый многогранник (многогранник аbс на рис. 2.2) с прямолинейными и криволинейными гранями.

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

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

2.3 Градиентные методы

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

                                          (2.8а)

где - единичные вектора (орты).

Величина этого вектора определяется по выражению

            (2.8)

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

Физический смысл градиента функции в том, что он показывает направление (2.8а) и скорость (2.8) наибольшего изменения функции в рассматриваемой точке. Если в некоторой точке , функция в этой точке не изменяется (не возрастает и не убывает). Эта точка соответствует экстремуму функции.

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

Этот минимум находится в точке с координатами x10 и x20.

В соответствии с граничными условиями (2.5) областью  допустимых значений переменных будет первый квадрант системы координат и х1 и х2. В этой области произвольно выберем исходное (нулевое) приближение - точку с координатами . Значение целевой функции в этой точке составляет Z0. В соответствии с выражением (2.8) вычислим в этой точке величину градиента функции Z.

Рис. 2.3 Иллюстрация градиентного метода с постоянным шагом l=1

Выполним шаг единичной длины (l=1) в направлении убывания функции Z. В результате выполненного шага получим первое приближение - точку с координатами . Значение целевой функции в этой точке составляет Z1.

Далее вычислительная процедура повторяется: последовательно получаем 2-е, 3-е и 4-е приближения - точки с координатами ;  и . Значения целевой функции в этих точках соответственно составляют Z2, Z3 и Z4.

Из рис. 2.3 видно, что в результате вычислительного процесса последовательно осуществляется "спуск" к минимуму функции Z. Вычислительная процедура заканчивается, когда относительное изменение целевой функции на предыдущем i-м и последующем (i+1)-м шагах оказывается меньше заданной точности вычислений е:

                                                                         (2.9)

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

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

Таким образом, точность и объем вычислений в градиентном методе с постоянным шагом определяются величиной этого шага.

Метод покоординатного спуска. Как и в предыдущем методе, выберем исходное (нулевое) приближение - точку с координатами  (рис. 2.4). Значение целевой функции в этой точке составляет z . В соответствии с выражением (2.8) вычислим частные производные целевой функции Z. Из совокупности частных производных выберем наибольшую по модулю производную. Пусть это будет производная  Следовательно, в направлении переменной х2 функция Z имеет наибольшее изменение. Если производная положительная, при увеличении переменной х2 функция увеличивается. Если производная отрицательная, при увеличении переменной х2 функция уменьшается.

Рис. 2.4 Иллюстрация метода покоординатного "спуска"

Осуществляем "спуск" по переменной х2 в направлении уменьшения целевой функции (выполняем единичные шаги ). Последовательно получаем 1-е, 2-е, 3-е приближения - точки с координатами  На каждом шаге вычисляем значение целевой функции:  Пусть

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

Из точки с координатами  продолжаем "спуск" в направлении другой переменной х1 Единичные шаги () в направлении переменной Xi выполняются до тех пор, пока целевая функция не начнет увеличиваться Получаем точки с координатами

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

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

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

Один из способов определения оптимальной длины шага  иллюстрируется на рис. 2.5 и носит название метода скорейшего "спуска".

Рис. 2.5 Иллюстрация метода скорейшего "спуска" (а) и параболическая аппроксимация целевой функции для выбора оптимального шага (б)

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

принимается исходное (нулевое) приближение ;

вычисляется значение целевой функции в этой точке Z0;

в соответствии с выражением (2.8) для этой точки вычисляется grad Z.

Из исходной точки в направлении убывания целевой функции выполним два единичных шага (). В конце каждого шага вычислим значения целевой функции Z1 и Z2.

Итак, имеем три значения целевой функции Z0,Z1 и Z2, отвечающие нулевой (l=0), единичной (l=1) и двойной (l=2) длинам шага (рис. 2.5,6). Эти три значения характеризуют сечение целевой функции Z в выбранном направлении "спуска".

Известно, что через три точки можно провести единственную параболу

                                                                          (2.10)

где а, b, с - постоянные коэффициенты.

Определим координату минимума этой параболы, для чего приравняем к нулю первую производную функции (4.10) по переменной l

                                                                 (2.11)

откуда l = -b/2а.

Полученное значение и будем считать оптимальной длиной шага lопт.

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

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

Из точки с координатами  вычислительная процедура повторяется. Получаем следующее приближение - точку с координатами  и значением целевой функции Z2 . Процесс продолжается до достижения требуемой точности в соответствии с соотношением (2.9).

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

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

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

                                                                           (2.12)

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

Рис. 2.6. Иллюстрация метода проектирования градиента

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

в области W принимается исходное (нулевое) приближение ;

вычисляется значение целевой функции в этой точке z ;

в соответствии с выражением (2.8) в этой точке вычисляется градиент целевой функции grad Z;

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

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