列生成算法在金融投资组合优化中的风险分散应用示例 题目描述 考虑一个投资组合优化问题：投资者有1000万元资金，需要从200只股票中选择投资组合。每只股票有预期收益率、风险系数（方差）和行业分类。目标是最大化组合预期收益，同时满足：(1)总风险（方差）不超过设定阈值；(2)单只股票权重不超过5%；(3)每个行业权重不超过20%。由于股票数量众多，直接求解整数规划计算量大，采用列生成算法逐步添加有潜力的股票列。 问题建模 设决策变量x_ j表示股票j的投资比例（j=1,...,200），r_ j为预期收益率，σ_ j²为方差，σ_ max为风险阈值。数学模型： max Σr_ jx_ j s.t. Σx_ j = 1 （预算约束） Σσ_ j²x_ j ≤ σ_ max （风险约束） 0 ≤ x_ j ≤ 0.05, ∀j （单股上限） Σ_ {j∈行业k} x_ j ≤ 0.2, ∀k （行业上限） 列生成原理 初始限制主问题(RMP)：仅包含少量股票（如10只）的子集 定价问题：寻找 reduced cost 最负的股票（最有潜力改善目标函数的股票） 迭代过程：将新股票加入RMP，重新求解，直到无负reduced cost股票 求解步骤 第一步：初始化限制主问题 选取10只不同行业的股票构成初始列集合（确保RMP可行） 求解RMP得到对偶变量值：π_ b（预算约束）、π_ r（风险约束）、π_ k（行业约束） 第二步：构建定价问题 定价问题目标：min (c_ j - π_ b - σ_ j²π_ r - Σπ_ k) 其中c_ j = -r_ j（最大化转最小化），π_ k仅当股票j属于行业k时生效 定价问题实质是求解200只股票中reduced cost最小的股票 第三步：列生成迭代 求解当前RMP，得到对偶解 求解定价问题：遍历所有股票计算reduced cost 若最小reduced cost ≥ 0（最优条件满足），停止迭代 否则，将对应股票列加入RMP，返回步骤1 第四步：实例演示 假设初始RMP包含10只股票，求解后对偶变量： π_ b = 0.8, π_ r = 0.2, π_ k = [ 0.1, 0.05, ... ] 计算第11只股票（收益率8%，方差0.04，属于行业3）： reduced cost = -0.08 - 0.8 - 0.04×0.2 - 0.05 = -0.938 负值表明应加入该列 算法收敛性 经过15次迭代后，定价问题显示所有股票reduced cost均非负，获得原问题最优解。最终组合包含35只股票，预期收益率9.8%，风险控制在阈值内。 关键优势 计算效率：仅维护活跃列集合，避免200维完整问题 内存优化：无需存储全部约束矩阵 灵活终止：可设置reduced cost阈值提前终止