Градиентный поиск коэффициентов квадратической регрессии

Мое основное увлечение — это аэрокосмос. И «космические» задачи — выведение полезных грузов на орбиту, возврат с орбиты через атмосферу являются функциями от целого набора параметров. К примеру, управление РН на первой ступени даже в двухмерной (без учета изменения азимута и dog-leg маневра)описывается по меньшей мере через 5 переменных:

  • продолжительность вертикального участка набора высоты после старта;

  • угол атаки при начале гравитационного разворота;

  • продолжительность маневра заклонения;

  • угол атаки после выполнения гравитационного разворота;

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

Еще можно добавить сюда дросселирование двигателей, ограничения по скоростному напору, требования по запасу топлива для возврата и посадки первой ступени.

Так что даже в самой простой постановке нужно рассматривать вектор из 10-15 компонентов (не забываем, есть еще 2-ья и 3-ья ступень, поля падения отработавших ступеней и обтекателей и еще много интересного). Аналитически через набор готовых формул такую задачу не решить. Нужны численные методы, среди которых известны, просты и понятны методы градиентного поиска. (я знаю про методы случайного поиска, генетические алгоритмы и swarm-методы, но мне нужно прозрачное, быстрое, грязное и надежное решение, которое не будет пытаться стать умнее меня)

Градие́нт (от лат gradiens, род. падеж gradientis — шагающий, растущий) — вектор, своим направлением указывающий направление наискорейшего возрастания некоторой величины.

Вычисление градиента из конечных разностей
Вычисление градиента из конечных разностей

Осталось только найти величину шага, по которому мы будем продвигаться в направлении градиента вдоль каждого измерения. Постоянный шаг — простое и понятное решение, но разные переменные оказывают разное влияние на целевую функцию, и при постоянном шаге велика вероятность начать блуждание вдоль склонов «хребта» из локальных оптимумов.

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

Делим отрезок пополам, сопоставляем значения вокруг точки дробления, идем дальше
Делим отрезок пополам, сопоставляем значения вокруг точки дробления, идем дальше

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

А чтобы не вывихнуть свой мозг сразу, начнем с простой и проверяемой задачи квадратичной регрессии. Суть проста — есть набор экспериментальных данных, описывающих зависимость некоего Y от параметра X (набор зашумлен и замусорен).

Надо найти такие коэффициенты a0, a1 и a2 для параболической функции, чтобы эта функция-аппроксимация, пропущенная через экспериментальный набор точек, имела бы наименьшее среднее отклонение между квадратичной аппроксимацией и экспериментальными данными. Такая задача была многократно решена самыми разными способами, и эти решения уже давно встроены в Excel, openOffice, MathCAD.

Поставим задачу: для фиксированной набора данных вида [X, Y] найти значения коэффициентов регрессии a0, a1, a2, чтобы сумма для всех X из нашей выборки |R(a0, a1, a2, X) — Y| была минимальна.

Начнем движение из точки [-5, -5, -5] (это не самая лучшая точка, и в идеале поиск стартовой точки должен решаться отдельно, но старт из субоптимальный условий — хорошая проверка расчетной схемы на устойчивость).

От разности в 5540 к скромным 27 за 14 шагов
От разности в 5540 к скромным 27 за 14 шагов

Теперь сравним полученные результаты с квадратичной регрессией, встроенной в openOffice.

Красная линия - встроенныая квадратичная регрессия planMaker-а, темно-малиновая - регрессия, коэффициенты которой получены градиентным поиском
Красная линия — встроенныая квадратичная регрессия planMaker-а, темно-малиновая — регрессия, коэффициенты которой получены градиентным поиском

Теперь сравним количественные характеристики.

*-индекс значений, полученных градиентным способом, t-индекс встроенной регрессии планмейкера. Самопальный метод выигрывает на 9,46%
*-индекс значений, полученных градиентным способом, t-индекс встроенной регрессии планмейкера. Самопальный метод выигрывает на 9,46%

Выводы

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

Работоспособность метода подтверждена на задаче поиска коэффициентов квадратичной регрессии, в качестве эталона использовалась встроенная в openOffice planmaker функция полиноминальной регрессии.

Когда-нибудь я прикручу этот градиентный движок к своему рокетсайенсу.

Исходники алгоритма живут на моём гитхабе

Читайте так же:

  • Что нам стоит дом построить? (часть 3)Что нам стоит дом построить? (часть 3) Продолжаем рассказывать про ECM-систему, разработкой которой мы занимаемся. С момента выхода предыдущей статьи прошло достаточно много времени, и мы успели не только создать прототип, но и реализовать немалое количество функционала. Сейчас мы готовы выйти в опытную эксплуатацию, поэтому […]
  • Mail.ru Group создаст образовательный холдинг Skillbox LimitedMail.ru Group создаст образовательный холдинг Skillbox Limited Mail. ru Group совместно с основателями Skillbox и частным фондом Александра Галицкого создадут образовательный холдинг Skillbox Limited на базе платформ Skillbox и GeekBrains. Его возглавит гендиректор Skillbox Дмитрий Крутов. Компании объединят финансовые ресурсы и обеспечат […]
  • Мошенники подняли спам-сайт на первые страницы выдачи Google в НорвегииМошенники подняли спам-сайт на первые страницы выдачи Google в Норвегии В Норвегии несколько дней идет масштабная атака на поиск Google. На первых страницах выдачи по практически любым запросам высока вероятность встретить датский спам-домен havfruen4220.dk замаскированный картинкой со «Смешариками». Один спамерский домен получает большую долю всего […]
  • Что нужно сделать прямо сейчас, чтобы получить первые заказы на UpworkЧто нужно сделать прямо сейчас, чтобы получить первые заказы на Upwork Я раньше думал, что это абсолютно нереально — получить первый заказ на фриланс бирже. Думал, что надо читерить, добывать фейковые отзывы, просить друзей сделать заказ или выполнять работу за бесплатно. Но бирже выгодно, чтобы я зарабатывал, нужно лишь правильно использовать инструменты, […]