部分基数组占比未知的线性转非线性优化问题求解咨询

你当前遇到的是双线性非负矩阵分解的变种问题，变量分为两类：待求解的基数组取值、每条数据对应的未知混合占比，两类变量各自线性、仅存在交叉乘积项，完全可以在合理时长内求解，以下是可直接落地的方案：

首选方案：交替最小化法 #

该方案可100%复用你之前实现的线性规划求解逻辑，开发成本极低，适配你的问题规模：

• 步骤1：初始化所有单条数据对应的未知占比x_i，可默认设为区间中值（比如你示例的x范围为0~0.5就初始设0.25），也可以用已知无未知占比的样本做初步预计算得到更优初始值。
• 步骤2：固定所有x_i的取值，此时问题退化为你熟悉的已知混合占比求基数组的线性规划问题，直接调用你之前的pulp求解代码得到当前最优的基数组取值，计算当前总拟合误差。
• 步骤3：固定所有基数组的取值，此时每个x_i的优化完全独立，属于带边界约束的一维L1误差最小化凸问题，直接用三分法、甚至小步长枚举就能在毫秒级完成所有10条数据的x_i更新。
• 重复执行步骤2和步骤3，直到两次迭代的总误差下降幅度低于你设定的收敛阈值（比如1e-4）即可停止。

一般这类问题迭代20~50次就能收敛，你当前的规模（10条数据、单条10万条目、4个基数组）在普通服务器上跑完全不需要高性能机器，几十分钟内就能出结果。如果需要提速可以给基数组加稀疏性约束，进一步降低线性规划的求解复杂度。

备选提速方案：基于自动微分的梯度优化 #

如果对迭代速度有更高要求，可以直接用Pytorch/Tensorflow实现带约束的梯度下降：

• 将基数组、所有x_i都设为待优化张量，给x_i加边界约束（比如0≤x≤0.5）
• 目标函数直接设为L1拟合误差总和，用Adam优化器迭代求解，有GPU的情况下可以在几分钟内完成计算。

优化注意事项 #

该问题属于非凸优化，初始值会影响最终收敛到的局部最优解，你可以多尝试3~5组不同的初始x_i取值，最终选择总拟合误差最小的结果即可。

内容的提问来源于stack exchange，提问作者DottyPhone