非线性约束条件下梯度投影法的一个统一途径

对于问题(P),我们作如下假设: (H1):g_j(x)(j=1,…,m)为一阶连续可微凸函数.f(x)为一阶连续可微函数. (H2):x∈R={x|x∈E~n,g_j(x)≤0,j=1,…,m}:{g_j(x)|j∈J_J(x)}为线性无关向量组.其中J_0(x)={j|g_j(x)=0}. 自Rosen的梯度投影法产生以来,国内外流行的求解(P)的梯度投影法都是先对切面做投影,然后拉回可行域,目的是保证所取得的搜索方向为可行下降方向.1985年     

简约梯度法与ROSEN梯度投影法的一个关系

1 引 言 考虑如下非线性规划问题 min{f(x)|A_1x=b,a_i~Tx≤b_i,i∈I},(1.1)其中I表示所有不等式约束指标集合。设R为(1.1)的可行域,对任意x∈R记A~T(x)=(A_1~T:A_2~T(x)),其中A_2(x)是以a_i,i∈I(x)为行的矩阵,I(x)={i|a_i~Tx=b_i,i∈I},对不同的可行点x∈R,A~2(x)可能不同 问题(1.1)的假设条件。 〈H1〉f一阶连续可微, 〈H2〉x∈R,A(x)行满秩。 1960年Rosen对问题(1.1)给出一种梯度投影法,其基本定理为     

线性约束下的共轭投影梯度法及其超线性收敛性

本文考虑线性约束非线性规划问题，提出了一类共轭投影梯度法，证明了算法的全局收敛性，并对算法的二次终止性，超线性收敛特征进行了分析，算法的优点是（１）采用计算机上实现的Ａｒｍｉｊｏ线性搜索规则，（２）初始点不要求一定是可行点，可以不满足线性等式约束，（３）具有较快的收敛速度。     

非线性最优化的广义梯度投影法

梯度投影法已有许多有效算法,但这些算法还存在三个问题:1)为了保证算法的收敛性,在算法的每一迭代步,需要选取δ-主动约束集,计算量较大.2)在迭代过程中,需要跟踪主动约束集.3)只能处理非线性不等式约束问题.本文讨论非线性等式与不等式约束的优化问题,给出了一个广义梯度投影法,证明了算法的收敛性并且完满地解决了上述三个问题.本文算法结构简单且其处理技巧有普遍意义.     

线性规划问题退化最优基可行解的性质

本通过分析两用阶段法求解线性规划初始可行解的一个例子,归纳了线性规划问题退化的最优基可行解的性质,包括同一退化最优基可行解不同表示,有无穷多最优解的表示。     

非线性约束条件下的梯度投影—可行方向法

§1 引言对于约束条件为非线性的算法而言,具有收敛性的算法是不多的(参见[9])。1971年在[3]中,E.Polak提出了一个关于非线性约束的梯度投影-可行方向法,并证明了收敛性。1981年,章祥荪在[6]中又对E.Polak方法进行了改进。1985年堵丁柱在[7]工中对特定的非精确线搜索给出了一种具有收敛性的关于非线性约束的梯度投影-可行方向法。这些方法较以前那种先对切面做梯度投影,然后再拉回到可行域的传统梯度投影法(参见[2])具有了     

一族非线性约束条件下的摄动梯度投影法

对问题(P),堵丁柱改变了以往的做法,利用对约束切空间的摄动技巧,给出了一个收敛的梯度投影方法.本文推广了[1]中方法,给出了一个更一般的收敛算法,它无需[1]中对约束函数的凸性假设,也不须多次求投影梯度.本文中算法的收敛性证明是建立在[3]中引理10.2.6的简单推广得到的引理3的基础上的.本文引理3减弱了引理10.2.6中的条件3,因而更具实用性.可以简化许多算法的收敛性证明.     

拓广的Rosen梯度投影法及其整体收敛性证明

§1.引言 Rosen梯度投影法是求解非线性规划问题的基本方法之一,方法简便,实际应用的数值效果好,而且许多近代的更有效的算法继续采用了它的基本思想和技巧。在这些算法中最有代表性的是Goldfarb方法和Murtagh-Sargents方法,其收敛性自然在某种程度上依赖于Rosen方法的收敛性。但是,Rosen方法之严格的收敛性证明尚未取得。尽管D.G.Luenberger在其著作中应用Zangwill的总体收敛性充分性定理说     

约束优化问题的修正共轭梯度投影算法

对闭凸集约束的非线性规划问题构造了一个修正共轭梯度投影下降算法,在去掉迭代点列有界的条件下,分析了算法的全局收敛性.新算法与共轭梯度参数结合,给出了三类结合共轭梯度参数的修正共轭梯度投影算法.数值例子表明算法是有效的.     

A CLASS OF REDUCED GRADIENT METHODS FOR HANDLING OPTIMIZATION PROBLEMS WITH LINEAR INEQUALITY CONSTRAINTS

A class of reduced gradient methods for handling general optimization problems with linear equality and inequality constraints is suggested in this paper. Although a slack vector is introduced, the dimension of the problem is not increased, which is unlike the conventional way of transferring the inequality constraints into the equality constraints by introducing slack variables. When an iterate x(k) is not a K-T point of the problem under consideration, different feasible descent directions can be obtained by different choices of the slack vectors. The suggested method is globally convergent and the numerical experiment given in the paper shows that the method is efficient.     

解非凸规划问题的一种连续化方法

针对一类非线性规划问题的解存在的新等价性条件，给出了大范围收敛的连续化方法及证明了收敛性的结论．     

A NEW PERTURBATION SIMPLEX ALGORITHM FOR LINEAR PROGRAMMING

1.IntroductionThedualsimplexalgorithm[1,91andtheprimal-dualsimplealgorithm[6]arewellknownandefficientsimplexvariants.However,bothofthemneedaninitialdualfeasiblebasistogetstarted,andthereforecannotbedirectlyappliedtosolvingproblemsthatdonothavesuchane...     

一类分式线性规划问题的对偶规划与算法

给出线性分式规划问题的对偶规划与对偶定理，由此得到一个解线性分式规划的方法．     

一个求解线性不等式约束的非线性规划的广义梯度投影内点 …

基于内点算法思想,利用广义投影技术设计了求解带线性不等式约束和非负约束的非线性规划的广义梯度投影内点算法,并了算法的收敛性质,数值例子表明算法是有效的。     

关于二次规划问题分段线性同伦算法的改进

本文利用Ｃｈｏｌｅｓｋｙ分解，Ｇａｕｓｓ消去等技术和定义适当的同伦映射，将关于二次规划问题的分段线性同伦算法加以改进，改进后的算法，对于严格凸二次规划来说，计算效率与Ｇｏｌｄｆａｒｂ－Ｉｄｎａｎｉ的对偶法相当。     

线性规划流动等值面算法

对于线性规划问题,本文给出了基于流动等值面的等价模型,提出了一种不可行流动等值面算法．新算法保留了传统单纯形算法的优点并克服了它的不足。初步数值结果表明新算法比传统方法更为有效．     

一种改进的多维偏好线性规划分析方法

本文对传统的多维偏好线性规划分析方法—LINMAP法进行改进,提出一种新的多维偏好线性规划分析方法,该方法运用加性加权法建立线性规划模型,同时引入任意小正数δ,使得评价结果更加符合决策人偏好集。     

求线性规划问题相容方程组非负解的算法

本文提出一个解线性规划问题的新算法.其最优解是通过求一个相容方程组的非负解而得到.这算法的计算量在最坏情况下是O(mnτ),其中τ是相应方程的m×n矩阵非零元素的个数.     

初始点任意的解非线性不等式约束优化问题的结合共轭梯度参数的超记忆梯度广义投影算法

本文利用广义投影矩阵,对求解无约束规划的超记忆梯度算法中的参数给出一种新的取值范围以保证得到目标函数的超记忆梯度广义投影下降方向,并与处理任意初始点的方法技巧结合建立求解非线性不等式约束优化问题的一个初始点任意的超记忆梯度广义投影算法,在较弱条件下证明了算法的收敛性．同时给出结合FR,PR,HS共轭梯度参数的超记忆梯度广义投影算法,从而将经典的共轭梯度法推广用于求解约束规划问题．数值例子表明算法是有效的．