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

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

求解约束极小极大问题的一种K─S函数的近似迭代法

借助于极大熵方法和逼近法，给出了一种求解约束极小极大问题的K－S函数近似迭代法，同时讨论算法的有关收敛性．     

由FR共轭梯度法控制的两类优化算法的全局收敛性

１引言 考虑无约束优化问题其中ｆ：Ｒｎ→Ｒ是一阶可微函数．求解（１）的非线性共轭梯度法具有如下形式：其中ｇｋ＝　ｆ（ｘｋ）,ａｋ是通过某种线搜索获得的步长,纯量βｋ的选取使得方法（２）—（３）在ｆ（ｘ）是严格凸二次函数且采用精确线搜索时化为线性共轭梯度法［１］．比较常见的βｋ的取法有Ｆｌｅｔｃｈｅｒ－Ｒｅｅｖｅｓ（ＦＲ）公式［２］和Ｐｏｌａｋ－Ｒｉｂｉｅｒｅ－Ｐｏｌｙａｋ（ＰＲＰ）公式［３－４］等．它们分别为其中　　　取欧几里得范数．对于一般非线性函数,ＦＲ方法具有较好的理论收敛性［５－６］,而…     

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

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

一类约束不可微优化问题的区间极大熵方法

本文研究求解不等式约束离散ｍｉｎｉｍａｘ问题的区间算法,其中目标函数和约束函数是 Ｃ~１类函数．利用罚函数法和极大熵函数思想将问题转化为无约束可微优化问题,讨论了极大熵函数的区间扩张,证明了收敛性等性质,提出了无解区域删除原则,建立了区间极大熵算法,并给出了数值算例．该算法是收敛、可靠和有效的．     

调节熵函数法

１．引言 考虑如下极小极大问题这里ｆｉ（ｘ）是Ｒｎ中连续可微的函数,ｍ≥２是正整数（Ｐ）是一类比较典型的非光滑优化问题,是许多实际问题的数学模型．同时,线性规划的 Ｋａｒｍａｒｋａｒ标准型的对偶也是（Ｐ）的形式,光滑约束优化问题的一类重要罚函数法也是将问题化为类似（Ｐ）的形式．所以,如何有效地求解（Ｐ）,是一个重要问题．近些年发展起来的嫡函数法（或称凝聚函数法）是一种较新颖而实用的方法．它借助信息论中 Ｓｈａｎｎｏｎ熵的概念,推导出一族光滑的极大熵函数Ｆｐ（ｘ）,且Ｆｐ（ｘ）一致逼近要极小化的非光…     

多孔介质驱动问题的混合元最小二乘特征有限元方法及其收敛分析

１．引言多孔介质二相驱动问题的数学模型是偶合的非线性偏微分方程组的初边值问题．该问题可转化为压力方程和浓度方程［１－４］．浓度方程一般是对流占优的对流扩散方程,它的对流速度依赖于比浓度方程的扩散系数大得多的Ｆａｒｃｙ速度．因此Ｄａｒｃｙ速度的求解精度直接影响着浓度的求解精度．为了提高速度的求解精度,７０年代Ｐ．Ａ．Ｒａｖｉａｔ和Ｊ．Ｍ．Ｔｈｏｍａｓ提出混合有限元方法［５］．Ｊ．ＤｏｕｇｌａｓＪｒ,Ｔ．Ｆ．Ｒｕｓｓｅｌｌ,Ｒ．Ｅ．Ｅｗｉｎｇ,Ｍ．Ｆ．Ｗｈｅｅｌｅｒ［１］－［４］,［９］,［１２］袁…     

方程u_(tt)=u_(xxt) f(u_x)_x初边值问题的差分法

１．引言方程是在国内外引起广泛关注的一类重要的非线性发展方程．文［１］在函数ｆ（ｓ）满足局部 Ｌｉｐ－ｓｃｈｉｔｚ条件及单调性条件（ｆ（ｓ２）－ｆ（ｓ１））（ｓ２－ｓ１）＞ ０的假设下得到了（１．１）初边值问题整体弱解的存在与唯一性;文［２］用 Ｇａｌｅｒｋｉｎ方法,研究了（１．１）的初边值问题,周期边值问题和初值问题,并在函数ｆ’（ｓ）下方有界的假设下得到了整体强解的存在与唯一性． 本文在有限区域 ＱＴ＝［０,１］×［０,Ｔ］（Ｔ＞ ０）上讨论方程（１．１）带有初值条件和边值条件（ｕ（ｘ,ｔ）为未知…     

求解约束优化问题的一个对偶算法

１．引言 考虑下述形式的不等式约束优化问题：其中 ＝０,１,…,ｍ,是连续可微函数．求解（１．１）的数值方法有很多,传统方法有乘子法,序列一次规划方法,等等（见 Ｂｅｒｔｓｅｋａｓ（１９８２）, Ｈａｎ（１９７６, １９７７））．近年来对求解（１．１）的原始－对偶算法的研究已成为非线性规划领域的新的热点,如ＥＩ－Ｂａｋｒｙ,Ｔａｐｉａ,Ｔｓｕｃｈｉｙａ　＆　Ｚｈａｎｇ（１９９６）,Ｙａｍａｓｈｉｔａ（１９９２,１９９６,１９９７）等;尽管这些原始－对偶算法具有好的收敛性质和计算效果,但其算法结构相对…     

延迟动力系统线性θ-方法的散逸性

１．引言 科学与工程中的许多问题具有散逸性,即系统具有一有界吸引集,从任意初始条件出发的解经过有限时间后进入该吸引集并随后保持在里面．如 ２维的 Ｎａｖｉｅｒ－Ｓｔｏｋｅｓ方程、Ｌｏｒｅｎｚ方程等许多重要系统都是散逸的．散逸性研究一直是动力系统研究中的重要课题（参见Ｔｅｍａｍ［７］）．当数值求解这些系统时,自然希望数值方法能保持系统的该重要特性．１９９４年, Ｈｕｍｐｈｒｉｅｓ和 Ｓｔｕａｒｔ［６］首次研究了 Ｒｕｎｇｅ－Ｋｕｔｔａ方法对有限维系统的散逸性．１９９７年Ｈｉｌｌ［２］研究了其无穷维散逸性…     

New Relaxation Method for Mathematical Programs with Complementarity Constraints

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.     

Global Method for Monotone Variational Inequality Problems with Inequality Constraints

We consider optimization methods for monotone variational inequality problems with nonlinear inequality constraints. First, we study the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed, and some desirable properties of the merit function are obtained. Through the merit function, the original variational inequality problem is reformulated as simple bounded minimization. Under certain assumptions, we show that any stationary point of the optimization problem is a solution of the problem considered. Finally, we propose a descent method for the variational inequality problem and prove its global convergence.     

Exact penalty functions method for mathematical programming problems involving invex functions

In this paper, some new results on the exact penalty function method are presented. Simple optimality characterizations are given for the differentiable nonconvex optimization problems with both inequality and equality constraints via exact penalty function method. The equivalence between sets of optimal solutions in the original mathematical programming problem and its associated exact penalized optimization problem is established under suitable invexity assumption. Furthermore, the equivalence between a saddle point in the invex mathematical programming problem and an optimal point in its exact penalized optimization problem is also proved.     

Comparative computer results of a new complementary pivot algorithm for solving equality and inequality constrained optimization problems

This paper reports the development of a new algorithm for solving the general constrained optimization problem (that of optimizing an objective function subject to both equality and inequality constraints). The approach is based on the complementary pivoting algorithms which have been developed to solve certain classes of fixed point problems. The specific approach is to use the equality constraints to solve for some variables in terms of the remaining ones thus enabling one to eliminate the equality constraints altogether. The result, under certain circumstances, is an optimization problem which may be transformed into a fixed point problem in such a way that a complementary pivoting code may be used to search for a solution.Seventeen test problems have been solved by this method and the results are compared against those obtained from GRG (Generalized Reduced Gradient method). The results of the tests indicate that the fixed point approach is robust (all 17 problems were solved by this method where as GRG solved 16). As to the computer times, the fixed point code proved to be as fast or faster than GRG on the lower dimensional problems; however, as the dimension increased, the trend reversed and on a 40 dimensional problem GRG was approximately 11 times faster. The conclusion from these tests is that when the dimension of the original problem can be reduced sufficiently by the equality constraints, the fixed point approach appears to be more effective than GRG.     

A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties

We present a null-space primal-dual interior-point algorithm for solving nonlinear optimization problems with general inequality and equality constraints. The algorithm approximately solves a sequence of equality constrained barrier subproblems by computing a range-space step and a null-space step in every iteration. The ℓ₂ penalty function is taken as the merit function. Under very mild conditions on range-space steps and approximate Hessians, without assuming any regularity, it is proved that either every limit point of the iterate sequence is a Karush-Kuhn-Tucker point of the barrier subproblem and the penalty parameter remains bounded, or there exists a limit point that is either an infeasible stationary point of minimizing the ℓ ₂ norm of violations of constraints of the original problem, or a Fritz-John point of the original problem. In addition, we analyze the local convergence properties of the algorithm, and prove that by suitably controlling the exactness of range-space steps and selecting the barrier parameter and Hessian approximation, the algorithm generates a superlinearly or quadratically convergent step. The conditions on guaranteeing that all slack variables are still positive for a full step are presented.     

Partial Augmented Lagrangian Method and Mathematical Programs with Complementarity Constraints

In this paper, we apply a partial augmented Lagrangian method to mathematical programs with complementarity constraints (MPCC). Specifically, only the complementarity constraints are incorporated into the objective function of the augmented Lagrangian problem while the other constraints of the original MPCC are retained as constraints in the augmented Lagrangian problem. We show that the limit point of a sequence of points that satisfy second-order necessary conditions of the partial augmented Lagrangian problems is a strongly stationary point (hence a B-stationary point) of the original MPCC if the limit point is feasible to MPCC, the linear independence constraint qualification for MPCC and the upper level strict complementarity condition hold at the limit point. Furthermore, this limit point also satisfies a second-order necessary optimality condition of MPCC. Numerical experiments are done to test the computational performances of several methods for MPCC proposed in the literature. This research was partially supported by the Research Grants Council (BQ654) of Hong Kong and the Postdoctoral Fellowship of The Hong Kong Polytechnic University. Dedicated to Alex Rubinov on the occassion of his 65th birthday.     

A local search method for optimization problem with d.c. inequality constraints

This paper addresses a nonconvex optimization problem with the cost function and inequality constraints given by d.c. functions. The original problem is reduced to a problem without inequality constraints by the exact penalization procedure. A special local search method for the penalized problem is developed, which is based, first, on the linearization procedure with respect to the basic nonconvexity and, second, on the consecutive solutions of linearized convex problems. Convergence properties of the method are investigated. In particular, it is shown that a limit point of the sequence produced by the method is considerably stronger than the usual KKT-vector.In addition, the relations between an approximate solution of linearized convex problem and the KKT-vector of the original problem are established, and the various stopping criteria are substantiated. Besides, we established the relations among the Lagrange multipliers of the original problem, those ones of the linearized problem, and the value of the penalty parameter. Finally, a preliminary computational testing of the LSM developed has been carried out on several test problems taken from literature.     

Optimization with Variable Sets of Constraints and an Application to Truss Design

We discuss the minimization of a continuous function on a subset of Rⁿ subject to a finite set of continuous constraints. At each point, a given set-valued map determines the subset of constraints considered at this point. Such problems arise e.g. in the design of engineering structures.After a brief discussion on the existence of solutions, the numerical treatment of the problem is considered. It is briefly motivated why standard approaches generally fail. A method is proposed approximating the original problem by a standard one depending on a parameter. It is proved that by choosing this parameter large enough, each solution to the approximating problem is a solution to the original one. In many applications, an upper bound for this parameter can be computed, thus yielding the equivalence of the original problem to a standard optimization problem.The proposed method is applied to the problem of optimally designing a loaded truss subject to local buckling conditions. To our knowledge this problem has not been solved before. A numerical example of reasonable size shows the proposed methodology to work well.     

Gap Function Approach to the Generalized Nash Equilibrium Problem

We consider an optimization reformulation approach for the generalized Nash equilibrium problem (GNEP) that uses the regularized gap function of a quasi-variational inequality (QVI). The regularized gap function for QVI is in general not differentiable, but only directionally differentiable. Moreover, a simple condition has yet to be established, under which any stationary point of the regularized gap function solves the QVI. We tackle these issues for the GNEP in which the shared constraints are given by linear equalities, while the individual constraints are given by convex inequalities. First, we formulate the minimization problem involving the regularized gap function and show the equivalence to GNEP. Next, we establish the differentiability of the regularized gap function and show that any stationary point of the minimization problem solves the original GNEP under some suitable assumptions. Then, by using a barrier technique, we propose an algorithm that sequentially solves minimization problems obtained from GNEPs with the shared equality constraints only. Further, we discuss the case of shared inequality constraints and present an algorithm that utilizes the transformation of the inequality constraints to equality constraints by means of slack variables. We present some results of numerical experiments to illustrate the proposed approach.     

非线性规划问题的精确增广Lagrange函数

对于一般的非线性规划给出一种精确增广Lagrange函数,并讨论其性质.无需假设严格互补条件成立,给出了原问题的局部极小点与增广Lagrange函数在原问题的变量空间上的局部极小的关系.进一步,在适当的假设条件下,建立了两者的全局最优解之间的关系.