(!i ui)(xi !i) > 0

для всех xi, для которых выполняется

i 6 xi 6 i i = 1; 2; :::; n

Отсюда суммируя по индексу i от 1 до n получим, что

< ! u; x ! >> 0x 2 X

Следовательно, построенная точка !является проекций точки u на множество X

21.8Метод покоординатного спуска для отыскания условного экстремума

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

f(x) ! minx 2 X = fx1; :::; xn; ai 6 xi 6 bi; i = 1; 2:::; ng

Рассмотрим метод покоординатного спуска без вычисления производных. Так как производные @f(xkn+s)

@xs

не вычисляются, то вычисления происходят по следующей схеме: выбирается esнаправление и проверяются условия

(

xkn+s kn+ses 2 X

(4:20)

f(xkn+s kn+ses) < f(xkn+s)

Если оба условия (4:20) выполняются , то приближение xkn+s+1определяется по формуле

xkn+s+1 = xkn+s kn+ses

Если хотя бы одно из условий (4:20) не выполняется, то проверяют условия

(

xkn+s + kn+ses 2 X

(4:21)

f(xkn+s + kn+ses) < f(xkn+s)

Если оба условия (4:21) выполняются, то приближение определяют по формуле

xkn+s+1 = xkn+s + kn+ses

Если хотя бы одно из условий (4:21) не выполняется, то производят дробление шагом kn+sи повторяют приведенную процедуру заново до тех пор, пока не будут выполнены или оба условия (4:20) или оба условия (4:21).

22 Метод штрафных ф-ий

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

1.на большей части допустимого множества задачи оптимизации эти ф-и близки к 0;

2.каждая из них достаточно быстро возрастает либо при приближении изнутри границы допустимого множества (внутренние или барьерная ф-и), либо при выходе за его пределы (внешние штрафные ф-и);

3.степень близости штрафа к 0 и скорость его возрастания зависят от значения штрафного параметра и увеличиваются с ростом параметра

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

41