Ограничение Scipy минимизировать: одно из двух значений должно быть нулевым - PullRequest
Новая
       59

Ограничение Scipy минимизировать: одно из двух значений должно быть нулевым

0 голосов
/ 19 марта 2020

Я хочу минимизировать следующую функцию: 

def objective(B, P, O):
    return - (sum([(p * o - 1) * b for p, o, b in zip(P, O, B)]) /\
    math.sqrt(sum([(1-p) * p * b**2 * o**2 for p, o, b in zip(P, O, B)])))

sol = minimize(objective, x0=bets, args=(P,O,), method='SLSQP', bounds=bnds, constraints=constr)

Я хочу добавить следующее ограничение к B = [1,2,3,4,5,6,....] (B всегда имеет четную длину):

Для каждой пары в list (1,2), (3,4), (5,6) ... (b1, b2), ровно одно из двух значений должно стать 0 в конце оптимизации. Итак, с логической точки зрения: b1 + b2 = b1 xor b1 + b2 = b2

Если я напишу это как ограничение, оно будет выглядеть примерно так: 

def constb(B):
    for i in range(0, len(B), 2):
        b1, b2 = B[i:i+2]
        if b1 == 0.0:
            return b2 + b1 - b2
        elif b2 == 0.0:
            return b1 + b2 - b1
        else: 
            return 42

Ограничения выглядят так: 

constr = [{'type': 'ineq', 'fun': lambda x: sum(x) - 100},
          {'type': 'eq', 'fun': constb}]

Но это не работает, так как мои пары выглядят так в конце (Мои границы (0,20) для каждого значения): 

20.0 20.0
20.0 20.0
20.0 20.0
20.0 20.0
20.0 20.0

Казалось бы, алгоритм по умолчанию в ограничении на else заявление. Я попытался инициализировать B как 0, но затем возникла MathError, потому что невозможно разделить на 0.

Есть ли способ реализовать это?

1 Ответ

1 голос
/ 19 марта 2020

Нет. В общем, это невозможно.

A: Эти ограничения похожи на дизъюнкции или ограничения кардинальности, типичные вещи, которые ставят проблемы оптимизации NP-hard.

B: Решатели в scipy.minimize основаны на некоторых сильных предположениях и обеспечивают локально-оптимальные значения за полиномиальное время. Основное предположение, которое вы игнорируете, таково:

  • ограничения + цель дважды дифференцируемы
    • простое правило: если вы используете вещи if-else в ваших объектах / ограничениях, вероятно, это не дважды diff!

А и В вместе должны прояснить, что вы отчасти потерялись.

См. также это связанное введение из Стэнфорда по Выпукло-кардинальные проблемы , которые очерчивают проблему. (Имейте в виду, что эта topi c является более общей и только связана с вашей проблемой; для вашего примера, дизъюнктивное представление по проблеме более специализировано!)

Либо вы отказываетесь от точности / go для аппроксимации и выполняете эти трюки l1-нормы, как это сделано в машинном обучении и совместной работе (см. lasso -optimization). Это нетривиально для настройки = выбора гиперпараметров (а также раздражает реализация в scipy -> запомнить => дважды-разность => вы не можете использовать np.linalg.norm(x, 1), но потребуется переформулировка, которая также делает проблему намного более сложной для решателей в scipy)

Или вы отказываетесь от алгоритмов полиномиального времени и go для смешанного целого числа математической оптимизации. Это не часть scipy.

Кандидатные подходы тогда:

  • Смешанное целочисленное программирование (линейное)
    • Например, CoinOR Cb c
  • различные выпукло-целочисленные программы
    • QP, SOCP, SDP и др.
  • общие положения Нелинейное смешанное целочисленное программирование
    • например, CoinOR Bonmin (локальный) / Couenne (глобальный)

Мне лень анализировать вашу цель, но кажется, что первое не обсуждается, поскольку у вас есть нелинейные части (квадрат- root).

...