二次計画法
↑ Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. p. 449. ISBN 978-0-387-30303-1 .
1 2 Murty, Katta G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp.. ISBN 3-88538-403-5. MR949214. オリジナルの2010年4月1日時点におけるアーカイブ。. https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/
↑ Delbos, F.; Gilbert, J.Ch. (2005). “Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems”. Journal of Convex Analysis 12: 45–69. http://www.heldermann-verlag.
二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、c = 0 かつ Q が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。
L ( x , λ ) = 1 2 x T Q x + λ T ( A x − b ) . {\displaystyle L(x,\lambda )={\tfrac {1}{2}}x^{T}Qx+\lambda ^{T}(Ax-b).}
(ラグランジュ)双対関数を g ( λ ) {\displaystyle g(\lambda )} とし、 g ( λ ) = inf x L ( x , λ ) {\displaystyle g(\lambda )=\inf _{x}L(x,\lambda )} を満たすものとすれば、 ∇ x L ( x , λ ) = 0 {\displaystyle \nabla _{x}L(x,\lambda )=0} という条件と Q の正値定符号性を用いることで、L の下限を見つけることができる。
x ∗ = − Q − 1 A T λ .
であり、もし Z を EZ = 0 となるように選べば、制約方程式は常に満たされるようになる。このような Z を見つけるということは E の零空間を見つけるということを意味し、E の構造に依存するが多かれ少なかれ単純である。二次形式に代入すると次の無制約の最小化問題が得られる。
1 2 x T Q x + c T x ⇒ 1 2 y T Z T Q Z y + ( Z T c ) T y {\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{T}Q\mathbf {x} +\mathbf {c} ^{T}\mathbf {x} \quad \Rightarrow \quad {\tfrac {1}{2}}\mathbf {y} ^{T}Z^{T}QZ\mathbf {y} +(Z^{T}\mathbf {c} )^{T}\mathbf {y} }
この解は以下で与えられる。
Z T Q Z y = − Z T c {\displaystyle Z^{T}QZ\mathbf {y} =-Z^{T}\mathbf {c} }
Q についてのある条件の下で、退化した行列 ZQZ は正値定符号となる。Z の陽な計算を避けた共役勾配法のバリエーションとして書くことも可能である。
Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc.. pp. xxiv+762 pp.. ISBN 0-12-192350-9. MR1150683
Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5 A6: MP2, pg.245.