LinearConstraint в scipy.optimize

Question

Я хотел бы использовать scipy.optimize, чтобы минимизировать функцию (в конечном итоге нелинейную) над большим набором линейных неравенств.В качестве разминки я пытаюсь минимизировать x + y над полем 0 <= x <= 1, 0 <= y <= 1.Следуя предложению Джонни Драмы, приведенному ниже, в настоящее время я использую dict-comprehesion для составления словаря неравенств, но не получаю ожидаемого ответа (min value = 0, min at (0,0)). </p>

Новый раздел кода (актуально):

import numpy as np
from scipy.optimize import minimize



#Create initial point.

x0=[.1,.1]

#Create function to be minimized

def obj(x):
    return x[0]+x[1]


#Create linear constraints  lbnd<= A*(x,y)^T<= upbnd

A=np.array([[1,0],[0,1]])

b1=np.array([0,0])

b2=np.array([1,1])

cons=[{"type": "ineq", "fun": lambda x: np.matmul(A[i, :],x) -b1[i]} for i in range(A.shape[0])]

cons2=[{"type": "ineq", "fun": lambda x: b2[i]-np.matmul(A[i, :], x) } for i in range(A.shape[0])]

cons.extend(cons2)

sol=minimize(obj,x0,constraints=cons)

print(sol)

Оригинальная версия вопроса:

Я хотел бы использовать объект LinearConstraint в scipy.optimize, как описано в руководстве здесь: «Определение линейных ограничений»

Я попытался сделать более простой пример, где очевидно, каким должен быть ответ: минимизировать x + y над квадратом 0 <= x <= 1, 0 <= y <= 1.Ниже приведен мой код, который возвращает сообщение об ошибке «Объект LinearConstraint не повторяется», но я не вижу, как я пытаюсь выполнить итерацию. </p>

РЕДАКТИРОВАТЬ 1: пример намеренно более простой.В конечном счете, я хочу минимизировать нелинейную функцию по большому количеству линейных ограничений.Я знаю, что могу использовать словарное понимание, чтобы превратить мою матрицу ограничений в список словарей, но я хотел бы знать, можно ли использовать «LinearConstraints» в качестве готового способа превращения матриц в ограничения.

РЕДАКТИРОВАТЬ 2: Как указал Джонни Драма, LinearConstraint для конкретного метода.Итак, выше, я попытался использовать вместо этого его предложение для понимания диктата, чтобы произвести линейные ограничения, но все еще не получаю ожидаемого ответа.

Оригинальный раздел кода (теперь не имеет значения):

from scipy.optimize import minimize
from scipy.optimize import LinearConstraint


#Create initial point.

x0=[.1,.1]

#Create function to be minimized

def obj(x):
    return x[0]+x[1]


#Create linear constraints  lbnd<= A* 
#(x,y)^T<= upbnd

A=[[1,0],[0,1]]

lbnd=[0,0]

upbnd=[0,0]

lin_cons=LinearConstraint(A,lbnd,upbnd)

sol=minimize(obj,x0,constraints=lin_cons)

print(sol)

Answer 1

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

minimize(obj_fun, x0=xinit, bounds=bnds, constraints=cons)

, где obj_fun - ваша целевая функция, xinit начальная точка,bnds список кортежей для границ ваших переменных и cons список диктов.

---

Вот пример.Предполагая, что вы хотите

Поскольку все ограничения являются линейными, мы можем записать его как A * x> = b, где A - матрица 3x2 иb вектор правой стороны 3x1:

import numpy as np
from scipy.optimize import minimize

obj_fun = lambda x: (x[0] - 1)**2 + (x[1] - 2.5)**2
A = np.array([[1, -2], [-1, -2], [-1, 2]])
b = np.array([-2, -6, -2])
bnds = [(0, None) for i in range(A.shape[1])]  # x_1 >= 0, x_2 >= 0
xinit = [0, 0] 

Теперь осталось только определить ограничения, каждое из которых должно быть в форме

{"type": "ineq", "fun": constr_fun}

, где constr_fun является вызываемой функцией, такой, что constr_fun> = 0. Для первого ограничения это будет

{"type": "ineq", "fun": lambda x: x[0] - 2* x[1] + 2}

Поскольку оно работает так же для других, вы можете определить

cons = [{'type': 'ineq', 'fun': lambda x:  x[0] - 2 * x[1] + 2},
        {'type': 'ineq', 'fun': lambda x: -x[0] - 2 * x[1] + 6},
        {'type': 'ineq', 'fun': lambda x: -x[0] + 2 * x[1] + 2}]

и все будет готовоВ качестве альтернативы вы можете передать все ограничения непосредственно с помощью векторной функции (настоятельно рекомендуется в случае множества ограничений):

cons = [{"type": "ineq", "fun": lambda x: A @ x - b}]

Обратите внимание, что @ является оператором матричного умножения (доступно только с Python3.5)и я предположил, что все ограничения являются ограничениями неравенства.

Вызов

res = minimize(obj_fun, x0=xinit, bounds=bnds, constraints=cons)
print(res)

output

     fun: 0.799999999999998
     jac: array([ 0.79999999, -1.59999999])
 message: 'Optimization terminated successfully.'
    nfev: 16
     nit: 4
    njev: 4
  status: 0
 success: True
       x: array([1.39999999, 1.69999999])

---

Редактировать: Чтобы ответить на ваш новый вопрос:

# b1    <= A * x   <==>   -b1 >= -A*x        <==>   A*x - b1 >= 0
# A * x <= b2      <==>    A*x - b2 <= 0     <==>  -Ax + b2 >= 0
cons = [{"type": "ineq", "fun": lambda x: A @ x - b1}, {"type": "ineq", "fun": lambda x: -A @ x + b2}]
sol=minimize(obj,x0,constraints=cons)
print(sol)

Answer 2

Ошибка заключается в том, как вы вызываете функцию minimize

sol= minimize(obj, x0, constraints=lin_cons)

Действительно, ограничения ожидают словарь или список словарей, см. http://scipy.optimize.minimize.

Для вашего конкретного LP я бы написал что-то вроде:

from scipy.optimize import linprog
import numpy as np

c = np.array([1, 1])

res = linprog(c, bounds=(0, 1))

print('Optimal value: {}'.format( res.fun))
print('Values: {}'.format(res.x))

который выводит

Optimal value: -0.0
Values: [ 0.  0.]

поскольку ограничений нет.

Предположим, вы хотите добавить ограничение x + y >= 0.5 (что эквивалентно -x - y <= -0.5). Тогда ваш Lp становится:

c = np.array([1, 1])

A_ub = np.array([[-1,-1]])

b_ub = np.array([-0.5])

res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=(0, 1))

print('Optimal value: {}'.format( res.fun))
print('Values: {}'.format(res.x))

который теперь выводит:

Optimal value: 0.5
Values: [ 0.5  0. ]