Метод внешней точки

Метод внутренней точки

Данный метод используется для задач с ограничениями в виде неравенств, то есть для задач следующего вида:

(4.6)

Рассматривается два вида штрафных функций:

1)логарифмические

2)обратные

Внутренние штрафные функции должны удовлетворять следующим условиям:

1)на большей части допустимого множества X внутренние штрафные функции близки к нулю.

2)при приближении изнутри к границе допустимого множества X внутренние штрафные функции быстро возрастают (поэтому их также называют барьерными)

Логарифмические штрафные функции:

Если ограничение одно, то можно построить график:

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

Обратные штрафные функции:

Если ограничение одно, то можно построить график:

Нужно контролировать нахождение в допустимой области, так как функция будет определена, но решение будет неверным (попадет в область).

Метод используется как итерационный, так как:

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

В качестве последовательности следует выбирать монотонно убывающую, сходящуюся к нулю последовательность положительных чисел.

Выбирается некоторая константа (часто ), некоторая константа (часто ) и используется рекуррентная формула:

(4.7)

Штрафные функции должны обладать следующими свойствами:

1)во всех точках допустимого множества X внешние штрафные функции равны нулю.

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

Для задач (4.6) используются штрафные функции типа квадрата «срезки»:

Параметр должен возрастать, то есть в качестве последовательности следует выбирать монотонно возрастающую последовательность положительных чисел.

(4.8)

Зададим в виде ограничения равенства:

(4.9)

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

«+» метода внутренней точки / «–» метода внешней точки:

1)на каждом шаге мы поучаем допустимое решение и поэтому процедуру мы можем прекратить на любом шаге

2)требуется определение допустимой начальной точки

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