5.2.5.2. Функции многих переменных

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

а) покоординатный спуск к точке минимума;

б) случайный поиск.

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

Min4(f,x,d,) n ← Last(x), a ← x, ym ← f(x), k ← 0

while d > 

j ← 0

for i  0 . . n

for h  - d, d

a _i ← x _i + h, q ← f(x)

if q < ym

ym ← q, j ← j + 1

x _i ← a _i

d ← if (j = 0, 0.5  d, 1.2  d)

k ← k + 1

Пример 2. Фиксируем n , положим i 0 . . n - 1 и определим функцию (Розенброка) f(x) 100  (x ₀ - 1) ⁴ + (x _i - (x _{i - 1}) ²) ² с ми-нимумом в точке x _i = 1,  i. Возьмем в качестве стартовой точки нача-ло координат, d = 1,  = 0.0001. Положим r1 Min4(f, x, d, ), тогда при n = 4 получим:

r1 ₀ = r1 ₂ = 685 (сравните: minimize (f, x) = ), неплохо по сравнению со встроенной функцией.

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

Minran(f, x, d, ) m ← lenght(x), k ← 1, fm ← f(x)

while d > 

q ← fm + 1

while q > fm

s ← x + runif(m, -d, d)

q ← f(s), k ← k + 1

d ← if(|s - x| < 0.4  d, 0.8  d, 1.2  d)

x ← s, fm ← q

Здесь использована функция lenght(x), возвращающая длину вектора х, а также функция runif(m, a, b), возвращающая вектор длины m случайных чисел, равномерно распределенных на интервале (а, b). В условиях предыдущего примера получаем: r2 Minran(f, x, d, ) r2 ₀ = r2 ₂ = 7944 (для случайностей тоже неплохо).

С использованием производных наиболее популярны два мето-да: метод антиградиента (наискорейшего спуска) и метод сопряжен-ных направлений. Познакомимся с первым. Так как производная функ-ции f : ℝ → ℝ определяет вектор Df = как направ-ление наибольшего возрастания функции, то естественно двигаться к точке минимума в противоположном направлении. Ради экономии вычислений движение в выбранном направлении осуществляется до тех пор, пока функция не перестанет убывать. Тогда находится новое направление и процесс повторяется пока перемещение больше задан-ного уровня чувствительности. Если D(x) - вектор частных производ-

ных функции f , то процедуру поиска минимума можно оформить так:

Min5(D, x, e) d ← 1, k ← 0

while (d > e)  (k < 130)

y ← x, k ← k + 1

h ← D(x), t ← 0

t ← root(D(x - t  h)  h, t)

x ← x - t  h, d ← |y - x|

x

Производную можно вычислить непосредственно, случайным поис-

ком, либо с помощью программы-функции (пример 7 п. 5.1).

В условиях предыдущего примера имеем Min5(D, x, e) =

5.2.5.2.2. Задачи с ограничениями. Полезно рассматривать огра- ничения двух типов: ограничения типа равенств G(x) = 0 и ограниче-ния типа неравенств G(x)  0. Будем для простоты рассматривать не-вырожденный случай: при ограничениях-равенствах будем считать rank DG(x) = dim G(x), при ограничениях-неравенствах  : G() < 0. Тогда при ограничениях типа равенств задача эквива-лентна задаче f(x) + G(x) → min без ограничений на х и . Век-тор  называется (вектором-) множителем Лагранжа, а функция

ℒ(x, ) = f(x) + G(x) - функцией Лагранжа.

При ограничениях-неравенствах популярен метод штрафов. По-лагая G = (g ₁ , g ₂ , ... , g _m), можно рассматривать G ₊ = (g ₁₊, g ₂₊, ... ,g _m+) при g ₊ = 0.5(g + |g|) (положительная часть) и функцию f(x) + G(x), так что если

x^*: f(x^*) = , x^*_: f(x^*_) + G(x^*_) = { f(x) + G₊(x) }, то x^* = . Это так называемый "внешний штраф", здесь старто-вая точка поиска может быть произвольной, но и точность поиска от-носительно невысока. Для непосредственного поиска можно использо-вать методы, оговоренные выше. Рассмотрим пример использования встроенных блоков.

Пример 3. Пусть требуется найти расстояние между сферой х ² +у ² + z ² = 4 и плоскостью x + 2y + 3z = 10 - тривиальная аналити-ческая задача с решением . Определим функцию f(x,y,z,u,v,w) = = (x - u) ² +(y - v) ² +(z - w) ² (квадрат искомого расстояния) и ограни- чения g1(x, y, z) = x ² + y ² +z ² - 4, g2(u, v, w) = u +2v + 3w - 10 и для задачи запишем функцию Лагранжа

ℒ(x, y, z, u, v, w, m, n) = f(x, y, z, u, v, w) + mg1(x, y, z) + ng2(u, v, w). Функция легко дифференцируема по всем аргументам, поэтому сразу

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

x 1 y1 z 1 u 1 v 1 w 1

Given

x - u + m  x = 0 y - v + m  y = 0

z - w + m  z = 0 - 2  (x - u) + n = 0

- 2  (y - v) + 2  n = 0

- 2  (z - w) + 3  n = 0

x ² + y ² + z ² = 4 u + 2  v + 3  w = 10

r Find(x, y, z, u, v, w, m, n)

r ^T = (0.5345 1.0690 1.6036 0.7143 1.4286 2.1429 0.3365 - 0.3595)

f(r₀, r₁, r₂, r₃, r₄, r₅) = 0.452407 (точное значение 0.452407)

Непосредственное использование блока Given ... minimize дает нес-

колько худший результат (но проще использование):

Given

g1(x, y, z) = 0

g2(u, v, w) = 0

s minimize(f, x, y, z, u, v, w)

f(s₀, s₁, s₂, s₃, s₄, s₅) = 0.452744

Пример 4. Для иллюстрации ограничений-неравенств найдем ре-шение задачи , где F(x, y) = 2 – 7x² + 2 x y – y² + x – y :

x := 10 y := 10

Given

x + 1  0

2  x - y  4

x + y  4

Minimize(F,x,y) = (точное решение: х = - 1, у = 5).