А.С. Антипин. О методах оптимизации функции чувствительности при ограничениях ... С. 33-42.

УДК 517.988.68

MSC: 90C25, 90C31, 90C46, 90C90, 49K40

DOI: 10.21538/0134-4889-2017-23-3-33-42

Полная версия статьи

Работа выполнена при финансовой поддержке Российского научного фонда (проект 17-11-01353).

Рассматривается параметрическое семейство задач выпуклого программирования. В качестве параметра выступает вектор правых частей функциональных ограничений задачи. Каждому векторному значению параметра, взятому из неотрицательного ортанта, отвечает регулярная (условие Слейтера) задача выпуклого программирования и ее минимальное значение целевой функции. Это значение, зависящее от параметра ограничений, порождает функцию чувствительности. Наряду с этой функцией априори задается выпуклое множество (геометрически или функционально заданное). Ставится задача минимизации неявно заданной функции чувствительности на этом множестве. Такая задача имеет содержательную интерпретацию как задача выпуклого программирования, когда вместо заданного вектора правых частей функциональных ограничений указывается только множество, которому этот вектор принадлежит. В результате получаем двухуровневую задачу. В отличие от классических двухуровневых иерархических задач, где неявно задаются ограничения, в нашем случае неявно задаются целевые функции. Никакой иерархии в этой задаче нет. Как правило функции чувствительности обсуждаются в научной литературе в более общем контексте как функции оптимального значения. Автору не известны оптимизационные постановки этих задач как самостоятельных исследований и, тем более, не известны предлагаемые методы их решения. В работе предлагается оригинальный седловой подход к решению задач с функциями чувствительности. Доказывается монотонная сходимость метода к решению задачи по переменным пространства, в котором рассматривается задача.

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

Список литературы

1. Антипин А.С., Голиков А.И., Хорошилова Е.В. Функция чувствительности, ее свойства и приложения // Журн. вычисл. математики и мат. физики. 2011. T. 51. № 12. C. 2126-2142.

2. Васильев Ф.П. Методы оптимизации. Т. 1,2. М.: Изд-во МЦНМО, 2011. 1056 p.

3. Rockafellar R.T. Monotone operators and the proximal point algorithm // SIAM J. Control Optim. 1976. Vol. 14, № 5. C. 877-898. doi:10.1137/0314056.

4. Антипин А.С. О методе выпуклого программирования, использующем симметрическую модификацию функции Лагранжа // Экономика и мат. методы. 1976. XII, вып. 6. C. 1164-1173.

5. Антипин А.С. О сходимости и оценках скорости сходимости проксимальных методов к неподвижным точкам экстремальных отображений // Журн. вычисл. математики и мат. физики. 1995. T. 35, № 5. C. 688-704.

6. Коннов И.В. Нелинейная оптимизация и вариационные неравенства. Казань: Изд-во Казан. ун-та, 2013. 508 p.

7. Антипин А.С. Седловая задача и задача оптимизации как единая система // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14, № 2. C. 5-15.

8. Антипин А.С. Экстрапроксимальный метод решения равновесных и игровых задач со связанными переменными // Журн. вычисл. математики и мат. физики. 2005. T. 45, № 12. C. 2102-2111.

9. Clempner J., Poznyak A.S. Using the extraproximal method for computing the shotest-path mixeв Lyapunov equilibrium in stackelberg security games// Inernational J. on Artificial Intelligence Tools. 2014. Vol. 11. P. 3-23.

10. Trejo K.K., Clempner J.B., Poznyak A.S. A stackelberg security game with random strategic based on the extraproximal theoretic approach // Engineering Appl. Artificial Intelligence. 2015. Vol. 37. P. 145-153. doi: http://dx.doi.org/10.1016/j.engappai.2014.09.002.

Поступила 04.06.2016

Антипин Анатолий Сергеевич
д-р физ.-мат. наук, профессор, главный науч. сотрудник
Федеральный исследовательский центр ``Информатика и управление'' РАН, г. Москва
e-mail: asantip@yandex.ru

English

A.S. Antipin. Optimization methods for the sensitivity function with constraints.

We consider a parametric family of convex programming problems. The parameter is the vector of the right-hand sides in the functional constraints of the problem. Each vector value of the parameter taken from the nonnegative orthant corresponds to a regular (Slater's condition) convex programming problem and the minimum value of its objective function. This value depends on the constraint parameter and generates the sensitivity function. Along with this function, a convex set is given geometrically or functionally. The problem of minimization of the implicit sensitivity function on this set is posed. It can be interpreted as a convex programming problem in which, instead of a given vector of the right-hand sides of functional constraints, only a set to which this vector belongs is specified. As a result, we obtain a two-level problem. In contrast to the classical two-level hierarchical problems with implicitly given constraints, it is objective functions that are given implicitly in out case. There is no hierarchy in this problem. As a rule, sensitivity functions are discussed in the literature in a more general context as functions of the optimal value. The author does not know optimization statements of these problems as independent studies or, even more so, solution methods for them. A new saddle approach to the solution of problems with sensitivity functions is proposed. The monotone convergence of the method is proved with respect to the variables of the space in which the problem is considered.

Keywords: sensitivity function, parametric optimization, parametric Lagrangian, saddle point, extraproximal methods, convergence.

 The paper was received by the Editorial Office on June 13, 2017.

Anatolii Sergeevich Antipin, Dr. Phys.-Math. Sci., Prof.,  Federal Research Center ''Computer Science  and Control'' of Russian Academy of  Science,  Moscow, 119333 Russian, e-mail: asantip@yandex.ru .