最优化复习考点.doc

第二章（对偶问题与原问题解的关系，主要思想） 1对偶问题的提出：这里的对偶指对同一问题从不同的立场观察的两种相同的表述。从经济意义来看，原问题只在有限的资源约束条件下的最优生产决策，而对偶问题则表示如果不生产，而是考虑将资源出租应该如何定价的问题。 2对称性：对偶问题的对偶问题是原问题 3弱对偶性：若是原问题的可行解,是对偶问题的可行解。则存在。 证明：原问题 对偶问题 可以得到 4无界性：若原问题为无界解，则其对偶问题无可行解。 5可行解是最优解：设是原问题的可行解，是对偶问题的可行解，当时，是最优解。 证明：由弱对偶性可知：,得是最优解 同理可得是最优解 6对偶定理：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。 证明：若是最优解，则基矩阵B对应的检验数为 令，得 若是对偶问题的可行解，它使 7互补松弛性：若分别是原问题和对偶问题的可行解。那么和,当且仅当为最优解。 第四章（线性目标规划——模型、计算） 第十六章（多目标决策） —— 一般情况处理思想、有约束极值问题如何化为无约束问题、等式约束、不等式约束 1一般处理情况 化多为少法：将多目标问题化成只有一个或二个目标的问题，然后用简单的决策方法求解，最常用的是线性加权和法。分层序列法：将所有目标按其重要性程度依次排序，先求出第一个最重要的目标的最优解，然后在保证前一目标最优解的前提下依次求下一目标的最优解，一直求到最后一个目标为止。直接求非劣解法：先求出一组非劣解，然后按事先确定好的评价标准从中找出一个满意的解。 定义辅助函数： （8.1） 这样就能把等式约束极值问题转化为无约束问题 （8.2） 显然，该问题的最优解必须使得接近0，否则，（8.1）的第二项将是很大的正数，现行点必不是极小点。因此可见，求解问题（8.2）能够得到（NLP1）问题的近似解 3不等式约束的一般形式： 不等式约束问题的辅助函数与等式约束的辅助函数情形不同，但构造辅助函数的基本思想是一致的，这就是:在可行点辅助函数等于原来的目标函数值，在不可行点，辅助函数值等于原来的目标函数值加上一个很大的正数。根据这个原则有： 定义辅助函数： 参数是很大的正数。 当为可行点时， 当为不可行点时， 这样就能把（NLP2）转化为无约束问题 (8.4) 显然，问题（8.4）的最优解必须使得大于等于零，否则，（8.3）的第二项将是很大的正数，现行点必不是极小点。因此可见，求解问题（8.4）能够得到问题（NLP2）的近似解 第六章（无约束问题） 1非线性问题极值有什么特点 1)局部极值与全局极值(定义)： 设为定义在维欧 式空间En的某一区域上的 元实函数，其中。对于，如果存在某个，使所有与的距离小于的均满足不等式,则称为在R上的局部极小点，为局部极小值。 若点，而对于所有都有，则称为在R上的全局极小点，为全局极小值。 2 )极值点存在条件： 必要条件：是维欧式空间上的某一开集，在上有一阶连续偏导数，在点取得局部极值，则必有，即在处的梯度为零。 充分条件：是维欧式空间上的某一开集，在R上具有二阶连续偏导数，，若，且对任何非零向量有：,则为的严格局部极小点。即海塞矩阵在处正定。 2怎么判断函数的凹凸性 1）定义判断：是维欧式空间上的某一凸集上的函数，若对任何实数 以及中的任意两点和，恒有 则称是定义在上的凸函数。（类似可得严格凸函数的定义） 2）性质判断： 性质一：设是定义在上的凸函数，对于任意实数，函数也是定义在上的凸函数。 性质二：设是定义在上的两个凸函数，则其和仍为定义在上的凸函数。 3怎么证明函数的凹凸性 1）定义证明： 2）定理证明： 定理一：设是维欧式空间上的开凸集，在上有一阶连续偏导数，则为上的凸函数的充要条件是，对中的任意两个不同的点和，恒有： 定理二：设是维欧式空间上的开凸集，在上有二阶连续偏导数，则为上的凸函数的充要条件是，的海塞矩阵在上处处半正定。 4凸函数极值特点 若为定义在凸集上的凸函数，则它的任一极小点就是它在上的最小点（全局极小点），而且它的极小点形成凸集。 设是定义在凸集上的可微凸函数，若存在点，使得对所有的 有 =0,则是在上的最小点（全局极小点） 5凸规划的定义、性质 1)定义：考虑非线性规划 假定其中为凸函数，为凹函数，则这样的非线性规划称为凸规划。 2)性质：凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优解的集合形成一个凸集。当凸规划的目标函数为严格凸函数时，其最优解必定唯一（当最优解存在时），凸规划的最优点存在的充分必要条件是库恩-塔克条件。 6下降迭代算法思想及其常用的算法终止条件 1)基本思想：为了求函数的最优解，首先给定一个初