凸二次规划的有效集方法

辽宁师范大学硕士学位论文非光滑非凸约束问题的一种迫近束方法姓名：***申请学位级别：硕士专业：数学、运筹学与控制论指导教师：***2012-04辽宁师范大学硕士学位论文摘要对于非光滑最优化问题（ＮＳＯ），算法主要有次梯度法、切平面法、解析中心割平面法（ＡＣＣＰ）和束方法。

束方法和ＡＣＣＰ方法是割平面方法的稳定形式。

束方法被公认为是目前解决非光滑优化问题的最有效的方法之一。

全局Ｉ段敛的约束最优化算法传统上应用参数罚函数。

近些年，滤子算法被用来作为替换罚函数的方法，用滤子算法替换的一部分原因在于它能够避免先确定一个合适的罚函数参数，而确定罚函数参数这项工作通常是非常复杂的。

本文中，我们表明，在非光滑凸优化的参数化罚函数的使用中可以避免不使用比较复杂的滤子方法。

我们提出一个方法，这似乎是更直接，更容易实现的，在某种意义上说，它在精神和结构上都更接近于比较完善的无约束束方法。

本文主要分为三部分，第一部分是预备知识，在这一部分中先简单介绍与束方法有关的知识，包括凸规划的次梯度法和割平面方法，为介绍束方法作铺垫。

接下来概述了一般的束方法，为接下来几章的研究奠定基础。

第二部分首先概述了解决非光滑无约束优化问题的一种迫近束方法，接着又提出了解决非光滑凸约束优化问题的一种不可行束方法，然后将凸约束优化问题等价的转换为对改进函数的无约束优化问题的研究，随着新的下降迭代点的产生，我们需要重新定义改进函数。

迫近束方法保证了就算迭代过程中产生的下降迭代点以及初始点的选取都是不可行的，而由迭代所产生的序列仍会收敛到原问题的最优解。

最后一部分创新性的通过替换线性化误差将非光滑凸约束的不可行迫近束方法推广到非凸约束的情况，给出非光滑非凸函数迫近束方法的算法，并且证明了算法的收敛性。

关键词非光滑最优化；非凸函数；次梯度局部测度；束方法非光滑非凸约束优化问题的一种迫近束：疗法ＡｐｒｏｘｉｍａｌｂｕｎｄｌｅｍｅｔｈｏｄｆｏｒｎｏｎｓｍｏｏｔｈａｎｄｎｏｎｃｏｎｖｅｘｃｏｎｓｔｒａｉｎｅｄｏｐｔｉｍｉｚａｔｉｏｎＡｂｓｔｒａｃｔＮｏｎｓｍｏｏｔｈｏｐｔｉｍｉｚａｔｉｏｎ（ＮＳＯ）ｐｒｏｂｌｅｍｓａｒｅｉｎｇｅｎｅｚ’ａｌｄｉｆｆｉｃｕｌｔｔｏｓｏｌｖｅ，ｅｖｅｎｗｈｅｎｔｈｅｙａｒｅｕｎｃｏｎｓｔｒａｉｎｅｄ．ＡｍｏｎｇａｌｇｏｒｉｔｈｍｓｆｏｒＮＳＯ，ｗｅｍｅｎｔｉｏｎｔｈｅｓｕｂｇｒａｄｉｅｎｔ，ｃｕｔｔｉｎｇ—ｐｌａｎｅｓ，ａｎａｌｙｔｉｃｃｅｎｔｅｒｃｕｔｔｉｎｇ—ｐｌａｎｅｓ（ＡＣＣＰ）ａｎｄｂｕｎｄｌｅｍｅｔｈｏｄｓ．ＢｕｎｄｌｅａｎｄＡＣＣＰｍｅｔｈｏｄｓａｒｅｓｔａｂｉｌｉｚｅｄｖｅｒｓｉｏｎｓｏｆｔｈｅｃｕｒｔｉｎｇ—ｐｌａｎｅｓｍｅｔｈｏｄ，ａｎｄｔｈｅｙａｒｅｃｕｒｒｅｎｔｌｙｒｅｃｏｇｎｉｚｅｄａｓｔｈｅｍｏｓｔｒｅｌｉａｂｌｅＮＳＯａｌｇｏｒｉｔｈｍｓ．ＴｈｅＢｕｎｄｌｅｍｅｔｈｏｄｓａｒｅａｔｔｈｅｍｏｍｅｎｔｃｏｎｓｉｄｅｒｅｄａＳｏｎｅｏｆｔｈｅｍｏｓｔｅｆｆｉｃｉｅｎｔｍｅｔｈｏｄｓｆｏｒｓｏｌｖｉｎｇｎｏｎｓｍｏｏｔｈｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｇｌｏｂａｌｃｏｎｖｅｒｇｅｎｃｅｉｎｃｏｎｓｔｒａｉｎｅｄｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｈａｓｔｒａｄｉｔｉｏｎａｌｌｙｂｅｅｎｅｎｆｏｒｃｅｄｂｙｔｈｅｕｓｅｏｆｐａｒａｍｅｔｅｒｉｚｅｄｐｅｎａｌｔｙｆｕｎｃｔｉｏｎｓ．Ｒｅｃｅｎｔｌｙ，ｔｈｅｆｉ］ｔｅｒｓｔｒａｔｅｇｙｈａｓｂｅｅｎｉｎｔｒｏｄｕｃｅｄａｓａｎａｌｔｅｒｎａｔｉｖｅ．Ａｔ１ｅａｓｔｐａｒｔｏｆｔｈｅｍｅｔｉｗａｔｉｏｎｆｏｒｆｉｌｔｅｒｍｅｔｈｏｄｓｃｏｎｓｉｓｔｓｉｎａｖｏｉｄｉｎｇｔｈｅｎｅｅｄｆｏｒｅｓｔｉｍａｔｉｎｇａｓｕｉｔａｂｌｅｐｅｎａｌｔｙｐａｒａｍｅｔｅｒ，ｗｈｉｃｈｉＳｏｆｔｅｎａｄｅ１ｉｃａｔｅｔａｓｋ．ＩｎｔｈｉＳｐａｐｅｒ，ｗｅｄｅｍｏｎｓｔｒａｔｅｔｈａｔｔｈｅｕｓｅｏｆａｐａｒａｍｅｔｒｉｚｅｄｐｅｎａｌｔｙｆｕｎｃｔｉｏｎｉｎｎｏｎｓｍｏｏｔｈｃｏｎｖｅｘｏｐｔｉｍｉｚａｔｉｏｎｃａｎｂｅａｖｏｉｄｅｄｗｉｔｈｏｕｔｕｓｉｎｇｔｈｅｒｅｌａｔｉｖｅｌｙｃｏｍｐｌｅｘｆｉｉｔｅｒｍｅｔｈｏｄｓ．Ｗｅｐｒｏｐｏｓｅａｎａｐｐｒｏａｃｈｗｈｉｃｈａｎｄｅａｓｉｅｒｔｏｉｍｐｌｅｍｅｎｔ，ｉｎｔｈｅｓｅｎｓｅｔｈａｔｉｔｉＳｃｌｏｓｅｒａｐｐｅａｒｓｔｏｂｅｍｏｒｅｄｉｒｅｃｔｉｎｓｐｉｒｉｔａｎｄｓｔｒｕｃｔｕｒｅｔｏｂｅｔｈｅｗｅ］１一ｄｅｖｅｌｏｐｅｄｕｎｃｏｎｓｔｒａｉｎｅｄｂｕｎｄｌｅｍｅｔｈｏｄｓ．ＴｈｉｓａｒｔｉｃｌｅｉＳｄｉｖｉｄｅｄｉｎｔｏｔｈｒｅｅｐａｒｔｓ．Ｔｈｅｆｉｒｓｔｐａｒｔａｒｅｔｈｅｐｒｉｏｒｋｎｏｗｌｅｄｇｅ，ｉｎｔｈｉＳｓｅｃｔｉｏｎ，ｍａｉｎｌｙｔｏｂｒｉｅｆｔｈｅｒｅｌｅｖａｎｔｋｎｏｗｌｅｄｇｅｏｎｔｈｅｂｕｎｄｌｅｍｅｔｈｏｄ，ｉｎｃｌｕｄｅｔｈｅｓｕｇｒａｄｉｅｎｔｍｅｔｈｏｄａｎｄｃｕｔｔｉｎｇｐｌａｎｅｓｍｅｔｈｏｄ．Ｐａｙｅｔｈｅｗａｙｆｏｒｔｈｅｉｎｔｒｏｄｕｃｔｉｏｎｏｆｔｈｅｂｕｎｄｌｅｍｅｔｈｏｄ．Ｔｈｅｓｅｃｏｎｄｐａｒ’ｔｂｒｉｅｆａｐｒｏｘｉｍａｌｂｕｎｄｌｅｍｅｔｈｏｄｆｏｒｎｏｎｓｍｏｏｔｈｃｏｎｖｅｘｕｎｃｏｎｓｔｒａｉｎｅｄｏｐｔｉｍｉｚａｔｉｏｎ．ＡｎｉｎｆｅａｓｉｂｌｅｂｕｎｄｌｅｍｅｔｈｏｄｆｏｒｓｏｌｖｉｎｇｎｏｎｓｍｏｏｔｈｃｏｎｖｅｘｃｏｎｓｔｒａｉｎｅｄｏｐｔｉｒａｉｚａｔｉｏｎｐｒｏｂｌｅｍｉＳａｌＳＯｉｎｔｏｔｈｅｕｎｃｏｎｓｔｒａｉｎｅｄｐｒｅｓｅｎｔｅｄ．Ｉｎｔｈｅｆｏｌｌｏｗｉｎｇ，ｔｈｅｐｒｏｂｌｅｍｃｈａｎｇｅｓｍｉｎｉｍｉｚａｔｉｏｎｏｆｔｈｅｉｍｐｒｏｖｅｄｆｕｎｃｔｉｏｎ．ＢｕｔｗｉｔｈｔｈｅｇｅｎｅｒａｔｉｏｎｏｆｎｅｗｓｅｒｉＯＵＳｔｈｅｓｔｅｐｓ，ｔｈｅｉｍｐｒｏｖｅｄｆｕｎｃｔｉｏｎｍｕｓｔｂｅｄｅｆｉｎｅｄａｇａｉ：ｎ．Ｉｎｔｈｉｓｍｅｔｈｏｄ，ｅｖｅｎｓｅｒｉｏｕｓｐｏｉｎｔｓｇｅｎｅｒａｔｅｄｉｎｉｔｅｒａｔｉｏｎｐｒｏｃｅｓｓａｎｄｔｈｅｆｉｒｓｔｏｒｉｇｉｎａｌｐｏｉｎｔａｒｅｌａｓｔｐａｒｔｉｎｆｅａｓｉｂｌｅ，ｔｈｅｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍａｌｓｏ１’Ｓｅｎｓｕｒｅｄ．Ｔｈｅｇｅｎｅｒａｌｉｚｅｔｈｅｐｒｏｘｉｍａｌｂｕｎｄｌｅｍｅｔｈｏｄｏｆｎｏｎｅｏｎｖｅｘｃｏｎｓｔｒａｉｎｅｄｏｐｔｉｍｌｚａｔｌｏｎ，～一．—————————塑堕奎堂堡：主堂垡笙塞～ｋｅＹｗ。

第五章 非线性规划：理论和算法5.5 约束优化我们现在继续讨论更一般的有约束的线性优化问题。

特别的,我们考虑一个具有非线性目标函数和（或者）非线性约束的优化问题。

我们可以将这种问题表示为下面的一般形式：I∈≥∈=i x g i x g x f i i x ,0)(,0)()(min ε (5.10) 在本节的末尾，我们假设f 和i g ，i ε∈⋃I 全部是连续可微的。

拉格朗日函数是研究有约束的优化问题的一个重要工具。

为了定义这个函数，我们结合每个约束的乘子i λ——称作拉格朗日乘子。

对于问题（5.10）拉格朗日函数如下定义：∑I⋃∈-=ελλi iix g x f x L )()(:),( （5.11） 本质上，我们考虑的是目标函数违反了可行约束时的惩罚函数。

选择合适的i λ，最小化无约束函数(),L x λ等价于求解约束问题（5.10）。

这就是我们对拉格朗日函数感兴趣的最根本的原因。

与这个问题相关的最重要问题之一是求解最优问题的充要条件。

总之，这些条件称为最优性条件，也是本节的目的。

在给出问题（5.10）最优性条件之前，我们先讨论一个叫做正则性的条件，由下面的定义给出：定义5.1：设向量x 满足ε∈=i x g i ,0)(和I ∈≥i x g i ,0)(。

设J ⊂I 是使得0)(≥x g i 等号成立的指标集。

x 是问题（5.10）约束条件的正则点，如果梯度向量)(x g i ∇（i J ∈⊂I ）相互线性无关。

在上述定义中与J ε对应的约束，即满足0)(=x g i 的约束称为在x 点处的有效约束。

我们讨论第一章提到的两个优化的概念，局部和全局。

回顾（5.10）的全局最优解向量*x ，它是可行的而且满足)()(*x f x f ≤对于所有的x 都成立。

相比之下，局部最优解*x 是可行的而且满足)()(*x f x f ≤对于{}ε≤-*:x x x （0>ε）成立。

因此局部解一定是它邻域的可行点中最优的。

《最优化方法》复习题一、 简述题1、怎样判断一个函数是否为凸函数.(例如:判断函数f(x) =昇+ 2兀內+ 2近一 10州+ 5兀2是否为凸函数)2、 写出几种迭代的收敛条件.3、 熟练掌握利用单纯形表求解线性规划问题的方法(包括大M 法及二阶段法).见书本61页(利用单纯形表求解)；69页例题(利用大M 法求解、二阶段法求解)； 4、 简述牛顿法和拟牛顿法的优缺点.简述共辘梯度法的基木思想.写岀Goldstein> Wolfe 非精确一维线性搜索的公式。

5、叙述常用优化算法的迭代公式.心=务+吕—％),化-知1仏二务+召一色)(3) Newton —维搜索法的迭代公式：x k+i = x k -G~'g k ・ (4) 推导最速下降法用于问题min/(x) = —++ c 的迭代公式:耳+1 二无一-VfgS k G k gx k(5) Newton 法的迭代公式：x k+] = x k -[V 2/(^)]_l V/*(x A )・ (6) 共轨方向法用于问题min/(x)=丄x rQx+b 1x + c 的迭代公式:2忑+1 =J二、计算题双折线法练习题 课本135页 例3.9.1FR 共辘梯度法例题：课本150页 例4.3.5(1) 0.618法的迭代公式:A- =ak +（1-厂）（勺一务）,(2) Fibonacci 法的迭代公式: 伙= 1,2,…,一1）二次规划有效集：课本213页例6.3.2,所有留过的课后习题.三、练习题：1、 设A G R ,iXn是对称矩阵，bwR”，cwR,求/(%) =丄*心+戻兀+ c 在任意点x 处 的梯度和Hesse 矩阵.解 V/*(x) = Ar + /?, V 2/(x) = A ・2、 设0(/) = /(兀 + 力)，其屮/:/?" T R 二阶可导，XG R\de R\te R ,试求0"(/)・解 0(/) = W(x + /d) 丁4,矿⑴=dF f(x~Hd)d .3、 证明：凸规划min f(x)的任意局部最优解必是全局最优解.xeS证明 用反证法.设住S 为凸规划问题min /(x)的局部最优解，即存在丘的某xeS个5邻域N s (x),使f(x)<f(x)yxeN 6(x)C\S ・若元不是全局最优解，则存在花S,使/(i) < /(x)・由于/(兀)为S 上的凸函数，因此VA G (0,1),有/(Ax + (1-2)x) < 2/(x) + (1-2)/(x) < f(x)・当2充分接近1时，可使2元+(1 — 2)农 皿(元)「IS,于是/(x)</(2x + (l-/i)x), 矛盾.从而元是全局最优解.min f(x) = 2x t -x 2 +x 3; s.t. 3兀］+ x 2 + x 3 < 60,x l - 2X 2 + 2X 3 <10,%! + x 2 - x 3 < 20, (1)用单纯形法求解该线性规划问题;(2)写出线性规划的对偶问题;解 (1)引进变量兀，兀5,兀6,将给定的线性规划问题化为标准形式:min /(%) = 2x t -x 2 +x 3; s.t. 3x ( + 兀 + 耳 + % = 60,%j - 2X 2 + 2X 3 + 冯=10,所给问题的最优解为x = （0,20,0）r ,最优值为/ = -20・4、已知线性规划:（2）所给问题的对偶问题为：max g（y） = -60^-10^ - 20%；皿_3”_旳_儿52,< _必+2旳_儿S_l，一开_2旳 + %<1，儿力*3»°・5、用0.618法求解min 0（f） = （f-3尸，要求缩短后的区间长度不超过0.2,初始区间取[0,10]・解第一次迭代：取y [0,10],£ = 0.2.确定最初试探点人，“分别为入=^+0.382（^-^,） = 3.82, M =坷+0.618（勺一马）=6・18 .求目标函数值：°（人）=（3.82— 3）2 =0.67, °（“）= （6.18 — 3）2 =10.11.比较目标函数值：0（人）< 0（"）・比较 //| —6f| = 6.18 — 0 > 0.2 = E ・第二次迭代：a2 = a x = 0,Z?2= “| = 6.18,/ =人=3.82,。

一维搜索:1精确一维搜索精确一维搜索可以分为三类：区间收缩法、函数逼近法（插值法）、以及求根法。

区间收缩法：用某种分割技术缩小最优解所在的区间(称为搜索区间)。

包括：黄金分割法、成功失败法、斐波那契法、对分搜索法以及三点等间隔搜索法等。

优化算法通常具有局部性质，通常的迭代需要在单峰区间进行操作以保证算法收敛。

确定初始区间的方法：进退法①已知搜索起点和初始步长；②然后从起点开始以初始步长向前试探，如果函数值变大，则改变步长方向；③如果函数值下降，则维持原来的试探方向，并将步长加倍。

1.1黄金分割法：黄金分割法是一种区间收缩方法(或分割方法)，其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断缩短以逼近极小值点。

具有对称性以及保持缩减比原则。

优点：不要求函数可微，除过第一次外，每次迭代只需计算一个函数值，计算量小，程序简单；缺点：收敛速度慢；函数逼近法（插值法）：用比较简单函数的极小值点近似代替原函数的极小值点。

从几何上看是用比较简单的曲线近似代替原的曲线，用简单曲线的极小值点代替原曲线的极小点。

1.2牛顿法：将目标函数二阶泰勒展开，略去高阶项后近似的替代目标函数，然后用二次函数的极小点作为目标函数的近似极小点。

牛顿法的优点是收敛速度快，缺点是需要计算二阶导数，要求初始点选的好，否则可能不收敛。

1.2抛物线法：抛物线法的基本思想就是用二次函数抛物线来近似的代替目标函数，并以它的极小点作为目标函数的近似极小点。

在一定条件下，抛物线法是超线性收敛的。

1.3三次插值法：三次插值法是用两点处的函数值和导数值来构造差值多项式，以该曲线的极小点来逼近目标函数的极小点。

一般来说，三次插值法比抛物线法的收敛速度要快。

精确一维搜索的方法选择：1如目标函数能求二阶导数：用Newton法，收敛快。

2如目标函数能求一阶导数：1如果导数容易求出，考虑用三次插值法，收敛较快；2对分法、收敛速度慢，但可靠；3只需计算函数值的方法：1二次插值法, 收敛快，但对函数单峰依赖较强；2黄金分割法收敛速度较慢，但实用性强，可靠；4减少总体计算时间：非精确一维搜索方法更加有效。

第四章 非线性规划教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降法，约束最优化问题的最优性条件及简约梯度法。

教学难点：约束最优化问题的最优性条件。

教学课时：24学时主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题。

第一节 基本概念教学重点：非线性规划问题的引入，非线性方法概述。

教学难点：无。

教学课时：2学时主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非线性规划方法的求解难题。

1、非线性规划问题举例例1 曲线最优拟合问题已知某物体的温度ϕ 与时间t 之间有如下形式的经验函数关系：312c t c c t e φ=++ （*）其中1c ，2c ，3c 是待定参数。

现通过测试获得n 组ϕ与t 之间的实验数据),(i i t ϕ，i=1，2，…,n 。

试确定参数1c ，2c ，3c ，使理论曲线(*)尽可能地与n 个测试点),(i i t ϕ拟合。

∑=++-n 1i 221)]([ min 3i t c i i e t c c ϕ例 2 构件容积问题通过分析我们可以得到如下的规划模型：⎪⎪⎩⎪⎪⎨⎧≥≥=++++=0,0 2 ..)3/1( max 212121222211221x x S x x x x a x x t s x x a V ππππ基本概念设n T n R x x x ∈=),...,(1，R R q j x h p i x g x f n j i :,...,1),(;,...,1),();(==,如下的数学模型称为数学规划(Mathematical Programming, MP)：⎪⎩⎪⎨⎧===≤q j x h p i x g t s x f j i ,...,1,0)( ,...,1,0)( ..)( min约束集或可行域X x ∈∀ MP 的可行解或可行点MP 中目标函数和约束函数中至少有一个不是x 的线性函数，称(MP)为非线性规划令 T p x g x g x g ))(),...,(()(1=T p x h x h x h ))(),...,(()(1=，其中，q n p n R R h R R g :,:，那么(MP )可简记为⎪⎩⎪⎨⎧≤≤ 0)( 0 ..)( min x h g(x)t s x f 或者 )(min x f X x ∈ 当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。

天津大学《最优化方法》复习题(含答案)天津大学《最优化方法》复习题（含答案）第一章 概述(包括凸规划)一、 判断与填空题1 )].([arg )(arg m in m axx f x f nnRx Rx -=∈∈ √2 {}{}.:)(min :)(max nnR D x x f R D x x f ⊆∈-=⊆∈ ⨯3 设.:R R D f n →⊆ 若nR x∈*，对于一切nR x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题)(minx f Dx ∈的全局最优解. ⨯4 设.:R RD f n→⊆ 若Dx∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(minx f Dx ∈的严格局部最优解. ⨯5 给定一个最优化问题，那么它的最优值是一个定值. √6 非空集合nR D ⊆为凸集当且仅当D 中任意两点连线段上任一点属于D . √7 非空集合nR D ⊆为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √8 任意两个凸集的并集为凸集. ⨯ 9 函数RR D f n→⊆:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √10 设RRD f n→⊆:为凸集D 上的可微凸函数，Dx ∈*.则对D x ∈∀，有).()()()(***-∇≤-x x x f x f x f T⨯ 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n是凸集。

√12 设{}kx 为由求解)(minx f Dx ∈的算法A 产生的迭代序列，假设算法A 为下降算法，则对{},2,1,0∈∀k ，恒有)()(1kk x f x f ≤+ .13 算法迭代时的终止准则（写出三种）：_____________________________________。

14 凸规划的全体极小点组成的集合是凸集。

1 (LP)的解集是凸的. √2 对于标准型的(LP)，设{}k x 由单纯形算法产生，则对{} ,2,1,0∈k ，有.1+>k T k T x c x c ×3 若*x 为(LP)的最优解，*y 为(DP)的可行解，则.**y b x c T T ≥ √4 设0x 是线性规划(LP)对应的基),,(1m P P B =的基可行解，与基变量m x x ,,1 对应的规范式中，若存在0<k σ，则线性规划(LP)没有最优解。