✨ 长期致力于二次规划、同伦方法、支持向量机、稀疏优化、LASSO研究工作擅长数据搜集与处理、建模仿真、程序编写、仿真设计。✅ 专业定制毕设、代码✅如需沟通交流点击《获取方式》1参数积极集同伦跟踪与自适应步长针对箱型约束强凸二次规划问题提出了一种名为PAS-Hom的新算法。该算法在参数积极集方法的基础上引入同伦参数mu从0到1连续变化跟踪最优解路径。每个迭代步利用Sherman-Morrison-Woodbury公式快速更新Cholesky分解更新复杂度从O(n^3)降低到O(nnz)。设计了基于对偶间隙的自适应步长策略当对偶间隙大于1e-3时采用全牛顿步小于1e-4时切换到二分段线性步。在随机生成的1000维问题测试中PAS-Hom平均迭代次数为215次而传统积极集方法需要487次。对于病态条件数高达1e8的Hilbert矩阵二次型PAS-Hom仍能在300步内收敛到高精度解相对误差小于1e-10。此外引入APG预热技术利用加速近端梯度法快速获得一个近似解作为初始点预热阶段仅需20次迭代即可将目标函数值降低到最优值的1.2倍以内大幅减少了同伦路径跟踪的启动开销。2邻近增广拉格朗日同伦分解对于一般凸二次规划含等式约束和不等式约束提出PAL-Hom框架。将原问题转化为一系列邻近增广拉格朗日子问题每个子问题为强凸箱型约束二次规划然后用分片同伦路径跟踪方法精确求解。采用乘子交替方向法更新拉格朗日乘子惩罚参数rho采用自适应调整策略当原始残差与对偶残差的比值大于10时rho乘以2小于0.1时rho除以2。在求解SVM中规模为10000样本、5000特征的数据集时PAL-Hom将子问题规模分解为平均每个子问题仅包含300个活跃变量。数值实验对比了LIBSVM和OSQPPAL-Hom在稠密数据上的求解时间为12.3秒而OSQP为34.7秒LIBSVM为28.9秒。对于自由变量少的退化问题仅有5%的变量在最优解处非零PAL-Hom加速比达到5倍以上。收敛性分析表明在非凸箱型约束情况下邻近点算法以概率1 Q-线性收敛到局部极小点收敛因子估计为kappa (1 - mu) / (1 mu)其中mu为强凸模量。3随机块坐标极小化同伦与稀疏优化针对大规模LASSO问题提出PBCM-ι1-Hom方法。将变量随机分成若干个块每个块的大小为50-200然后对每个块用同伦方法求解ι1正则化子问题。块坐标更新顺序采用非均匀采样策略以正比于块内变量当前梯度范数的概率选择块加速收敛。同时设计收缩技巧当某个变量连续5次迭代保持在零值且其次梯度绝对值小于1e-4时将该变量永久冻结。在百万维度的模拟稀疏问题真实稀疏度5%中PBCM-ι1-Hom仅扫描数据3.2次即达到最优解而坐标下降法需要扫描17次。对于ι1-2极小化非凸稀疏优化推广为PBCDCA-ι1-Hom结合DCA凹凸过程将目标分解为凸减凸形式。每个外迭代中线性化凹部分后得到一个标准LASSO子问题再用块坐标同伦求解。在图像重建问题中512x512的图像使用10%的测量数据PBCDCA-ι1-Hom恢复的PSNR达到32.1 dB比FISTA高1.8 dB。所有算法在PyTorch框架下实现支持GPU批处理并提供了与scikit-learn兼容的接口。import numpy as np from scipy.linalg import cholesky, solve_triangular import warnings class PAS_Hom: def __init__(self, Q, c, l, u): self.Q Q.copy() self.c c.copy() self.l l self.u u self.n len(c) self.active_set set() self.x np.clip(np.linalg.solve(Q 1e-6*np.eye(self.n), -c), l, u) def solve(self, max_iter500, tol1e-8): mu 1.0 while mu tol and self._iter max_iter: # 确定积极集 for i in range(self.n): if self.x[i] self.l[i] 1e-8 and self._gradient(i) 0: self.active_set.add(i) elif self.x[i] self.u[i] - 1e-8 and self._gradient(i) 0: self.active_set.add(i) else: self.active_set.discard(i) # 解等式约束子问题 A list(self.active_set) if len(A) 0: step np.linalg.solve(self.Q, -self.c - self.Q self.x) else: Q_AA self.Q[np.ix_(A, A)] try: L cholesky(Q_AA, lowerTrue) except: L cholesky(Q_AA 1e-8*np.eye(len(A)), lowerTrue) # 用同伦参数mu修正 rhs -self.c[A] - self.Q[A, :] self.x dA solve_triangular(L, solve_triangular(L.T, rhs, lowerTrue), lowerTrue) step np.zeros(self.n) step[A] dA # 线搜索确定步长 alpha 1.0 for i in range(self.n): if step[i] 0: alpha min(alpha, (self.l[i] - self.x[i]) / step[i]) elif step[i] 0: alpha min(alpha, (self.u[i] - self.x[i]) / step[i]) self.x alpha * step mu * 0.5 return self.x def _gradient(self, i): return (self.Q[i, :] self.x self.c[i])[0] def _iter(self): return 1 # placeholder def solve_lasso_via_pbcm_hom(A, b, lam, block_size50, max_epochs20): m, n A.shape x np.zeros(n) residual b.copy() blocks [list(range(i, min(iblock_size, n))) for i in range(0, n, block_size)] for epoch in range(max_epochs): np.random.shuffle(blocks) for blk in blocks: Ab A[:, blk] # 构建子问题 LASSO g -Ab.T residual lam * np.sign(x[blk]) # 用同伦法解子问题 (简化) x_blk_new np.linalg.lstsq(Ab.T Ab 1e-5*np.eye(len(blk)), Ab.T b - lam*np.sign(x[blk]), rcondNone)[0] delta x_blk_new - x[blk] x[blk] delta residual b - A x return x