Прямые методы условной оптимизации
Download 481 Kb.
|
Методы условной оптимизации
- Bu sahifa navigatsiya:
- Определение
Метод ЗойтендейкаТипичным представителем класса методов возможных направлений является метод Зойтендейка. На каждой итерации метода находят возможное направление спуска, а затем проводят оптимизацию вдоль этого направления. Для изложения идеи метода введем ряд необходимых понятий. Напомним Определение 2. Рассмотрим задачу минимизации при условии, что xD Rn, где D- непустое множество. Ненулевой S называется возможным направлением спуска в точке xD, если существует такое , что и x+SD для всех . Вначале рассмотрим случай, когда ограничения линейные и задача НП имеет вид: Минимизировать (10) при условиях (11) (12) где - матрица порядка ; - матрица порядка ; b – m-мерный вектор; k – l-мерный вектор. Справедливо следующее утверждение. Лемма 2. Рассмотрим задачу минимизации (10)-(12). Пусть x - допустимая точка и предположим, что , где , а . Ненулевой вектор S является возможным направлением в точке в том и только в том случае, если и . Если, кроме того, f(x)T·S<0, то S является возможным направлением спуска. Доказательство этого утверждения очень простое. Предлагаем читателю выполнить это самостоятельно. Проиллюстрируем геометрически множество возможных направлений спуска на следующем примере. Пример 1. Минимизировать при условиях Выберем и заметим, что первые два ограничения являются активными в этой точке. В частности, матрица из вышеприведенной леммы 2, равна . Следовательно, вектор S является возможным направлением тогда и только тогда, когда т.е. в том случае, если На рис. 1. изображена совокупность этих направлений, образующая конус возможных направлений. Здесь 1 - конус возможных направлений; 2 - конус возможных направлений спуска; 3 - линии уровня целевой функции; 4 - полупространство направлений спуска. Если вектор S удовлетворяет неравенству , то он является направлением спуска. Таким образом, совокупность возможных направлений спуска определяется открытым полупространством . Пересечение конуса возможных направлений с этим полупространством задает множество всех возможных направлений спуска. Download 481 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling