广义交替近似梯度算法的线性收敛分析

针对两个可分凸函数的和在线性约束下的极小化问题,在交替方向法的框架下,提出广义的交替近似梯度算法.在一定的条件下,该算法具有全局及线性收敛性.数值实验表明该算法有好的数值表现.     

Properties of updating methods for the multipliers in augmented Lagrangians

The convergence properties of different updating methods for the multipliers in augmented Lagrangians are considered. It is assumed that the updating of the multipliers takes place after each line search of a quasi-Newton method. Two of the updating methods are shown to be linearly convergent locally, while a third method has superlinear convergence locally. Modifications of the algorithms to ensure global convergence are considered. The results of a computational comparison with other methods are presented.This work was supported by the Swedish Institute of Applied Mathematics.     

A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming

ABSTRACT

In this note, we consider three types of problems, H-weighted nearest correlation matrix problem and two types of important doubly non-negative semidefinite programming, derived from the binary integer quadratic programming and maximum cut problem. The dual of these three types of problems is a 3-block separable convex optimization problem with a coupling linear equation constraint. It is known that, the directly extended 3-block alternating direction method of multipliers (ADMM3d) is more efficient than many of its variants for solving these convex optimization, but its convergence is not guaranteed. By choosing initial points properly, we obtain the convergence of ADMM3d for solving the dual of these three types of problems. Furthermore, we simplify the iterative scheme of ADMM3d and show the equivalence of ADMM3d to the 2-block semi-proximal ADMM for solving the dual's reformulation, under these initial conditions.     

一类自适应广义交替方向乘子法

广义交替方向乘子法是求解凸优化问题的有效算法.当实际问题中子问题难以求解时,可以采用在子问题中添加邻近项的方法处理,邻近矩阵正定时,算法收敛,然而这也会使迭代步长较小.最新研究表明,邻近矩阵可以有一定的不正定性.本文在基于不定邻近项的广义交替方向乘子法框架下,提出一种自适应的广义交替方向乘子法,动态地选择邻近矩阵,增大迭代步长.在一些较弱的假设下,证明了算法的全局收敛性.我们进行一些初等数值实验,验证了算法的有效性.     

稀疏线性规划研究

稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.     

Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints

In this paper, we extend the classical convergence and rate of convergence results for the method of multipliers for equality constrained problems to general inequality constrained problems, without assuming the strict complementarity hypothesis at the local optimal solution. Instead, we consider an alternative second-order sufficient condition for a strict local minimum, which coincides with the standard one in the case of strict complementary slackness. As a consequence, new stopping rules are derived in order to guarantee a local linear rate of convergence for the method, even if the current Lagrangian is only asymptotically minimized in this more general setting. These extended results allow us to broaden the scope of applicability of the method of multipliers, in order to cover all those problems admitting loosely binding constraints at some optimal solution. This fact is not meaningless, since in practice this kind of problem seems to be more the rule rather than the exception.In proving the different results, we follow the classical primaldual approach to the method of multipliers, considering the approximate minimizers for the original augmented Lagrangian as the exact solutions for some adequate approximate augmented Lagrangian. In particular, we prove a general uniform continuity property concerning both their primal and their dual optimal solution set maps, a property that could be useful beyond the scope of this paper. This approach leads to very simple proofs of the preliminary results and to a straight-forward proof of the main results.The author gratefully acknowledges the referees for their helpful comments and remarks. This research was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Technológico de Chile).     

关于函数空间上三个特殊拓扑满足第一可数公理的条件

本文给出了函数空间上的一致收敛拓扑、紧收敛拓扑及 Cauchy收敛拓扑满足第一可数公理的条件 .     

Lacunary equi-statistical convergence of positive linear operators

In this paper, the concept of lacunary equi-statistical convergence is introduced and it is shown that lacunary equi-statistical convergence lies between lacunary statistical pointwise and lacunary statistical uniform convergence. Inclusion relations between equi-statistical and lacunary equi-statistical convergence are investigated and it is proved that, under some conditions, lacunary equi-statistical convergence and equi-statistical convergence are equivalent to each other. A Korovkin type approximation theorem via lacunary equi-statistical convergence is proved. Moreover it is shown that our Korovkin type approximation theorem is a non-trivial extension of some well-known Korovkin type approximation theorems. Finally the rates of lacunary equi-statistical convergence by the help of modulus of continuity of positive linear operators are studied.      

Mean Convergence of Lagrange Type Interpolation on an Arbitrary System of Nodes

Abstract Sufficient conditions of convergence and rate of convergence for Lagrange type interpolation in theWeighted L~p norm on an arbitrary system of nodes are given.     

三个可分离算子凸优化的线性化方法

本文研究了三个可分离算子不含交叉变量的线性约束凸优化问题.利用定制的邻近点算法,对其变分不等式子问题进行线性化处理,并增加一邻近点项,使其子问题成为易于运算的单调线性变分不等式,得到了线性化定制的邻近点算法,并证明了全局收敛性,推广了文献中的研究结果.     

Optimization of functionals subject to integral constraints

The classical method for optimizing a functional subject to an integral constraint is to introduce the Lagrange multiplier and apply the Euler-Lagrange equations to the augmented integrand. The Lagrange multiplier is a constant whose value is selected such that the integral constraint is satisfied. This value is frequently an eigenvalue of the boundary-value problem and is determined by a trial-and-error procedure. A new approach for solving this isoperimetric problem is presented. The Lagrange multiplier is introduced as a state variable and evaluated simultaneously with the optimum solution. A numerical example is given and is shown to have a large region of convergence.     

关于函数空间Y~X上三个特殊拓扑间关系的讨论

本文对函数空间上的一致收敛拓扑、紧收敛拓扑及 Cauchy收敛拓扑之间的关系进行了讨论 ,给出了这三个拓扑间两两等价的充要条件     

Newton-type methods of high order and domains of semilocal and global convergence

We present the geometric construction of some classical iterative methods that have global convergence and “infinite” speed of convergence when they are applied to solve certain nonlinear equations f(t)=0. In particular, for nonlinear equations with the degree of logarithmic convexity of f^′, L_f^′(t)=f^′(t)f^?(t)/f^″(t)², is constant, a family of Newton-type iterative methods of high orders of convergence is constructed. We see that this family of iterations includes the classical iterative methods. The convergence of the family is studied in the real line and the complex plane, and domains of semilocal and global convergence are located.     

Complete Moment Convergence for Arrays of Rowwise Widely Orthant Dependent Random Variables

In this paper, complete moment convergence for widely orthant dependent random variables is investigated under some mild conditions. For arrays of rowwise widely orthant dependent random variables, the main results extend recent results on complete convergence to complete moment convergence. These results on complete moment convergence are shown to yield new results on complete integral convergence.     

Some Properties of Methods of Centers

Huard's method of centers is a method that solves constrained convex problems by means of unconstrained problems. In this paper we give some properties of this method, we analyse its convergence and rate of convergence and suggest some other variants and techniques to improve the speed of convergence.     

Convergence of interval-type algorithms for generalized fractional programming

The purpose of this paper is to analyze the convergence of interval-type algorithms for solving the generalized fractional program. They are characterized by an interval [LB _k , UB _k ] including*, and the length of the interval is reduced at each iteration. A closer analysis of the bounds LB _k and UB _k allows to modify slightly the best known interval-type algorithm NEWMODM accordingly to prove its convergence and derive convergence rates similar to those for a Dinkelbach-type algorithm MAXMODM under the same conditions. Numerical results in the linear case indicate that the modifications to get convergence results are not obtained at the expense of the numerical efficiency since the modified version BFII is as efficient as NEWMODM and more efficient than MAXMODM.This research was supported by NSERC (Grant A8312) and FCAR (Grant 0899).     

Mean Convergence of Lagrnage Type Interpolation on an Arbitrary System of Nodes

Abstract   Sufficient conditions of convergence and rate of convergence for Lagrange type interpolation in the weighted L ^p norm on an arbitrary system of nodes are given. Supported by the National Natural Sciences Foundation of China (No.19671082)     

TRUNCATED HERMITE INTERPOLATION ON AN ARBITRARY SYSTEM OF NODES

1 IntroductionThis paper deals with the uniform collvergence of truncated Hermte illterpolatioll oll anarbitrary systelll of 11odes. Tl1e mean collvergellce of trllllcated Herntite interpolation oll a11arbitrary syste12l of 1lodes 1las been st11died recently by tlle al1t11or[31. The converge11ce oftruncated Hern1ite illterpolatiou on tl1e zeros of the Jacobi polynontials is discussed in both tlleweigl1ted LP and the unfform norm by P. Vertesi and Y. X.[61.First we iutroduce some defi11itio…     

i.i.d情况下非参数回归模型的误差密度估计的收敛性质

本文研究了i．i．d情况下非参数回归的误差密度估计的一致收敛和均方收敛，给出了一定条件下误差密度的估计量f^n(x)的一致收敛速度和均方收敛速度。     

Global convergence and rate of convergence of a method of centers

We consider a method of centers for solving constrained optimization problems. We establish its global convergence and that it converges with a linear rate when the starting point of the algorithm is feasible as well as when the starting point is infeasible. We demonstrate the effect of the scaling on the rate of convergence. We extend afterwards, the stability result of [5] to the infeasible case anf finally, we give an application to semi-infinite optimization problems.