lecture2-6 nonlinear最优性条件-凸函数.ppt

凸函数的充要条件 定理（一阶充要条件） 凸性 证 明 几何意义 f(x)是凸函数当且仅当任意点处的切线增 量不超过函数的增量。 x(1) x(2) f(x(2))-f(x(1)) f(x(1)) f(x(2)) 证明： 例：判断下列函数是否为凸函数. 凸规划 凸规划：求凸函数在凸集上的极小点。 性质：凸规划的局部极小点就是整体极小点， 且极小点的集合为凸集。 KKT点应满足方程组 linearized feasible direction set Constraint qualifications are conditions under which the linearized feasible set F(x) is similar to the tangent cone T_(x). In fact, most constraint qualifications ensure that these two sets are identical. the critical cone 证明： 假设 不是问题的严格局部极小点, 则存在序列 , 使得 , 并且 , 即 记 显然, 根据有界序列的性质可知, 存在一个收敛子列 不妨假设 令 于是有 . 因为 利用KKT条件, 得到 因此, 由Taylor展开公式, 有 Lagrange函数为 Lagrange函数不存在极小点。 例:求下列非线性规划问题的KKT点. 对偶向量形式 Lagrange乘子的意义 对约束的右端项进行扰动 扰动问题 广告费作微小改动，考虑扰动问题 凸规划 凸函数 凸函数：设S是En中的非空凸集， f(x)是定义在S上的实函数，如果对于每一对x1，x2?S及每一个a，0≤a≤1,都有 　　　f(ax1+(1－a)x2)≤a f(x1)+(1－a)f(x2) 则称函数f(x)为S上的凸函数．上式中，若≤变为，则称为严格凸函数。 若-f(x)为S的凸函数，则称f(x)为S上的凹函数． (a) 严格凸 x 凸 x 非凸 x (b) (c) 凸函数性质 (1) 设f1(x)，f2(x)是凸集S上的凸函数，则函数f1(x)+f2(x)在S上也是凸函数。 (2) 设f(x)是凸集S上的凸函数，则对任意的a≥0，函数af(x)是凸的。 推广：设f1(x)，f2(x), …, fk(x)是凸集S上的凸函数，ai≥0,则a1f1(x)+a2f2(x)+ …+ akfk(x)也是凸集S上的凸函数. (3) 设f(x)是凸集S上的凸函数，对每一个实数c，则集合(level set) Sc＝{x | x?S，f(x)?c}是凸集。 (4)设S是En中的非空凸集，f是定义在S上的凸函数， 则f在S上的局部极小点是整体极小点，且极小点 的集合是凸集． 凸函数性质 证明： 凸函数的判别 梯度： Hesse矩阵： 方向导数 方向导数通常用下面的公式计算： 复习概念 定义１：设f(x)为目标函数，S为可行域，x0∈S，若对?x∈S,有f(x)≥f(x0),则x0称为极小化问题minf(x)， x∈S的（全局）最优解． 定义２：设f(x)为目标函数，S为可行域，若存在x0的ε邻域 　　　 使得对?x∈S∩Nε(x0)，有f(x)≥f(x0),则x0称为极小化问题minf(x)， x∈S的局部最优解． 显然，与直线AB相切的点必为最优解。 图中D点即为最优点，此时目标函数值为： f(x*)=2，x1*=x*2=3 A f(x)=4 f(x)=2 x1 x2 6 3 2 0 2 3 6 B C D [例]求解下述非线性规划 min f(x)=(x1－2)2+(x2－2)2 h(x)=x1+x2－6=0 [例]非线性规划为 min f(x)=(x1－2)2+(x2－2)2 h(x)=x1+x2－6≤0 最优解为x1*=x2*=2 ，f(x*)=0，该点落在可行域内部，其边界约束失去作用。 结论:非线性规划的最优解（如果存在）可在其可行域上任一点达到。 求下列约束问题的解： (-1,0)T (3,0)T 约束优化问题的最优性条件 思路： 几何------ 代数 直观------ 抽象 简单------ 复杂 ？？？ Start with some basic concepts/knowledge 定义: 定义: TANGENT CONE AND CONSTRAINT QUAL