Консалтология Общая теория консалтинга (стр. 32 )

Рис. 9.3. Многоэкстре­мальная задача опти­мального консультирования

На рисунке показаны линии равного уровня це­левой функции F(X)(a3>a2>a1>a0) и видны три локаль­ных оптимума, которые находятся в областях, определяе­мых общим направляющим принципом (точки Х1лок, Х2лок, Х3лок являются точками локальных оптимумов, причем точка Х3лок совпадает с глобальным оптимумом).

К сожалению, отсутствуют формальные признаки мно­гоэкстремальных ситуаций. Исключением являются задачи, где целевая функция выпуклая (в задачах минимиза­ции) или вогнутая (при максимизации).

Напомним, что функцию F(X) с числовыми значениями, определенными на выпуклом множестве S, называют вогнутой, если для любой пары точек X1, X2S и для всех чисел λ (0≤λ≤1) выполняется неравенство F(λX1+(1— λ)X2)≥λ F(X1)+(1-λ)F(X2). Если F(λX1+(1—λ)X2)≤λF(X1)+(1-λ)F(X2), то функцию f(X) назы­вают выпуклой. Если имеют место строгие неравенства, то говорят, что функция строго вогнута или строго выпукла. Для дважды дифференцируемой функции критерий во­гнутости или выпуклости формируется следующим обра­зом. Дифференцируемая функция F(X) строго вогнута в некоторой окрестности точки Х(0)= (х1(0),..., хт(0)), если вы­полняются условия

т. е. если знаки этих определителей чередуются указанным образом. Здесь Fij(Х(0))—частная производная второго порядка, вычисленная в точке Х(0).

Функция F(X) строго выпукла в малой окрестности точки Х(0), если все определители, указанные выше, поло­жительны.

Достаточные условия для определения максимума или минимума формулируются следующим образом: для того, чтобы в точке Х(0) достигался внутренний локальный мак­симум, достаточно равенства нулю всех частных производ­ных и строгой вогнутости функции в некоторой окрестно­сти этой точки; для того чтобы в точке Х(0) достигался вну­тренний локальный минимум, достаточно, чтобы все частные производные обращались в нуль и чтобы в малой окрестности этой точки функция была строго выпуклой.

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

Методы поиска экстремума классифицируются по сле­дующим признакам: в зависимости от характера экстрему­ма существуют методы условной и безусловной, локальной и глобальной оптимизации; по числу переменных консультирования различают методы одномерного и многомерного поиска, а по характеру информации о виде целевой функ­ции — методы нулевого, первого и второго порядков, при­чем в методах первого порядка используют градиент целевой функции, поэтому эти методы называются гради­ентными, в методах второго порядка применяют вторые производные, а в методах нулевого порядка производные не используют.

9.4. Показатели эффективности сформированных рекомендаций и выбор методов поиска экстремума

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

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

Поиск локального оптимума состоит из следующих эта­пов определения: направления движения к оптимуму, дли­ны шага поиска, окончания поиска.

Алгоритмы поиска локального оптимума X* являются, как правило, итеративными, т. е. порождают последова­тельность векторов

{X(k)}=X1, X2..... Xk, сходящуюся к вектору X*.

Будем говорить, что вектор X* является пределом сходящейся последовательности {X(k)}, если для любого ε>0 найдется такой номер N, что при k>N выполняется неравенство |Xk —Х*|< ε. Отсюда следует, что допустимая область S должна вместе с любой сходящейся последовательностью содержать и ее предел. Такую область будем называть замкну­той. Примером замкнутой области может служить множе­ство всех точек, удовлетворяющих ограничениям (9.2) и (9.3).

Множество всех точек пространства Еп, которые не со­держатся в замкнутой области S(Еп\S), будем называть откры­тым. В замкнутой области S, если она не совпадает со всем пространством Еп, всегда можно найти точки, в ε-окрестности которых имеются точки из En\S. Такие точки обла­сти будем называть граничными. Множество всех граничных точек образует границу области S. В частности, если об­ласть S определяется условиями (9.2) и (9.3), его границу составляют те точки, в которых хотя бы одно из ограниче­ний выполняется как строгое равенство.

Эффективность методов поиска локального оптимума определяется скоростью их сходимости к X*, а критерия­ми оценки качества выбора направления являются:

- улучшение значения критерия оптимальности во вновь выбранной точке по сравнению с его величиной в данной точке;

- наиболее быстрое убывание (возрастание) критерия в окрестности данной точки;

- наиболее вероятное расположение экстремума с учетом кривизны гиперповерхности, представляющей критерий оп­тимальности.

Использование каждого из трех критериев выбора на­правления движения к оптимуму требует различного числа обращений к модели КП. Необоснованное усиление критерия выбора направления поиска может привести к резкому возрастанию числа обращений к модели КП, а ослабление — к беспорядочному блужданию в окрестности оптимума. В обоих случаях возрастают затраты машинного времени на консультирование.

Проведем краткий анализ методов поиска экстремума. Особенности методов будем иллюстрировать примерами их применения к поиску экстремума функции F(X) в двумер­ном пространстве переменных консультирования.

Методы безусловной оптимизации. Для решения зада­чи безусловной оптимизации будем использовать итерационные процессы вида

Xk = Xk-1 + αk∆Xk, (9.42)

где ∆Xk — вектор, определяющий направление движения из точек Xk-1, αk — числовой множитель, значение которо­го определяет длину шага в направлении ∆Xk. Для боль­шинства методов

∆Xk = Рk /|| Рk ||. (9.43)

где Р — вектор, указывающий направление поиска; ||Рk||— норма вектора Р; k — индекс, обозначающий номер шага поиска.

Процесс (9.42) будет определен, если указаны спосо­бы построения вектора ∆Xk. и вычисления величины αk на каждой итерации. От того, каким образом строится вектор ∆Xk и определяется множитель αk, непосредственно зави­сят свойства процесса: поведение функции F(X) на эле­ментах последовательности {Х(k)}, сходимость последова­тельности к решению, скорость сходимости и др. В то же время различные способы построения вектора ∆Xk и мно­жителя αk требуют различных затрат машинного време­ни и различной емкости оперативной памяти ЭВМ.

Чтобы приблизиться к точке X*, естественно двигать­ся от точки Xk-1 в одном из направлений убывания функ­ции F(Х) (в направлении спуска). Если точка Xk-1 не является точкой минимума или стационарной точкой, то су­ществует бесконечно много векторов ∆Xk, определяющих направления спуска из точки Xk-1, причем каждый из них определяется условием

(F'(Xk-1), ∆Xk)<0,

вытекающим из (9.40).

Поскольку местонахождение точки X* неизвестно, про­цесс поиска экстремума может быть прекращен в точке Xk, при этом число шагов r, разделяющих точки Xk и Xk-1, определяют из условия |Xk — Xk-r| <ε. Следовательно, поиск прекращается, если расстояние, на которое продви­нулась отображающая точка в пространстве переменных консультирования за последние r шагов, оказывается мень­ше заданного числа ε.

Прямые методы оценки направлений. Наи­более простым является метод покоординатного спуска (метод Гаусса — Зейделя). Направление поиска вы­бирают поочередно вдоль всех координатных осей, т. е. вектор Рk в (9.43) состоит из нулевых элементов за исключением одного, равного единице.