Решить недоопределенное линейное уравнение Ax + By = C, где y ограничено x - PullRequest
Новая
       24

Решить недоопределенное линейное уравнение Ax + By = C, где y ограничено x

0 голосов
/ 28 августа 2018

Я новичок в оптимизации и изо всех сил пытался найти переменные x и y в линейном уравнении Ax + By = C, в то время как y ограничено решением x. Примером проблемы может быть: 

A = np.random.rand(20,100)
B = np.random.rand(20,200)
C = np.random.rand(20)

Решите для x и y, чтобы Ax +By = C с ограничениями, которые x неотрицательны и -0.7*x0 < y0,y1 <0.7*x0, -0.7*x1 < y2,y3 <0.7*x1... ( -0.7x[i] < y[2i],y[2i+1]<0.7x[i] )

Я был бы очень признателен, если бы кто-нибудь порекомендовал мне пакет python, который решает эту проблему, или какой-то способ преобразовать мою проблему в более традиционный формат, который может быть решен непосредственно с помощью таких библиотек, как Scipy.optimize

Ответы [ 2 ]

0 голосов
/ 28 августа 2018

Я решил проблему с помощью CVXPY: 

import cvxpy as cp
import numpy as np
m = 20
n = 100
A = np.random.rand(m,n)
B = np.random.rand(m,n)
C = np.random.rand(m,n)
d = np.random.rand(m)

# construct the problem.

x = cp.Variable(n)
y = cp.Variable(n)
z = cp.Variable(n)
objective = cp.Minimize(cp.sum_squares(A*x + B*y + C*z -d))
constaints = [0 <= x, x <= 1, y <= 0.7*x, y >= -0.7*x, z <= 0.7*x, z >= -0.7*x]
prob = cp.Problem(objective, constraints)
result = prob.solve()
0 голосов
/ 28 августа 2018

Это зависит от того, что вы подразумеваете под решением, у того, что вы описали, есть несколько решений, и это внутренность многогранника.

Это проблема линейного программирования, если вы хотите преобразовать задачу в 

-0.7x_0 <=y_0 <= 0.7x_0

Предположим, нет, рассмотрим введение небольшого положительного числа m для создания линейной программы. 

-0.7x_0 + m <=y_0 <= 0.7x_0 - m

Затем вы можете использовать scipy.optimize.linprog для решения линейной программы.

Если вас просто интересует конкретное решение, вы можете просто установить c в целевой функции равным нулю.

Edit: 

import numpy as np
from scipy.optimize import linprog

m_size = 20
bound = 0.7
x_size = 100
y_size = 2 * x_size
small_m = 0

A = np.random.rand(m_size, x_size)
B = np.random.rand(m_size, y_size)
C = np.random.rand(m_size)

A_eq = np.hstack((A, B))
b_eq = C

sub_block = np.array([-bound, -bound ])
sub_block.shape = (2,1)
block = np.kron(np.eye(x_size), sub_block)

upper_block = np.hstack((block, - np.eye(y_size)))
lower_block = np.hstack((block, np.eye(y_size)))

A_ub = np.vstack((upper_block, lower_block))
b_ub = -small_m * np.ones( 2 * y_size)

bounds = tuple([tuple([0, None]) for i in range(x_size)] + [tuple([None, None]) for i in range(y_size)])

c = [0 for i in range(x_size+y_size)]

res = linprog(c, A_ub = A_ub, b_ub = b_ub, A_eq = A_eq, b_eq = b_eq, bounds = bounds)

x_part = res.x[:x_size]
y_part = res.x[x_size:]
...