Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Оптимизация методом координатного спуска

Автор: rudolfninja 16.10.2014, 23:47

Ребята, приветствую.
Сразу извиняюсь, если тему нужно было создать в "Центре помощи", но, по-моему, тут она более уместна.
Проблема вот в чем, нужно написать алгоритм поиска минимума многомерной функции методом Гаусса-Зейделя (или координатного спуска). В качестве метода поиска минимума одномерной функции использовать метод золотого сечения. Я написал функции на Си++, одна функция находит минимум одномерной функции методом золотого сечения, другая - непосредственно метод координатного спуска.
Для примера была дана тестовая целевая функция с начальными значениями.

Код


F(x1, x2, x3) = exp(x1 + x2 + x3)/(x1*x2^2*x3^3);
x1_0 = 0.5, x2_0 = 0.5, x3_0 = 0.5;
Шаг (H) = 0.5; 
Погрешность (eps) = 0.0001;

Я старался написать наиболее универсальный код, но вышло как вышло. У меня возникло, пока что, два вопроса:
1) Какие границы отрезка передавать в метод золотого сечения?
2) Зачем нужен шаг, если поиск минимума одномерной функции проводится по методу золотого сечения, а не через частные производные

Код


double full_function(double x1, double x2, double x3) {return (exp(x1 + x2 + x3)/(x1 * x2 * x2 * x3 * x3 * x3));}
double f2(double x2, double x1, double x3) {return (exp(x1 + x2 + x3)/(x1 * x2 * x2 * x3 * x3 * x3));}
double f3(double x3, double x1, double x2) {return (exp(x1 + x2 + x3)/(x1 * x2 * x2 * x3 * x3 * x3));}
double golden_section(func_ptr f, double first_var, double second_var, double eps, double a, double b);

int _tmain(int argc, _TCHAR* argv[])
{
    double eps = 0.0001;
    double step = 0.5;
    int steps_count = 100;
    double x10 = 0.5, x20 = 0.5, x30 = 0.5;
    double x1 = x10, x2 = x20, x3 = x30;
    double B = full_function(x10, x20, x30), A = 0;

    for(int i = 0; i < steps_count; i++) {
        A = B;

        x1 = golden_section(full_function, x2, x3, eps, x1, x1 + step);
        x2 = golden_section(f2, x1, x3, eps, x2, x2 + step);
        x3 = golden_section(f3, x1, x2, eps, x3, x3 + step);
        
        B = full_function(x1, x2, x3);

        if(fabs(A - B) <= eps)
        {
            std::cout << i+1 << std::endl;
            break;
        }
    }

    std::cout << x1 << std::endl;
    std::cout << x2 << std::endl;
    std::cout << x3 << std::endl;
    std::cout << full_function(x1, x2, x3) << std::endl;

    return 0;
}

метод golden_section работает правильно и возвращает значение аргумента при котором значение функции будет минимальным на заданном отрезке. Это я проверял на нескольких различных примерах.
В итоге программа выдает результат не такой, который должен быть, но довольно близкий к нему. Это только на этом примере. Переписывал целевые функции для других примеров (с последующей корректировкой функций main и golden_section), вообще ерунда какая-то получается.
В общем, если кто видит ошибки/недочеты в моей реализации и(или) может ответить на вопросы, написанные выше, ответьте, пожалуйста.

Спасибо.

Автор: Akina 17.10.2014, 08:01

Цитата(rudolfninja @ 17.10.2014, 00:47

)

Какие границы отрезка передавать в метод золотого сечения?

Гарантированно охватывающие минимум, не захватывающие точек разрыва, не выходящие за пределы существования.

Цитата(rudolfninja @ 17.10.2014, 00:47

)

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

Где написано, что ВСЕ параметры обязаны быть использованы?

Автор: rudolfninja 17.10.2014, 09:09

Цитата(Akina @ 17.10.2014, 08:01

)

А как я узнаю, что они гарантированно охватывают минимум?

Цитата(Akina @ 17.10.2014, 08:01

)

Где написано, что ВСЕ параметры обязаны быть использованы?

Такого не написано, но зачем, тогда нагружать лишними данными?

Автор: Akina 17.10.2014, 11:13

Цитата(rudolfninja @ 17.10.2014, 10:09

)

как я узнаю, что они гарантированно охватывают минимум?

Ну, например, для контроля можно посмотреть чисельно производную в выбранных краевых точках.

Цитата(rudolfninja @ 17.10.2014, 10:09

)

зачем, тогда нагружать лишними данными?

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

Автор: rudolfninja 17.10.2014, 16:21

Akina, а вы знакомы с методом? Шаг вообще должен меняться по ходу изменения координат?

Автор: Akina 17.10.2014, 16:45

Не понял... какой ещё шаг? В золотом сечении шага нет в принципе, а покоординатный спуск - вообще метод не минимизации, а выбора плоскости минимизации.

Автор: rudolfninja 17.10.2014, 16:47

Я имел в виду покоординатный спуск.

Цитата(Akina @ 17.10.2014, 16:45

)

вообще метод не минимизации, а выбора плоскости минимизации.

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

Автор: Akina 17.10.2014, 19:54

Цитата(rudolfninja @ 17.10.2014, 17:47

)

А это не одно и тоже, что и метод минимизации многомерной функции?

Покоординатный спуск - это не метод минимизации! Это метод выбора порядка перебора координат, метод выбора следующей координаты, по которой мы будем искать очередной частный минимум. И далеко не всегда координаты перебираются тупо по порядку в цикле...