一类线性与框式约束凸规划问题的原始-对偶内点算法

《一类线性与框式约束凸规划问题的原始-对偶内点算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２２卷第６期运筹与管理Ｖｏｌ．２２，Ｎｏ．６２０１３年１２月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＤｅｃ．２０１３一类线性与框式约束凸规划问题的原始-对偶内点算法张艺（宁波大学理学院，浙江宁波３１５２１１）摘要：本文对一类具有线性和框式约束的凸规划问题给出了一个原始－对偶内点算法，该算法可在任一原始－对偶可行内点启动，并且全局收敛，当初始点靠近中心路径时，算法成为中心路径跟踪算法。数值实验表明，算法对求解大型的这类问题是有效的。关键词：凸规划；内点算法；原始-对偶；路径跟踪中

2、图分类号：Ｏ２２１．２　　　文章标识码：Ａ文章编号：１００７-３２２１（２０１３）０６-００３９-０６APrimal-dualInteriorPointAlgorithmforaClassofConvexProgrammingProblemwithLinearandBoxConstraintsＺＨＡＮＧＹｉ（FacultyofScience，NingboUniversity，Ningbo３１５２１１，China）Abstract：Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｐｒｅｓｅｎｔａｐｒｉｍａｌ-ｄｕａｌｉｎｔｅｒｉｏｒｐｏ

3、ｉｎｔａｌｇｏｒｉｔｈｍｆｏｒａｃｌａｓｓｏｆｃｏｎｖｅｘｐｒｏｇｒａｍｍｉｎｇｐｒｏｂ-ｌｅｍｗｉｔｈｌｉｎｅａｒａｎｄｂｏｘｃｏｎｓｔｒａｉｎｓ．Ｔｈｅａｌｇｏｒｉｔｈｍｃａｎｂｅｓｔａｒｔｅｄａｔａｎｙｐｒｉｍａｌ-ｄｕａｌｆｅａｓｉｂｌｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｎｄａｄｍｉｔｓｔｈｅｇｌｏｂａｌｃｏｎｖｅｒｇｅｎｃｅ．Ｗｈｅｎｔｈｅｉｎｉｔｉａｌｐｏｉｎｔｉｓｃｌｏｓｅｔｏｔｈｅｃｅｎｔｒａｌｐａｔｈ，ｉｔｂｅｃｏｍｅｓａｃｅｎｔｒａｌｐａｔｈ-ｆｏｌｌｏｗｉｎｇａｌｇｏｒｉｔｈｍ．Ｎｕｍｅｒｉｃａｌｅ

4、ｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｅｆｆｅｃｔｉｖｅｆｏｒｔｈｅｌａｒｇｅｓｃａｌｅｐｒｏｂｌｅｍｓ．Keywords：ｃｏｎｖｅｘｐｒｏｇｒａｍｍｉｎｇ；ｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍ；ｐｒｉｍａｌ-ｄｕａｌ；ｐａｔｈ-ｆｏｌｌｏｗｉｎｇ０　引言［１］自从１９８４年Ｋａｒｍａｒｋａｒ给出线性规划的多项式时间内点算法以来，人们对线性规划的内算法作了［２～５］［６，７］大量的研究，其中许多算法已经推广应用到二次凸规划及其他一些非线性规划问题，路径跟踪算法是其中的一大

5、类算法，在这一类算法的收敛性分析中，都要求初始迭代点在“中心路径”（ＣｅｎｔｒａｌＰａｔｈ）的附近，这给算法的直接使用带来了不便。本文对一类具有线性和框式约束的凸规划问题提出了一个原始-对偶内点算法，该算法可在任一原始-对偶内部可行点启动，并具有全局收敛性，当初始点靠近中心路径时，算法便成为中心路径跟踪算法。在描述问题之前，先给出一些记号，本文记‖·‖，‖·‖１分别为向量（或矩阵）的２－范数和１－范nnTn数，R＋＝｛x｜x＞０，x∈R｝，e＝｛１，１，⋯，１｝∈R，当小写字母表示向量时，对应的大写字母如果没有给出

6、Tn明确的含义，则表示为以该向量元素为对角线元素的对角矩阵，如x＝（x１，x２，⋯，xn）∈R，则X＝diag（x１，x２，⋯，xn），又如E是n阶单位矩阵。考虑如下的线性框式约束凸规划问题：　　　　　　　　　　　　　　　　　（ＢＰ）ｍｉｎq（x）ｓ．ｔ．Ax＝bl≤x≤h，l＜h收稿日期：２０１１-１２-２１基金项目：宁波大学学科科研资金资助项目（ｘｋｌ０６０）；浙江省海洋与渔业资金资助项目（ＺＨＹＦ２０１１０２）；浙江省教育厅科研资金资助项目（Ｙ２０１１１９３８２）作者简介：张艺（１９６０-），男，副教授，主要

7、研究方向：最优化理论与计算、数值代数。４０运筹与管理　　　　　　　　　　　２０１３年第２２卷m×nmnn其中A∈R，b∈R，x，l，h∈R，q（x）：R→R满足下列条件：２（１）q（x）二次连续可微，磹q半正定。n（２）q（x）满足尺度Ｌｉｐｓｃｈｉｔｚ条件，即存在常数M＞０，０＜β＜１，使得橙Δx∈R，l＜x＜h，当－１－１‖（X－L）Δx‖≤β，‖（H－X）Δx‖≤β时，有２T２‖（X－L）（磹q（x＋Δx）－磹q（x）－磹q（x）Δx）‖≤MΔx磹q（x）Δx２T２（１）‖（H－X）（磹q（x＋Δx）－磹q（

8、x）－磹q（x）Δx）‖≤MΔx磹q（x）Δx２这里磹q（x），磹q（x）分别表示q（x）的梯度向量和Ｈｅｓｓｅ矩阵。n满足上述条件的函数包含了一次函数，二次函数及其他一些函数，如熵函数q（x）＝∑xiｌｎxi及其正线i＝１性组合。１　算法描述及收敛性分析问题（ＢＰ）的Ｌａｇｒａｎｇｅ对偶问题为TTTT　　　　　　　　（ＤＰ）　　ｍａｘd（x，y）＝q（x）