二次规划

✍ dations ◷ 2025-04-04 10:01:26 #运筹学

二次规划(Quadratic programming),在运筹学当中,是一种特殊类型的最佳化问题。

一个有n个变数与m个限制的二次规划问题可以用以下的形式描述。首先给定:

则此二次规划问题的目标即是在限制条件为

的条件下,找一个n 维的向量 x ,使得

为最小。其中 x T {\displaystyle x^{T}} x {\displaystyle x} 的转置。

根据不同的参数特性,可以得到对问题不同的结论

根据优化理论,一个点x成为全局最小值的必要条件是满足Karush-Kuhn-Tucker条件(KKT)。当f(x)是凸函数时,KKT条件也是充分条件。

当二次规划问题只有等式约束时,二次规划可以用线性方程求解。否则的话,常用的二次规划解法有:

凸集二次规划问题是凸优化问题的一个特例。

每个二次规划问题的对偶问题也是二次规划问题。以正定矩阵Q为例:

对偶问题 g ( λ ) {\displaystyle g(\lambda )} ,可定义为

可用 x L ( x , λ ) = 0 {\displaystyle \nabla _{x}L(x,\lambda )=0} :得到 L {\displaystyle L} 的极小

对偶函数:

对偶问题为:

maximize : ( 1 / 2 ) λ T A Q 1 A T λ ( c T Q 1 A T + b T ) λ {\displaystyle -(1/2)\lambda ^{T}AQ^{-1}A^{T}\lambda -(c^{T}Q^{-1}A^{T}+b^{T})\lambda }

subject to : λ 0 {\displaystyle \lambda \geq 0}

当Q正定时,用椭圆法可在多项式时间内解二次规划问题。当Q非正定时,二次规划问题是NP困难的(NP-Hard)。即使Q只存在一个负特征值时,二次规划问题也是NP困难的。

相关

  • 燕巢区燕巢区(台湾话:.mw-parser-output .sans-serif{font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,Lato,"Helvetica Neue",Helvetica,Arial,sans-serif} Iàn-
  • 加拿大行政区划加拿大的行政区划是由10个省(Province)和3个地区/领地(英语:territory;法语:territoire)所组成的。省和地区的主要不同的地方在于省是根据宪法法令所设立的,但地区是据联邦法律所设
  • span class=nowrapUClsub3/sub/span三氯化铀(UCl3)是一个铀和氯的化合物。 三氯化铀主要用于再加工用过的核燃料。四氯化铀从各种方式可以合成三氯化铀,但三氯化铀不比四氯化铀稳定的。三氯化铀可由四氯合铀(III)
  • 保罗·史塔曼兹保罗·史塔曼兹(英文:Paul Stamets,1955年7月17日-)是美国的一名真菌学家、作家与真菌修复和药用真菌(英语:Medicinal fungi)的提倡者。保罗·史塔曼兹于1979年毕业于长青州立大学(英
  • 拉曼光谱学拉曼光谱学(Raman spectroscopy)是用来研究晶格及分子的振动模式、旋转模式和在一系统里的其他低频模式的一种分光技术。拉曼散射为一非弹性散射,通常用来做激发的激光范围为可
  • UTC−04:00UTC−04:00时区比协调世界时慢4小时,使用于地区如下:
  • 2019冠状病毒病列支敦士登疫情2019冠状病毒病列支敦士登疫情,介绍在2019冠状病毒病疫情中,在列支敦士登发生的情况。2019冠状病毒病于2020年3月波及列支敦士登。 2月11日,列支敦士登政府设立了“2019‐nCoV
  • 盲点 (眼)视网膜的后方称为眼底,在正对视神经起始处,有一呈白色的圆形隆起,称为视神经盘(又称视神经乳头)。此处是神经纤维进出的地方,没有感光细胞,不能感应到光线,故称为盲点。影像能够在盲
  • 迪尔玛·罗塞夫迪尔玛·罗塞夫(葡萄牙语:Dilma Vana Rousseff,巴西葡萄牙语:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unic
  • 黑云龙 (明朝辽东武将)黑云龙,生卒不详,女真族,明朝辽东都司广宁卫人,官至参将,副总兵黑春之长子,历仕嘉靖、隆庆、万历三朝,后无考。嘉靖四十一年(1562年),黑云龙父亲黑春在征剿叛明的女真部落首领王杲时牺