Есть ли функция квадратичного программирования, которая может иметь как нижнюю, так и верхнюю границы - Python

Обычно я использую GNU Octave для решения задач квадратичного программирования.

Я решаю такие проблемы, как

x = 1/2x'Qx + c'x

С учетом

A*x <= b
lb <= x <= ub

куда lb а также ub нижние и верхние границы, например, пределы для x

Мой код Octave выглядит так, когда я решаю. Всего одна простая строка

U = quadprog(Q, c, A, b, [], [], lb, ub);

Квадратные скобки [] пусты, потому что мне не нужны ограничения равенства

Aeq*x = beq,

Итак, мой вопрос: есть ли простой в использовании квадратичный решатель в Python для решения проблем

x = 1/2x'Qx + c'x

С учетом

A*x <= b
lb <= x <= ub

Или при условии

b_lb <= A*x <= b_ub
lb <= x <= ub
Источник

3 ответа

Решение

Вы можете написать свой собственный решатель на основе scipy.optimizeВот небольшой пример того, как кодировать свой собственный питон quadprog():

# python3
import numpy as np
from scipy import optimize

class quadprog(object):

    def __init__(self, H, f, A, b, x0, lb, ub):
        self.H    = H
        self.f    = f
        self.A    = A
        self.b    = b
        self.x0   = x0
        self.bnds = tuple([(lb, ub) for x in x0])
        # call solver
        self.result = self.solver()

    def objective_function(self, x):
        return 0.5*np.dot(np.dot(x.T, self.H), x) + np.dot(self.f.T, x)

    def solver(self):
        cons = ({'type': 'ineq', 'fun': lambda x: self.b - np.dot(self.A, x)})
        optimum = optimize.minimize(self.objective_function, 
                                    x0          = self.x0.T,
                                    bounds      = self.bnds,
                                    constraints = cons, 
                                    tol         = 10**-3)
        return optimum

Вот как это использовать, используя те же переменные из первого примера, представленного в matlab-quadprog:

# init vars
H  = np.array([[ 1, -1],
               [-1,  2]])

f  = np.array([-2, -6]).T

A  = np.array([[ 1, 1],
               [-1, 2],
               [ 2, 1]])

b  = np.array([2, 2, 3]).T
x0 = np.array([1, 2])
lb = 0
ub = 2

# call custom quadprog
quadprog  = quadprog(H, f, A, b, x0, lb, ub)
print(quadprog.result)

Результат этого короткого фрагмента:

     fun: -8.222222222222083
     jac: array([-2.66666675, -4.        ])
 message: 'Optimization terminated successfully.'
    nfev: 8
     nit: 2
    njev: 2
  status: 0
 success: True
       x: array([0.66666667, 1.33333333])

Для получения дополнительной информации о том, как использовать scipy.optimize.minimize пожалуйста, обратитесь к документации.

Источник

Если вам нужен общий решатель квадратичного программирования, например quadprog, Я бы предложил программное обеспечение cvxopt с открытым исходным кодом, как указано в одном из комментариев. Это надежно и по-настоящему современно. Главный участник - крупный эксперт в данной области и соавтор классической книги по Convex Optimization.

Вы хотите использовать функцию cvxopt.solvers.qp. Простая оболочка для использования вNumpy нравиться quadprogследующее. Обратите внимание, что границы могут быть включены как частный случай ограничений неравенства.

import numpy as np
from cvxopt import matrix, solvers

def quadprog(P, q, G=None, h=None, A=None, b=None, options=None):
     """
    Quadratic programming problem with both linear equalities and inequalities

        Minimize      0.5 * x @ P @ x + q @ x
        Subject to    G @ x <= h
        and           A @ x = b
    """
    P, q = matrix(P), matrix(q)

    if G is not None:
        G, h = matrix(G), matrix(h)

    if A is not None:
        A, b = matrix(A), matrix(b)

    sol = solvers.qp(A, b, G, h, A, b, options=options)

    return np.array(sol['x']).ravel()

cvxoptраньше было сложно установить, но в настоящее время он также включен в дистрибутив Anaconda и может быть установлен (даже в Windows) с помощьюconda install cvxopt.

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

Minimize || A @ x - b ||
subject to lb <= x <= ub

потом Scipy имеет определенную функцию scipy.optimize.lsq_linear(A, b, bounds).

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

Источник

Вы можете использоватьsolve_qpфункция от qpsolvers . Он решает квадратичные программы в следующем виде:

      minimize_x  1/2 x' P x + q'x
subject to  G x <= h
            A x == b
            lb <= x <= ub

Функция объединяет множество решателей QP, доступных в Python ( полный список здесь ), через свойsolverключевой аргумент. Обязательно попробуйте разные решатели, чтобы найти тот, который лучше всего подходит для вашей проблемы.

Вот фрагмент для решения небольшой проблемы:

      from numpy import array, dot
from qpsolvers import solve_qp

M = array([[1., 2., 0.], [-8., 3., 2.], [0., 1., 1.]])
P = dot(M.T, M)  # this is a positive definite matrix
q = dot(array([3., 2., 3.]), M)
G = array([[1., 2., 1.], [2., 0., 1.], [-1., 2., -1.]])
h = array([3., 2., -2.])
A = array([1., 1., 1.])
b = array([1.])

x = solve_qp(P, q, G, h, A, b, solver="osqp")
print(f"QP solution: x = {x}")

И если вас интересуют линейные методы наименьших квадратов с линейными или прямоугольными (ограничениями) ограничениями, есть такжеsolve_lsфункция. Вот краткое руководство по решению таких проблем.

Источник
Другие вопросы по тегам