Использование scipy.optimize.fmin_slsqp

Question

Я пытаюсь использовать пакет scipy.optimize, чтобы найти максимум моей функции стоимости.

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

price_list = np.array([1,2,6,8,8,5,2,1])

В этом упрощенном случае я хочу выбрать 4 максимальных цены из этого прайс-листа. И по разным причинам я не хочу просто сортировать и выбирать лучшие четыре цены, но использую некоторый алгоритм оптимизации. У меня есть несколько ограничений, поэтому я решил использовать алгоритм наименьших квадратов из scipy, scipy.optimize.fmin_slsqp.

Сначала я создаю расписание для выбранных часов:

schedule_list = np.zeros( len(price_list), dtype=float)

Далее мне нужно определить мою обратную функцию-прибыль. За все выбранные часы я хочу подвести итоги своей прибыли. Хотя я хочу оптимизировать свой график, price_list фиксирован, поэтому мне нужно поместить его в *args:

def price_func( schedule_list, *price_list ):
    return -1.*np.sum( np.dot( schedule_list, price_list ) )

Как только я пойму, как все работает в принципе, я переверну некоторые вещи. До тех пор, пока я просто не использую больше аргументов *, я определяю свое ограничение с жестко запрограммированным количеством часов для запуска. И я хочу, чтобы мои выбранные часы были ровно 4, поэтому я использую ограничение равенства:

def eqcon(x, *price_list):
    return sum( schedule_list ) - 4

Кроме того, я хочу ограничить значения моего расписания либо 0, либо 1. Я не уверен, как реализовать это прямо сейчас, поэтому я просто использую ключевые слова bounds.

Неограниченная оптимизация с границами работает нормально. Я просто передаю свой schedule_list как первое предположение.

scipy.optimize.fmin_slsqp( price_func, schedule_list, args=price_list, bounds=[[0,1]]*len(schedule_list) )

и результат настолько хорош, насколько это возможно:

Optimization terminated successfully.    (Exit mode 0)
        Current function value: -33.0
        Iterations: 2
        Function evaluations: 20
        Gradient evaluations: 2
Out[8]: array([ 1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.])

Без каких-либо дополнительных ограничений это оптимальное решение!

Используя ограниченную оптимизацию с помощью следующей команды:

scipy.optimize.fmin_slsqp( price_func, schedule_list, args=price_list, bounds=[[0,1]]*len(schedule_list), eqcons=[eqcon, ] )

дает мне ошибку:

Singular matrix C in LSQ subproblem    (Exit mode 6)
        Current function value: -0.0
        Iterations: 1
        Function evaluations: 10
        Gradient evaluations: 1
Out[9]: array([ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.])

Из gnuplot я знаю, что это часто связано с бессмысленными вопросами или плохими начальными значениями. Я попробовал почти оптимальные начальные значения, но это не помогает. У кого-нибудь есть идея или даже решение для меня?

На следующем этапе я уже сформулировал ограничения неравенства. Правильно ли я понимаю, что в оболочке минимизации scipy предполагается, что неравенства больше 0, а в fmin_slsqp - наоборот. Решения ограничены отрицательными функциями ограничения?

Answer 1

У вас есть простая линейная программа, верно?

min: - prices . x
constrain: x >= 0, sum x = 4

так что вторая производная матрица, также известная как гессиан, равна 0
slsqp пытается инвертировать это --- не возможно. Согласен, сообщение об ошибке может быть лучше.
(То же самое случится с другими квадратичными методами в любом пакете: они будут сходиться намного быстрее при гладких функциях, но падать на грубых скалах.)

См. Также, почему cant-i-rig-scipys-constrained-optimized-for-integer-программирование -
но LP должен делать работу (максимум 4), целочисленное программирование сложнее.

Answer 2

Алгоритм SLSQP является оптимизатором на основе градиента, то есть он ожидает, что производные цели и ограничений будут непрерывными. Насколько я понимаю, кажется, что вы пытаетесь решить задачу целочисленного программирования (непрерывные значения в списке расписания недопустимы). Вам нужен алгоритм, который выбирает подходящие значения (0 или 1) для независимых переменных, а не пытается найти минимум непрерывного пространства значений. К сожалению, я не уверен, что в scipy есть такие.

Answer 3

В вашем коде есть ошибки. верное:

1. def price_func( schedule_list, price_list )
2. def eqcon(schedule_list , price_list):
       return sum( schedule_list ) - 4
3. scipy.optimize.fmin_slsqp( price_func, schedule_list, args=(price_list,), bounds=[[0,1]]*len(schedule_list), eqcons=[eqcon, ] )

тогда это работает.