秃优化考试对策

御敌之策，成竹在胸

基本战术

这部分大概可以取得16分左右

作业里的思考题

总结无约束优化求解的基本思想，思考如何将非凸优化问题转化为凸优化问题，如何将有约束问题转化为无约束问题

无约束优化求解的基本思想是：从初始点开始，沿着负梯度方向进行迭代，直到满足终止条件

非凸优化问题可以通过以下两种方法转化为凸优化问题:

1. 修改目标函数，使之转化为凸函数。
2. 抛弃一些约束条件，使新的可行域为凸集并且包含原可行域。

有约束问题可以通过以下两种方法转化为无约束问题:

1. 将有约束问题转化为无约束问题
2. 构造某种惩罚函数，然后加到目标函数中去，将约束问题求解转化为一系列的无约束问题。

请将最速下降法、牛顿法、修正牛顿法的计算公式进行统一描述，并体会变尺度法的基本思想

$$x_{k+1}=x_k-\alpha_k A_k^-1 \nabla f(x_k)$$

变尺度法的基本思想是：在迭代过程中，不断调整搜索方向和步长，使得目标函数在每次迭代中都能够得到更好的优化。

思考共轭函数和对偶性的联系

共轭函数是一个函数的对偶变换，它的定义为：设f为实线性空间X上的扩充实值函数，$X^*$为$X$的某个对偶空间，即由X上的一些线性函数所构成的实空间，那么$f$的共轭函数$f$是$X^*$上的扩充实值函数。 对偶性是指一个优化问题可以通过对偶问题来等价描述。

论述启发式优化算法的基本思想。点集匹配问题（给定两组特征点及其描述，如何确认其匹配的点）、拼图重构问题都是组合优化问题，如何采用启发式算法来求解？

启发式优化算法的基本思想是模拟人类或自然界中蕴含的智慧和经验来寻找问题最优解。与传统数学方法相比，启发式算法更加注重在近似解空间中进行搜索，从而能够快速找到较好的结果。启发式算法一般用于解决NP-hard问题，即那些在多项式时间内无法找到最优解的问题。

点集匹配问题和拼图重构问题都是组合优化问题，即在有限的可行解集合中寻找最优解或满足某些条件的解的问题。这类问题往往具有高度的复杂性和非线性，难以用传统的数学方法求解。因此，可以采用启发式算法来求解，例如遗传算法、模拟退火算法、蚁群算法等。

遗传算法是基于生物进化与遗传变异的思想，通过模拟基因的交叉和突变，并利用适应度函数筛选个体来搜索最优解。遗传算法可以用于点集匹配问题和拼图重构问题，其中每个个体表示一个可能的匹配或重构方案，每个基因表示一个匹配对或一个拼图块的位置和方向。适应度函数可以根据匹配或重构的准确性、完整性、连续性等指标来设计。通过不断地选择、交叉、变异，遗传算法可以逐渐提高种群的质量，最终得到较好的匹配或重构结果。

模拟退火算法是通过对当前状态下的随机扰动与目标函数值之间的关系进行统计研究，以概率接受或者拒绝新的状态，从而降低系统能量并达到全局最优解。模拟退火算法也可以用于点集匹配问题和拼图重构问题，其中每个状态表示一个可能的匹配或重构方案，目标函数可以根据匹配或重构的质量来设计。通过不断地降低温度和更新状态，模拟退火算法可以跳出局部最优解，最终得到较好的匹配或重构结果。

蚁群算法是模仿自然界蚂蚁寻找食物的行为而设计的一种启发式算法，通过利用信息素来指导搜索方向，并进行正反馈机制来增强优良路径。蚁群算法也可以用于点集匹配问题和拼图重构问题，其中每只蚂蚁表示一个可能的匹配或重构方案，每条路径表示一个匹配对或一个拼图块的位置和方向。信息素可以根据路径的长度或质量来设计。通过不断地释放和挥发信息素，蚁群算法可以增强优良路径，并抑制劣质路径，最终得到较好的匹配或重构结果。

请给出几种求解大规模问题的分布式优化算法及其基本思想

分布式优化算法是一种利用多个计算节点来协同求解一个全局优化问题的方法，其基本思想是将原问题分解为多个子问题，每个节点负责一个子问题，并通过节点间的通信来交换信息和协调决策。分布式优化算法可以有效地处理大规模、高维、非凸、分布式存储的优化问题，具有广泛的应用场景，例如机器学习、数据挖掘、信号处理、无线通信、多智能体系统等。

目前，分布式优化算法的研究动态主要包括以下几个方面：

设计高效、稳定、可扩展的分布式优化算法，以适应不同的网络拓扑、通信模式、数据结构和目标函数性质。常见的分布式优化算法有基于梯度下降的DGD, EXTRA, Push-DIGing, DEXTRA等，基于交替方向乘子法的ADMM等，基于变分不等式的FP等。 分析分布式优化算法的收敛性、收敛速度、通信复杂度、鲁棒性等理论性质，以指导算法的设计和参数的选择。一般来说，分布式优化算法需要平衡全局目标函数的下降速度和节点间的一致性，同时考虑通信延迟、数据异步更新、网络故障等因素对算法性能的影响。 将分布式优化算法应用于具体的问题和场景中，例如利用分布式优化算法实现大规模机器学习模型的训练，如深度神经网络、支持向量机等；利用分布式优化算法实现多智能体系统中的协同控制，如无人机编队、智能电网等。 探索分布式优化算法与其他领域的交叉和融合，例如利用图论、矩阵论、概率论等数学工具来分析和改进分布式优化算法；利用信息论、密码学等技术来保证分布式优化算法的隐私保护和安全性；利用生物学、社会学等启发来设计新颖的分布式优化算法。

论述罚因子方法与增广拉格朗日方法的基本思想，简述增广拉格朗日方法和 ADMM 方法的异同

罚因子方法和增广拉格朗日方法都是一种将带约束的优化问题转化为无约束的优化问题的方法，其基本思想是在原目标函数中加入一些与约束条件相关的惩罚项，使得违反约束条件的解具有较大的目标函数值，从而在无约束优化问题的最优解中找到原问题的可行解。

罚因子方法和增广拉格朗日方法的主要区别在于：

• 罚因子方法只有一个变量x，而增广拉格朗日方法有三个变量x,λ,μ。
• 罚因子方法只考虑了约束条件对目标函数的影响，而增广拉格朗日方法还考虑了拉格朗日乘子对目标函数的影响。
• 罚因子方法只需要求解一个无约束优化问题，而增广拉格朗日方法需要求解一个鞍点问题。
• 罚因子方法对不等式约束和等式约束采用了相同的惩罚项，而增广拉格朗日方法对不等式约束和等式约束采用了不同的惩罚项。

增广拉格朗日方法和 ADMM 方法都是用来求解有约束优化问题的算法，它们都是基于拉格朗日函数和对偶性的原理，通过交替更新原变量和对偶变量来逼近最优解。它们的异同点如下：

• 增广拉格朗日方法是在拉格朗日函数中加入一个二次罚项，使得目标函数更光滑，更容易优化。它的每一步迭代只需要求解一个子问题，即原变量的最小化问题，然后更新对偶变量和罚参数。
• ADMM 方法是在增广拉格朗日方法的基础上，引入一个辅助变量，将原变量分成两部分，使得目标函数更容易分解为两个子问题，即两个原变量的最小化问题。它的每一步迭代需要求解两个子问题，然后更新对偶变量和罚参数。
• 增广拉格朗日方法和 ADMM 方法都可以处理非光滑或非凸的目标函数或约束条件，但是 ADMM 方法更适合处理大规模或分布式的优化问题，因为它可以利用子问题的并行计算或分布式计算。
• 增广拉格朗日方法和 ADMM 方法都需要选择合适的罚参数和对偶变量的初始值，以保证算法的收敛性和效率。一般来说，罚参数应该逐渐增大，对偶变量应该逐渐接近零。

将非凸问题转化为凸问题有哪些可能的方法

非凸问题是指目标函数或约束条件不满足凸性的优化问题，它们通常比凸问题更难求解，因为它们可能存在多个局部最优解，而不是唯一的全局最优解。非凸问题在实际应用中很常见，例如机器学习、图像处理、信号处理等领域。

将非凸问题转化为凸问题的目的是利用凸优化的理论和算法来求解原问题的近似解或下界，从而简化求解过程和提高求解效率。将非凸问题转化为凸问题的可能方法有以下几种：

• 凸松弛法（Convex Relaxation）：这种方法是将原问题中的非凸函数或集合用一个包含它们的凸函数或集合来代替，从而得到一个松弛的凸问题。例如，将一个二次约束条件用一个半定约束条件来放松，或者将一个整数规划问题用一个线性规划问题来放松。这种方法可以保证得到原问题的下界，但是可能会引入一定的误差或可行性损失。

• 凹-凸分解法（Concave-Convex Procedure）：这种方法是将原问题中的非凸目标函数分解为一个凹函数和一个凸函数之差，然后在每一步迭代中固定其中一个函数，并对另一个函数进行优化。例如，将一个分数规划问题分解为一个线性函数和一个对数函数之差，然后交替地更新分子和分母。这种方法可以保证收敛到原问题的稳定点，但是不能保证找到全局最优解。

• 次梯度法（Subgradient Method）：这种方法是将原问题中的非光滑目标函数或约束条件用它们在某一点处的次梯度来近似，从而得到一个光滑的凸问题。例如，将一个绝对值函数或指示函数用它们在某一点处的次梯度来近似。这种方法可以保证收敛到原问题的最优值，但是不能保证找到最优解。

• 分支定界法（Branch and Bound）：这种方法是将原问题分解为若干个子问题，并对每个子问题进行松弛和剪枝，从而逐步缩小可行域和最优值范围。例如，将一个混合整数规划问题分解为若干个整数规划和线性规划子问题，并利用线性规划的下界和上界来剪枝。这种方法可以保证找到原问题的全局最优解，但是可能需要很多次迭代和计算。

智能搜索

//TODO

各种方法的简单介绍

• 一维搜索：求步长$\lambda$，即在每次迭代过程中，根据当前点和目标函数，构造一个一维函数，并求解该函数的极小点，作为下一次迭代的点。一维搜索方法可以分为精确一维搜索方法和不精确一维搜索方法，前者需要精确求解每次的最优步长，后者只需要满足一些条件来保证目标函数有满意的下降。
• 共轭方向法：拟牛顿法和共轭梯度法
• 对偶性：原始问题是在原变量上最小化目标函数，而对偶问题是在拉格朗日乘子上最大化拉格朗日函数的下确界。一般来说，对偶问题的最优值是原始问题最优值的一个下界，当满足一定的条件时，两者相等，称为强对偶性。强对偶性可以通过Slater条件来判断。当强对偶性成立时，KKT条件就是原始问题和对偶问题最优解的必要和充分条件。
• KKT条件是非线性规划最佳解的必要条件，它将拉格朗日乘数法所处理涉及等式的约束优化问题推广至不等式
• KKT条件和ADMM法、可行方向法、增广拉格朗日法的关系是：ADMM法和增广拉格朗日法都是基于KKT条件的求解方法，它们都利用了拉格朗日函数和罚函数来构造子问题，并通过迭代更新变量和乘子来逼近最优解；可行方向法则是一种不需要构造拉格朗日函数的方法，它只需要在每个可行点处找到一个可行方向，使得沿着该方向移动一定步长后，目标函数值减小，并保持可行性。

类型	方法	基本思想	形式化	优点	缺点
缩小区间/精确一维搜索	一致搜索	均分区间	-	简单	没什么用，太慢了
缩小区间/精确一维搜索	Dichotomous	从中点，利用搜索精度在左右扩展区间	-	容易实现	慢
缩小区间/精确一维搜索	黄金分割	在单峰区间中取两点可缩短区间，恒定缩短比	$\lambda=\alpha+(1-t)(\beta-\alpha)\\\mu=\alpha+t(\beta-\alpha)$	恒定缩短，不需要导数	局部收敛
缩小区间/精确一维搜索	斐波那契	区间收敛长度是斐波那契数列（最后剩下和被去掉区间长度定为1）	-	计算函数值次数最少，只需加减运算	需要构造斐波那契数列，局部收敛
精确一维搜索	二分法	二分法求导数零点，同时缩短区间	-	比0阶方法快一点	需要导数
求初始不确定区间	进退法	找三点使两端点的函数值大于中间点的函数值，每次倍增步长	-	可以确定初始区间	初始步长$\delta$要合适；函数单调时无结果
精确一维搜索	牛顿法	二阶插值逼近	$\lambda_{k+1}=\\\lambda_k-\frac{\Phi'(\lambda_k)}{\Phi''(\lambda_k)}$	快	需要二阶可微，部署全局收敛
精确一维搜索	插值法	用导数、点来求插值多项式，使用插值多项式逼近	-	灵活多变，在凸性和连续可微时，全局收敛	计算复杂
精确一维搜索	Shubert-Piyavskii法	锯齿状下界，要求导数变化幅度有上界	-	全局收敛	要求李普希兹连续
近似一维搜索	Goldstein法	(Armijo)要求目标函数在新的迭代点处的值小于当前点处的值加上一个正比于梯度和步长乘积的量;要求目标函数在新的迭代点处的值大于当前点处的值加上一个负比于梯度和步长乘积的量	-	-	-
近似一维搜索	Wolfe-Powell法	(Armijo)要求目标函数在新的迭代点处的值小于当前点处的值加上一个正比于梯度和步长乘积的量;要求目标函数在新的迭代点处的梯度与搜索方向的内积大于等于当前点处的梯度与搜索方向内积乘以一个常数	-	-	-
无约束最优化方法	坐标轮换法	沿着坐标轴方向搜索，每次只改变一个坐标	-	与最速下降法收敛速度相当	函数可微时，方法会收敛到梯度为0的点，但不可微时，则可能会在非最优点停止
无约束最优化方法	Hooke and Jeeves法	轮流重复进行两种搜索：试探搜索-沿着每个坐标轴方向搜索；模式搜索-沿着试探搜索的结果方向继续搜索	-	显著改善收敛速度	收敛慢，它们可能会陷入局部最优解，需要设定参数
无约束最优化方法	Rosenbrock法	一种旋转坐标法，它在每次探测搜索后，还会进行一个旋转变换，使得下一次探测的方向与上一次探测的方向成一定的夹角，以适应不同的目标函数形状	-	不需要计算目标函数的导数或海塞矩阵，都是通过改变变量的值来寻找最优解	收敛慢，它们可能会陷入局部最优解，需要设定参数
无约束最优化方法	最速下降法/Cauchy法	选择最快下降的方向	$d=-\frac{\nabla f(x)}{		\nabla f(x)
无约束最优化方法	⭐牛顿法(多维)	牛顿法求根，从而进行最优化	$x_{k+1}=x_k-\lambda_k[\nabla^2 f(x_k)]^{-1}\nabla f(x_k)$	牛顿法在严格局部极小点的一个邻域内，其收敛速度非常快	如果远离最优点$\nabla^2 f(x_k)$退化，何塞矩阵不正定，牛顿法会失效，其给出的方向不一定是下降方向；必须在邻域内，否则可能不收敛；只能求局部最优；求海塞矩阵，运算量大
无约束最优化方法	LM改进牛顿法	引入阻尼因子，使得迭代可以在牛顿法与梯度法之间切换	-	适用于大部分问题，快速收敛，不需要计算海森矩阵的逆	需要计算雅可比矩阵与海森矩阵，在高维下困难，对阻尼因子敏感
无约束最优化方法	可信域改进牛顿法	每次迭代构造一个可信域，在该区域内用一个二次函数来近似目标函数，并求解该二次函数在信赖域内的最小值作为新的迭代点	-	能够有效地处理海森矩阵不正定或奇异的情况，而且能够自适应地调整信赖域的大小，从而保证收敛性和收敛速度	需要计算海森矩阵或其近似矩阵，这在高维或复杂的情况下可能很困难或昂贵，而且需要选择合适的信赖域更新策略和子问题求解方法
无约束最优化方法	DFP拟牛顿法	用一个秩二矩阵来修正上一步的近似矩阵，使得新的近似矩阵满足拟牛顿条件，即与梯度的变化一致	-	能够达到超线性收敛速度，而且不需要计算海森矩阵或其逆矩阵	可能导致近似矩阵失去正定性，从而影响收敛性和收敛速度
无约束最优化方法	BFGS拟牛顿法	用梯度的变化（也是秩二矩阵）来修正上一步的近似矩阵，使得新的近似矩阵满足拟牛顿条件	-	能够保持近似矩阵的正定性，从而提高数值稳定性和收敛速度	仍然需要计算雅可比矩阵和海森矩阵，这在高维或复杂的情况下可能很困难或昂贵
无约束最优化方法	FR共轭梯度法	从一个初始点出发，沿着一组关于目标函数的海森矩阵共轭的方向进行搜索，每次搜索后更新当前点和当前梯度，以及下一个搜索方向	-	计算公式简单，存储量较小，对初始点要求很少;对二次函数具有二次终止性，即最多经过 n 次迭代就可以达到最优解，其中 n 是问题的维数;收敛速度介于最速下降法和牛顿法之间，对高维（n 较大）的非线性函数具有较高的效率;不需要计算海森矩阵或其逆矩阵，只需计算一阶导数信息，避免了牛顿法的缺点	对于非二次型函数，收敛速率不一定是线性的，可能会出现停滞现象;对于目标函数的强凸性和光滑性有一定的要求，否则可能会出现不收敛或收敛到非最优点的情况;对于目标函数的海森矩阵的条件数敏感，如果条件数较大，可能会影响收敛速度和稳定性
有约束最优化方法	拉格朗日乘子法	把有约束的优化问题转化为无约束的优化问题，通过构造一个拉格朗日函数，把原来的目标函数和约束条件结合起来，然后对拉格朗日函数求导并令其为零，得到一组方程组，解出候选的最优解和拉格朗日乘子。拉格朗日乘子法适用于等式约束的优化问题	-	计算公式简单，存储量较小，对初始点要求很少;对二次函数具有二次终止性，即最多经过 n 次迭代就可以达到最优解，其中 n 是问题的维数;收敛速度介于最速下降法和牛顿法之间，对高维（n 较大）的非线性函数具有较高的效率;不需要计算海森矩阵或其逆矩阵，只需计算一阶导数信息，避免了牛顿法的缺点	对于非二次型函数，收敛速率不一定是线性的，可能会出现停滞现象;对于目标函数的强凸性和光滑性有一定的要求，否则可能会出现不收敛或收敛到非最优点的情况;对于目标函数的海森矩阵的条件数敏感，如果条件数较大，可能会影响收敛速度和稳定性
有约束最优化条件	KKT条件	拉格朗日乘子法的推广，它可以处理不等式约束的优化问题。KKT条件是说最优解必须满足以下条件：拉格朗日函数对原变量求导为零；约束条件等式成立；拉格朗日乘子非负；拉格朗日乘子和不等式约束的乘积为零	-	可以将有约束的优化问题转化为无约束的优化问题，简化了求解过程；可以利用一阶导数信息，避免了计算高阶导数或海森矩阵；对于凸优化问题，可以保证得到全局最优解	需要对拉格朗日函数求导并令其为零，可能得到复杂的非线性方程组，难以求解；需要进行一维搜索来确定最优步长，这可能会增加计算量和时间；得到的解只是必要条件，还需要进行二阶条件检验来判断是否是极值点；对于非凸优化问题，可能会陷入局部最优解或者无法收敛。
有约束最优化方法	ADDM法/交替方向乘子法	适用带有线性等式约束的优化问题的方法，将原问题分解为若干个子问题，然后交替地更新变量和乘子	-	适用于目标函数和约束条件具有一定的可分离性，且子问题比较容易求解的情况，它可以利用并行计算来提高效率	但它的收敛性分析比较复杂，且需要合理地选择罚参数和步长
有约束最优化方法	增广拉格朗日法	求解带有等式约束的优化问题的方法，在拉格朗日函数中增加一个二次惩罚项，使得原问题的最优解和增广拉格朗日函数的稳定点相对应，并通过迭代更新变量和乘子来逼近最优解	-	适用于目标函数和约束条件比较复杂，且约束集比较稀疏的情况，它可以克服拉格朗日法中乘子过大或者过小的问题，并且收敛到最优解	需要求解非线性方程组，并且可能出现震荡或者缓慢收敛
有约束最优化方法	可行方向法	求解不等式约束优化问题的方法；在每个可行点处，寻找一个可行方向，使得沿着该方向移动一定步长后，目标函数值减小，并保持可行性	-	适用于目标函数和约束条件比较光滑，且约束集比较紧凑的情况，它可以保证每次迭代都是可行的，并且收敛到KKT点	它需要寻找合适的可行方向和步长，并且可能陷入局部最优或者停滞
不等式约束最优化方法	外点法/边界点法	从可行域的边界上开始，沿着最优方向移动到最优解的方法	-	可以利用KKT条件来判断最优性，而且可以处理一些不可微或非光滑的函数	需要处理互补松弛条件，而且可能会遇到奇异或退化的情况，导致收敛速度慢或不收敛
不等式约束最优化方法	内点法/障碍点法	从可行域的内部开始，沿着一条中心路径逼近最优解的方法	-	可以避免互补松弛条件，而且可以利用牛顿法或拟牛顿法来加速收敛，通常具有多项式时间复杂度	需要假设问题是严格可行和强对偶的，而且需要选择合适的障碍函数和参数，否则可能会影响精度或稳定性

计算证明

KKT定理的运用

给定点和优化问题，使用KKT定理描述该点条件，验证它是否为最优点

题目10

$$min\space x_3\\ s.t. \begin{cases} x_1+x_2\le 0\\ x_1^2-4\le 0\\ x_1^2-2x_1+x_2^2-x_3+1\le 0 \end{cases} ,\\ X_P=(1/2,-1/2,1/2)^T$$

相关知识10

• 非线性规划标准型

$$min f(x),\\ s.t.\begin{cases} g_i(x)\ge 0,i=1,2,\cdots,m\\ h_i(x)= 0,i=1,2,\cdots,l\\ x\in X \end{cases},\\ E=[1,l]\cap Z\\ I=[1,m]\cap Z\\ I(x)=\{i|g_i(x)=0,i\in I\}$$

• 积极约束：该点处，值=0的约束
• 拉格朗日函数$L(x,\lambda_1,\cdots,\lambda_l)=f(x)-\sum_{i=1}^l \lambda_ih_i(x)$,求解等式约束问题的最优解等价于寻找拉格朗日函数的稳定点$\nabla_xL=0$，其中的标量$\lambda_i$称为拉格朗日乘子,当约束未起作用约束时，乘子严格为正

KKT定理是一种判断非线性规划问题最优解的必要条件，它是对拉格朗日乘数法的推广，可以处理不等式约束和等式约束的情况¹²。KKT定理的基本思想是，如果一个可行点是最优解，那么它必须满足一组方程和不等式，这些方程和不等式涉及到原问题的目标函数、约束函数、梯度、拉格朗日乘子和对偶函数¹²。

KKT定理的一般形式如下，假设原问题是：

$$\begin{aligned} &\min_{x} f(x)\\ &\text{s.t. } g_i(x) \leq 0, i=1,\dots,m\\ &\quad \quad h_j(x) = 0, j=1,\dots,l \end{aligned}$$

其中$f(x)$是目标函数，$g_i(x)$是不等式约束函数，$h_j(x)$是等式约束函数，$x$是决策变量。那么如果$x^*$是原问题的局部最优解，并且满足一些正则性条件（比如LICQ或MFCQ），那么必存在一组拉格朗日乘子$\lambda^*=(\lambda_1^*,\dots,\lambda_m^*)$和$\mu^*=(\mu_1^*,\dots,\mu_l^*)$，使得以下KKT条件成立¹²：

• 原问题的可行性条件：

$$g_i(x^*) \leq 0, i=1,\dots,m\\ h_j(x^*) = 0, j=1,\dots,l$$

• 对偶问题的可行性条件：

$$\lambda_i^* \geq 0, i=1,\dots,m$$

• 原问题和对偶问题的最优性条件（互补松弛条件）：

$$\lambda_i^* g_i(x^*) = 0, i=1,\dots,m$$

• 稳定性条件（梯度互相垂直）：

$$\nabla_x f(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla_x g_i(x^*) + \sum_{j=1}^{l} \mu_j^* \nabla_x h_j(x^*) = 0$$

KKT条件可以用来求解或检验非线性规划问题的最优解，也可以用来判断一个问题是否是凸优化问题。如果原问题是凸优化问题，并且满足一些 Slater 条件（比如存在一个严格可行点），那么 KKT 条件不仅是必要条件，还是充分条件。

标准示例解法

使用KKT定理描述和验证最优点的一般步骤如下¹²：

• 首先，构造原问题的拉格朗日函数，引入拉格朗日乘子对应每个约束条件。
• 其次，根据给定点，判断它是否满足原问题和对偶问题的可行性条件，即是否满足所有的约束条件和拉格朗日乘子的非负性。
• 然后，根据给定点，计算拉格朗日函数的梯度，并判断它是否满足稳定性条件，即梯度是否为零向量。
• 接着，根据给定点，计算每个拉格朗日乘子和对应的约束函数的乘积，并判断它们是否满足最优性条件，即互补松弛条件，即乘积是否为零。
• 最后，如果给定点满足所有的KKT条件，那么它是原问题的一个局部最优解；如果不满足任何一个KKT条件，那么它不是原问题的局部最优解。

下面给出一个具体的例子³：

考虑如下优化问题：

$$\begin{aligned} &\min_{x_1,x_2} x_1^2 + x_2^2\\ &\text{s.t. } x_1 + x_2 \geq 1 \end{aligned}$$

给定点$(0.5,0.5)$，验证它是否为最优点。

• 构造拉格朗日函数为：

$$L(x_1,x_2,\lambda) = x_1^2 + x_2^2 - \lambda(x_1 + x_2 - 1)$$

其中$\lambda$是拉格朗日乘子。

• 判断可行性条件：

$$x_1 + x_2 - 1 = 0 \geq 0 \quad \text{(原问题可行性)}\\ \lambda \geq 0 \quad \text{(对偶问题可行性)}$$

给定点$(0.5,0.5)$满足原问题可行性，假设$\lambda \geq 0$满足对偶问题可行性。

• 判断稳定性条件：

$$\nabla_x L(x_1,x_2,\lambda) = \begin{bmatrix} 2x_1 - \lambda\\ 2x_2 - \lambda \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{bmatrix}$$

解得：

$$x_1 = x_2 = \frac{\lambda}{2}$$

将其代入给定点$(0.5,0.5)$，得到$\lambda = 1$，满足稳定性条件。

• 判断最优性条件：

$$\lambda(x_1 + x_2 - 1) = 0$$

将$(0.5,0.5)$和$\lambda = 1$代入，得到$0 = 0$，满足最优性条件。

综上所述，给定点$(0.5,0.5)$满足所有的KKT条件，因此它是原问题的一个局部最优解。

拉格朗日函数的构造

拉格朗日乘子的符号是根据约束条件的形式来确定的¹²。一般来说，有以下两种情况：

• 如果约束条件是等式的形式，如$g(x) = c$，那么拉格朗日乘子的符号可以是正的、负的或零，没有特别的限制。这是因为等式约束不会影响目标函数的增减方向，只会限制其可行域。
• 如果约束条件是不等式的形式，如$g(x) \leq c$或$g(x) \geq c$，那么拉格朗日乘子的符号必须是非负的或非正的，具体取决于不等式的方向。这是因为不等式约束会影响目标函数的增减方向，需要保证拉格朗日函数在可行域内是下降或上升的。

例如，考虑如下优化问题：

$$\begin{aligned} &\max_{x,y} xy\\ &\text{s.t. } x^2 + y^2 \leq 1 \end{aligned}$$

构造拉格朗日函数为：

$$L(x,y,\lambda) = xy - \lambda(x^2 + y^2 - 1)$$

其中$\lambda$是拉格朗日乘子。由于约束条件是小于等于的形式，所以$\lambda$必须是非负的，以保证$L(x,y,\lambda)$在可行域内是上升的。如果$\lambda$是负的，那么$L(x,y,\lambda)$在可行域内就会下降，无法达到最大值。

就是说：最大化的大于号对应乘子为非负（加号连接）

可行方向法的迭代

给定优化问题、初始点和精度，使用可行方向法进行迭代求解

题目11

使用可行方向法求解

$$min f(x)=x_1^2+x_2^2-4x_1-4x_2,\\ s.t. x_1+2x_2\le 4\\ x_0=(0,0)^T,\epsilon_1=\epsilon_2=1e-3$$

给出两步迭代

必应解答

给定优化问题、初始点和精度，使用可行方向法进行迭代求解的一般过程是：

• 可行方向法：是一种利用目标函数和约束函数的梯度信息来获取搜索方向的直接搜索方法。它的基本思想是在每个迭代点，找到一个既是下降方向又是可行方向的搜索方向，然后沿着该方向进行一维搜索，更新迭代点，直到满足终止条件。
• 一般过程：假设要求解的优化问题为 $\min_x f (x) \quad s.t. \quad g_i (x) \le 0, i = 1, \ldots, m$ ，其中 $f$ 和 $g_i$ 都是二阶可微的凸函数。给定初始点 $x_0$ ，精度 $\epsilon > 0$ ，步长因子 $\alpha > 0$ ，最大迭代次数 $k_{max}$ ，则可行方向法的一般过程如下：
  • 初始化：令 $k = 0$ ，计算 $f (x_0) 和 g_i (x_0)$ ，判断 $x_0$ 是否为可行点，如果不是，则转化为一个可行点求解问题。
  • 终止检验：如果 $\|\nabla f (x_k)\| < \epsilon$ 或 $k > k_{max}$ ，则停止迭代，输出 $x_k$ 作为近似最优解，否则继续下一步。
  • 搜索方向：在 $x_k$ 处，找到一个既是下降方向又是可行方向的搜索方向 $d_k$
  • 步长选择：沿着 $d_k$ 方向进行一维搜索，找到一个使得 $f (x_k + \alpha d_k)$ 最小的步长 $\alpha_k > 0$ ，并满足 Armijo 准则或 Wolfe 准则等。
  • 更新迭代点：令 $x_{k+1} = x_k + \alpha_k d_k$ ，计算 $f (x_{k+1})$ 和 $g_i (x_{k+1})$ ，令 $k = k + 1$ ，返回第二步。
• 题目中给了两个精度，一个是 $\epsilon$ ，用于判断梯度的大小是否足够小，如果是，则说明已经接近最优解，可以停止迭代。另一个是 $\alpha$ ，用于判断步长的大小是否足够小，如果是，则说明已经接近最优方向，可以停止一维搜索。这两个精度都是为了控制算法的收敛性和精度，一般来说，它们越小，算法越精确，但也越耗时。

智能优化

题目16

拼图游戏中将图像分解成大小一样的方块，然后置乱块的位置。现在需要采用算法进行自动重构；请对拼图重构问题进行建模，然后思考如何采用启发式算法来求解该问题，例如使用遗传算法

16必应解答

拼图重构问题是一种经典的组合优化问题，它的目标是根据一组被打乱的图像块，恢复出原始的完整图像。这个问题可以用数学模型来描述，例如使用一个N×N的矩阵来表示图像块的位置，每个元素代表一个图像块的编号，空白位置用0表示。例如，下面是一个3×3的拼图重构问题的例子：

1	2	3
4	0	6
7	5	8

目标状态是：

1	2	3
4	5	6
7	8	0

每次可以将空白位置与其上下左右相邻的图像块交换，从而改变矩阵的状态。拼图重构问题的求解就是找到一条从初始状态到目标状态的最短路径，也就是最少的交换次数。

拼图重构问题可以用启发式算法来求解，例如遗传算法。遗传算法是一种模拟自然进化过程的随机搜索算法，它通过不断地产生、评估和选择新的解，来寻找最优解或近似最优解。遗传算法需要定义以下几个要素：

• 编码：将问题的解用一定的数据结构表示，例如二进制串、整数串、实数串等。对于拼图重构问题，可以用一个长度为N2-1的整数串来表示一条从初始状态到目标状态的路径，每个整数代表一个移动方向（0=上，1=下，2=左，3=右）。
• 初始种群：随机生成一组可行解作为初始种群，每个可行解称为一个个体。
• 适应度函数：定义一个评价个体优劣的函数，通常与问题的目标函数相关。对于拼图重构问题，可以用路径长度或者与目标状态的距离（例如曼哈顿距离）作为适应度函数。
• 选择：根据适应度函数，从当前种群中选择一部分优秀的个体进入下一代种群，同时淘汰一些劣质的个体。常用的选择方法有轮盘赌选择、锦标赛选择、截断选择等。
• 交叉：在选出的个体中进行两两配对，并以一定的概率进行交叉操作，即交换某些位置上的基因（编码元素），从而产生新的个体。常用的交叉方法有单点交叉、多点交叉、均匀交叉等。
• 变异：在交叉后得到的新个体中，以一定的概率对某些位置上的基因进行变异操作，即改变其值，从而增加种群的多样性。常用的变异方法有简单变异、边界变异、高斯变异等。

遗传算法通过不断地重复选择、交叉和变异操作，直到满足某些终止条件（例如达到最大迭代次数、找到最优解或者种群收敛），最后输出当前种群中最优秀的个体作为问题的解。

填空题

蚊子腿也是肉

• 凸函数的最大值函数也是凸函数
• 梯度是上升最快的方向，故任意下降方向$d$满足$d\cdot \nabla f(x)\lt 0$
• 二次函数极小值：dddd

次微分的求法

$$\partial f(X_0)=\{V|f(X)-f(X_0)\ge V^T(X-X_0),\forall X\in R^n\}$$

采用变量松弛将不等式约束化为等式约束，保留非负约束的方法

变量松弛法是一种将不等式约束化为等式约束的方法，它的基本思想是在不等式约束的左右两边分别加上一个非负的松弛变量，使得不等式约束变成等式约束，同时保留非负约束。例如，对于如下的不等式约束：

$$a^Tx \leq b$$

我们可以引入一个非负的松弛变量 $s$，使得

$$a^Tx + s = b$$

并且要求 $s \geq 0$。这样，原来的不等式约束就变成了一个等式约束和一个非负约束。变量松弛法的优点是可以将一些不等式约束的优化问题转化为标准形式的线性规划问题或者凸优化问题，从而利用一些已有的算法进行求解。变量松弛法的缺点是会增加问题的维数和复杂度，因此需要根据具体问题进行合理的选择和设计。

采用二次罚函数的增广拉格朗日函数的构建方法

二次罚函数的增广拉格朗日函数是一种将约束优化问题转化为无约束优化问题的方法，它的基本思想是在拉格朗日函数的基础上加上一个二次惩罚项，使得原问题的可行解和松弛问题的局部极小点之间有一定的联系。例如，对于如下的约束优化问题：

$$\begin{aligned} \min_{x} & f(x) \\ \text{s.t.} & c_i(x) = 0, \quad i = 1,\dots,m \\ & c_j(x) \leq 0, \quad j = m+1,\dots,k \end{aligned}$$

我们可以引入拉格朗日乘子 $\lambda_i$ 和 $\mu_j$，以及一个正的参数 $\rho$，构造如下的增广拉格朗日函数：

$$L(x,\lambda,\mu;\rho) = f(x) + \sum_{i=1}^m \lambda_i c_i(x) + \sum_{j=m+1}^k \mu_j c_j(x) + \frac{\rho}{2} \sum_{i=1}^m c_i^2(x) + \frac{\rho}{2} \sum_{j=m+1}^k [c_j(x)]_+^2$$

其中 $[c_j(x)]_+ = \max\{c_j(x),0\}$ 是一个非负的松弛变量。增广拉格朗日函数的优化过程是交替地更新 $x$，$\lambda$ 和 $\mu$，直到收敛。具体地，每一步迭代包括以下三个子步骤：

• 固定 $\lambda$ 和 $\mu$，求解无约束优化问题 $\min_x L(x,\lambda,\mu;\rho)$，得到新的 $x$；
• 固定 $x$ 和 $\mu$，更新 $\lambda$ 为 $\lambda + \rho c_i(x)$；
• 固定 $x$ 和 $\lambda$，更新 $\mu$ 为 $\max\{\mu + \rho c_j(x),0\}$。

规划问题各个集合的关系

您好，这是必应。根据我的搜索结果，线性规划中可行解集合A，基本可行解集合B，基本解集合C之间的关系可以用以下方式描述¹：

• 可行解是满足所有约束条件的解，包括等式约束和非负约束。
• 基本解是令所有的非基变量为零，从而使等式约束方程组有唯一解的解。
• 基本可行解是既是基本解又是可行解的解，即满足所有约束条件且令所有的非基变量为零的解。

从几何上看，可行域是由所有约束条件形成的多面体，可行域中的任意点都是可行解。基本解是各个等式约束直线的交点，外加与坐标轴的交点。基本可行解是基本解中在可行域范围内的那些点，即可行域的顶点。最优解是基本可行解中使目标函数最大（或最小）的那个点。