optimization - CPLEX二次シンプレックス?

Question

CPLEXが二次計画を解くために使用するシンプレックスのようなアルゴリズムを知っている人はいますか? それが使用しているいわゆる二次シンプレックスは何ですか?

前もってありがとう、メディ

Answer 1

CPLEXが何を使用するかはわかりませんが、シンプレックス法は二次計画法を解くためにフィリップ・ウルフによって修正されました。一言で言えば、これはそれが行うことです：

二次計画問題を考えると：QPP。p'x + 1 / 2x'Cx、制約付きAx = b

1. Cは対称正定値でなければなりません（正半定値も機能する可能性があります）
2. Karush-Kuhn-Tucker条件を使用して線形制約を生成します
3. ピボット列を選択するときに補完的なたるみが保持されるようにシンプレックス法を変更します。
4. 他の通常のシンプレックス法の手順に進みます

詳細については、次のペーパーを参照してください。http: //pages.cs.wisc.edu/~brecht/cs838docs/wolfe-qp.pdf

お役に立てれば。