改进HS共轭梯度算法及其全局收敛性

１．引 言 １９５２年 Ｍ．Ｈｅｓｔｅｎｅｓ和Ｅ．Ｓｔｉｅｆｅｌ提出了求解正定线性方程组的共轭梯度法［１］．１９６４年Ｒ．Ｆｌｅｔｃｈｅｒ和Ｃ．Ｒｅｅｖｅｓ将该方法推广到求解下列无约束优化问题： ｍｉｎｆ（ｘ）,ｘ∈Ｒｎ,（１）其中ｆ：Ｒｎ→Ｒ１为连续可微函数,记ｇｋ＝ ｆ（ｘｋ）,ｘｋ∈ Ｒｎ． 若点列｛ｘｋ｝由如下算法产生：其中 βｋ＝［ｇＴｋ（ｇｋ－ｇｋ－１）］／［ｄＴｋ－１（ｇｋ－ｇｋ－１）］．（Ｈｅｓｔｅｎｅｓ－Ｓｔｉｅｆｅｌ）　　（４）则称该算法为 Ｈｅｓｔｅｎｅｓ—Ｓｔｉｅｆｅｌ共轭梯度算…     

参数最短路的原始-对偶算法

本文利用原始－对偶方法,对于含参数λ的网络（Ｖ,Ｅ,ｆ_１-λｆ_２）,给出了某一点至其它各点的参数最短路的求解算法,其时间复杂度为 Ｏ（ｎｍ＋ｎ~２ｌｏｇｎ）．     

求解不等式约束最优化问题的MBF—ODE方法

１引言考虑用基于修正内罚函数的常微分方程（ＭＢＦ－ＯＤＥ）方法求解下列不等式约束极小化问题：其中ｆi∈ｃ２：Ｒ,ｉ=0,１,…,ｍ．求解无约束极小化问题的ＯＤＥ的一般形式是其中,φ（ｘ）∈Ｃ１：ΩＲｎ→Ｒ;ｓ（ｘ）∈Ｃ１：ΩＲｎ→Ｒｎ且满足φ（ｘ）＞０,ｓＴ（ｘ）ｆ（ｘ）＜０,ｆ（ｘ）∈Ｃ１：Ｒｎ→Ｒ为目标函数．为便于用ＯＤＥ方法求解（１．ｌ）,可藉助于罚函数将（１．ｌ）变换为无约束极小化问题（见［７］．但由于经典罚函数（ＣＢＦ）在计算上有较大的困难,我们采用修正内罚函数（ＭＢＦ）．其基本思想是用…     

非光滑约束问题的既约次梯度法

１引言 对带约束的不可微的非线性规划问题,由于不能使用梯度,求极小点就比较困难．本文给出解决此问题的一种有效的算法． ２　非光滑约束问题的既约次梯度法 １）非线性规划问题的Ｌａｅｒａｎｅ对偶理论 考虑下面非线性规划问题其中ｇ（ｘ）＝（ｇ１（ｘ）,…,ｇｒ（ｘ））Ｔ,ｈ（ｘ））＝（ｈ１（ｘ）,…,ｈｍ（ｘ））Ｔ,ｆ（ｘ）＝　　　　　　Ｒｎ中是Ｌｉｓｐｓｃｈｉｔｚ连续的ｉ＝１,２,…,ｒ,ｊ＝１,２,…,ｍ相应的Ｌａｇｒａｎｇｅ对偶问题为其中　　（ｕ,　）＝ｉｎｆＬ（ｘ;ｕ,ｖ）＝ｉｎｆ（ｆ（ｘ）＋ｕＴ…     

广义Newton法求解非线性互补问题

１引言考虑非线性互补问题ＮＣＰ（ｆ）：的求解，即我们要寻求某ｘ∈Ｒｎ，使其满足（１．１）．其中映射ｆ：Ｒｎ→Ｒｎ为具有连续Ｆ－导数的非线性映射．众所周知，问题（１．ｌ）可以等价地转化为Ｂ－可微方程组：求解，其中：容易证明，由（１．３）定义的映射Ｇ处处Ｂ－可微，且其在点ｘ∈Ｒｎ处的Ｂ－导数ＢＧ（ｘ）为而对于问题（１．２）（１．３），我们希望直接用经典的广义Ｎｅｗｔｏｎ法进行求解．但是，由于由（１．３）定义映射Ｇ在（１．１）的解ｘ∈Ｒｎ处，没有可逆的强Ｆ－导数存在，因此，关于算法（１．５）（１．６）…     

一个命题的再研究

命题　△ＡＢＣ中，∠Ａ、∠Ｂ、∠Ｃ所对边分别是ａ、ｂ、ｃ，求证　　ｓｉｎＡ－ｓｉｎＢｂｃ＋ｓｉｎＢ－ｓｉｎＣｃａ＋ｓｉｎＣ－ｓｉｎＡａｂ　≥０．（１）（《数学通报》１９９７年５月号问题１０７２）文［１］对上述命题给出了一种简捷证法．通过对（１）式证法的研究，笔者得到了以下几个命题．命题１　设△ＡＢＣ中，∠Ａ、∠Ｂ、∠Ｃ所对边分别是ａ、ｂ、ｃ，则有：　　ｓｉｎＡ－ｓｉｎＢｃａ＋ｓｉｎＢ－ｓｉｎＣａｂ＋ｓｉｎＣ－ｓｉｎＡｂｃ　≤０．（２）证明　由正弦定理知，不等式（２）等价于ａ－ｂｃａ＋ｂ－ｃａｂ＋…     

矩阵方程AXB=C的通解

本文给出了矩阵方程 Ａ_（ｍ×ｎ）Ｘ_（ｎ×５）Ｂ_（ｓ×）＝Ｃ_（ｍ×ｔ）有解且有无穷解的通解表达式 Ｘ＝Ｃ~（＊＊）＋［ｋ_（１１）ξ_１~Ｔ＋…＋ｋ_（１（ｎ－ｒ））ξ_（ｎ－ｒ）~Ｔ＋……ｋ_（ｓ１）ξ_１~Ｔ＋…＋ｋ_（ｓ（ｎ－ｒ））ξ_（ｎ－ｒ）~Ｔ］ ＋［Ｐ_（１１）η_１＋…＋Ｐ_（１（ｓ－１））η_（ｓ－１）……Ｐ_（ｎ１）η_１＋…Ｐ_（ｎ（ｓ－１））η_（ｓ－１）］~Ｔ（其中ｋ_（ｉｊ）;Ｐ_（ｉｊ）为任意常数;ξ_１…,ξ_（ｎ－ｒ）;η_１…,η_（ｓ－１）分别为Ａ_（ｍ×ｎ）Ｘ_（ｎ×１）＝０;Ｘ_（１×ｓ）Ｂ_（ｓ×ｔ）＝０的一个基础解系,Ｃ~（＊＊）为ＡＸＢ＝Ｃ的一个特解）及利用矩阵初等变换求其通解的方法．     

贪婪t－相交有限序列族

设Ｆ为有限序列族，对ａ＝（ａ１，ａ２，…，ａｎ）∈Ｆ，ａｉ为整数且０≤ａｉ≤ｓｉ（整数），记ｓ（ａ）＝｛ｊ｜１≤ｊ≤ｎ，ａｊ＞０｝，ｓ（Ｆ）＝｛ｓ（ａ）｜ａ∈Ｆ｝，及Ａ｛１，２，…，ｎ｝时Ｗ（Ａ）＝Пｉ∈Ａｓｉ．称Ｆ为贪婪ｔ－相交，如对任何ａ，ｂ∈Ｆ，至少有ｔ个ａｉ，ｂｉ＞０，且Ｗ（Ａ）≥Ｗ（（｛１，２，…，ｎ｝－Ａ）＋Ｂ）对任何Ａ∈Ｓ（Ｆ）及ＢＡ（｜Ｂ｜＝ｔ－１）成立．本文得到当ｓ１＞ｓ２＞…＞ｓｎ时的最大贪婪ｔ－相交有限序列族．     

关于单调的变分不等式问题的收敛性方法

１引言变分不等式的性质及解法的研究是优化领域的重要课题．所谓变分不等式问题就是：寻找一个点,使得其中Ｘ是Ｒｎ中的非空闲凸集,Ｆ是Ｒｎ中的映射,表示Ｒｎ中的内积．求解问题（１．１）有多种思路［１,４,５］其中之一就是将（１．１）转化为它的某种等价问题,再进行求解．在山中ＭａｓａｏＦｕｋｕｓｈｉｍａ给出了（１．１）的如下的等价问题Ｇ是对称正定矩阵．山提出了求解（１．２）的带精确搜索和Ａｒｍｉｊｏ搜索的两种收敛性算法．本文建立了“ｄ－ｆｕｎｃｔｉｏｎ”的概念,利用“Ｄ－ｆｕｎｃｔｉｎ”给出了（１．１）…     

The Semigroup Characterizations of Positive Implicative BCK—algebras

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＢｙａＢＣＩ－ａｌｇｅｂｒａｗｅｍｅａｎａｎａｌｇｅｂｒａ（Ｘ，，０）ｏｆｔｙｐｅ（２，０）ｗｉｔｈｔｈｅｆｏｌｌｏｗｉｎｇｃｏｎｄｉ－ｔｉｏｎｓ：（１）（（ｘｙ）（ｘｚ））（ｚｙ）＝０；（２）（ｘ（ｘｙ））ｙ＝０；（３）ｘｘ＝０；（４）ｘｙ＝ｙｘ＝０ｉｍｐｌｉｅｓｘ＝ｙ．ＩｆａＢＣＩ－ａｌｇｅｂｒａ（Ｘ，，０）ｓａｔｉｓｆｉｅｓ（５）０ｘ＝０．ｔｈｅｎｉｔｉｓｃａｌｌｅｄａＢＣＫ－ａｌｇｅｂｒａ．ＩｎａＢＣＩ－ａｌｇｅｂｒａ，ｔｈｅｆ…     

求解不等式约束优化问题的一个改进算法

本文改进了一个求解不等式约束优化问题的对偶算法，建立了一个相应的算法，进一步证明了该算法的收敛性．最后，给出数值结果以验证该算法的有效性。     

Nonlinear Lagrangians for Nonlinear Programming Based on Modified Fischer-Burmeister NCP Functions

This paper proposes nonlinear Lagrangians based on modified Fischer-Burmeister NCP functions for solving nonlinear programming problems with inequality constraints. The convergence theorem shows that the sequence of points generated by this nonlinear Lagrange algorithm is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions, and the error bound of solution, depending on the penalty parameter, is also established. It is shown that the condition number of the nonlinear Lagrangian Hessian at the optimal solution is proportional to the controlling penalty parameter. Moreover, the paper develops the dual algorithm associated with the proposed nonlinear Lagrangians. Numerical results reported suggest that the dual algorithm based on proposed nonlinear Lagrangians is effective for solving some nonlinear optimization problems.     

Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.     

On certain optimization methods with finite-step inner algorithms for convex finite-dimensional problems with inequality constraints

Numerical methods are proposed for solving finite-dimensional convex problems with inequality constraints satisfying the Slater condition. A method based on solving the dual to the original regularized problem is proposed and justified for problems having a strictly uniformly convex sum of the objective function and the constraint functions. Conditions for the convergence of this method are derived, and convergence rate estimates are obtained for convergence with respect to the functional, convergence with respect to the argument to the set of optimizers, and convergence to the g-normal solution. For more general convex finite-dimensional minimization problems with inequality constraints, two methods with finite-step inner algorithms are proposed. The methods are based on the projected gradient and conditional gradient algorithms. The paper is focused on finite-dimensional problems obtained by approximating infinite-dimensional problems, in particular, optimal control problems for systems with lumped or distributed parameters.     

具简单界约束变分不等式的拟牛顿算法的收敛性分析

１．引言 牛顿型方法是解变分不等式的一类重要数值迭代算法．其局部收敛性质的研究也取得了很好的成果（见［５］等）．近几年来,此类算法的全局收敛性研究也得到了许多进展．如阻尼牛顿法的局部超线性乃至二阶收敛性质的研究（见［４,６,９; １１, １２, １４; １６］等）．然而,对于计算上更为实用的拟牛顿法的研究还不多见．文［１８］基于祁力群等在［１４］中给出的逐次逼近牛顿型法,建立了一种解非线性互补问题的拟牛顿法,并得到了类Ｂｒｏｙｄｅｎ算法的全局收敛性．但是,该方法有以下两个缺陷：１．线搜索可能不能实现…     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

从常步长梯度方法的视角看不可微凸优化增广Lagrange方法的收敛性

增广Lagrange方法是求解非线性规划的一种有效方法.从一新的角度证明不等式约束非线性非光滑凸优化问题的增广Lagrange方法的收敛性.用常步长梯度法的收敛性定理证明基于增广Lagrange函数的对偶问题的常步长梯度方法的收敛性,由此得到增广Lagrange方法乘子迭代的全局收敛性.     

The convergence of a dual algorithm for nonlinear programming

A dual algorithm based on the smooth function proposed by Polyak (1988) is constructed for solving nonlinear programming problems with inequality constraints. It generates a sequence of points converging locally to a Kuhn-Tucker point by solving an unconstrained minimizer of a smooth potential function with a parameter. We study the relationship between eigenvalues of the Hessian of this smooth potential function and the parameter, which is useful for analyzing the effectiveness of the dual algorithm.     

Augmented Lagrangian Objective Penalty Function

Augmented Lagrangian function is one of the most important tools used in solving some constrained optimization problems. In this article, we study an augmented Lagrangian objective penalty function and a modified augmented Lagrangian objective penalty function for inequality constrained optimization problems. First, we prove the dual properties of the augmented Lagrangian objective penalty function, which are at least as good as the traditional Lagrangian function's. Under some conditions, the saddle point of the augmented Lagrangian objective penalty function satisfies the first-order Karush-Kuhn-Tucker condition. This is especially so when the Karush-Kuhn-Tucker condition holds for convex programming of its saddle point existence. Second, we prove the dual properties of the modified augmented Lagrangian objective penalty function. For a global optimal solution, when the exactness of the modified augmented Lagrangian objective penalty function holds, its saddle point exists. The sufficient and necessary stability conditions used to determine whether the modified augmented Lagrangian objective penalty function is exact for a global solution is proved. Based on the modified augmented Lagrangian objective penalty function, an algorithm is developed to find a global solution to an inequality constrained optimization problem, and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the modified augmented Lagrangian objective penalty function is proved for a local solution. An algorithm is presented in finding a local solution, with its convergence proved under some conditions.     

Simple Sequential Quadratically Constrained Quadratic Programming Feasible Algorithm with Active Identification Sets for Constrained Minimax Problems

In this paper, the nonlinear minimax problems with inequality constraints are discussed. Based on the idea of simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization, an alternative algorithm for solving the discussed problems is proposed. Unlike the previous work, at each iteration, a feasible direction of descent called main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions. Then a high-order correction direction used to avoid the Maratos effect is computed by updating the main search direction with a system of linear equations. The proposed algorithm possesses global convergence under weak Mangasarian–Fromovitz constraint qualification and superlinear convergence under suitable conditions with the upper-level strict complementarity. At last, some preliminary numerical results are reported.