一个解带线性或非线性约束最优化问题的梯度投影方法

§1 引言 Rosen在[1,2]中利用梯度投影建立了带约束非线性规划问题的可行方向算法,称为梯度投影方法.由于此方法简单易行,计算的每一步都是显式迭代,而不必去解复杂的线性规划或二次规划问题,因此人们颇为注意.现在梯度投影方法已成为非线性规划算法     

Rosen法中二次求投影梯度的一种简化方法

用Rosen投影梯度法构造搜索方向经常要两次汁算投影负梯度，对此本文提出一种改进的方法．     

解带线性或非线性约束最优化问题的三项记忆梯度Rosen投影算法

利用Rosen投影矩阵，建立求解带线性或非线性不等式约束优化问题的三项记忆梯度Rosen投影下降算法，并证明了算法的收敛性．同时给出了结合FR，PR，HS共轭梯度参数的三项记忆梯度Rosen投影算法，从而将经典的共轭梯度法推广用于求解约束规划问题．数值例子表明算法是有效的。     

改进的Rosen-Polak方法

(一)前言 梯度投影法由Rosen于1960年首先较完整地提出以后,成为非线性规划算法的基本方法之一。Rosen处理了以下的模型:     

解非线性约束拟凸规划的一个梯度投影法

目前国内外所流行的梯度投影法(包括Rosen的原有算法和一些修正算法)还存在以下几个问题:一、要增加Polak程序以保证算法的收僉性。二、在计算投影梯度时,每步一般要作两次投影。三、对于非线性约束问题,负梯度投影方向是不可行的,因此必须在此方向的基础上构造出能保证算法收歛的新可行下降方向。而目前为构造出这个新方向所作的计算都比较复杂。 1981年[5]提出了一个处理线性约束条件的梯度投影法,基本上解决了线     

一般单调变分不等式的近似邻近外梯度算法

近似邻近点算法是求解单调变分不等式的一个有效方法,该算法通过解决一系列强单调子问题,产生近似邻近点序列来逼近变分不等式的解,而外梯度算法则通过每次迭代中增加一个投影来克服一般投影算法限制太强的缺点,但它们均未能改变迭代步骤中不规则闭凸区域上投影难计算的问题.于是,本文结合外梯度算法的迭代格式,构造包含原投影区域的半空间,将投影建立在半空间上,简化了投影的求解过程,并对新的邻近点序列作相应限制,使得改进的算法具有较好的收敛性.     

对Rosen的梯度投影法收敛性的讨论

一、引言 Rosen的梯度投影法发表于1960,是非线性规划的一个基本方法。方法简单,实际应用的数值效果好。方法的重要性还在于,一些更有效的近代算法继续采用了它的基本思想,在这些算法中,有代表性的是Goldfarb方法。 从Rosen方法发表到现在,已有二十余年了,但它的收敛性问题尚未解决,所谓收敛性问题,是指,当算法产生一无穷序列时,其聚点是否是所求的解。或者从点到集映像的收敛性理论出发,在几何上可解释为,算法是否会由于jamming(zigzaging)的现象而导     

Resen梯度投影法的整体收敛性

考虑问题:maxf(x),其中Ω={x∈R~m:a_j~Tx≥b_j,j=1,…,n}.记J(x)={j:a_j~Tx=b_j}.对{1,…,n}之子集J,记A_J=(a_j,j∈J)及P_J=I-A_J(A_J~TA_J)~(-1)A_J.一个解如上最优化问题之方法——Rosen梯度投影法可描述如下:初始步任选一可行点x~0∈Ω和一正常数c>0.     

一个新的梯度投影方法

Rosen的梯度投影法自问世以来获得了广泛的注意和系统的研究。它的收敛问题经Polak和章祥荪的研究已获基本解决.但是,目前的梯度投影法都有如下两个问题:     

关于拟线性抛物型方程的加速收敛分析

在工程实际问题中,求解非线性问题的有限元近似解,通常采用低次元,得到的解精度较低。为了达到较高的精度,就必须采用高次元,但这给实际计算带来了很大的困难,为此,文[1]作者提出了一种求解非线性问题的加速计算方法。首先用低次元求出非线性问题的有限元近似解,再利用这个近似解把非线性问题的求解化成相应的线性问     

A computational method for large‐scale differential symmetric Stein equation

We propose a numerical method for solving large‐scale differential symmetric Stein equations having low‐rank right constant term. Our approach is based on projection the given problem onto a Krylov subspace then solving the low dimensional matrix problem by using an integration method, and the original problem solution is built by using obtained low‐rank approximate solution. Using the extended block Arnoldi process and backward differentiation formula (BDF), we give statements of the approximate solution and corresponding residual. Some numerical results are given to show the efficiency of the proposed method.     

A Family of Supermemory Gradient Projection Methods for Constrained Optimization

A family of supermemory gradient projection methods for solving the convex constrained optimization problem is presented in this article. It is proven to have stronger convergence properties than the traditional gradient projection method. In particular, it is shown to be globally convergent if the objective function is convex.     

A NOTE ON THE GRADIENT PROJECTION METHOD WITH EXACT STEPSIZE RULE

In this paper, we give some convergence results on the gradient projection method with exact stepsize rule for solving the minimization problem with convex constraints. Especially, we show that if the objective function is convex and its gradient is Lipschitz continuous, then the whole sequence of iterations produced by this method with bounded exact stepsizes converges to a solution of the concerned problem.     

A gradient projection method for solving continuous games

This paper develops a procedure for numerically solving continuous games (and also matrix games) using a gradient projection method in a general Hilbert space setting. First, we analyze the symmetric case. Our approach is to introduce a functional which measures how far a strategy deviates from giving zero value (i.e., how near the strategy is to being optimal). We then incorporate this functional into a nonlinear optimization problem with constraints and solve this problem using the gradient projection algorithm. The convergence is studied via the corresponding steepest-descent differential equation. The differential equation is a nonlinear initial-value problem in a Hilbert space; thus, we include a proof of existence and uniqueness of its solution. Finally, nonsymmetric games are handled using the symmetrization techniques of Ref. 1.     

A proximal-Newton method for unconstrained convex optimization in Hilbert spaces

We propose and study the iteration-complexity of a proximal-Newton method for finding approximate solutions of the problem of minimizing a twice continuously differentiable convex function on a (possibly infinite dimensional) Hilbert space. We prove global convergence rates for obtaining approximate solutions in terms of function/gradient values. Our main results follow from an iteration-complexity study of an (large-step) inexact proximal point method for solving convex minimization problems.     

A fuzzy multiobjective programming algorithm in decision support systems

Multicriteria analysis is one of the analytical functions in the problem processing system of decision support systems (DSS). In this paper, an interactive and iterative fuzzy programming method for solving a quasi-optimization problem in complex decisions under constraints involving a multiple objective function is proposed. Comparing with an adapted gradient search method, a surrogate worth tradeoff method, and a Zionts—Wallenius method, an approximate preference structure is emphasized in the proposed method.     

利用Fisher函数解非线性不等式约束优化问题的梯度投影算法

本文将利用梯度投影与Fisher函数提出一个新的二阶段搜索方向,给出相应的解非线性不等式约束优化问题的梯度投影算法,并证明了该算法具有全局收敛性.     

互补约束数学规划问题的一个广义梯度投影罚算法

结合罚函数思想和广义梯度投影技术,提出求解非线性互补约束数学规划问题的一个广义梯度投影罚算法.首先,通过扰动技术和广义互补函数,将原问题转化为序列带参数的近似的标准非线性规划;其次,利用广义梯度投影矩阵构造搜索方向的显式表达式.一个特殊的罚函数作为效益函数,而且搜索方向能保证效益函数的下降性.在适当的假设条件下算法具有全局收敛性.     

A smoothing homotopy method for variational inequality problems on polyhedral convex sets

In this paper, based on the Robinson’s normal equation and the smoothing projection operator, a smoothing homotopy method is presented for solving variational inequality problems on polyhedral convex sets. We construct a new smoothing projection operator onto the polyhedral convex set, which is feasible, twice continuously differentiable, uniformly approximate to the projection operator, and satisfies a special approximation property. It is computed by solving nonlinear equations in a neighborhood of the nonsmooth points of the projection operator, and solving linear equations with only finite coefficient matrices for other points, which makes it very efficient. Under the assumption that the variational inequality problem has no solution at infinity, which is a weaker condition than several well-known ones, the existence and global convergence of a smooth homotopy path from almost any starting point in $R^n$ are proven. The global convergence condition of the proposed homotopy method is same with that of the homotopy method based on the equivalent KKT system, but the starting point of the proposed homotopy method is not necessarily an interior point, and the efficiency is more higher. Preliminary test results show that the proposed method is practicable, effective and robust.