Л.А. Артемьева, А.А. Дряженков, М.М.Потапов. О задаче квадратичной минимизации с неравномерными возмущениями в критерии и ограничениях ... С. 19-34

УДК 519.853.62

MSC: 65J20, 65K05, 90C25

DOI: 10.21538/0134-4889-2021-27-2-19-34

Работа выполнена при поддержке гранта Президента РФ МК-3539.2019.1.

Полный текст статьи (Full text)

Статья переведена: ISSN 0081-5438 

Proceedings of the Steklov Institute of Mathematics, 2021, Vol. 315, Suppl. 1, pp. S27–S41. (Abstract)

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

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

СПИСОК ЛИТЕРАТУРЫ

1.  Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1986. 288 с.

2.  Бакушинский А.Б., Гончарский А.В. Итеративные методы решения некорректных задач. М.: Наука, 1989. 128 с.

3.  Бакушинский А.Б. Методы решения монотонных вариационных неравенств, основанные на принципе итеративной регуляризации // Журн. вычисл. математики и мат. физики. 1977. Т. 17, № 6. С. 1350-1362.

4.  Васильев Ф.П., Ячимович М.Д. Об итеративной регуляризации метода условного градиента и метода Ньютона при неточно заданных исходных данных // Докл. АН СССР. 1980. Т. 250, № 2. С. 265-269.

5.  Сумин М.И. Регуляризация в линейно-выпуклой задаче математического программирования на основе теории двойственности // Журн. вычисл. математики и мат. физики. 2007. Т. 47, № 4. С. 602-625.

6.  Васильев Ф.П., Потапов М.М., Артемьева Л.А. Регуляризованный экстраградиентный метод в многокритериальных задачах управления с неточными данными // Дифференц. уравнения. 2016. Т. 52, № 11. С. 1555-1567. doi: 10.1134/S037406411611011X

7.  Дряженков А.А. Модифицированный обобщенный метод невязки для задач минимизации с погрешностями известного уровня в ослабленных нормах // Вычисл. методы и программирование. 2015. Т. 16. C. 456-463.  doi: 10.26089/NumMet.v16r443

8.  Васильев Ф.П.  Методы оптимизации: в 2-х кн. М.: МЦНМО, 2011. 1053 с.

9.  Экланд И., Темам Р. Выпуклый анализ и вариационные проблемы. М.: Мир, 1979. 400 с.

Поступила 19.02.2021 

После доработки 3.03.2021 

Принята к публикации 15.03.2021

Артемьева Людмила Анатольевна
канд. физ.-мат. наук,
ассистент
Московский государственный университет им. М.В. Ломоносова
г. Москва
e-mail: artemieva.luda@gmail.com

Дряженков Андрей Александрович
канд. физ.-мат. наук,
младший науч. сотрудник
Московский государственный университет им. М.В. Ломоносова
г. Москва
e-mail: andrja@yandex.ru

Потапов Михаил Михайлович
д-р физ.-мат. наук, доцент
профессор
Московский государственный университет им. М.В. Ломоносова
г. Москва
e-mail: mmpotapovrus@gmail.com

Ссылка на статью: Л.А. Артемьева, А.А. Дряженков, М.М.Потапов. О задаче квадратичной минимизации с неравномерными возмущениями в критерии и ограничениях // Тр. Ин-та математики и механики УрО РАН. 2021. Т. 27, № 2. С. 19-34

English

L.A. Artem’eva, A.A. Dryazhenkov, M.M. Potapov. On a quadratic minimization problem with nonuniform perturbations in the criteria and constraints

A quadratic minimization problem is considered in Hilbert spaces in the presence of a linear operator constraint of the equality type and a quadratic constraint of the inequality type. The problem is reformulated as the problem of finding the saddle point of the normal Lagrange function. For the numerical solution of this problem, a regularized gradient-type method is proposed that iterates both in primal and in dual variables. Approximate solutions are constructed under nonclassical information conditions, when the approximations to the exact operators from the problem statement available to the computer approximate these operators only strongly pointwise and there are no corresponding error estimates in the operator norms of the original spaces. Instead, a priori information is used about the error levels that become accessible when the norms are changed in the domains or ranges of the operators. Estimates of the first type appear after strengthening norms in the domain spaces of the operators, and estimates of the second type appear after weakening norms in their range spaces. At each iteration of the proposed method, two main actions are performed. First, the next approximation to the minimum value of the functional is computed using error estimates of the first type. Then, the next approximation to the optimal solution is found using error estimates of the second type. It is proved that the approximations generated by the proposed method converge to the solution of the original optimization problem in the norm of the original space.

Keywords: quadratic minimization problem, approximate data, numerical solution, ill-posed problem, regularized gradient method, Lagrange function, saddle point

Received February19, 2021

Revised  March 3, 2021

Accepted March 15, 2021

Funding Agency: This work was supported by the Russian President's grant no. MK-3566.2019.1.

Liudmila Anatolievna Artemieva, Cand. Phys.-Math. Sci., Lomonosov Moscow State University, Moscow, 119991 Russia, e-mail: artemieva.luda@gmail.com

Andrey Alexandrovich Dryazhenkov, Cand. Phys.-Math. Sci., Lomonosov Moscow State University, Moscow, 119991 Russia, e-mail: andrja@yandex.ru

Mikhail Mikhailovich Potapov, Dr. Phys.-Math. Sci., Prof., Lomonosov Moscow State University, Moscow, 119991 Russia, e-mail: mmpotapovrus@gmail.com

Cite this article as: L.A. Artem'eva, A.A. Dryazhenkov, M.M. Potapov. On a quadratic minimization problem with nonuniform perturbations in the criteria and constraints, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 2, pp.19-34; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 315, Suppl. 1, pp. S27–S41.

[References -> on the "English" button bottom right]