Optimization Toolbox 2.2 Руководство пользователя

А.Г.Трифонов. Многокритериальная оптимизация

Достаточно часто в реальных ситуациях качество эксплуатации исследуемого объекта или системы оценивается не единственным критерием или показателем качества (см. параметрическую оптимизацию уравнение 3-1), а совокупностью таких критериев, причем представляющих одинаково значимыми. Такая постановка задачи приводит к задаче оптимизации с векторной целевой функцией , которая должна трактоваться неким определенным образом. Как правило, относительная значимость этих целей в общем неизвестна до тех пор, пока не будут определены все основные свойства системы и не будут полностью истолкованы все возможные взаимосвязи. По мере того, как число возможных целей возрастает, то, очевидно, что эти взаимосвязи образуют сложную структуру и их становятся труднее идентифицировать. В данном случае многое зависит от интуиции исследователя и его или ее умения точно выражать те или иные предпочтения в процессе оптимизации. Таким образом, стратегия построения многокритериальной оптимизации состоит, прежде всего, в способности адекватно определить постановку задачи так, что бы эта задача допускала свое решение, а также выразить необходимые предпочтения в виде числовых зависимостей и сохранив при этом реальность поставленной задачи.

Далее приводятся следующие тематические разделы:

• Введение в многокритериальную оптимизацию, где уделяется внимание множеству альтернативных методов.

• Обсуждение метода достижения цели, который можно рассматривать как задачу нелинейного программирования.

• Алгитмическое улучшение метода SQP, с целью его применения в методе достижения цели.

Введение в многокритериальную оптимизацию

Многокритериальная оптимизация представляет собой минимизацию некого вектора целей F(x), на которой могут быть наложены дополнительныеограничения или предельные значения:

Отметим, что поскольку F(x) является неким вектором, то любые компоненты F(x) являюся конкурирующими и отсутсвует некое единое решение поставленной задачи. Взамен этого, для описания характеристик целей вводится концепция множества точек неулучшаемых решений [41] (так называемая оптимальность по Паретто [4],[6]). Неухудшаемое решение есть такое решение, в котором улучшение в одной из целей приводит к некому ослаблению другой. Для более точной формулировки данной концепции рассмотрим некую область допустимых решений в параметрическом пространстве , которое удовлетворяет всем принятым ограничениям, т.е.

при ограничениях

Отсюда возможно опредлить соответствующую область допустисых решений для пространства целевых функций .

В двумерном случае, как это представлено на Рисунке 3-7, вектор характеристик F(x) отображает параметрическое пространство в пространство целевых функций

Рисунок 3-7. Отображение параметрического пространства а пространство целевых функций

Точка неулучшаемого решения может быть определена как:

Определение. Точка является неулучшаемым решением, если для некоторой окрестности нет некого такого, что и

Для двухмерной интерпретации Рисугка 3-8. Множество неулучшаемых решений, Множество точек неулучшаемых решений лежит на кривой между точками С и D. Точки А и В представляют специфичические неулучшаемые точки.

Рисунок 3-8. Множество неулучшаемых решений

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

.

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

Стратегия взвешенных сумм

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

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

Все это допускает геометрическую интерпретацию. Рассмотрим случай двух взятых целей, как это представлено на Рисунке 3-9. Геометрическая интерпретация метода взвешенных сумм. Отобразим линию L в пространстве целевых функций Минимизацию уравнения 3-51 можно интерпретировать как поиск такого значения с, при котором линия L будет как раз касаться границы при проведении данной процедуры решения задаче вне выбранной области. Путем подбора весов и возможно, по существу, задать наклон линии L таким образом, что, в свою очередь, приводит к искомой точке решения в месте касании линии L с границей области поиска решения .

Рисунок 3-9. Геометрическая интерпретация метода взвешенных сумм

Упомянутая выше проблема выпуклости становится актуальной в случае, когда нижняя граница области не является выпуклой, как это показано на Рисунке 3-10. Граница невыпуклого решения. В этом случае множество неухудшаемых решений между точками A и B не является достижимым при использовании подобных процедур.

Рисунок 3-10. Граница невыпуклого решения

Метод -ограничений

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

при выполнении условия

На Рисунке 3-11. Геометрическая интерпретация метода -ограничений, представлена двумерная интерпретация метода -ограничений для задачи с двумя целями.

Рисунок 3-11. Геометрическая интерпретация метода -ограничений

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

Для того, что бы в математическом описании были надлежавшим образом представлены истинные цели разработчика необходимо, чтобы разработчик четко представлял полный набор всех его предпочтений, а также допустимые уровни диапазона сочетаний значений выбранных целей. Таким образом, требуемая методика должна быть реализована таким образом, что бы максимально учесть все выше сказанное. Подобные методы были построены для дискретных функций с использованием отдельных достижений теории статистики, а именно, теории принятия решений и теории игр (в качестве введения в данные разделы можно порекомендовать работу [26]). Приложение к непрерывным функциям может быть реализовано с помощью подходящих стратегий дискретизации, а также комплексных методов решения. Поскольку только в редких случаях, когда разработчику известна такая детальная информация, то, по-видимому, приведенный выше метод является скорее всего мало практичным. Тем не менее, это может сферой для последующих исследований.

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

Метод достижения цели.

Описанный далее метод представляет собой метод достижения цели Гембики [18]. Данный метод включает в себя выражение для множества намерений разработчика , которое связано с множеством целей . Такая формулировка задачи допускает, что цели могут быть или недо- или передостижииыми, и что дает разработчику возможность относительно точно выразить исходные намерения. Относительная степень недо- или передостижимости поставленных намерений контролируется посредством вектора взвешенных коэффициентов и может быть представлена как стандартная задача оптимизации с помощью следующей формулировки

При условии, что

Член вносит в данную задачу элемент ослабления, что, иначе говоря, обозначает жесткость заданного намерения. Весовой вектор w дает исследователю возможность достаточно точно выразить меру взаимосвязи между двумя целями. Например, установка весового вектора w как равного исходному намерению указывает на то, что достигнут тот же самый процент недо- или передостижимости цели . Посредством установки в ноль отдельного весового коэффициента (т.е. ) можно внести жесткие ограничения в поставленную задачу. Метод достижения цели обеспечивает подходящую интуитивную интерпретацию поставленной исследовательской задачи и которая, в свою очередь, является вполне разрешимой с помощью стандартных процедур оптимизации. Иллюстративный пример подобного использования метода достижения цели для систем управления можно найти у Флеминга ([12], [13]).

На рисунке 3-12. Геометрическая интерпретация метода достижения цели, представлена интерпретация двумерной задачи данного метода.

3-12. Геометрическая интерпретация метода достижения цели

Задание компонентов намерений определяет точку намерений P. Весовой вектор определяет поиска от точки P в сторону пространства допустимых функций . В процессе оптимизации происходит изменение величины , что вызывает изменение размера заданной допустимой области. Границы ограничений стягиваются к единственной в своем роде точке решения .

Алгоритмическое улучшение метода достижения цели

Метод достижения цели имеет определенные преимущества, а именно, на него может быть наложена задача нелинейного программирования. Характерной особенностью данной проблемы является то, что в данном случае могут так же решаться задачи нелинейного программирования. Что касается метода последовательного квадратичного программирования, то выбор функции выгоды в случае линейного поиска является далеко нелегкой задачей, поскольку в большинстве случаев достаточно трудно "определить" относительную значимость между улучшением целевой функции и степенью отклонения от нарушения налагаемых ограничений. Такой подход приводит к ряду дифференциальных схем для построения функции выгоды (смотри, например Шитковский [38]). В задаче программирования достижения цели может быть найдена более подходящая функция выгоды, которая может быть получена путем наложения уравнения 3-53 на задачу минимакса

где

Следуя заключения Врайтона и др. [2] для минимаксной оптимизации на основе метода SQP, применение функции выгоды к уравнению 3-44 для задачи достижения цели согласно уравнению 3-54 приводит к следующей постановке задачи

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

Согласно пути движения Брайтона и др. [2] поиск некого решения заключается в установке значения как равного наиболее неблагоприятной цели, т.е. как

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

Другая особенность, которая так же может быть использована в методе SQP, является принятая целевая функция . Исходя из КТ уравнений (уравнения 3-26) можно показать, что аппроксимация матрицы Гессе для Лагранжиана H, должна иметь нули в связанных с переменной соответствующих строках и колонках матрицы. Однако данное свойство ни как не проявляется, если матрица H инициализируется как некая тождественная матрица. Следовательно, матрица H должна инициализироваться и сохраняться как матрица с нулями в связанных с переменной соответствующих строках и колонках матрицы.

Подобные действия делают матрицу Гессе H бесконечной. Поэтому необходимо устанавливать нули в связанных с переменной соответствующих строках и колонках матрицы за исключением диагональных элементов, где вносятся небольшие положительные числа (например 1e-10). Такой подход позволяет использовать достаточно быстро сходящийся положительно определенный QP метод, как это описано в разделе Решение задачи квадратичного программирования.

Приведенные выше модификации были внесены в программу fgoalattain и было обнаружено, что эти коррекции приводят к эффективности данного метода. Однако, вследствие быстрой сходимости метода SQP, требование, что бы функция выгоды строго уменьшалась, иногда приводит к большему числу расчетов функции при внедрении метода SQP с использованием функции выгоды согласно уравнению 3-44.

Избранная библиография

[1]  Biggs, M.C., "Constrained Minimization Using Recursive Quadratic Programming," Towards Global Optimization (L.C.W. Dixon and G.P. Szergo, eds.), North-Holland, pp 341-349, 1975.

[2]  Brayton, R.K., S.W. Director, G.D. Hachtel, and L. Vidigal, "A New Algorithm for Statistical Circuit Design Based on Quasi-Newton Methods and Function Splitting," IEEE Transactions on Circuits and Systems, Vol. CAS-26, pp 784-794, Sept. 1979.

[3]  Broyden, C.G., "The Convergence of a Class of Double-rank Minimization Algorithms," J. Inst. Maths. Applics., Vol. 6, pp 76-90, 1970.

[4]  Censor, Y., "Pareto Optimality in Multiobjective Problems, " Appl. Math. Optimiz., Vol. 4, pp 41-59, 1977.

[5]  Conn, N.R., N.I.M. Gould, and Ph.L. Toint, Trust-Region Methods, MPS/SIAM Series on Optimization, SIAM and MPS, 2000.

[6]  Da Cunha, N.O. and E. Polak, "Constrained Minimization Under Vector-valued Criteria in Finite Dimensional Spaces," J. Math. Anal. Appl., Vol. 19, pp 103-124, 1967.

[7]  Dantzig, G., Linear Programming and Extensions, Princeton University Press, Princeton, 1963.

[8]  Dantzig, G., A. Orden, and P. Wolfe, "Generalized Simplex Method for Minimizing a Linear from Under Linear Inequality Constraints," Pacific J. Math. Vol. 5, pp 183-195.

[9]  Davidon, W.C., "Variable Metric Method for Minimization," A.E.C. Research and Development Report, ANL-5990, 1959.

[10]  Dennis, J.E., Jr., "Nonlinear least-squares," State of the Art in Numerical Analysis ed. D. Jacobs, Academic Press, pp 269-312, 1977.

[11]  Dennis, J.E., Jr. and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, 1983.

[12]  Fleming, P.J., "Application of Multiobjective Optimization to Compensator Design for SISO Control Systems," Electronics Letters, Vol. 22, No. 5, pp 258-259, 1986.

[13]  Fleming, P.J., "Computer-Aided Control System Design of Regulators using a Multiobjective Optimization Approach," Proc. IFAC Control Applications of Nonlinear Prog. and Optim., Capri, Italy, pp 47-52, 1985.

[14]  Fletcher, R., "A New Approach to Variable Metric Algorithms," Computer Journal, Vol. 13, pp 317-322, 1970.

[15]  Fletcher, R., "Practical Methods of Optimization," Vol. 1, Unconstrained Optimization, and Vol. 2, Constrained Optimization, John Wiley and Sons, 1980.

[16]  Fletcher, R. and M.J.D. Powell, "A Rapidly Convergent Descent Method for Minimization," Computer Journal, Vol. 6, pp 163-168, 1963.

[17]  Forsythe, G.F., M.A. Malcolm, and C.B. Moler, Computer Methods for Mathematical Computations, Prentice Hall, 1976.

[18]  Gembicki, F.W., "Vector Optimization for Control with Performance and Parameter Sensitivity Indices," Ph.D. Thesis, Case Western Reserve Univ., Cleveland, Ohio, 1974.

[19]  Gill, P.E., W. Murray, M.A. Saunders, and M.H. Wright, "Procedures for Optimization Problems with a Mixture of Bounds and General Linear Constraints," ACM Trans. Math. Software, Vol. 10, pp 282-298, 1984.

[20]  Gill, P.E., W. Murray, and M.H. Wright, Numerical Linear Algebra and Optimization, Vol. 1, Addison Wesley, 1991.

[21]  Gill, P.E., W. Murray, and M.H.Wright, Practical Optimization, London, Academic Press, 1981.

[22]  Goldfarb, D., "A Family of Variable Metric Updates Derived by Variational Means," Mathematics of Computing, Vol. 24, pp 23-26, 1970.

[23]  Grace, A.C.W., "Computer-Aided Control System Design Using Optimization Techniques," Ph.D. Thesis, University of Wales, Bangor, Gwynedd, UK, 1989.

[24]  Han, S.P., "A Globally Convergent Method for Nonlinear Programming," J. Optimization Theory and Applications, Vol. 22, p. 297, 1977.

[25]  Hock, W. and K. Schittkowski, "A Comparative Performance Evaluation of 27 Nonlinear Programming Codes," Computing, Vol. 30, p. 335, 1983.

[26]  Hollingdale, S.H., Methods of Operational Analysis in Newer Uses of Mathematics (James Lighthill, ed.), Penguin Books, 1978.

[27]  Levenberg, K., "A Method for the Solution of Certain Problems in Least Squares," Quart. Appl. Math. Vol. 2, pp 164-168, 1944.

[28]  Madsen, K. and H. Schjaer-Jacobsen, "Algorithms for Worst Case Tolerance Optimization," IEEE Transactions of Circuits and Systems, Vol. CAS-26, Sept. 1979.

[29]  Marquardt, D., "An Algorithm for Least-Squares Estimation of Nonlinear Parameters," SIAM J. Appl. Math. Vol. 11, pp 431-441, 1963.

[30]  Moré, J.J., "The Levenberg-Marquardt Algorithm: Implementation and Theory," Numerical Analysis, ed. G. A. Watson, Lecture Notes in Mathematics 630, Springer Verlag, pp 105-116, 1977.

<[31]  NAG Fortran Library Manual, Mark 12, Vol. 4, E04UAF, p. 16.

[32]  Nelder, J.A. and R. Mead, "A Simplex Method for Function Minimization," Computer J., Vol.7, pp 308-313, 1965.

[33]  Nocedal, J. and S.J. Wright, Numerical Optimization, Springer Series in Operations Research, Springer Verlag, 1999.

[34]  Powell, M.J.D., "The Convergence of Variable Metric Methods for Nonlinearly Constrained Optimization Calculations," Nonlinear Programming 3, (O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.), Academic Press, 1978.

[35]  Powell, M.J.D., "A Fast Algorithm for Nonlinearly Constrained Optimization Calculations," Numerical Analysis, G.A.Watson ed., Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.

[36]  Powell, M.J.D., "A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations," Numerical Methods for Nonlinear Algebraic Equations, (P. Rabinowitz, ed.), Ch.7, 1970.

[37]  Powell, M.J.D., "Variable Metric Methods for Constrained Optimization," Mathematical Programming: The State of the Art, (A. Bachem, M. Grotschel and B. Korte, eds.) Springer Verlag, pp 288-311, 1983.

[38]  Schittkowski, K., "NLQPL: A FORTRAN-Subroutine Solving Constrained Nonlinear Programming Problems," Annals of Operations Research, Vol. 5, pp 485-500, 1985.

[39]  Shanno, D.F., "Conditioning of Quasi-Newton Methods for Function Minimization," Mathematics of Computing, Vol. 24, pp 647-656, 1970.

[40]  Waltz, F.M., "An Engineering Approach: Hierarchical Optimization Criteria," IEEE Trans., Vol. AC-12, pp 179-180, April, 1967.

[41]  Zadeh, L.A., "Optimality and Nonscalar-valued Performance Criteria," IEEE Trans. Automat. Contr., Vol. AC-8, p. 1, 1963.