曲铁平，里 莉

(1.沈阳理工大学 理学院，辽宁 沈阳 110159；2.沈阳化工大学 数理系，辽宁 沈阳 110114)

带有势约束的组合最优化的一种解法

曲铁平1，里 莉2

(1.沈阳理工大学 理学院，辽宁 沈阳 110159；2.沈阳化工大学 数理系，辽宁 沈阳 110114)

从经典的马克维茨投资组合问题引出一个一般的组合最优化模型，并给出此模型的一个解法.首先，由拉格朗日分解从原模型的对偶问题得出一个二阶锥规化的松弛.其次，给出一个新的含混合整数二次约束的二次规化的改进.最后，证明了此改进的连续松弛问题比原问题的连续松弛问题更紧.

拉格朗日分解；二阶锥规化；组合最优化

组合最优化的应用十分广泛，但因为它是一个NP难问题，使得求得最优解的过程变得异常困难，即不可能在多项式时间内寻得其最优解.先以投资组合的经典问题为例看一下组合最优化的求解模型.马克维茨投资组合模型[1-2]在投资组合理论中十分重要，他的期望—方差模型中用期望度量投资的期望收益，用方差度量组合风险.已有很多关于带有势约束和二次约束的组合最优化模型的求解成果，比如Bertsimas等[3]提出了一种分支定界法，其中子问题的连续松弛是用Lemke方法求解.Bonami等[4]研究了带有整数约束和最小买入约束的投资组合问题，其中也用了分支定界方法.Shaw等[5]提出了一种建立在拉格朗日松弛基础上的分支定界法求解带有势约束的期望—方差模型，在分支定界步骤中的每个子问题的拉格朗日对……