6

通常、私はGNU Octaveを使用して二次計画問題を解決してきました。

のような問題を解決します

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

を対象として

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

lbとは下限ubと上限です。たとえば、x

解決すると、私の Octave コードは次のようになります。シンプルな1行だけ

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
4

2 に答える 2

2

のような一般的な二次計画法ソルバーが必要な場合は、コメントの 1 つに記載されてquadprogいるオープンソース ソフトウェアcvxoptをお勧めします。これは堅牢で、まさに最先端です。主な寄稿者は、この分野の主要な専門家であり、凸最適化に関する古典的な本の共著者です。

使用する関数は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)。

受け入れられた回答は非常に非効率的なアプローチであり、推奨されないことに注意してください。最適化する関数が二次関数であるという重要な事実を利用せず、代わりに一般的な非線形最適化プログラムを使用し、解析勾配を指定しません。

于 2019-12-11T13:29:58.023 に答える