Библиотека 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 отправить.