141701, г. Долгопрудный, Институтский пер., д. 9, МФТИ, Россия

e–mail: [email protected] · 2025

Read 141701, г. Долгопрудный, Институтский пер., д. 9, МФТИ, Россия by e–mail: [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-04866.txt.

Introduction

Pletnev builds a gradient method for quadratic optimization that aims straight at the exact answer, in a paper published in two thousand twenty-five. Problems of this kind arise in Hilbert spaces when people solve ill-posed questions about differential equations, where the best value of the target is already known.

Because the target's shape lets the gradient be computed by solving well-posed side problems, step-by-step methods are practical. The author constructs one, the m-moment minimum error method, designed to shrink the distance to the exact solution as fast as possible. He proves that it converges and that no method of its kind can do better. He also shows that methods working inside Krylov subspaces cannot converge evenly across all cases. Tests on hard problems, including a Helmholtz problem and a backward-in-time Cauchy problem, show the method working well.

Catalog record

CREATORe–mail: [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-04866

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

141701, г. Долгопрудный, Институтский пер., д. 9, МФТИ, Россия e–mail: [email protected] Abstract О построении градиентного метода квадратичной оптимизации, оптимального с точки зрения минимизации расстояния до точного решения ©2025 г. 20 Н.В. Плетнев Задачи квадратичной оптимизации в гильбертовом пространстве часто возникают при решении некорректных задач для дифференциальных уравнений. При этом известно целевое значение функционала. Кроме того, структура функционала позволяет вычислять градиент с помощью решения корректных задач, что позволяет применять методы первого порядка. Данная статья посвящена построению m -моментного метода минимальных ошибок — эффективного метода, минимизирующего расстояние до точного решения. Доказывается сходимость и оптимальность построенного метода, а также невозможность равномерной сходимости методов, работающих в подпространствах Крылова. Проводятся численные эксперименты, демонстрирующие эффективность применения m -моментного метода минимальных ошибок к решению различных некорректных задач: начально-краевой задачи для уравнения Гельмгольца, ретроспективной задачи Коши для уравнения теплопроводности, обратной задачи термоакустики. Ключевые слова: некорректные и обратные задачи, квадратичная оптимизация, оптимизация в гильбертовом пространстве, минимизация расстояния до точного решения, начально-краевая задача для уравнения Гельмгольца, ретроспективная задача Коши для уравнения теплопроводности, обратная задача термоакустики. 1. Введение Теория некорректных и обратных задач — очень важный раздел математической физики. Область их применения в физике, геофизике, технике, медицине весьма обширна. Многие обратные задачи могут быть представлены в виде операторного уравнения: Aq=f (1) Здесь оператор A определён в некотором гильбертовом пространстве H , решение q^{*} предполагается единственным, а f — результат измерений, доступных в условиях задачи. При этом вычисление результата действия оператора A на произвольный элемент H — корректная, прямая задача. Примеры задач, представимых в таком виде: начально-краевая задача для уравнения Гельмгольца, задача Коши для уравнения теплопроводности, интегральное уравнение Фредгольма 1-ого рода. Часто оператор A не является линейным из-за неоднородных граничных условий. При рассмотрении таких задач вводится оператор A_{0} , который определяется аналогично, но с нулями вместо всех начальных и граничных условий, кроме заданного функцией q . Важное свойство: Aq-Aq^{\prime}=A_{0}(q-q^{\prime}). Широкое распространение получил подход к решению подобных задач с помощью сведения их к задачам выпуклой оптимизации: J(q)=\frac{1}{2}||Aq-f||^{2}\rightarrow\min (2) Его эффективность обусловлена сравнительной простотой вычисления градиента: \nabla J(q)=A^{*}(Aq-f) (3) Здесь A^{*} — сопряжённый оператор для A_{0} . Градиент удовлетворяет условию Липшица с константой L=||A_{0}||^{2} . Поскольку задача вычисления оператора A является корректной, A_{0} ограничен. ||\nabla J(q)-\nabla J(q^{\prime})||=||A^{*}(Aq-f)-A^{*}(Aq^{\prime}-f)||=||A^{*}A_{0}(q-q^{\prime})||\leq L||q-q^{\prime}||. (4) Часто для решения используется метод градиентного спуска, также применимы ускоренные методы, в том числе и метод сопряжённых градиентов. Структура функционала позволяет выполнить точную вспомогательную одномерную минимизацию для произвольного направления. В некоторых случаях возможна также минимизация расстояния до точного решения. Построению эффективного метода оптимизации, основанного на этом подходе, и посвящена статья. 2. Работы, основанные на похожих идеях В статье [ 5 ] был предложен, а в статье [ 6 ] развит развит так называемый PMM — метод минорант Поляка. Он основан на следующей идее: на каждом шаге k подбирается <<миноранта>> m_{k}(q) — функция простого вида, для которой m_{k}(q)\leq J(q) и m_{l}(q_{k})=J(q_{k}) . Подбирается точка q_{k+1} , для которой m_{k}(q_{k+1})=J(q^{*})=0 . При этом J(q_{k+1})<J(q_{k}) . Поскольку <<естественная>> миноранта для гладкого выпуклого функционала — это его линейное приближение, метод принимает вид: q_{k+1}=q_{k}-\frac{J(q_{k})}{||\nabla J(q_{k})||^{2}}\nabla J(q_{k}) (5) В дальнейшем будет показано, что одномерная минимизация расстояния до точного решения приводит к похожей формуле. Эксперименты показывают, что метод Поляка эффективнее одномерной минимизации расстояния. Как указывает сам автор, его скорость сходимости примерно соответствует характеристикам обычных градиентных методов. Однако, оказывается возможным достижение лучших результатов при использовании многомерной вспомогательной минимизации. В статье [ 7 ] предпринята попытка построить метод квадратичной минимизации (адаптивный тяжёлый шарик), оптимальный в смысле минимизации расстояния до точного решения. Однако для такого метода это расстояние должно монотонно убывать. Эксперименты показывают, что построенный в указанной статье метод не обладает этим свойством. Однако данная работа решает проблему: метод строится, а его свойства доказываются. 3. Построение оптимального метода квадратичной оптимизации 3.1. Одномерная минимизация расстояния до точного решения: метод минимальных ошибок Специальный вид функционала и градиента позволяет (согласно [ 8 ] , раздел 2.6) выбрать длину шага в общем случае. Пусть шаг k делается в направлении s_{k} : q_{k+1}=q_{k}+\alpha_{k}s_{k}. (6) \alpha_{k}(\rho)=\arg\min\limits_{\alpha\geq 0}||q_{k}+\alpha s_{k}-q^{*}||^{2}. Элементарные преобразования минимизируемого выражения позволяют получить искомое значение коэффициента: ||q_{k}+\alpha s_{k}-q^{*}||^{2}=||q_{k}-q^{*}||^{2}+2\alpha\langle q_{k}-q^{*},\ s_{k}\rangle+\alpha^{2}||s_{k}||^{2}\Rightarrow \Rightarrow\alpha_{k}(\rho)=-\frac{\langle q_{k}-q^{*},\ s_{k}\rangle}{||s_{k}||^{2}}. (7) Поскольку точное решение q^{*} неизвестно, эта формула применима лишь тогда, когда скалярное произведение в числителе может быть преобразовано к вычислимому виду. Соответственно, минимизация расстояния до точного решения возможна не при любом выборе направления спуска. Если она возможна, то на шаге k достигается уменьшение расстояния до точки минимума: ||q_{k+1}-q^{*}||^{2}=||q_{k}-q^{*}||^{2}-\frac{\langle q_{k}-q^{*},\ s_{k}\rangle^{2}}{||s_{k}||^{2}}=||q_{k}-q^{*}||^{2}-||q_{k+1}-q_{k}||^{2}. Суммируя от 0 до n , получаем: ||q_{0}-q^{*}||^{2}-||q_{n+1}-q^{*}||^{2}=\sum\limits_{k=0}^{n}||q_{k+1}-q_{k}||^{2}. Убывающая и ограниченная снизу нулём последовательность ||q_{n}-q^{*}||^{2} имеет предел, перейдём к нему: ||q_{0}-q^{*}||^{2}-\lim\limits_{n\rightarrow\infty}||q_{n}-q^{*}||^{2}=\sum\limits_{k=0}^{\infty}||q_{k+1}-q_{k}||^{2}. (8) Следовательно: • ряд в правой части всегда сходится; • его сумма не превосходит ||q_{0}-q^{*}||^{2} ; • равенство суммы ||q_{0}-q^{*}||^{2} — необходимое и достаточное условие сильной сходимости метода с шагами s_{k} и длиной каждого шага \alpha_{k}(\rho) ; • \lim\limits_{k\rightarrow\infty}||q_{k+1}-q_{k}||=0 (необходимое условие сходимости ряда). Из признака сравнения рядов следует, что для любой числовой последовательности x_{k} такой, что ряд \sum\limits_{k=1}^{\infty}x_{k} расходится, выполнено условие ||q_{k+1}-q_{k}||=o(\sqrt{x_{k}}) . В частности, ||q_{k+1}-q_{k}||=o\left(\frac{1}{\sqrt{k}}\right) . Если s_{k}=-\nabla J(q_{k}) , то \alpha_{k}(\rho)=-\frac{\langle q_{k}-q^{*},\ s_{k}\rangle}{||s_{k}||^{2}}=\frac{\langle q_{k}-q^{*},\ \nabla J(q_{k})\rangle}{||\nabla J(q_{k})||^{2}}=\frac{\langle q_{k}-q^{*},\ A^{*}(Aq_{k}-f)\rangle}{||\nabla J(q_{k})||^{2}}= =\frac{\langle A_{0}(q_{k}-q^{*}),\ Aq_{k}-f\rangle}{||\nabla J(q_{k})||^{2}}=\frac{||Aq-f||^{2}}{||\nabla J(q_{k})||^{2}}\Rightarrow \Rightarrow\alpha_{k}(\rho)=\frac{2J(q_{k})}{||\nabla J(q_{k})||^{2}}. (9) 3.2. Моментный метод минимальных ошибок Моментными называют методы следующего вида: q_{k+1}=q_{k}-\alpha_{k}\nabla J(q_{k})+\gamma_{k}(q_{k}-q_{k-1}) (10) или s_{k}=-\nabla J(q_{k})+\beta_{k}s_{k-1};\quad q_{k+1}=q_{k}+\alpha_{k}s_{k} (11) . Поскольку векторы s_{k-1} и q_{k}-q_{k-1} коллинеарны, эти записи эквивалентны, и одни коэффициенты можно выразить через другие: \gamma_{k}\alpha_{k-1}=\alpha_{k}\beta_{k} . Можно заметить, что к данному классу относятся различные уже рассмотренные методы, такие как метод сопряжённых градиентов, метод подобных треугольников или метод тяжёлого шарика. Идея заключается в том, чтобы оптимально подобрать коэффициенты. Выполним вспомогательную двумерную минимизацию расстояния до точного решения при вычислении q_{k+1} в форме ( 10 ). Пусть \gamma_{0}=0 , \alpha_{0}=\alpha_{0}(\rho) . q_{k}\not=q^{*} (иначе новый шаг не нужен). ||q_{k+1}-q^{*}||^{2}=||q_{k}-q^{*}-\alpha_{k}\nabla J(q_{k})+\gamma_{k}(q_{k}-q_{k-1})||^{2}= =||q_{k}-q^{*}||^{2}+\alpha_{k}^{2}||\nabla J(q_{k})||^{2}+\gamma_{k}^{2}||q_{k}-q_{k-1}||^{2}-2\alpha_{k}\langle q_{k}-q^{*},\nabla J(q_{k})\rangle+ +2\gamma_{k}\langle q_{k}-q^{*},q_{k}-q_{k-1}\rangle-2\alpha_{k}\gamma_{k}\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle. Вычислим частные производные. Их равенство нулю является необходимым условием экстремума. \frac{1}{2}\frac{\partial}{\partial\alpha_{k}}||q_{k+1}-q^{*}||^{2}=\alpha_{k}||\nabla J(q_{k})||^{2}-\gamma_{k}\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle-\langle q_{k}-q^{*},\nabla J(q_{k})\rangle; \frac{1}{2}\frac{\partial}{\partial\gamma_{k}}||q_{k+1}-q^{*}||^{2}=-\alpha_{k}\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle+\gamma_{k}||q_{k}-q_{k-1}||^{2}+\langle q_{k}-q^{*},q_{k}-q_{k-1}\rangle. Преобразуем слагаемые, содержащие q^{*} : \langle q_{k}-q^{*},\nabla J(q_{k})\rangle=\langle q_{k}-q^{*},A^{*}(Aq_{k}-f)\rangle=\langle A_{0}(q_{k}-q^{*}),Aq_{k}-f\rangle= =||Aq_{k}-f||^{2}=2J(q_{k}); (12) \langle q_{k}-q^{*},q_{k}-q_{k-1}\rangle=0, потому что q_{k} выбрано на предыдущем шаге, как ближайший к q^{*} элемент линейного многообразия q_{k-1}+Lin\left\{\nabla J(q_{k-1}),q_{k-1}-q_{k-2}\right\} , а это проекция на гиперплоскость. Итак, получаем систему линейных уравнений: \begin{cases}\alpha_{k}||\nabla J(q_{k})||^{2}-\gamma_{k}\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle=2J(q_{k});\\ -\alpha_{k}\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle+\gamma_{k}||q_{k}-q_{k-1}||^{2}=0.\end{cases} Для её решения необходимо проверить, что она не является вырожденной. Для этого вычислим определитель: \Delta=||\nabla J(q_{k})||^{2}||q_{k}-q_{k-1}||^{2}-\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle^{2}. Неравенство Коши — Буняковского показывает, что всегда \Delta\geq 0, и равенство эквивалентно коллинеарности \nabla J(q_{k}) и q_{k}-q_{k-1} . Поскольку \langle q_{k}-q^{*},q_{k}-q_{k-1}\rangle=0, одновременно выполняется и следующее равенство: 2J(q_{k})=\langle q_{k}-q^{*},\nabla J(q_{k})\rangle=\langle q_{k}-q^{*},\lambda(q_{k}-q_{k-1})\rangle=0. Но это возможно только в том случае, когда q_{k} — точное решение задачи. По исходному предположению, это не так. Близость \Delta к нулю обозначает плохую обусловленность системы и низкую точность очередного шага в условиях реальных вычислений. Этот признак может быть использован для формулировки критерия остановки метода. Если решение задачи оптимизации не достигнуто, то \Delta>0 . Тогда система имеет единственное решение (\alpha_{k},\gamma_{k}) . Оно является точкой минимума ||q_{k+1}-q^{*}||^{2} , поскольку матрица вторых производных — положительно определённая по критерию Сильвестра: её главные миноры ||\nabla J(q_{k})||^{2} и \Delta положительны. Осталось вычислить это решение. Из второго уравнения: \gamma_{k}=\alpha_{k}\cdot\frac{\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle}{||q_{k}-q_{k-1}||^{2}}. Подставляя в первое уравнение, получаем: \alpha_{k}=\frac{2J(q_{k})}{||\nabla J(q_{k})||^{2}-\frac{\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle^{2}}{||q_{k}-q_{k-1}||^{2}}}. Полученный метод является оптимальным среди моментных методов по признаку уменьшения расстояния до точного решения после одного шага. Введём обозначение: s_{k}=-\nabla J(q_{k})+\frac{\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle}{||q_{k}-q_{k-1}||^{2}}(q_{k}-q_{k-1}). Поскольку q_{k}-q_{k-1}=\alpha_{k-1}s_{k-1}, выполняется равенство: s_{k}=-\nabla J(q_{k})+\beta_{k}s_{k-1}, где \beta_{k}=\frac{\langle\nabla J(q_{k}),s_{k-1}\rangle}{||s_{k-1}||^{2}}. Очевидно, \langle s_{k},q_{k}-q_{k-1}\rangle=0 . Поэтому ||s_{k}||^{2}+\frac{\langle\nabla J(q_{k}),q_{k}-q_{k-1}\rangle^{2}}{||q_{k}-q_{k-1}||^{2}}=||\nabla J(q_{k})||^{2}, откуда \alpha_{k}=\frac{2J(q_{k})}{||s_{k}||^{2}}. Вычисление \alpha_{k}(\rho) для введённого шага s_{k} приводит к тому же результату: \alpha_{k}(\rho)=-\frac{\langle q_{k}-q^{*},s_{k}\rangle}{||s_{k}||^{2}}=\frac{\langle q_{k}-q^{*},\nabla J(q_{k})\rangle}{||s_{k}||^{2}}-\beta_{k}\frac{\langle q_{k}-q^{*},s_{k-1}\rangle}{||s_{k}||^{2}}=\frac{2J(q_{k})}{||s_{k}||^{2}}, так как \langle q_{k}-q^{*},s_{k-1}\rangle=0 по доказанному в ходе преобразования частных

Read the complete text