Методика аналитического решения задачи условной оптимизации с ограничениями типа неравенств
Для аналитического решения задачи типа (1.1, 1.2) предлагается использовать методику, в основе которой лежит теорема Куна и Таккера (H.W. Kuhn, A.W. Tucker) [1], представляющая собой в общем случае необходимые условия минимума целевой функции при наличии ограничений типа неравенств на множество допустимых значений векторного аргумента функции (см.(1.2)). В рассматриваемом приложении эту методику целесообразно представить в виде следующего расширенного алгоритма. 1. Формирование функции Лагранжа. Исходя из обозначений принятых в постановке (1.1, 1.2), функция Лагранжа будет иметь вид:
где l - вектор множителей Лагранжа размерности [m´1], соответствующей количеству ограничений gj(x)≤0, j=1,…,m. 2. Применение необходимых условий (НУ) в форме Куна и Таккера для определения условных стационарных точек для задачи (1.1, 1.2). В компактной форме для случая минимизации функции условия Куна и Таккера могут быть записаны в виде:
Где При рассмотрении конкретных задач, в которых количестве ограничений более одного, то есть при m >1 возможны различные сочетания активных и пассивных ограничений:
Где I1 – множество номеров индексов активных ограничений, I2 – множество номеров индексов пассивных ограничений (сумма элементов этих множеств всегда равна m). Очевидно, что в этих случаях НУ (2.2) должны быть применены при всех возможных сочетаниях активных и пассивных ограничений, включая крайние случаи: когда множество номеров активных ограничений I1 пусто (l = 0), то есть фактически рассматривается задача безусловной оптимизации; и когда количество активных ограничений, то есть количество элементов множества I1 равно размерности вектора х – [n´1] (так называемые «угловые» точки), тогда эта точка фиксируется активными ограничениями и не допускает вариации целевой функции (имеется ввиду корректная постановка задачи (1.1, 1.2)).
В результате применения НУ для всех возможных сочетаний активных ограничений будут получены варианты стационарных точек - 3. Исключение всех стационарных точек, не удовлетворяющих пассивным ограничениям. То есть:
4. Исключение стационарных точек, не удовлетворяющих условиям неотрицательности множителей Лагранжа. Из оставшегося числа вариантов стационарных точек необходимо исключить все точки, не удовлетворяющие условиям неотрицательности соответствующих множителей Лагранжа - 5. Проверка оставшихся стационарных точек на достаточные условия локального минимума функции. Все оставшиеся стационарные точки, за исключением «угловых» точек, должны быть проверены с помощью достаточных условий (ДУ), подтверждающих или опровергающих наличие в них условного локального минимума. Одним из широко распространенных вариантов ДУ нахождения в исследуемой стационарной точке условного локального минимума является положительная определенность матрицы Гессе, размера [n´n] (матрицы вторых частных производных) для функции Лагранжа F(х, l) по вектору х – [n´1].
Известно, что матрица положительно определена, если составленная с ее помощью квадратичная форма положительно определена [1], то есть:
Где H (x) (х, l) - матрица Гессе (Гессиан) по вектору х; y – любой вектор с фиксированными значениями, размера [n´1].
Для проверки положительной определенности квадратичной формы (2.6) предлагается применить критерий Сильвестра [2, 4]. Суть его заключается в следующем. Для того, чтобы квадратичная форма (2.6) была положительно определенной, необходимо и достаточно, чтобы матрица H (x) (х, l) имела все положительные угловые миноры, нарастающие вдоль главной ее диагонали, то есть были бы положительными определители матриц:
Где hij – элементы матрицы Гессе H (x) (х, l). Таким образом, при подтверждении положительной определенности матрицы Гессе в стационарных точках, в которых согласно НУ возможно было нахождение условного локального минимума, то есть при
6. Определение условного глобального минимума. Сравнение значений целевой функции f(x) в точках условного локального минимума и в «угловых» точках позволяет выявить условный глобальный минимум:
Где xугл – координаты «угловых» точек, определяемых n активными ограничениями из числа jÎ1,…,m (см. пункт 2). Таким образом условный глобальный минимум целевой функции равняется f(xmin). В соответствии с требованиями к КР (см. раздел 1.2) полученный результат необходимо представить графически и прокомментировать его с помощью поясняющих подписей и отдельных пояснений, следующих после рисунка (масштаб рисунка должен выбираться из соображений его наглядности). Пример графического представления результата аналитического решения задачи типа (1.1, 1.2) изображен на рис. 2.1.
В частности, на рис. 2.1 изображены: целевая функция f(x) с помощью линий уровня C1, C2, C3, …., причем C1 < C2 < C3 и т.д.; ограничения gj ≤ 0, j =1,2,3, выделяющие множество допустимых аргументов (параметров) - Х (запретные области условно заштрихованы); точки условного локального минимума определены номерами №1, №2, №3, №4, причем на рисунке видно, что точки №1 и №3 не удовлетворяют всем ограничениям gj ≤ 0; «угловые» точки: №5, №6, №7. Как следует из рассмотренной выше методики в результате сравнения значений функций в точках условного локального минимума №2, №4 и в «угловых» точках №5, №6, №7 определяются координаты условного глобального минимума, которые на рисунке обозначены №2.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|