A conjugate gradient method for the unconstrained minimization of strictly convex quadratic splines

In this paper, we show that an analogue of the classical conjugate gradient method converges linearly when applied to solving the problem of unconstrained minimization of a strictly convex quadratic spline. Since a strictly convex quadratic program with simple bound constraints can be reformulated as unconstrained minimization of a strictly convex quadratic spline, the conjugate gradient method is used to solve the unconstrained reformulation and find the solution of the original quadratic program. In particular, if the solution of the original quadratic program is nondegenerate, then the conjugate gradient method finds the solution in a finite number of iterations. This author's research is partially supported by the NASA/Langley Research Center under grant NCC-1-68 Supplement-15.     

Refined-mesh interpolation method for functions with a boundary-layer component

Linear and quadratic spline interpolation methods for a one-variable function with a boundary-layer component are examined. It is shown that the interpolation method for such a function leads to considerable errors when applied on a uniform mesh. The error of linear and quadratic spline interpolations on meshes that are refined in the boundary layer is estimated. Numerical results are presented.     

Resolution of quadratic equations in banach spaces

A new convergence theorem is established for the super-Halley method. This method has, in general, order three, but when it is applied to quadratic equations, its order is four.     

非线性互补问题近似Newton法的二阶收敛性

本文给出了求解非线性互补问题近似Newton法二阶收敛性的一个条件，并且证明了在一定的条件下，有限差分Newton法具有二阶收敛性．     

A conjugate-direction method based on a nonquadratic model

A conjugate-gradient method for unconstrained optimization, which is based on a nonquadratic model, is proposed. The technique has the same properties as the Fletcher-Reeves algorithm when applied to a quadratic function. It is shown to be efficient when tried on general functions of different dimensionality.     

The out-of-kilter algorithm applied to traffic congestion

The out-of-kilter algorithm finds a minimum cost assignment of flows to a network defined in terms of one-way arcs, each with upper and lower bounds on flow, and a cost. It is a mathematical programming algorithm which exploits the network structure of the data. The objective function, being the sum taken over all the arcs of the products, cost×flow, is linear. The algorithm is applied in a new way to minimise a series of linear functions in a heuristic method to reduce the value of a non-convex quadratic function which is a measure of traffic congestion. The coefficients in these linear functions are chosen in a way which avoids one of the pitfalls occurring when Beale's method is applied to such a quadratic function. The method does not guarantee optimality but has produced optimal results with networks small enough for an integer linear programming method to be feasible.     

混合互补问题牛顿型算法的二阶收敛性

在凸规划理论中,通过ＫＴ条件,往往将约束最优化问题归结为一个混合互补问题来求解。该文就正则解和一般解两种情形分别给出了求解混合互补问题牛顿型算法的二阶收敛性的充分性条件,并在一定条件下证明了非精确牛顿法和离散牛顿法所具有的二阶收敛性。     

Alternative proofs of the convergence properties of the conjugate-gradient method

For the problem of minimizing an unconstrained function, the conjugate-gradient method is shown to be convergent. If the function is uniformly strictly convex, the ultimate rate of convergence is shown to ben-step superlinear. If the Hessian matrix is Lipschitz continuous, the rate of convergence is shown to ben-step quadratic. All results are obtained for the reset version of the method and with a relaxed requirement on the solution of the stepsize problem. In addition to obtaining sharper results, the paper differs from previously published ones in the mode of proof which contains as a corollary the proof of finiteness of the conjugate-gradient method when applied to a quadratic problem rather than assuming that result.     

A trust region method for solving linearly constrained locally Lipschitz optimization problems

In this paper, we present a nonsmooth trust region method for solving linearly constrained optimization problems with a locally Lipschitz objective function. Using the approximation of the steepest descent direction, a quadratic approximation of the objective function is constructed. The null space technique is applied to handle the constraints of the quadratic subproblem. Next, the CG-Steihaug method is applied to solve the new approximation quadratic model with only the trust region constraint. Finally, the convergence of presented algorithm is proved. This algorithm is implemented in the MATLAB environment and the numerical results are reported.     

降维梯度法

§1.引言 本文研究降维梯度法,它具有共轭梯度法的一切性质.对于正定二次函数,用不着精确的一维搜索,只要在每步加入两个校正项,即可将高阶问题转化为低阶问题,保证了二     

一个修正的秩1拟牛顿法及其收敛性质

的拟牛顿算法,具有结构简单,易于实现的特点.当用于正定二次凸函数时,算法有较好的收敛性质.但是,它也有严重的缺点.一方面,即使 H_k 正定,也不能保证 H_(k+1) 是正定的;另一方面,(S_k—H_kYk)~TY_k 可能为0,这时算法就不再有定义.自从秩1拟牛顿法问世以来,许多学者都想将其改变为一个有用的算法(参见),     

Minimization of extended quadratic functions

Summary A method is given for constructing algorithms which generate conjugate search directions when applied to functions of the formF o q whereq is a positive-definite quadratic andF is a non-negative strictly increasing function of a single variable with a non-vanishing derivative. Perfect line searches are not assumed.     

On the Barzilai and Borwein choice of steplength for the gradient method

In a recent paper, Barzilai and Borwein presented a new choiceof steplength for the gradient method. Their choice does notguarantee descent in the objective function and greatly speedsup the convergence of the method. They presented a convergenceanalysis of their method only in the two-dimensional quadraticcase. We establish the convergence of the Barzilai and Borweingradient method when applied to the minimization of a strictlyconvex quadratic function of any number of variables.     

On Quadratic Wasserstein Metric with Squaring Scaling for Seismic Velocity Inversion

The quadratic Wasserstein metric has shown its power in comparing probability densities. It is successfully applied in waveform inversion by generating objective functions robust to cycle skipping and insensitive to data noise. As an alternative approach that converts seismic signals to probability densities, the squaring scaling method has good convexity and thus is worth exploring. In this work, we apply the quadratic Wasserstein metric with squaring scaling to regional seismic tomography. However, there may be interference between different seismic phases in a broad time window. The squaring scaling distorts the signal by magnifying the unbalance of the mass of different seismic phases and also breaks the linear superposition property. As a result, illegal mass transportation between different seismic phases will occur when comparing signals using the quadratic Wasserstein metric. Furthermore, it gives inaccurate Fréchet derivative, which in turn affects the inversion results. By combining the prior seismic knowledge of clear seismic phase separation and carefully designing the normalization method, we overcome the above problems. Therefore, we develop a robust and efficient inversion method based on optimal transport theory to reveal subsurface velocity structures. Several numerical experiments are conducted to verify our method.     

Quadratic cost flow and the conjugate gradient method

By introducing quadratic penalty terms, a convex non-separable quadratic network program can be reduced to an unconstrained optimization problem whose objective function is a piecewise quadratic and continuously differentiable function. A conjugate gradient method is applied to the reduced problem and its convergence is proved. The computation exploits the special network data structures originated from the network simplex method. This algorithmic framework allows direct extension to multicommodity cost flows. Some preliminary computational results are presented.     

The role of the multipliers in the multiplier method

The paper studies the role of the multipliers when the multiplier method is applied as a computational technique for minimizing penalized cost functionals for optimal control problems characterized by linear systems and integral quadratic costs.Theauthor would like to gratefully thank two anonymous referees for many helpful suggestions which led to a major improvement in both the quality and clarity of the paper, and to Professor Angelo Miele for his encouragement.     

交替方向法求解带线性约束的变分不等式

１引言变分不等式是一个有广泛应用的数学问题,它的一般形式是：确定一个向量,使其满足这里ｆ是一个从到自身的一个映射,Ｓ是Ｒ中的一个闭凸集．在许多实际问题中集合Ｓ往往具有如下结构其中ＡｂＫ是中的一个简单闭凸集．例如一个正卦限,一个框形约束结构,或者一个球简言之,Ｓ是Ｒ中的一个超平面与一个简单闭凸集的交．求解问题（１）－（２）,往往是通过对线性约束Ａ引人Ｌａｇｒａｎｇｅ乘子,将原问题化为如下的变分不等式：确定使得我们记问题（３）－（４）为ＶＩ（Ｆ）．熟知［３］,ＶＩ（,Ｆ）等价于投影方程其中凡（·）表…     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

A modification of Cauchy's method for quadratic equations

The plan of this paper is to obtain one-point iterative methods with any R-order of convergence, when they are applied to approximate solutions of quadratic equations in Banach spaces. To do this, we consider real Cauchy's method and, under certain natural modifications, it is extended to Banach spaces. Some applications are also provided.     

A conjugate-gradient optimization method invariant to nonlinear scaling

A conjugate-gradient optimization method which is invariant to nonlinear scaling of a quadratic form is introduced. The technique has the property that the search directions generated are identical to those produced by the classical Fletcher-Reeves algorithm applied to the quadratic form. The approach enables certain nonquadratic functions to be minimized in a finite number of steps. Several examples which illustrate the efficacy of the method are included.