CVXPY: эффективное написание ограничений для попарных сумм

Я пытаюсь реализовать этот LP в CVXPY:

LP

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

import cvxpy as cp
import numpy as np

n_j = 10
n_i = 100

a = cp.Variable(n_j, nonneg=True)
b = cp.Variable(n_i, nonneg=True)

g = np.random.randint(low=1, high=10, size=n_j)
v = np.random.normal(size=(n_i, n_j))

obj = cp.Minimize(cp.sum(cp.multiply(g, a)) + cp.sum(b))

constraints = [a[j] + b[i] >= values[i, j] 
               for j in range(n_j) for i in range(n_i)]

prob = cp.Problem(obj, constraints)
prob.solve()

python linear-programming cvxpy
person audioslaver756    schedule 09.01.2020    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Мы можем перевести это в матричную запись:

введите здесь описание изображения

где e — векторы-столбцы всех единиц. Конечно, векторы e должны иметь соответствующий размер: каждый терм должен быть матрицей (n_i x n_j).

В CVXPY это можно записать так:

# changed into using explicit column vectors
a = cp.Variable((n_j,1), nonneg=True)
b = cp.Variable((n_i,1), nonneg=True)
g = np.random.randint(low=1, high=10, size=(n_j,1))

# column vectors of ones
e_i = np.ones((n_i,1))
e_j = np.ones((n_j,1))

# matrix style inequality
constraints = [e_i * a.T + b * e_j.T >= v]
person Erwin Kalvelagen    schedule 10.01.2020