二次规划

✍ dations ◷ 2025-04-04 11:06:23 #运筹学

二次规划(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困难的。

相关

  • 语调语调(英语:intonation、音高),又称语气、口气,是指说话者交谈发声的音调,即说话者依据个人心情(态度、个性),让声调的高低轻重音调,再附加上发声的高低轻重音调;前者是文法上的音调、后
  • 高血糖症高血糖(英语:Hyperglycemia)是指过量葡萄糖在血浆中堆积的医疗状况,一般指血糖水平高于11.1毫摩尔/升(200毫克/分升),但在血糖升到15-20毫摩尔/升(250-300毫克/分升)之前症状都不明显
  • 国家出柜日美国国家出柜日(英语:National Coming Out Day,NCOD),每年在10月11日举行,是增进大众对于LGBT的意识的节日。源自于1988年的美国,初始的概念来自于女性主义和同性恋解放运动中“个
  • 水蝇总科见内文水蝇总科(学名:Ephydroidea)是家蝇下目无瓣类之下的一个双翅目昆虫的总科。水蝇总科由下列五个科组成:
  • 美利坚合众国宪法第四条修正案宪法正文I ∙ II ∙ III ∙ IV ∙ V ∙ VI ∙ VII其它修正案 XI ∙ XII ∙ XIII ∙ XIV ∙ XV XVI ∙ XVII ∙ XVIII ∙ XIX ∙ XX XXI ∙ XXII ∙ XXIII ∙
  • 吉福德·平肖国家森林吉福德·平肖国家森林(英语:Gifford Pinchot National Forest)是座美国国家森林,位于美国华盛顿州南部,由美国国家森林局管辖。森林面积1.32 × 106英亩(5,300平方千米),沿着喀斯喀
  • 府 (行政区划)府是东亚的一种行政区划单位。中国自唐朝至民国初年,设置的二级行政区划单位称作“府”,相当于中华人民共和国的地级。同属东亚文化圈中的日本和韩国则使用“府”作为一级行政
  • 我妻荣我妻荣(1897年4月1日-1973年10月21日),日本民法学家。山形县米泽市出生。东京帝国大学法学部毕业。我妻教授是日本民法学界的代表性学者,主要进行德国法相关研究和判例研究,对于学
  • 碧野碧野(1916年2月-2008年5月),原名黄潮洋,男,广东大埔人,中华人民共和国作家,中国作家协会驻会作家。碧野祖籍广东省大埔县赤山村,后定居于潮安县城(今属潮州市湘桥区)。青年时代在广东省
  • PowerampPoweramp,是Android平台下一款音乐播放器,支持Android 2.0以上ROM,支持播放mp3,aac,flac,ape,alac,wma,ogg,wav等众多常见音乐格式,以输出音质绝佳著称且广受欢迎。此软件同样