最优化 复习题.doc

第一章 习题（补充）1、判断下列问题是线性优化问题还是非线性优化问题：，（）；2、判断对错：若多元函数在点关于x的各个分量的偏导数都存在，那么函数在x处连续。解答错误。例如：二元函数，在点处的偏导数都为0，但是这个函数在点处并不连续。3、判断对错，如果错误，请给出正确叙述：如果多元连续函数在对于x的各个分量的二阶偏导数都存在，那么是一个对称矩阵。解答错误。正确的叙述为：如果多元连续函数在对于x的各个分量的二阶偏导数都存在且连续，那么是一个对称矩阵。4、计算题：设是对称矩阵，向量，求二次函数在任意点处的梯度和海森矩阵。解设，于是。将关于求偏导得到：（因为A是对称矩阵，），所以梯度。再对关于求偏导得到：，所以海森矩阵为。5、求下列函数的最优解及最优值。（1）；解因为，所以最优解为，最优值为；Hesse矩阵为。（2）；解因为，所以最优解为，最优值为。（3）求函数适合附加条件下；解，令，则有，从而，故最优解为，最优值为。（4）；解因为，则最优解可能为或者。又因为，所以在取得最小值；在取得最小值。（5）在平面xOy上求一点，使得它到及三直线的距离之和最小。解设该点为，则原问题为，从而，令，得到最优解为，即为所求点。6、求下列函数的梯度及Hesse矩阵。（1）解，。（2）。解，。7、写出函数在处的线性近似和二次近似。解线性近似为；二次近似为。8、求解下列向量值函数的Jacobi矩阵。（1）；（2）；解（1）；（2）；9、设，求在点处的雅可比矩阵。解由定义可知，代入，得到：。10、证明题：如果都是凸集，则是凸集。11、证明题：若是定义在非空凸集D上的凸函数，则也是定义在D上的凸函数。12、证明题：若是定义在非空凸集D上的凸函数，则也是凸集D上的凸函数。13、判断对错，如果错误，请给出正确叙述：是D上的严格凸函数的充要条件是：。解答错误。正确的叙述为：是D上的凸函数的充要条件是：。是D上的严格凸函数的充要条件是：。14、判断对错，如果错误，请给出正确叙述：设为非空开凸集，且在D上二阶连续可微，则在D上是严格凸函数的充分必要条件为：的Hesse矩阵在D上是正定的。解答错误。由在非空凸集D上的严格凸函数不能推得Hesse矩阵在D上是正定矩阵。正确的叙述为：设为非空开凸集，且在D上二阶连续可微，则在D上是凸函数的充分必要条件为：的Hesse矩阵在D上是半正定的。设为非空凸集合，在D上二阶连续可微，如果的Hesse矩阵在D上正定，则为D上的严格凸函数。但如果为严格凸函数，则Hesse矩阵在D上是半正定矩阵。15、证明：（Farkas定理）设，则下面两组方程组有且仅有一组有解： （1） （2）16、简答：衡量最优化算法的指标有哪些？答收敛性、收敛速度、收敛准则。第二章习题1、判断对错，如认为错误，请给出正确的叙述：插值法是一种不精确线性搜索方法。解答错误。插值法是一种精确线性搜索方法。2、根据下面进退法的算法描述画出其流程图。进退法（1）选取初始点，初始步长，加倍系数（一般取）；（2）计算，；（3）比较函数值和。若（此时称搜索成功），则令；若（此时称搜索失败），则令，；（4），计算；（5）比较函数值和。若，则（加大搜索步长，）令，重复本步；否则，转（6）。（6）令，输出，停止迭代。3、构造0.618法的两个基本原则是什么？解答 对称原则：和到搜索区间的端点等距，即这两点在区间上处于对称位置：；（2）等比收缩原则：每次迭代留下的区间长度是上次留下的区间长度的倍。即。4、根据0.618法的算法描述画出流程图。0.618法（1）确定初始搜索区间和精度要求。（2）计算，；（3）计算，；（4）比较和。若，则令；如果，转（7）；否则，计算，转（4）；否则（），则令；如果，转（7）；否则，计算，转（4）；（5）计算并比较和，若，则令，停止迭代；否则，令，停止迭代。5、根据下面的三点二次插值法算法描述画出流程图：（三点二次插值法）（1）给出初始搜索区间、要求精度；（2）令，计算；（3）计算和；（4）若，令，终止计算；否则，比较和的大小，若，则转（5），否则，转（6）；（5）若，则，转（3）；否则，转（3）；（6）若，则，转（3）；否则，转（3）；6、判断正误，如果认为错误，请给出正确的叙述：在Goldstein不精确线性搜索准则中，可以取。7、请说明Goldstein不精确线性搜索准则：和Wolfe不精确性搜索准则：并且。中参数和的取值范围。解答 。8、请根据Goldstein不精确线性搜索算法的计算步骤描绘出流程图：（Goldstein不精确线性搜索算法）（1）给定初始搜索区间，及。计算。令，任取。（2）计算。若，则转（3）；否则，转（4）；（3）若，则，输出，停止；否则，；若，则转（4），否则，转（2）；（4），转（2）。9、请根据Wolfe不精确线性搜索算法的计算步骤描绘出流程图：沃尔夫（Wolfe）不精确线性搜索算法（1）给定初始搜索区间，。令，计算，令，取。（2）计算；（3）若，则转（4）；否则由应用二点二次插值法（I）计算出，令，转（2）；（4）计算。若，则取，停止；否则由应用二点二次插值法（II）计算出，令，转（2）。（10）下列算法描述是否正确，是否存在缺陷：（0.618法）（1）确定初始搜索区间和精度要求。（2）计算，；（3）计算，；（4）比较和。（5）若，则令；如果，转（7）；否则，转（3）；（6）否则（），则令；如果，转（7）；否则，转（2）；（7）计算并比较和，若，则令，停止迭代；否则，令，停止迭代。11、下列算法描述是否正确，是否存在缺陷：（Goldstein不精确线性搜索算法）（1）给定初始搜索区间，及。计算。令，任取。（2）计算。 若，则转（3）； 否则，转（4）；（3）若，则，输出，停止； 否则，转（2）；（4），转（2）。12、证明：设函数在闭区间上二次连续可微，且，存在常数，有。若在的唯一极小点，则。习题（第三章）1、设，求在以下各点，处的最速下降方向。解 ，所以，。2、证明题：设。其中A为对称正定矩阵，又设可以表示为：，其中p是A对应于特征值的特征向量。证明：（I）； （2）如果从x出发，沿最速下降法方向作精确的线性搜索，则一步达到最小点。3、判断下列论述是否正确，如认为错误，请给出正确的论述。当目标函数是二次函数时，最速下降法的收敛速度由对应于某个等值线的椭球的最短轴与最长轴之比决定。这个比越大，最速下降法越慢。解答错误。当目标函数是二次函数时，最速下降法的收敛速度由对应于某个等值线的椭球的最长轴与最短轴之比决定。这个比越大，最速下降法越慢。4、举例说明当Hesse矩阵不是正定矩阵时，牛顿法迭代不能继续进行的缺点。解 取，则，显然，是可逆矩阵，但不正定。的逆矩阵为，于是，沿方向进行线性搜索，其极小点为，因此，即迭代不能继续进行下去。5、请说明带保护措施的阻尼牛顿法如何选择下降方向。解答。6、判断下列论述是否正确，如认为错误，请给出正确的论述。在使用牛顿法时，只要找到的一个负曲率方向，便可得到一个下降方向，迭代就可继续进行下去。解答 当为正定矩阵时，找不到负曲率方向。在使用牛顿法时，当为不定矩阵时，只要找到的一个负曲率方向，便得到一个下降方向，迭代就可继续进行下去。7、证明：向量和关于矩阵共轭。8、证明：设A为n阶对称正定矩阵，则关于A共轭的非零向量是线性无关的。9、证明：设向量线性无关，则由这组向量可以构造m个关于A共轭的向量。10、关于矩阵与分别求出一组共轭方向。解 。令，。令，。11、设A为n阶实对称正定矩阵，证明：A的n个互相正交的特征向量关于A共轭。证明。12、根据给出的算法描述画出流程图。（求解二次函数的共轭梯度法）（1）给定任意初始点及精度；（2）计算。若，令，转步（7）；否则，转步（3）；（3）精确线性搜索，得到。（4）令；（5）计算。若，令，转步（7）；否则，转步（6）；（6）计算，转（3）；（7）输出，结束。13、用共轭梯度法求解，取初始点为。解易知，。第一次迭代：。精确线性搜索得到步长。从而。第二次迭代：。精确线性搜索得到步长。从而。易见，从而14、用共轭梯度法求解：，取初始点为。解易知，。所以，。第一次迭代，。线性搜索得到步长，从而。第二次迭代：，。，从而。15、设将共轭梯度法用于三个变量的函数，第一次迭代的搜索方向为，沿作精确线性搜索，得到点，又设，那么按共轭梯度法的规定，从出发的搜索方向是什么？解因为，所以设，则有，得到，即，又，所以，。16、判断下列论断是否正确，如不正确，请指出原因：当目标函数为非正定二次函数时，则对于采用精确线性搜索的共轭梯度法，关系式不成立。17、判断下列论断是否正确，如不正确，请指出原因：当目标函数为非正定二次函数时，则对于采用精确线性搜索的共轭梯度法，关系式不成立。18、证明题：如果在Fletcher-Reeves算法中，步长由不精确线性搜索的沃尔夫准则，其中，证明：对所有使得的k，成立不等式。19、比较下列算法的优劣。指出其中的不同及优劣。算法（1）（采用精确线性搜索的n步重新开始的PRP共轭梯度法）（1）给出初始点及精度，令。（2）如果，则；否则，计算，令；（3）精确线性搜索求得；（4）令。（5）若，则取，停止迭代；否则，若，则，转（2）；否则，转（2）。算法（2）：（采用精确线性搜索的n步重新开始的PRP共轭梯度法）（1）给出初始点及精度，令。（2）计算。若，输出，停止迭代；否则，转步（3）；（3）如果，则；否则，计算，令；（4）精确线性搜索求得；（5）令。若，则。转（2）。解答算法1没有对初始的梯度进行判断。20、比较下列算法的优劣。指出其中的不同及优劣。算法1（比勒（Beale）三次重新开始共轭梯度法）（1）给定初始点及精度，令，计算。若，则取，停止迭代；否则令；（2）采用精确线性搜索求步长；（3）令；（4）计算。若，则取，停止迭代；否则转（5）（5）检验下列条件是否成立：，。若两个条件均不成立，则转（7）；否则，转（6）。（6）。（7）令，其中，。（8）若，则转（9）；否则，转（2）。（9）检验不等式是否成立；若成立，则转（2），否则转（6）。算法2（比勒（Beale）三次重新开始共轭梯度法）（1）给定初始点及精度，迭代次数n。（2）计算，若，则取，停止迭代；否则转（3）；（3）令；（4）采用精确线性搜索求步长；（5）令；（6）计算。若，则取，停止迭代；否则转（7）；（7）检验条件是否成立，若成立，转（9），若不成立，转（8）；（8）检验条件是否成立。若成立，转（9），否则转（11）；（9）令；（10）计算，令，转（13）；（11）检验条件是否成立，若不成立，转（10）；否则，转（12）。（12）计算，令。（13）检验条件是否成立；若成立，转（4），若不成立，转（3）。解答算法1出现死循环。21、画出上面四个算法的流程图。22、简述拟牛顿方法满足的拟牛顿条件（要求两个）。解答或。23、试推导拟牛顿法的对称秩1校正公式：，其中，。24、证明对称秩1校正公式具有遗传性质，其中，。25、试用拟牛顿法（DFP方法：）求解无约束优化问题，初始点为，精度为。解目标函数的梯度为，取初始对称正定矩阵为。第一次迭代：，显然，所以计算搜索方向：，从出发进行直线搜索，得到步长为，从而。第二次迭代：，显然，计算，则所以搜索方向，从出发进行直线搜索，得到步长为，从而。这时，所以，停止计算，取。五、程序判断题：（信赖域方法）（1）给定初始点，初始步长，阈值，放大系数，令。（2）计算，如果，则，停止；否则，形成矩阵；（3）求解子问题（*），求出；（4）计算和的值。如果，那么；否则，那么；（5）如果，那么；否则，转（2）。用信赖域方法求解，其中。解第一次迭代：，。，。解子问题，即，计算，。由算法第（4）步，取。有算法第（5）步，得到。第一次迭代结束。第二次迭代：，。故。习题（第五章）1、已知，列出求解这个方程组的非线性最小二乘问题的数学模型。解；2、设定义如下，其中。写出求解该问题的Gauss-Newton法迭代公式的具体形式：解因为 ，所以3、对于非线性最小二乘问题，我们利用拟牛顿校正公式使用一个对称矩阵来割线近似迭代公式中的二阶信息项，请问应该满足什么样的拟牛顿条件？（请至少说出两种）。解 （1）由于，故我们用去近似。这里是的拟牛顿近似，满足，于是（2）如果令，则有，这也是满足的拟牛顿条件。习题（第六章）1、请说明求解复杂优化算法的直接法的基本特征。解答 第一，对目标函数和约束函数不必附加可解析性条件，对于目标函数而言，甚至不要求具有显式表达式，只需要在所计算的点处提供函数值；第二，在通常情况下，这些算法能够求解全局最优解。2、请说明模拟退火算法的定义以及两种典型的降温方式。解答利用优化问题求解与物理系统退火过程的相似性，使用Metropolis算法，适当控制温度的下降过程，实现模拟退火，从而达到求解全局优化问题的随机性方法。最典型的降温方式有经典退火方式和快速退火方式两种。3、请说明遗传算法的基本思想。遗传算法就是通过对生物基因的复制、交换和变异这三种模拟来实现其优化过程的。4、请解释遗传算法中的染色体和基因。解 遗传算法将优化问题的一组可行解进行编码，表示为一组二进制的字符串。一个解的编码称为一个染色体，组合编码的元素称为基因。第七章 最优化问题在我们未来的应用我们面临的最优化问题是：如何获取最大的“幸福”？也就是：如何以最少的时间和精力、最少的代价来使得自己的生活得到改善限制条件：（1）社会条件：不公平的（人人生下来就不平等）、残酷竞争的（就业压力、能否找到合适的工作）、有法律约束的（你只能去适应社会）。（2）自身条件：自身的性格（有内向的、有外向的）；（3）价值观：对人生的目标，也就是对幸福的概念理解不同（有人追求知识、有人追求财富、有人追求权利）。我们应该认识到：（1）虽然社会不公，但是父母把你带到了这个世界，已经是给你的最大财富，你应该抱有一颗感恩的心，对亲人、对朋友负责。另外，你应该有一颗快乐的心，勇敢地面对生活的挑战。（2）人生就像是一场马拉松，你已经进入了硕士研究生，就好比你已经骑上了自行车参加比赛，但是你是用