大规模非线性界约束优化：两种信赖域内点法的深度解析与应用

大规模非线性界约束优化：两种信赖域内点法的深度解析与应用一、引言1.1研究背景与意义在科学研究和工程实践的众多领域，大规模非线性界约束优化问题广泛存在且至关重要。在工程设计领域，例如航空航天工程中飞行器的结构设计，需要在满足材料强度、空气动力学性能等多种约束条件下，优化飞行器的结构参数，以实现重量最轻、性能最优的设计目标，这些约束条件和目标函数往往呈现出非线性的特征，且设计参数存在边界限制，属于大规模非线性界约束优化问题。在汽车制造中，汽车发动机的设计需要优化多个参数，如燃油喷射量、点火时间、进气量等，以提高发动机的燃油经济性和动力性能，同时要满足排放法规等约束条件，这些参数的取值范围也有严格限制，构成了典型的大规模非线性界约束优化问题。在经济领域，投资组合优化问题是一个重要的研究方向。投资者需要在众多的投资项目中进行选择，确定每个项目的投资比例，以实现投资收益最大化，同时要考虑风险承受能力、资金总量等约束条件，投资项目的收益和风险通常与投资比例呈现非线性关系，并且投资比例存在上下限约束，这同样是大规模非线性界约束优化问题的具体体现。在供应链管理中，企业需要优化生产计划、库存水平和运输路线等，以最小化成本，同时要满足市场需求、生产能力、库存容量等约束条件，这些决策变量往往受到边界限制，且成本函数和约束条件可能是非线性的，也属于大规模非线性界约束优化问题的范畴。鉴于大规模非线性界约束优化问题在上述诸多领域的广泛应用，研究高效的求解方法具有极其重要的意义。高效的求解方法能够帮助工程师在设计过程中更快、更准确地找到最优方案，降低设计成本，提高产品性能。在经济领域，能够帮助投资者做出更合理的投资决策，提高投资收益，降低风险。求解方法的改进和创新对于推动相关领域的发展具有重要的理论和实际价值，也是当前优化领域研究的热点和难点问题之一。1.2国内外研究现状大规模非线性界约束优化问题的求解一直是优化领域的研究重点，国内外学者在此方向开展了大量研究，取得了丰富成果。在早期，线性化方法是求解此类问题的常用手段，例如线性逼近法通过将非线性函数在当前点附近进行线性化处理，将原问题转化为一系列线性规划问题来求解。然而，线性化方法在处理高度非线性的问题时，往往精度不足，难以得到理想的结果。随着研究的深入，内点法逐渐成为求解约束优化问题的重要方法之一。内点法的基本思想是在可行域内部进行搜索，通过一系列迭代逐步逼近最优解，避免了在可行域边界上可能出现的复杂情况。例如，经典的障碍函数法通过引入障碍函数，将约束条件融入目标函数中，使得迭代点始终保持在可行域内部。但是，传统内点法在处理大规模问题时，由于需要求解大规模的线性方程组，计算量和存储量都非常大，限制了其应用范围。信赖域方法的出现为优化问题的求解带来了新的思路。信赖域方法在每次迭代中，通过构建一个以当前点为中心的信赖域，在信赖域内求解一个近似的子问题来确定搜索方向和步长。该方法充分考虑了目标函数的局部曲率信息，在一定程度上提高了算法的收敛速度和稳定性。在求解无约束优化问题时，信赖域方法已经展现出了良好的性能。但对于约束优化问题，如何有效地将信赖域方法与约束条件相结合，仍然是一个具有挑战性的问题。近年来，国内外学者在结合信赖域方法和内点法求解大规模非线性界约束优化问题方面取得了显著进展。例如，Coleman和Li提出了“双信赖域方法”（TRAM），通过仿射变换成功构建了近似二次模型函数和信赖域子问题，为解决线性不等式约束的优化问题提供了新的途径，然而该方法在求解信赖域子问题时计算量较大，且未给出具体求解方法。在国内，一些学者针对大规模问题的特点，提出了基于子空间技术的信赖域内点法，如北京交通大学的宫静提出了LMTI方法和STI方法，分别利用有限内存BFGS公式获取海色阵近似矩阵构造信赖域问题模型以及在低维子空间上求解信赖域子问题，实验表明这两种方法能够适应大规模问题求解的需要，且在一定程度上提高了求解效率。在算法改进方面，学者们不断探索新的策略来提高算法性能。有的研究引入全局搜索策略，采用多起点的全局搜索算法为信赖域算法提供初始点，帮助算法跳出局部最优解；还有的研究通过动态调整信赖域半径，根据实际优化问题中的噪声水平自适应地调整信赖域半径，使算法更加鲁棒和稳定。在应用领域，这些改进的算法被广泛应用于工程设计、经济分析、机器学习等多个领域，为解决实际问题提供了有效的工具。1.3研究目标与创新点本研究旨在深入分析两种信赖域内点方法（LMTI方法和STI方法），并与传统方法对比，从理论证明和数值实验两方面验证其有效性和优势，为大规模非线性界约束优化问题提供更高效、实用的求解策略。本研究在方法和算法结构上进行了创新。一方面，在构造和求解信赖域二次模型的环节中融入子空间实现的思想，提出了两种在子空间上对信赖域子问题求解的内点法，即LMTI方法和STI方法。LMTI方法利用有限内存BFGS公式的紧致形式获取目标函数海色阵的近似矩阵构造信赖域问题模型并求解，STI方法则在构造的低维子空间上求信赖域子问题的解，这种子空间技术的应用使得算法能够更有效地处理大规模问题，减少计算量和存储需求。另一方面，改进了算法结构，在算法的迭代过程中加入内点法的思想，要求每一步产生的迭代点位于可行域的严格内部，避免了在可行域边界上可能出现的复杂情况，提高了算法的稳定性和收敛性。二、相关理论基础2.1大规模非线性界约束优化问题概述大规模非线性界约束优化问题的数学模型通常可以表示为：\begin{align*}&\min_{x\in\mathbb{R}^n}f(x)\\&\text{s.t.}l_i\leqx_i\lequ_i,\quadi=1,2,\cdots,n\end{align*}其中，f(x):\mathbb{R}^n\rightarrow\mathbb{R}是目标函数，它是关于决策变量x=(x_1,x_2,\cdots,x_n)^T的非线性函数。l_i和u_i分别为变量x_i的下界和上界，这种对变量取值范围的限制被称为界约束。界约束在实际问题中有着广泛的应用，例如在资源分配问题中，每种资源的分配量都有其最小和最大限制；在生产计划中，产品的产量也会受到生产设备能力、原材料供应等因素的限制，从而存在上下界约束。在实际场景中，该问题有多种表现形式。在机器学习的特征选择与参数优化中，需要确定每个特征的权重以及模型的参数，以最小化预测误差或最大化模型性能指标，特征权重和模型参数的取值往往受到一定的限制，以保证模型的合理性和稳定性，这就构成了大规模非线性界约束优化问题。在电力系统的无功优化中，需要调整发电机的无功出力、变压器的分接头位置以及无功补偿装置的投入量等，以最小化有功网损和提高电压质量，这些控制变量都存在上下界约束，且目标函数和约束条件通常是非线性的，属于典型的大规模非线性界约束优化问题。2.2信赖域方法基本原理信赖域方法是求解非线性优化问题的重要迭代算法，其核心思想是在每次迭代时，围绕当前迭代点构建一个局部近似模型，并在一个被称为信赖域的区域内对该模型进行优化，以确定下一个迭代点。在迭代过程中，首先需要构建一个二次模型来近似目标函数。假设当前迭代点为x_k，目标函数为f(x)，则在x_k点附近，利用泰勒展开式构建二次模型函数m_k(d)：m_k(d)=f(x_k)+\nablaf(x_k)^Td+\frac{1}{2}d^TB_kd其中，d是搜索方向，\nablaf(x_k)是目标函数在x_k点的梯度，B_k是一个对称矩阵，通常是目标函数在x_k点的海森矩阵（HessianMatrix）或其近似矩阵。海森矩阵包含了目标函数的二阶导数信息，能够更准确地描述目标函数的局部曲率，从而为搜索方向的确定提供更有效的指导。确定信赖域半径\Delta_k也是信赖域方法的关键步骤。信赖域半径定义了一个以当前迭代点x_k为中心的区域，即\{d:\|d\|\leq\Delta_k\}，在这个区域内，二次模型被认为是对目标函数的一个可靠近似。信赖域半径的大小需要根据目标函数的性质和当前迭代的情况进行动态调整。如果当前的近似模型与目标函数的拟合效果较好，即实际下降量与预测下降量的比值接近1，说明在当前信赖域内的搜索是有效的，可以适当增大信赖域半径，以便在更大的区域内搜索更优的解，提高搜索效率；反之，如果拟合效果较差，比值远小于1，则需要减小信赖域半径，以保证在一个更可靠的小区域内进行搜索，避免搜索方向偏离最优解太远。调整迭代步长也是信赖域方法的重要环节。通过求解信赖域子问题：\begin{align*}&\min_{d}m_k(d)\\&\text{s.t.}\|d\|\leq\Delta_k\end{align*}得到搜索方向d_k。然后，根据实际下降量\rho_k来决定是否接受这个搜索方向作为新的迭代步长。实际下降量\rho_k定义为：\rho_k=\frac{f(x_k)-f(x_k+d_k)}{m_k(0)-m_k(d_k)}如果\rho_k大于某个预设的阈值（例如0.25），说明沿着搜索方向d_k移动能够使目标函数有显著的下降，此时接受d_k作为新的迭代步长，更新迭代点为x_{k+1}=x_k+d_k；否则，不接受d_k，保持当前迭代点不变，同时减小信赖域半径，重新求解信赖域子问题，寻找更合适的搜索方向。在每次迭代中，信赖域方法通过不断调整信赖域半径和搜索方向，逐步逼近目标函数的最优解。2.3内点法基本原理内点法是求解约束优化问题的一种重要方法，其核心思想是通过引入障碍函数，将有约束的优化问题巧妙地转化为一系列无约束的优化问题，使得迭代过程始终在可行域内部进行，有效避免了在可行域边界上可能出现的复杂情况，如梯度突变、不可微等问题，从而提高了算法的稳定性和收敛性。对于大规模非线性界约束优化问题\begin{align*}&\min_{x\in\mathbb{R}^n}f(x)\\&\text{s.t.}l_i\leqx_i\lequ_i,\quadi=1,2,\cdots,n\end{align*}内点法通过构建障碍函数来实现约束条件的处理。障碍函数是一种特殊的函数，它在可行域内部取值有限，而当迭代点趋近于可行域边界时，函数值会迅速增大，就像在可行域边界筑起了一道“高墙”，阻止迭代点越过边界。常用的障碍函数之一是对数障碍函数，对于上述界约束优化问题，其对数障碍函数形式为：B(x,\mu)=f(x)-\mu\sum_{i=1}^{n}(\ln(x_i-l_i)+\ln(u_i-x_i))其中，\mu是一个正的参数，称为障碍参数。随着迭代的进行，\mu会逐渐减小。当\mu趋近于0时，B(x,\mu)的最小值就趋近于原约束优化问题的最小值。在迭代过程中，内点法通过不断求解无约束优化问题\min_{x\in\mathbb{R}^n}B(x,\mu)来逼近原问题的最优解。每次迭代时，选择一个合适的\mu值，然后使用无约束优化算法（如牛顿法、拟牛顿法等）来求解B(x,\mu)的最小值。随着\mu逐渐减小，迭代点会越来越接近可行域的边界，同时也越来越接近原约束优化问题的最优解。例如，在某一迭代步中，给定一个\mu_k值，通过求解\min_{x\in\mathbb{R}^n}B(x,\mu_k)得到一个迭代点x_{k+1}，然后根据一定的准则减小\mu值，如\mu_{k+1}=\gamma\mu_k，其中\gamma是一个小于1的正数（通常取0.1到0.5之间），再继续求解下一个无约束优化问题，如此反复迭代，直到满足收敛条件为止。三、两种信赖域内点方法详解3.1LMTI方法3.1.1基于有限内存BFGS公式的海色阵近似在LMTI方法中，为了有效处理大规模非线性界约束优化问题，需要对目标函数的海色阵进行近似处理。有限内存BFGS公式（Limited-MemoryBFGS，L-BFGS）是一种常用的获取海色阵近似矩阵的方法，它在处理大规模问题时具有显著优势，能够在减少内存需求的同时，保持较好的近似效果。有限内存BFGS公式基于拟牛顿法的思想，通过迭代更新来逼近海色阵的逆矩阵。其紧致形式的核心在于利用最近的m次迭代信息来构建海色阵的近似。假设当前迭代点为x_k，步长为s_k=x_{k+1}-x_k，梯度差为y_k=\nablaf(x_{k+1})-\nablaf(x_k)。有限内存BFGS公式通过保存这些向量序列\{s_i\}和\{y_i\}（i=k-m+1,\cdots,k）来计算海色阵的近似矩阵。具体而言，在每次迭代中，首先计算\rho_k=\frac{1}{s_k^Ty_k}。然后，利用这些信息通过双循环递归公式计算海色阵近似矩阵与向量的乘积。对于给定的向量g，计算z=H_kg（H_k为海色阵近似矩阵）的过程如下：\begin{align*}q&=g\\\alpha_i&=\rho_is_i^Tq,\quadi=k,k-1,\cdots,k-m+1\\q&=q-\alpha_iy_i,\quadi=k,k-1,\cdots,k-m+1\\z&=H_0q\\\beta_i&=\rho_iy_i^Tz,\quadi=k-m+1,\cdots,k-1,k\\z&=z+(\alpha_i-\beta_i)s_i,\quadi=k-m+1,\cdots,k-1,k\end{align*}其中，H_0通常是一个初始的近似矩阵，一般选择为单位矩阵或对角矩阵。这种双循环递归计算方式避免了直接存储和计算完整的海色阵，大大减少了内存需求，其空间复杂度从传统BFGS方法的O(n^2)降低到O(mn)，其中n为问题的维数，m为存储的迭代信息数量，使得算法能够处理大规模问题。通过有限内存BFGS公式获取的海色阵近似矩阵，能够在一定程度上反映目标函数的局部曲率信息，为后续构建信赖域问题模型提供了关键的基础。在迭代过程中，随着迭代次数的增加，保存的向量序列不断更新，海色阵近似矩阵也能够更加准确地逼近真实的海色阵，从而提高算法的收敛速度和求解精度。在一些实际的大规模优化问题中，如大规模神经网络的参数优化，有限内存BFGS公式能够有效地处理高维参数空间，帮助算法更快地找到较优的解。3.1.2信赖域问题模型构造与求解在获取了基于有限内存BFGS公式的海色阵近似矩阵后，接下来需要利用该近似矩阵构造信赖域二次模型。对于大规模非线性界约束优化问题\begin{align*}&\min_{x\in\mathbb{R}^n}f(x)\\&\text{s.t.}l_i\leqx_i\lequ_i,\quadi=1,2,\cdots,n\end{align*}在当前迭代点x_k处，构建信赖域二次模型m_k(d)如下：m_k(d)=f(x_k)+\nablaf(x_k)^Td+\frac{1}{2}d^TB_kd其中，d是搜索方向，\nablaf(x_k)是目标函数在x_k点的梯度，B_k即为通过有限内存BFGS公式获取的海色阵近似矩阵。该二次模型在当前迭代点x_k的一个邻域内（即信赖域内）对目标函数进行近似，信赖域定义为\{d:\|d\|\leq\Delta_k\}，\Delta_k是信赖域半径。求解上述信赖域二次模型是LMTI方法的关键步骤。通常采用迭代算法来求解，以找到在信赖域内使二次模型m_k(d)最小的搜索方向d_k。常见的求解算法包括共轭梯度法（ConjugateGradientMethod）、截断牛顿法（TruncatedNewtonMethod）等。以共轭梯度法为例，其基本思想是通过迭代逐步搜索最优解。在每次迭代中，根据当前的搜索方向和梯度信息，计算一个新的搜索方向，使得搜索方向之间满足共轭性条件，从而提高搜索效率。具体步骤如下：初始化：给定初始迭代点x_k，计算梯度g_k=\nablaf(x_k)，初始搜索方向p_0=-g_k，设置迭代次数j=0。迭代计算：计算步长\alpha_j，使得m_k(x_k+\alpha_jp_j)最小，通常可以通过一维搜索算法（如黄金分割法、Armijo准则等）来确定。更新迭代点x_{k,j+1}=x_k+\alpha_jp_j，计算新的梯度g_{k,j+1}=\nablaf(x_{k,j+1})。判断是否满足收敛条件，如\|g_{k,j+1}\|\leq\epsilon（\epsilon为预设的收敛阈值），如果满足，则停止迭代，得到搜索方向d_k=x_{k,j+1}-x_k；否则，计算共轭系数\beta_j=\frac{g_{k,j+1}^Tg_{k,j+1}}{g_{k,j}^Tg_{k,j}}，更新搜索方向p_{j+1}=-g_{k,j+1}+\beta_jp_j，j=j+1，继续下一次迭代。在求解信赖域二次模型的过程中，还需要根据实际下降量与预测下降量的比值来动态调整信赖域半径\Delta_k。实际下降量\rho_k定义为：\rho_k=\frac{f(x_k)-f(x_k+d_k)}{m_k(0)-m_k(d_k)}如果\rho_k大于某个预设的阈值（如0.25），说明当前的近似模型与目标函数的拟合效果较好，搜索方向有效，可以适当增大信赖域半径，以便在更大的区域内搜索更优的解，如\Delta_{k+1}=2\Delta_k；反之，如果\rho_k小于另一个预设的阈值（如0.1），则说明拟合效果较差，需要减小信赖域半径，如\Delta_{k+1}=\frac{1}{4}\Delta_k，以保证在一个更可靠的小区域内进行搜索。通过不断迭代求解信赖域二次模型和调整信赖域半径，LMTI方法逐步逼近大规模非线性界约束优化问题的最优解。3.2STI方法3.2.1低维子空间的构造在STI方法中，构造低维子空间是关键步骤之一，其目的是通过将高维问题投影到低维空间，降低问题的复杂度，从而减少计算量并提升求解效率。通常采用的一种方法是基于主成分分析（PrincipalComponentAnalysis，PCA）的思想。对于大规模非线性界约束优化问题中的目标函数和约束条件，首先收集一定数量的样本点。假设当前迭代点为x_k，围绕该点采集m个邻域点x_{k,i}（i=1,2,\cdots,m）。将这些点组成矩阵X=[x_{k,1}-x_k,x_{k,2}-x_k,\cdots,x_{k,m}-x_k]。接下来，计算矩阵X的协方差矩阵C=\frac{1}{m-1}XX^T。对协方差矩阵C进行特征值分解，得到特征值\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n以及对应的特征向量v_1,v_2,\cdots,v_n。选择前p个（p\lln）最大特征值所对应的特征向量v_1,v_2,\cdots,v_p，由这些特征向量张成的子空间即为低维子空间。这个低维子空间具有重要特性。一方面，它能够保留原始高维空间中大部分的关键信息。由于选择的是最大特征值对应的特征向量，这些向量方向上的数据变化最为显著，能够最大程度地反映样本点之间的差异和分布特征。在图像识别中，原始图像数据通常具有很高的维度，但通过PCA进行降维后，在低维子空间中仍然能够保留图像的主要结构和特征信息，使得基于低维数据的图像分类和识别任务能够取得较好的效果。另一方面，在低维子空间上进行计算，大大减少了计算量。例如，在求解信赖域子问题时，原本在n维空间中需要处理的大规模矩阵运算，现在可以在p维的低维子空间中进行，计算量从O(n^3)降低到O(p^3)，存储需求也相应减少，从而显著提升了算法的效率。3.2.2低维子空间上信赖域子问题的求解在构造出低维子空间后，需要在该子空间上求解信赖域子问题。对于大规模非线性界约束优化问题\begin{align*}&\min_{x\in\mathbb{R}^n}f(x)\\&\text{s.t.}l_i\leqx_i\lequ_i,\quadi=1,2,\cdots,n\end{align*}在当前迭代点x_k处，构建的信赖域二次模型为m_k(d)=f(x_k)+\nablaf(x_k)^Td+\frac{1}{2}d^TB_kd，其中d是搜索方向，\nablaf(x_k)是目标函数在x_k点的梯度，B_k是海色阵或其近似矩阵。将该模型投影到低维子空间S上，设低维子空间S的一组基为[v_1,v_2,\cdots,v_p]，则搜索方向d可以表示为d=Vz，其中V=[v_1,v_2,\cdots,v_p]，z\in\mathbb{R}^p。将d=Vz代入信赖域二次模型m_k(d)中，得到在低维子空间上的二次模型\hat{m}_k(z)=f(x_k)+\nablaf(x_k)^TVz+\frac{1}{2}(Vz)^TB_k(Vz)，即\hat{m}_k(z)=f(x_k)+(V^T\nablaf(x_k))^Tz+\frac{1}{2}z^T(V^TB_kV)z。同时，信赖域约束\|d\|\leq\Delta_k也投影到低维子空间上，变为\|Vz\|\leq\Delta_k，即\|z\|\leq\frac{\Delta_k}{\|V\|}。此时，在低维子空间上的信赖域子问题为：\begin{align*}&\min_{z\in\mathbb{R}^p}\hat{m}_k(z)\\&\text{s.t.}\|z\|\leq\frac{\Delta_k}{\|V\|}\end{align*}求解这个低维子空间上的信赖域子问题，可以采用一些经典的优化算法，如共轭梯度法。共轭梯度法在低维子空间中具有较高的求解效率，其基本步骤如下：初始化：给定初始迭代点z_0，计算梯度g_0=\nabla\hat{m}_k(z_0)=V^T\nablaf(x_k)+(V^TB_kV)z_0，初始搜索方向p_0=-g_0。迭代计算：计算步长\alpha_j，使得\hat{m}_k(z_j+\alpha_jp_j)最小，可通过一维搜索算法（如黄金分割法）来确定。更新迭代点z_{j+1}=z_j+\alpha_jp_j，计算新的梯度g_{j+1}=\nabla\hat{m}_k(z_{j+1})=V^T\nablaf(x_k)+(V^TB_kV)z_{j+1}。判断是否满足收敛条件，如\|g_{j+1}\|\leq\epsilon（\epsilon为预设的收敛阈值），如果满足，则停止迭代，得到搜索方向z^*；否则，计算共轭系数\beta_j=\frac{g_{j+1}^Tg_{j+1}}{g_j^Tg_j}，更新搜索方向p_{j+1}=-g_{j+1}+\beta_jp_j，继续下一次迭代。得到低维子空间上的搜索方向z^*后，通过d=Vz^*将其转换回原高维空间，得到原问题的搜索方向d^*。然后，根据实际下降量与预测下降量的比值来调整信赖域半径\Delta_k，实际下降量\rho_k=\frac{f(x_k)-f(x_k+d^*)}{\hat{m}_k(0)-\hat{m}_k(z^*)}，若\rho_k大于某个预设阈值（如0.25），增大信赖域半径；若小于另一个预设阈值（如0.1），减小信赖域半径，通过不断迭代求解低维子空间上的信赖域子问题和调整信赖域半径，逐步逼近原问题的最优解。3.3两种方法的比较分析从计算复杂度来看，LMTI方法利用有限内存BFGS公式获取海色阵近似矩阵，在每次迭代中计算海色阵近似矩阵与向量的乘积时，主要计算量在于双循环递归公式，其时间复杂度为O(mn)，其中m为保存的迭代信息数量，n为问题的维数。而求解信赖域二次模型时，若采用共轭梯度法，每次迭代的时间复杂度主要取决于矩阵向量乘法，也为O(n)，总体上，每次迭代的时间复杂度为O(mn+n)=O(n(m+1))。STI方法构造低维子空间时，计算协方差矩阵的时间复杂度为O(nm^2)，对协方差矩阵进行特征值分解的时间复杂度为O(n^3)，但由于选择的低维子空间维度p远小于n，在低维子空间上求解信赖域子问题时，计算量大幅减少，如采用共轭梯度法求解，每次迭代的时间复杂度为O(p^2)，总体每次迭代的时间复杂度主要由构造低维子空间决定，为O(nm^2+n^3)。在大规模问题中，当m相对较小时，LMTI方法在计算复杂度上可能更具优势。在收敛速度方面，理论上，在一些较强的条件下，两种方法都能达到局部二次收敛。但在实际应用中，由于问题的复杂性和数据的多样性，收敛速度会有所不同。LMTI方法通过有限内存BFGS公式不断更新海色阵近似矩阵，能够较好地利用目标函数的局部曲率信息，对于一些目标函数具有较好光滑性的问题，能够较快地收敛。而STI方法将问题投影到低维子空间上求解，若低维子空间能够很好地保留原问题的关键信息，也能实现较快的收敛。但如果低维子空间的构造不合理，可能会丢失一些重要信息，导致收敛速度变慢。在某些具有明显低维结构的问题中，STI方法可能会因为充分利用了低维结构而表现出更快的收敛速度；而对于一般的大规模问题，LMTI方法的收敛速度可能更加稳定。两种方法对海色阵的依赖程度也有所不同。LMTI方法直接利用有限内存BFGS公式来近似海色阵，其性能在很大程度上依赖于海色阵近似矩阵的准确性。如果海色阵近似效果不佳，可能会影响搜索方向的准确性，进而影响算法的收敛性和收敛速度。STI方法虽然也需要海色阵信息来构建信赖域二次模型，但通过将问题投影到低维子空间，在一定程度上降低了对高维海色阵的依赖。在低维子空间上，计算和处理海色阵相关信息相对更容易，即使海色阵的估计存在一定误差，由于低维子空间的特性，对算法整体性能的影响可能相对较小。四、算法实现与数值实验4.1算法实现细节在实现LMTI方法时，首先进行参数初始化。设定初始迭代点x_0，根据问题的特点和经验，合理选择初始点可以加快算法的收敛速度。例如，在一些具有物理背景的问题中，可以根据物理原理或先验知识确定初始点。设置初始信赖域半径\Delta_0，通常取一个较小的正数，如0.1，以保证在初始阶段能够在一个较小的可靠区域内进行搜索。设定有限内存BFGS公式中保存的迭代信息数量m，一般根据问题的规模和计算资源来确定，如对于中等规模的问题，m可以取5到10。迭代终止条件设定为：当目标函数值的变化小于某个预设的极小值\epsilon_1（如10^{-6}），或者迭代次数达到预设的最大值N（如1000次）时，终止迭代。在每次迭代中，利用有限内存BFGS公式的紧致形式计算海色阵近似矩阵与向量的乘积，通过双循环递归公式实现，这是LMTI方法的关键步骤之一。根据共轭梯度法求解信赖域二次模型，得到搜索方向d_k，并根据实际下降量与预测下降量的比值\rho_k动态调整信赖域半径。关键代码段（以Python语言为例）如下：importnumpyasnp#定义目标函数defobjective_function(x):returnnp.sum(x**2)#定义目标函数的梯度defgradient(x):return2*x#有限内存BFGS公式计算海色阵近似矩阵与向量的乘积deflbfgs_approx(H0,s_list,y_list,g):m=len(s_list)q=g.copy()alpha=[]foriinrange(m-1,-1,-1):rho=1.0/np.dot(s_list[i],y_list[i])alpha_i=rho*np.dot(s_list[i],q)alpha.append(alpha_i)q=q-alpha_i*y_list[i]z=np.dot(H0,q)beta=[]foriinrange(0,m):rho=1.0/np.dot(s_list[i],y_list[i])beta_i=rho*np.dot(y_list[i],z)beta.append(beta_i)z=z+(alpha[m-1-i]-beta_i)*s_list[i]returnz#共轭梯度法求解信赖域二次模型defconjugate_gradient(B_k,g_k,delta_k):d_k=-g_kg=g_k.copy()for_inrange(len(g_k)):B_d=lbfgs_approx(np.eye(len(g_k)),s_list,y_list,d_k)alpha=np.dot(g,g)/np.dot(d_k,B_d)x_k_plus_1=x_k+alpha*d_kifnp.linalg.norm(x_k_plus_1-x_k)>delta_k:x_k_plus_1=x_k+delta_k*d_k/np.linalg.norm(d_k)breakg_k_plus_1=gradient(x_k_plus_1)beta=np.dot(g_k_plus_1,g_k_plus_1)/np.dot(g_k,g_k)d_k=-g_k_plus_1+beta*d_kg_k=g_k_plus_1returnx_k_plus_1-x_k#LMTI方法主程序deflmt_i_method():x_k=np.array([1.0,1.0])#初始迭代点delta_k=0.1#初始信赖域半径epsilon_1=1e-6#终止条件1N=1000#最大迭代次数m=5#有限内存BFGS保存的迭代信息数量s_list=[]y_list=[]H0=np.eye(len(x_k))#初始近似矩阵forkinrange(N):g_k=gradient(x_k)d_k=conjugate_gradient(H0,g_k,delta_k)x_k_plus_1=x_k+d_kf_k=objective_function(x_k)f_k_plus_1=objective_function(x_k_plus_1)rho_k=(f_k-f_k_plus_1)/(objective_function(x_k)-objective_function(x_k+d_k))ifrho_k>0.25:delta_k=min(2*delta_k,1.0)else:delta_k=delta_k/4s_k=x_k_plus_1-x_ky_k=gradient(x_k_plus_1)-g_ks_list.append(s_k)y_list.append(y_k)iflen(s_list)>m:s_list.pop(0)y_list.pop(0)ifnp.abs(f_k-f_k_plus_1)<epsilon_1:breakx_k=x_k_plus_1returnx_k#定义目标函数defobjective_function(x):returnnp.sum(x**2)#定义目标函数的梯度defgradient(x):return2*x#有限内存BFGS公式计算海色阵近似矩阵与向量的乘积deflbfgs_approx(H0,s_list,y_list,g):m=len(s_list)q=g.copy()alpha=[]foriinrange(m-1,-1,-1):rho=1.0/np.dot(s_list[i],y_list[i])alpha_i=rho*np.dot(s_list[i],q)alpha.append(alpha_i)q=q-alpha_i*y_list[i]z=np.dot(H0,q)beta=[]foriinrange(0,m):rho=1.0/np.dot(s_list[i],y_list[i])beta_i=rho*np.dot(y_list[i],z)beta.append(beta_i)z=z+(alpha[m-1-i]-beta_i)*s_list[i]returnz#共轭梯度法求解信赖域二次模型defconjugate_gradient(B_k,g_k,delta_k):d_k=-g_kg=g_k.copy()for_inrange(len(g_k)):B_d=lbfgs_approx(np.eye(len(g_k)),s_list,y_list,d_k)alpha=np.dot(g,g)/np.dot(d_k,B_d)x_k_plus_1=x_k+alpha*d_kifnp.linalg.norm(x_k_plus_1-x_k)>delta_k:x_k_plus_1=x_k+delta_k*d_k/np.linalg.norm(d_k)breakg_k_plus_1=gradient(x_k_plus_1)beta=np.dot(g_k_plus_1,g_k_plus_1)/np.dot(g_k,g_k)d_k=-g_k_plus_1+beta*d_kg_k=g_k_plus_1returnx_k_plus_1-x_k#LMTI方法主程序deflmt_i_method():x_k=np.array([1.0,1.0])#初始迭代点delta_k=0.1#初始信赖域半径epsilon_1=1e-6#终止条件1N=1000#最大迭代次数m=5#有限内存BFGS保存的迭代信息数量s_list=[]y_list=[]H0=np.eye(len(x_k))#初始近似矩阵forkinrange(N):g_k=gradient(x_k)d_k=conjugate_gradient(H0,g_k,delta_k)x_k_plus_1=x_k+d_kf_k=objective_function(x_k)f_k_plus_1=objective_function(x_k_plus_1)rho_k=(f_k-f_k_plus_1)/(objective_function(x_k)-objective_function(x_k+d_k))ifrho_k>0.25:delta_k=min(2*delta_k,1.0)else:delta_k=delta_k/4s_k=x_k_plus_1-x_ky_k=gradient(x_k_plus_1)-g_ks_list.append(s_k)y_list.append(y_k)iflen(s_list)>m:s_list.pop(0)y_list.pop(0)ifnp.abs(f_k-f_k_plus_1)<epsilon_1:breakx_k=x_k_plus_1returnx_kdefobjective_function(x):returnnp.sum(x**2)#定义目标函数的梯度defgradient(x):return2*x#有限内存BFGS公式计算海色阵近似矩阵与向量的乘积deflbfgs_approx(H0,s_list,y_list,g):m=len(s_list)q=g.copy()alpha=[]foriinrange(m-1,-1,-1):rho=1.0/np.dot(s_list[i],y_list[i])alpha_i=rho*np.dot(s_list[i],q)alpha.append(alpha_i)q=q-alpha_i*y_list[i]z=np.dot(H0,q)beta=[]foriinrange(0,m):rho=1.0/np.dot(s_list[i],y_list[i])beta_i=rho*np.dot(y_list[i],z)beta.append(beta_i)z=z+(alpha[m-1-i]-beta_i)*s_list[i]returnz#共轭梯度法求解信赖域二次模型defconjugate_gradient(B_k,g_k,delta_k):d_k=-g_kg=g_k.copy()for_inrange(len(g_k)):B_d=lbfgs_approx(np.eye(len(g_k)),s_list,y_list,d_k)alpha=np.dot(g,g)/np.dot(d_k,B_d)x_k_plus_1=x_k+alpha*d_kifnp.linalg.norm(x_k_plus_1-x_k)>delta_k:x_k_plus_1=x_k+delta_k*d_k/np.linalg.norm(d_k)breakg_k_plus_1=gradient(x_k_plus_1)beta=np.dot(g_k_plus_1,g_k_plus_1)/np.dot(g_k,g_k)d_k=-g_k_plus_1+beta*d_kg_k=g_k_plus_1returnx_k_plus_1-x_k#LMTI方法主程序deflmt_i_method():x_k=np.array([1.0,1.0])#初始迭代点delta_k=0.1#初始信赖域半径epsilon_1=1e-6#终止条件1N=1000#最大迭代次数m=5#有限内存BFGS保存的迭代信息数量s_list=[]y_list=[]H0=np.eye(len(x_k))#初始近似矩阵forkinrange(N):g_k=gradient(x_k)d_k=conjugate_gradient(H0,g_k,delta_k)x_k_plus_1=x_k+d_kf_k=objective_function(x_k)f_k_plus_1=objective_function(x_k_plus_1)rho_k=(f_k-f_k_plus_1)/(objective_function(x_k)-objective_function(x_k+d_k))ifrho_k>0.25:delta_k=min(2*delta_k,1.0)else:delta_k=delta_k/4s_k=x_k_plus_1-x_ky_k=gradient(x_k_plus_1)-g_ks_list.append(s_k)y_list.append(y_k)iflen(s_list)>m:s_list.pop(0)y_list.pop(0)ifnp.abs(f_k-f_k_plus_1)<epsilon_1:breakx_k=x_k_plus_1returnx_kreturnnp.sum(x**2)#定义目标函数的梯度defgradient(x):return2*x#有限内存BFGS公式计算海色阵近似矩阵与向量的乘积deflbfgs_approx(H0,s_list,y_list,g):m=len(s_list)q=g.copy()alpha=[]foriinrange(m-1,-1,-1):rho=1.0/np.dot(s_list[i],y_list[i])alpha_i=rho*np.dot(s_list[i],q)alpha.append(alpha_i)q=q-alpha_i*y_list[i]z=np.dot(H0,q)beta=[]foriinrange(0,m):rho=1.0/np.dot(s_list[i],y_list[i])beta_i=rho*np.dot(y_list[i],z)beta.append(beta_i)z=z+(alpha[m-1-i]-beta_i)*s_list[i]returnz#共轭梯度法求解信赖域二次模型defconjugate_gradient(B_k,g_k,delta_k):d_k=-g_kg=g_k.copy()for_inrange(len(g_k)):B_d=lbfgs_approx(np.eye(len(g_k)),s_list,y_list,d_k)alpha=np.dot(g,g)/np.dot(d_k,B_d)x_k_plus_1=x_k+alpha*d_kifnp.linalg.norm(x_k_plus_1-x_k)>delta_k:x_k_plus_1=x_k+delta_k*d_k/np.linalg.norm(d_k)breakg_k_plus_1=gradient(x_k_plus_1)beta=np.dot(g_k_plus_1,g_k_plus_1)/np.dot(g_k,g_k)d_k=-g_k_plus_1+beta*d_kg_k=g_k_plus_1returnx_k_plus_1-x_k#LMTI方法主程序deflmt_i_method():x_k=np.array([1.0,1.0])#初始迭代点delta_k=0.1#初始信赖域半径epsilon_1=1e-6#终止条件1N=1000#最大迭代次数m=5#有限内存BFGS保存的迭代信息数量s_list=[]y_list=[]H0=np.eye(len(x_k))#初始近似矩阵forkinrange(N):g_k=gradient(x_k)d_k=conjugate_gradient(H0,g_k,delta_k)x_k_plus_1=x_k+d_kf_k=objective_function(x_k)f_k_plus_1=objective_function(x_k_plus_1)rho_k=(f_k-f_k_plus_1)/(objective_function(x_k)-objective_function(x_k+d_k))ifrho_k>0.25:delta_k=min(2*delta_k,1.0)else:delta_k=delta_k/4s_k=x_k_plus_1-x_ky_k=gradient(x_k_plus_1)-g_ks_list.append(s_k)y_list.append(y_k)iflen(s_list)>m:s_list.pop(0)y_list.pop(0)ifnp.abs(f_k-f_k_plus_1)<epsilon_1:breakx_k=x_k_plus_1returnx_k#定义目标函数的梯度defgradient(x):return2*x#有限内存BFGS公式计算海色阵近似矩阵与向量的乘积deflbfgs_approx(H0,s_list,y_list,g):m=len(s_list)q=g.copy()alpha=[]foriinrange(m-1,-1,-1):rho=1.0/np.dot(s_list[i],y_list[i])alpha_i=rho*np.dot(s_list[i],q)alpha.append(alpha_i)q=q-alpha_i*y_list[i]z=np.dot(H0,q)beta=[]foriinrange(0,m):rho=1.0/np.dot(s_list[i],y_list[i])beta_i=rho*np.dot(y_list[i],z)beta.append(beta_i)z=z+(alpha[m-1-i]-beta_i)*s_list[i]returnz#共轭梯度法求解信赖域二次模型defconjugate_gradient(B_k,g_k,delta_k):d_k=-g_kg=g_k.copy()for_inrange(len(g_k)):B_d=lbfgs_approx(np.eye(len(g_k)),s_list,y_list,d_k)alpha=np.dot(g,g)/np.dot(d_k,B_d)x_k_plus_1=x_k+alpha*d_kifnp.linalg.norm(x_k_plus_1-x_k)>delta_k:x_k_plus_1=x_k+delta_k*d_k/np.linalg.norm(d_k)breakg_k_plus_1=gradient(x_k_plus_1)beta=np.dot(g_k_plus_1,g_k_plus_1)/np.dot(g_k,g_k)d_k=-g_k_plus_1+beta*d_kg_k=g_k_plus_1returnx_k_plus_1-x_k#LMTI方法主程序deflmt_i_method():x_k=np.array([1.0,1.0])#初始迭代点delta_k=0.1#初始信赖域半径epsilon_1=1e-6#终止条件1N=1000#最大迭代次数m=5#有限内存BFGS保存的迭代信息数量s_list=[]y_list=[]H0=np.eye(len(x_k))#初始近似矩阵forkinrange(N):g_k=gradient(x_k)d_k=conjugate_gradient(H0,g_k,delta_k)x_k_plus_1=x_k+d_kf_k=objective_function(x_k)f_k_plus_1=objective_function(x_k_plus_1)rho_k=(f_k-f_k_plus_1)/(objective_function(x_k)-objective_function(x_k+d_k))ifrho_k>0.25:delta_k=min(2*delta_k,1.0)else:delta_k=delta_k/4s_k=x_k_plus_1-x_ky_k=gradient(x_k_plus_1)-g_ks_list.append(s_k)y_list.append(y_k)iflen(s_list)>m:s_list.pop(0)y_list.pop(0)ifnp.abs(f_k-f_k_plus_1)<epsilon_1:breakx_k=x_k_plus_1returnx_kdefgradient(x):return2*x#有限内存BFGS公式计算海色阵近似矩阵与向量的乘积deflbfgs_approx(H0,s_list,y_list,g):m=len(s_list)q=g.copy()alpha=[]foriinrange(m-1,-1,-1):rho=1.0/np.dot(s_list[i],y_list[i])alpha_i=rho*np.dot(s_list[i],q)alpha.append(alpha_i)q=q-alpha_i*y_list[i]z=np.dot(H0,q)beta=[]foriinrange(0,m):rho=1.0/np.dot(s_list[i],y_list[i])beta_i=rho*np.dot(y_list[i],z)beta.append(beta_i)z=z+(alpha[m-1-i]-beta_i)*s_list[i]returnz#共轭梯度法求解信赖域二次模型defconjugate_gradient(B_k,g_k,delta_k):d_k=-g_kg=g_k.copy()for_inrange(len(g_k)):B_d=lbfgs_approx(np.eye(len(g_k)),s_list,y_list,d_k)alpha=np.dot(g,g)/np.dot(d_k,B_d)x_k_plus_1=x_k+alpha*d_kifnp.linalg.norm(x_k_plus_1-x_k)>delta_k:x_k_plus_1=x_k+delta_k*d_k/np.linalg.norm(d_k)breakg_k_plus_1=gradient(x_k_plus_1)beta=np.dot(g_k_plus_1,g_k_plus_1)/np.dot(g_k,g_k)d_k=-g_k_plus_1+beta*d_kg_k=g_k_plus_1returnx_k_plus_1-x_k#LMTI方法主程序deflmt_i_method():x_k=np.array([1.0,1.0])#初始迭代点delta_k=0.1#初始信赖域半径epsilon_1=1e-6#终止条件1N=1000#最大迭代次数m=5#有限内存BFGS保存的迭代信息数量s_list=[]y_list=[]H0=np.eye(len(x_k))#初始近似矩阵forkinrange(N):g_k=gradient(x_k)d_k=conjugate_gradient(H0,g_k,delta_k)x_k_plus_1=x_k+d_kf_k=objective_function(x_k)f_k_plus_1=objective_function(x_k_plus_1)rho_k=(f_k-f_k_plus_1)/(objective_function(x_k)-objective_function(x_k+d_k))ifrho_k>0.25:delta_k=min(2*delta_k,1.0)else:delta_k=delta_k/4s_k=x_k_plus_1-x_ky_k=gradient(x_k_plus_1)-g_ks_list.append(s_k)y_list.append(y_k)iflen(s_list)>m:s_list.pop(0)y_list.pop(0)ifnp.abs(f_k-f_k_plus_1)<epsilon_1:breakx_k=x_k_plus_1returnx_kreturn2*x#有限内存BFGS公式计算海色阵近似矩阵与向量的乘积deflbfgs_approx(H0,s_list,y_list,g):m=len(s_list)q=g.copy()alpha=[]foriinrange(m-1,-1,-1):rho=1.0/np.dot(s_list[i],y_list[i])alpha_i=rho*np.dot(s_list[i],q)alpha.append(alpha_i)q=q-alpha_i*y_list[i]z=np.dot(H0,q)beta=[]foriinrange(0,m):rho=1.0/np.dot(s_list[i],y_list[i])beta_i=rho*np.dot(y_list[i],z)beta.append(beta_i)z=z+(alpha[m-1-i]-beta_i)*s_list[i]returnz#共轭梯度法求解信赖域二次模型defconjugate_gradient(B_k,g_k,delta_k):d_k=-g_kg=g_k.copy()for_inrange(len(g_k)):B_d=lbfgs_approx(np.eye(len(g_k)),s_list,y_list,d_k)alpha=np.dot(g,g)/np.dot(d_k,B_d)x_k_plus_1=x_k+alpha*d_kifnp.linalg.norm(x_k_plus_1-x_k)>delta_k:x_k_plus_1=x_k+delta_k*d_k/np.linalg.norm(d_k)breakg_k_plus_1=gradient(x_k_plus_1)beta=np.dot(g_k_plus_1,g_k_plus_1)/np.dot(g_k,g_k)d_k=-g_k_plus_1+beta*d_kg_k=g_k_plus_1returnx_k_plus_1-x_k#LMTI方法主程序deflmt_i_method():x_k=np.array([1.0,1.0])#初始迭代点delta_k=0.1#初始信赖域半径epsilon_1=1e-6#终止条件1N=1000#最大迭代次数m=5#有限内存BFGS保存的迭代信息数量s_list=[]y_list=[]H0=np.eye(len(x_k))#初始近似矩阵forkinrange(N):g_k=gradient(x_k)d_k=conjugate_gradient(H0,g_k,delta_k)x_k_plus_1=x_k+d_kf_k=objective_function(x_k)f_k_plus_1=objective_function(x_k_plus_1)rho_k=(f_k-f_k_plus_1)/(objective_function(x_k)-objective_function(x_k+d_k))