Лексикографические задачи выпуклой оптимизации: условия разрешимости и оптимальности, метод отсекающих плоскостей

Abstract

Лексикографічний підхід до розв'язання багатокритеріальних задач полягає в строгому ранжируванні критеріїв за відносною важливістю і дозволяє домогтися оптимізації більш важливого критерію за рахунок будь-яких втрат за всіма іншими менш важливими критеріями. Найчастіше такі багатокритеріальні задачі виникають при послідовному введенні додаткових критеріїв у звичайні скалярні задачі оптимізації, які можуть мати не єдиний розв'язок. Задачі лексикографічної оптимізації виникають також при моделюванні ієрархічних структур, у стохастичному програмуванні, при розв'язанні деяких задач динамічного характеру тощо. В даній статті отримано умови існування розв’язків багатокритеріальних задач лексикографічної оптимізації з необмеженою опуклою допустимою множиною та умови оптимальності розв’язків на основі використання властивостей рецесивного конусу опуклої допустимої множини, конусу, що лексикографічно упорядковує допустиму множину щодо критеріїв оптимізації, та локальних шатрів, побудованих у граничних точках допустимої множини. Наведено властивості лексикографічно оптимальних розв’язків Отримані умови та властивості можна успішно використовувати при розробці алгоритмів пошуку оптимальних розв’язків зазначених задач лексикографічної оптимізації. На основі ідей методів лінеаризації та відсікаючих площин Келлі побудовано та обґрунтовано метод знаходження лексикографічно оптимальних розв’язків опуклих задач лексикографічної оптимізації.This article establishes conditions for the existence of solutions to multicriteria lexicographic optimization problems with unbounded convex feasible sets and optimality conditions for solutions based on properties of the recession cone of the convex feasible set, the cone that lexicographically orders the feasible set with respect to optimization criteria, and local polyhedral tents constructed at boundary points of the feasible set. Properties of lexicographically optimal solutions are presented.