Основы вычислительной математики. Денисова Э.В - 138 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

.,...,,
21
⎭
⎬
⎫
⎩
⎨
⎧
∂
∂
∂
∂
∂
∂
=
n
x
f
x
f
x
f
fgrad
Формулы для частных производных можно получить в явном виде лишь в том случае, когда целевая
функция задана аналитически. В противном случае эти производные вычисляются с помощью численного
дифференцирования:
()()
[]
n. ..., 2, ,1 ,,...,,...,,...,,...,
1
11
=−Δ+
Δ
≈
∂
∂
ixxxfxxxxf
xx
f
ninii
ii
При использовании градиентного спуска в задачах оптимизации основной объем вычислений приходится
обычно на вычисление градиента целевой функции в каждой точке траектории спуска. Поэтому
целесообразно уменьшить количество таких точек без ущерба для самого решения. Это достигается в
некоторых методах, являющихся модификациями градиентного спуска. Одним из них является метод
наискорейшего спуска. Согласно этому методу, после определения в начальной точке направления,
противоположного градиенту целевой функции, в этом направлении делают не один шаг, а двигаются до тех
пор, пока целевая функция убывает, достигая таким образом минимума в некоторой точке. В этой точке снова
определяют направление спуска (с помощью градиента) и ищут новую точку минимума целевой функции и т.
д. В этом методе спуск происходит гораздо более крупными шагами и градиент функции вычисляется в
меньшем числе точек.
Заметим, что метод наискорейшего спуска сводит многомерную задачу оптимизации к последовательности
одномерных задач на каждом шаге оптимизации, как и в случае покоординатного спуска. Разница состоит в
том, что здесь направление одномерной оптимизации определяется градиентом целевой функции, тогда как
покоординатный спуск проводится на каждом шаге вдоль одного из координатных направлений.
§ 4. Задачи с ограничением. Метод штрафных функций. Линейное программирование.
Геометрический метод. Симплекс метод.
4.1 Метод штрафных функций. Решение задач математического программирования значительно более
трудоемко по сравнению с задачами безусловной оптимизации. Ограничения типа равенств или неравенств
требуют их учета на каждом шаге оптимизации. Одним из направлений в методах решения задач
математического программирования является сведение их к последовательности задач безусловной
минимизации. К этому направлению относится, в частности, метод штрафных функций.
Сущность метода состоит в следующем. Пусть j(x
1
, х
2
, ..., х
n
) — целевая функция, для которой нужно найти
минимум m в ограниченной области D (x
1
, x
2
, ..., x
n
∈
D). Данную задачу заменяем задачей о безусловной
минимизации однопараметрического семейства функций
{}
.,...,, ),(
1
)(),(
21 n
xxxxxxfxF =+=
ϕ
β
β
(9.12)
При этом дополнительную (штрафную) функцию
)(x
ϕ
выберем таким образом, чтобы при
0→
β
решение
вспомогательной задачи стремилось к решению исходной или, по крайней мере, чтобы их минимумы
совпадали:
0. при ),(min →→
β
β
mxF
Штрафная функция
)(x
ϕ
должна учитывать ограничения, которые задаются при постановке задачи оптими-
зации. В частности, если имеются ограничения-неравенства вида g
j
(x
1
, x
2
, ..., х
п
)>0 (j=1, 2, ...,J), то в качестве
штрафной можно взять функцию, которая: 1) равна нулю во всех точках пространства проектирования,
удовлетворяющих заданным ограничениям-неравенствам; 2) стремится к бесконечности в тех точках, в
которых эти неравенства не выполняются. Таким образом, при выполнении ограничений-неравенств функции
f(x) и F(x, β) имеют один и тот же минимум. Если хотя бы одно неравенство не выполнится, то
вспомогательная целевая функция F(x, β) получает бесконечно большие добавки, и ее значения далеки от
минимума функции f(x). Другими словами, при несоблюдении ограничений-неравенств налагается «штраф».
Отсюда и термин «метод штрафных функций».
Теперь рассмотрим случай, когда в задаче оптимизации заданы ограничения двух типов — равенства и нера-
венства:
{}
.,...,, ; ..., 2, 1, ,0)(
; ..., 2, 1, ,0)(
21 nj
i
xxxxJjxh
Iixg
==≥
=
=
(9.13)
В этом случае в качестве вспомогательной целевой функции, для которой формулируется задача безусловной
оптимизации во всем n-мерном пространстве, принимают функцию
[]
.0
,)( 1)()(
1
)(),(
11
22
>
⎩
⎨
⎧
−++=
∑∑
==
β
β
β
I
i
J
j
jii
xhsignxhxgxfxF
(9.14)

Страницы