Библиотека C++ для поиска min методом градиентного спуска

[Igor_Dmitriev]

Здравствуйте.
Сейчас решаю задачу поиска минимума с помощью производных в Matlab, используя функцию fmincon. Те параметры, которые я пытаюсь найти, должны быть в определённых сегментах, других ограничений нет. Функция дифференцируема, используются только первые призводные. Мне кажется, что C++ должен работать быстрее, чем Matlab. Посоветуйте, пожалуйста, библиотеку с алгоритмами и примерами. Если есть такие библиотеки на Python (досутуп через Python, но внутренность написана на плюсах), то тоже было бы интересно узнать.

Если кто-то решал подобные задачи на Matlab, Python и C++, напишите, пожалуйста, изменилась ли скорость вычисления.

[mihaild]

Просто градиентный спуск - любая библиотека для нейронок (tensorflow, pytorch). Правда там ничего кроме символьного дифференцирования и арифметики не будет, ограничения придется как-то достраивать руками.

[dsge]

Igor_Dmitriev в сообщении #1715067 писал(а):

Мне кажется, что C++ должен работать быстрее, чем Matlab.

Igor_Dmitriev в сообщении #1715067 писал(а):

Если кто-то решал подобные задачи на Matlab, Python и C++, напишите, пожалуйста, изменилась ли скорость вычисления.

Matlab позволяет разрабатывать функции на С++, так называемые МЕХ-функции. У меня эти трюки только замедлили вычисления. Возможно потому, что большинство встроенных (built-in) функций MATLABа уже написаны на C/C++.

[worm2]

я в сообщении #61280 писал(а):

Есть серьёзная библиотека, DONLP2 (на C и Фортране), для решения задачи нелинейного программирования. Там используется метод SQP. Насколько я знаю, эта библиотека используется в Матлабе. Сам пробовал, правда, на задачах попроще --- мне понравилось.

Почти за 20 лет ссылка протухла (кто бы сомневался). Хотя поискать на просторах можно. Например, мне выдаёт что-то про "IMSL C Library".
Но выигрыша в скорости едва ли можно ожидать, используя эту библиотеку напрямую: Матлаб, R и прочие Питоны ведь тоже её же под капотом и используют.

[Mental]

(Gemini 3.5)

#include <iostream>
#include <cmath>
#include <iomanip>

// Функция, которую мы хотим минимизировать: f(x) = (x - 3)^2 + 5
double function(double x) {
    return std::pow(x - 3, 2) + 5;
}

// Производная функции (градиент): f'(x) = 2 * (x - 3)
double gradient(double x) {
    return 2 * (x - 3);
}

int main() {
    // Параметры алгоритма
    double x_current = 0.0;       // Начальное приближение
    double learning_rate = 0.1;   // Шаг обучения (alpha)
    double precision = 0.000001;  // Точность (критерий остановки)
    int max_iterations = 1000;    // Максимальное число итераций

    int iteration = 0;
    double x_next;

    std::cout << "Начало оптимизации..." << std::endl;
    std::cout << std::fixed << std::setprecision(6);

    while (iteration < max_iterations) {
        // Формула: x_next = x_current - alpha * f'(x_current)
        x_next = x_current - learning_rate * gradient(x_current);

        // Проверка условия сходимости (если изменение ничтожно мало)
        if (std::abs(x_next - x_current) < precision) {
            break;
        }

        x_current = x_next;
        iteration++;

        std::cout << "Итерация " << iteration << ": x = " << x_current 
                  << ", f(x) = " << function(x_current) << std::endl;
    }

    std::cout << "\nМинимум найден в точке: " << x_current << std::endl;
    std::cout << "Значение функции в этой точке: " << function(x_current) << std::endl;
    std::cout << "Количество итераций: " << iteration << std::endl;

    return 0;
}

[Igor_Dmitriev]

Mental в сообщении #1715240 писал(а):

(Gemini 3.5)

std::pow(x - 3, 2) + 5

Спасибо за пример, но моя функция гораздо сложнее, много локальных ям, простым градиентным спуском искать минимумы сильно долго, для этого мне и нужны более сложные алгоритмы поиска, которые уже написаны.

worm2 в сообщении #1715134 писал(а):

Но выигрыша в скорости едва ли можно ожидать, используя эту библиотеку напрямую: Матлаб, R и прочие Питоны ведь тоже её же под капотом и используют.

dsge в сообщении #1715083 писал(а):

У меня эти трюки только замедлили вычисления. Возможно потому, что большинство встроенных (built-in) функций MATLABа уже написаны на C/C++.

Была надежда, что кто-то напишет о десятикратном ускорении. Но всё равно спасибо, что написали, тогда пока что отложу идею о переписывании.

-- 03.02.2026, 13:55 --

mihaild в сообщении #1715070 писал(а):

ограничения придется как-то достраивать руками.

А как их достраивать? Для одних случаев использовать метод неопределённых множителей Лагранжа, а для других просто добавить в целевую функцию положительное слагаемое, которое быстро растёт при отклонении от заданных значений или есть ещё какие-нибудь методы?
Например, если надо найти минимум функции $f = x^2+y^2$ при $2 < x < 4$ и $1 < y < 3$, то надо заменить нашу функцию на $f = x^2+y^2 + \alpha \cdot (e^{-(x - 3)^2} + e^{-(y - 2)^2}) $, где в зависимости от необходимой точности надо методом подбора найти значение $ 10^{-6} < \alpha < 10^{-2} $ ?
Или есть ещё какие-то стандартные способы и методы?

[dsge]

Igor_Dmitriev в сообщении #1717116 писал(а):

Например, если надо найти минимум функции $f = x^2+y^2$ при $2 < x < 4$ и $1 < y < 3$, то надо заменить нашу функцию на $f = x^2+y^2 + \alpha \cdot (e^{-(x - 3)^2} + e^{-(y - 2)^2}) $, где в зависимости от необходимой точности надо методом подбора найти значение $ 10^{-6} < \alpha < 10^{-2} $ ?
Или есть ещё какие-то стандартные способы и методы?

Если вы будете минимировать функцию

f =$x^2+y^2 -1/t(-\ln(-x+4)-\ln(-2+x)-\ln(-y+3)-\ln(-1+y))$,

то при увеличении $t$ это будет метод внутренней точки, один из самых эффективных. Однако, в матлабовской функции fmincon, вроде уже есть опция применить этот метод

[Igor_Dmitriev]

dsge в сообщении #1717312 писал(а):

Если вы будете минимировать функцию
f =$x^2+y^2 -1/t(-\ln(-x+4)-\ln(-2+x)-\ln(-y+3)-\ln(-1+y))$

Странная функция, $t$ в знаменателе, а логарифмы в числителе? Почему она не симметрична относительно центра окна?

dsge в сообщении #1717312 писал(а):

в матлабовской функции fmincon, вроде уже есть опция применить этот метод

Да, там есть возможность добавить эти условия, но я переспросил про самостоятельное задание условий, потому что речь перешла на Python и C++.
Кроме того, не все матлабовские алгоритмы поддерживают гессиан с одновременным заданием разных условий, иногда приходится протаскивать условия в саму функцию.

[dsge]

Igor_Dmitriev в сообщении #1717336 писал(а):

Странная функция, $t$ в знаменателе, а логарифмы в числителе?

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

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

[Mental]

Igor_Dmitriev в сообщении #1717116 писал(а):

Спасибо за пример, но моя функция гораздо сложнее, много локальных ям, простым градиентным спуском искать минимумы сильно долго, для этого мне и нужны более сложные алгоритмы поиска, которые уже написаны.

Напишите промт, могу в Gemini Pro отправить.

[Igor_Dmitriev]

Mental в сообщении #1717457 писал(а):

Напишите промт, могу в Gemini Pro отправить.

Спасибо за предложенную помощь, но судя по предварительным расчётам, функции на C++ должны работать быстрее.
Попробовал на локальной машине вычислять куски функции, С++ оказался в 5 раз быстрее Matlab. Если ничего не оптимизировать, то С++ примерно в 2 раза быстрее. На Python не пробовал, но полагаю, что разница в скорости работы уже не будет такой большой из-за того, что некоторые виды оптимизации были связаны с доступом к памяти в С++.

Надо либо попытаться найти и использовать алгоритм оптимизации для С++, либо использовать функции, написанные на C++, в Matlab. Но в случае выбора второго варианта, как здесь уже написали, может оказаться, что плюсовые функции работают в Matlab уже не так быстро, как хотелось бы.

[Igor_Dmitriev]

Mental в сообщении #1717457 писал(а):

Напишите промт, могу в Gemini Pro отправить.

1. Write a C++ function implementing the sequential quadratic programming (SQP) optimization algorithm. The function must have the following parameters: objective function, gradient, starting point, parameter constraints, boundary constraints, and stopping conditions. Use only standard library (stl). Print example.

2. Write a C++ function implementing the trust region reflection (TRR) optimization algorithm. The function must have the following parameters: objective function, gradient, Hessian, starting point, parameter constraints, boundary constraints, and stopping conditions. Use only standard library (stl). Print example.

3. Write a C++ function implementing the sequential quadratic programming (SQP) optimization algorithm. The function must have the following parameters: objective function, gradient, starting point, parameter constraints, boundary constraints, and stopping conditions. Print example.

4. Write a C++ function implementing the trust region reflection (TRR) optimization algorithm. The function must have the following parameters: objective function, gradient, Hessian, starting point, parameter constraints, boundary constraints, and stopping conditions. Print example.

1 почти похоже на 3, а 2 почти похоже на 4
Попробовал напечатать команды 1 и 2 в бесплатных чатах, посмотрю, что они там написали. Если есть возможность, наберите, пожалуйста, команды 1, 2, 3, 4 в платном чате.

[Mental]

Igor_Dmitriev в сообщении #1717921 писал(а):

Write a C++ function

Поскольку форум не дает создавать большие сообщения с кодом, разместил на внешнем ресурсе:
https://docs.google.com/document/d/1GAg ... sp=sharing

[Igor_Dmitriev]

Mental в сообщении #1718048 писал(а):

разместил на внешнем ресурсе

Спасибо, скачал, переделал под свои нужды. Сейчас C++ алгоритмы работают намного быстрее тех, которые были написаны на Matlab, за тот же промежуток времени ищут больше минимумов, которые к тому же более глубокие. Наверное, где-то неправильно поставил параметры или ошибся, потому что не всегда в найденных точках производные близки к нулю. Иногда бывает, что в более глубоких C++ минимумах градиент отличен от нуля, в то время как у всех решений Matlab градиент близок к нулю. То ли сильно рано останавливается, то ли дело в граничных условиях. Если кто-то сталкивался с подобным, просьба написать.

Если кому-то интересно, для Matlab кроме градиента был написан Гессиан, его удалось выразить через промежуточные результаты, в итоге время расчёта целевой функции увеличилось вдвое, но итоговые результаты улучшились на 10%. Хорошо, что хотя бы не уменьшились, но я ожидал от Гессиана большего.

[Igor_Dmitriev]

Как известно, алгоритм оптимизации можно при необходимости дополнить условием $g(x) < 0$.
Предположим, что есть функция $f(x, t)$ в точках $t_1 ... t_n$, величина $x$ векторная. Нужно найти минимум функции $F = (f(x, t_1) - a_1)^2 + ... + (f(x, t_n) - a_n)^2$ при условиях $g_i = f(x, t_i) \cdot a_i > 0$.
Понятно, что при опреденённом виде функции $f(x, t_i)$ и определённых значениях $x$ условие будет выполняться автоматически. Но для достаточно малых по модулю $a_i$ добиться этого всё сложнее. Как не прибегая к введению в алгоритм отдельного условия-неравенства вшить такие условия в целевую функцию? Первое, что приходит в голову, является замена, когда вместо старой $F$ используем $F = 5 \cdot(f(x, t_1) - a_1)^2 + ... + (f(x, t_n) - a_n)^2$ для того случая, когда $a_1$ мал по модулю. А есть ли более удачные способы?