Основные определения. Экстремумом функции многих переменных F(Х) называется ее минимальное или максимальное значение

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

Функция n переменных описывается поверхностью в (n+1)-мерном пространстве.

F F(X₁, X₂)

Fmin l₂

l₁

А

X^*₁ X₁

X^*₂ А^* l₂^*

X2 l₁^* Рис. 2.

Функция двух переменных F(X₁,X₂) представлена в трехмерном пространстве. На Рис.2. точке А с координатами (Х₁, Х₂) соответствует минимум функции F_min. Пересекая поверхность функции плоскостями, параллельными плоскости X1 - X2, получаем на ее поверхности ряд линий, которые называются линиями равного уровня. В каждой точке таких линий, функция имеет одно и то же значение. На Рис. 2. – линии l₁, l₂ .

Линия равного уровня – геометрическое место точек в пространстве независимых переменных Xi (i=1,2,..,n), в которых функция имеет одно и тоже значение F_j=const.

Количество линий равного уровня может быть бесконечным.

На плоскости Х₁ – Х₂ рассматриваем проекции точки минимума функции А^*, проекции линий равного уровня l₁^* , l₂^*, …

С поиском экстремума функции связана задача оптимизации. Она заключается в определении экстремального значения функции F(Х), с учетом ограничений, налагаемых на элементы n -мерного вектора параметров Х:

X ={ X ₁, X ₂,.., X _n}.

Функцию F(Х) называют целевой функцией.

При решении задачи оптимизации в первую очередь определяются значения параметров, при которых обеспечивается экстремум функции. На рисунке это соответствует координатам т. А^* (проекция min функции А на плоскость X₁- X₂).

Ограничения при оптимизации могут быть представлены в виде равенств и неравенств.

Ограничения в виде равенств: j(х)=0 - представляют собой уравнения или системы уравнений (линейные или нелинейные), которые связывают между собой параметры, являющиеся элементами вектора Х. В этом случае изменение любого из параметров, входящих в уравнение, приводит к соответствующему изменению остальных параметров (чтобы соблюдалось равенство). Например, в уравнении Х₁ + Х₂ - 10 = 0 при любом значении Х₁ (Н-р, 1, 5, 10, …) для соблюдения равенства, значения Х₂ могут принимать только соответствующие определённые значения (9, 5, 0, …). Т.е. параметры Х₁ и Х₂ в уравнении связаны между собой, возможности изменения их значений ограничены уравнением. Такие уравнения называют иногда уравнениями связи.

Ограничения в виде неравенств: X_i^min £ X_i £ X_i^max. Они определяют допустимый интервал изменения параметров. Например, допустимые пределы изменения напряжения в электрической сети U определяются в 5% от номинального U_н :

(U_н – 5% U_н)£ U £(U_н + 5% U_н)

Ограничения в виде неравенств образуют допустимую область D_x

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

Пример:

Целевая функция F(x₁,x₂)=x₁+2x₂-x₁x₂+100

Ограничения в виде равенств j(x₁,x₂)=x₁+x₂-10=0

Ограничения в виде неравенств 0 £ X₁£ 10

Нужно определить значения параметров х₁ и х₂, при которых достигается минимум целевой функции F(x₁,x₂) с учетом ограничений на значения параметров в виде равенств и в виде неравенств.

Абсолютным (безусловным) экстремумом называется точка экстремума функции без учета ограничений в форме неравенств (точка 1).

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

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

Общими методами решения задач оптимизации являются методы математического программирования. Математическое программирование при линейной целевой функции F(Х) и линейных ограничениях в виде равенств называется линейным программированием. Математическое программирование при нелинейной целевой функции F(x) или нелинейных ограничениях в виде равенств называется нелинейным программированием.

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

В этих методах задается исходная точка Х₀ с координатами (Х₁⁽⁰⁾, Х₂⁽⁰⁾,…,Х_n⁽⁰⁾). Для достижения искомой точки минимума выполняется ряд последовательных шагов D Х ^(к) в пространстве параметров. На каждом шаге решается задача выбора направления шага и его длины. Способом выбора длины и направления различаются методы оптимизации. После выполнения очередного шага получаем координаты следующей точки Х ^(к+1):

Х^(к+1) = Х^(к)+D Х^(к) .

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

x₂

Х^*

Х⁽⁰⁾

X₂⁽⁰⁾

X₁ ⁽⁰⁾ X₁

Методы перебора

Это простейшие из методов. Вся допустимая область D представляется в виде многомерной (равномерной) сетки. Узлы этой сетки соответствуют дискретным значениям Х. Вычисляются значения функции в каждом из узлов, и выбирается экстремальное из них F(x₁^(к), x₂^(k))

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

Метод не эффективен при большом количестве n и обширных областях D.

Более эффективны методы направленного перебора и среди них метод покоординатной оптимизации.

В любом из методов, при выполнении шага оптимизации X₁⁽¹⁾ = X₁⁽⁰⁾+D X₁

каждая новая точка должна быть лучше предыдущей:

F(x₁⁽¹⁾, x₂⁽¹⁾)< F(x₁⁽⁰⁾, x₂⁽⁰⁾),

F(x₁⁽²⁾, x₂⁽²⁾)< F(x₁⁽¹⁾, x₂⁽¹⁾), ….

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

X₂ В методах покоординатной

оптимизации шаги оптимизации

выполняются вдоль осей координат.

X^*

X₂⁽⁰⁾

X₂⁽¹⁾

X₁

X₁⁽⁰⁾ X₁⁽¹⁾ X₁⁽²⁾ X₁⁽³⁾