Минимальное изменение функции

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

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

Поэтому необходимо заранее выбирать, как будет завершен процесс поиска экстремума.

Поиск экстремума функции нескольких переменных. Если функция вычисляется от нескольких переменных, то для поиска ее минимума используется (после приблизительной оценки начальных приближений переменных в предполагаемом минимуме) команда [ x, y ]= fminsearch (имяФункции, вектор Начальных Приближений Переменных).

Минимум функции нескольких переменных z=f(x₁, x₂, …, x_n) осуществляет встроенная функция [X,Z]=fminsearch(name, x0, options) где:

· name имя М-функции вычисляющей z=f(x1, x2, …, xn),

· х0 вектор из n элементов, содержащих координаты точки начального приближения,

· options параметры управляющие ходом решения,

· Х вектор из n элементов, содержащий значения переменных, при которых функция z=f(x1, x2, …, xn) минимальна,

· Z это и есть минимальное значение функции.

Например, [X, Z]=fminsearch(@extr, [3 2]); где @extr обращение к М-функции extr, вычисляющей значение интересующей нас функции z=x₁²+x₂²-6x₂-2x₁+11, причем заданы начальные приближения [3 2] для х₁ и х₂ соответственно. В результате получим значения переменных в точке минимума и значение функции в минимуме.

>> [x,y]=fminsearch(@extr,[2 3]) x = 1.0000 3.0000 y = 1.0000

function z=extr(x) z=x(1)^2+x(2)^2-6*x(2)-2*x(1)+11; end

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

Пусть функция L (x ₁, x ₂, x ₃, x ₄)= x ₁ + x ₂ + x ₃ - x ₄ и надо найти ее максимум и соответствующие ее максимуму значения переменных.

Пусть даны ограничения в виде неравенств. x ₁ ≥0, x ₂ ≥0, x ₃ ≥0, x ₄ ≥0.

Пусть также даны еще ограничения в виде неравенств.

3 x ₁ - x ₂ ≤7, x ₂ -2 x ₃ ≤-1, 4 x ₃ - x ₄ ≤3, 5 x ₁ +2 x ₄ ≥14.

Для решения задачи линейного программирования (нахождения минимума) используется функция [ x, L, f ]= linprog (c, A, b, A 1, b 1, Lx, Rx) где x вектор значений переменных, полученный в качестве ответа;

L значение функции в минимуме;

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

  c функция цели представленная в виде вектора коэффициентов (в нашем случае [1 1 1 -1]), но так как нам нужен максимум,

а функция [ x, L, f ]= linprog (c, A, b, A 1, b 1, Lx, Rx) ищет минимум, то в выражении для функции поменяем знак, поэтому вектор коэффициентов будет [-1 -1 -1 1];

A, b система ограничений, заданная в матричном виде Ax ≤ b (это в нашей задаче ограничения 3 x ₁ - x ₂ ≤7, x ₂ -2 x ₃ ≤-1, 4 x ₃ - x ₄ ≤3, 5 x ₁ +2 x ₄ ≥14, но так как 5 x ₁ +2 x ₄ ≥14 не подходит, то надо поменять знак в этом неравенстве и тогда оно будет -5 x ₁ -2 x ₄ ≤-14, в таком случае матрица А состоит из коэффициентов (при переменных) в этих неравенствах, а столбец b состоит из правых (не содержащих переменных) частей неравенств;

A 1, b 1 система равенств вида A 1 x = b (в нашей задаче такой системы ограничений нету, но могла бы быть);

Lx, Rx относятся к ограничениям в виде Lx ≤ x ≤ Rx, Lx ≤ x, x ≤ Rx (в нашей задаче есть ограничения вида Lx ≤ x, поэтому вектор Lx будет 0 0 0 0).

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

function Start_linprog1 c=[-1;-1;-1;1]; A=[3 -1 0 0;0 1 -2 0;0 0 4 -1;-5 0 0 -2]; b=[7;-1;3;-14]; lx=[0;0;0;0]; [x,L,f]=linprog(c,A,b,[],[],lx) end

Optimization terminated x = 2.5882 0.7647 0.8824 0.5294 L = -3.7059 f = 1

Рассмотрим еще пример для тренировки. Пусть дана функция W = x ₁ + x ₂ +3 x ₃ - x ₄ и надо найти ее максимум. Пусть даны ограничения в виде неравенств.

x ₁ -5 x ₂ +4 x ₃ ≤5, x ₁ -2 x ₂ -3 x ₃ ≤4, x ₁ +6 x ₂ +5 x ₃ ≤4, x ₂ + x ₃ ≤1. И пусть есть еще ограничения в виде неравенств. x ₁ ≥0, x ₂ ≥0, x ₃ ≥0, x ₄ ≥0.

Решим задачу с помощью функции

[ x, L, f ]= linprog (c, A, b, A 1, b 1, Lx, Rx). Для ее применения нам надо подготовить аргументы функции.

Вектор с коэффициентов функции равен (1 1 3 -1), но так как функция linprog ищет минимум, а нам нужен максимум, то поменяем знак у коэффициентов функции и тогда вектор с будет (-1 -1 -3 1).

Матрица А состоит из коэффициентов при переменных в системе неравенств x ₁ -5 x ₂ +4 x ₃ ≤5, x ₁ -2 x ₂ -3 x ₃ ≤4, x ₁ +6 x ₂ +5 x ₃ ≤4, x ₂ + x ₃ ≤1.

Так как все они со знаком ≤ то ничего менять не требуется.

Вектор b состоит из правых частей этих же неравенств.

Матрица A 1 из системы A 1х= b 1 для нас не актуальна (нет таких условий). Lx, Rx относятся к ограничениям в виде Lx ≤ x ≤ Rx, Lx ≤ x, x ≤ Rx.

У нас есть ограничения в виде неравенств. x ₁ ≥0, x ₂ ≥0, x ₃ ≥0, x ₄ ≥0. Тогда вектор Lx =[0; 0; 0; 0]. Что касается остальных типов ограничений, то так как у нас нет таких ограничений, то для нас они не важны.

function Start_linprog_2 c=[-1;-1;-1;1]; A=[1 -5 4 0;1 -2 -3 0;1 6 5 0;0 1 1 0]; b=[5;4;4;1]; lx=[0;0;0;0]; [x,L,f]=linprog(c,A,b,[],[],lx) end

Optimization terminated. x = 4.0000 0.0000 0.0000     0 L = -4.0000 f = 1

Задачи нелинейного программирования. Нелинейная задача отличается от линейной. В ней есть система линейных неравенств Ax ≤ b, система линейных равенств A 1 x = b 1, система ограничений вида lx ≤ x ≤ rx, lx ≤ x, x ≤ rx.

Однако помимо этих уже знакомых (из линейного программирования) условий, есть еще система нелинейных ограничений вида g 1(x)≤0, и система нелинейных равенств g 2(x)=0.

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

[ x, y, f ]= fmincon (F, x 0, A, b, A 1, b 1, Lx, Rx, G), где F это M-функция exNotLinear, G это М-функция exGNotLinear, вычисляющая левые части нелинейных ограничений g 1(x)≤0, g 2(x)=0.

Если какие-то аргументы не определены, то вместо них в вызове функции ставятся квадратные скобки.

Рассмотрим для примера следующую задачу. Пусть дана функция x ₁ ² + x ₂ ² =1 при условии, что x ₁ x ₂ =4, x ₁ ≥0, x ₂ ≥0. Вектор начальных приближений примем равным х0=(0.1, 0.1).

Опишем функции exGNotLinear и exNotLinear.

function y=exNotLinear(x) y=x(1)^2+x(2)^2-1; end

function[g1,g2]=exGNotLinear(x) g1=[]; g2=x(1)*x(2)-4; end

Применим функцию [ x, y, f ]= fmincon (F, x 0, A, b, A 1, b 1, Lx, Rx, G).

function Start_fmincon1 x0=[0.1 0.1]; Lx=[0 0]; [x, y, f]=fmincon(@exNotLinear, x0, [],[],[],[],Lx,[],@exGNotLinear) end

x = 2.0000 2.0000 y = 7.0000 f = 1