关于求解随机用户均衡问题的截断拟牛顿型信赖域法研究

信赖域法是一种保证全局收敛性的优化算法,为避免Hessian矩阵的计算,基于拟牛顿校正公式构造了求解带线性等式约束的非线性规划问题的截断拟牛顿型信赖域法.首先给出了截断拟牛顿型信赖域法的构造过程及具体步骤;然后针对随机用户均衡模型中变量和约束的特点对算法进行了修正,并将多种拟牛顿校正公式下所得结果与牛顿型信赖域法的结果进行了比较,结果发现基于对称秩1校正公式的信赖域法更为合适.最后基于数值算例结果得到了一些在算法编程过程中的重要结论,对其它形式信赖域法的编程实现具有一定的参考意义.     

A characterization of graphs with rank 4

The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: What is the structure of a connected graph with rank 4? This question has not yet been fully answered in the literature, and only some partial results are known. In this paper we resolve this question by completely characterizing graphs G whose adjacency matrix has rank 4.     

Partitioned quasi-Newton methods for sparse nonlinear equations

In this paper, we present two partitioned quasi-Newton methods for solving partially separable nonlinear equations. When the Jacobian is not available, we propose a partitioned Broyden’s rank one method and show that the full step partitioned Broyden’s rank one method is locally and superlinearly convergent. By using a well-defined derivative-free line search, we globalize the method and establish its global and superlinear convergence. In the case where the Jacobian is available, we propose a partitioned adjoint Broyden method and show its global and superlinear convergence. We also present some preliminary numerical results. The results show that the two partitioned quasi-Newton methods are effective and competitive for solving large-scale partially separable nonlinear equations.     

Orthogonal representations over finite fields and the chromatic number of graphs

We study the relationship between the minimum dimension of an orthogonal representation of a graph over a finite field and the chromatic number of its complement. It turns out that for some classes of matrices defined by a graph the 3-colorability problem is equivalent to deciding whether the class defined by the graph contains a matrix of rank 3 or not. This implies the NP-hardness of determining the minimum rank of a matrix in such a class. Finally we give for any class of matrices defined by a graph that is interesting in this respect a reduction of the 3-colorability problem to the problem of deciding whether or not this class contains a matrix of rank equal to three.The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.     

无约束优化问题的对角稀疏拟牛顿法

对无约束优化问题提出了对角稀疏拟牛顿法,该算法采用了Armijo非精确线性搜索,并在每次迭代中利用对角矩阵近似拟牛顿法中的校正矩阵,使计算搜索方向的存贮量和工作量明显减少,为大型无约束优化问题的求解提供了新的思路．在通常的假设条件下,证明了算法的全局收敛性,线性收敛速度并分析了超线性收敛特征。数值实验表明算法比共轭梯度法有效,适于求解大型无约束优化问题．     

Exploiting damped techniques for nonlinear conjugate gradient methods

In this paper we propose the use of damped techniques within Nonlinear Conjugate Gradient (NCG) methods. Damped techniques were introduced by Powell and recently reproposed by Al-Baali and till now, only applied in the framework of quasi-Newton methods. We extend their use to NCG methods in large scale unconstrained optimization, aiming at possibly improving the efficiency and the robustness of the latter methods, especially when solving difficult problems. We consider both unpreconditioned and Preconditioned NCG. In the latter case, we embed damped techniques within a class of preconditioners based on quasi-Newton updates. Our purpose is to possibly provide efficient preconditioners which approximate, in some sense, the inverse of the Hessian matrix, while still preserving information provided by the secant equation or some of its modifications. The results of an extensive numerical experience highlights that the proposed approach is quite promising.     

Quasi-Newton methods in infinite-dimensional spaces and application to matrix equations

In the first part of this paper, we give a survey on convergence rates analysis of quasi-Newton methods in infinite Hilbert spaces for nonlinear equations. Then, in the second part we apply quasi-Newton methods in their Hilbert formulation to solve matrix equations. So, we prove, under natural assumptions, that quasi-Newton methods converge locally and superlinearly; the global convergence is also studied. For numerical calculations, we propose new formulations of these methods based on the matrix representation of the dyadic operator and the vectorization of matrices. Finally, we apply our results to algebraic Riccati equations.     

Unitary matrix digraphs and minimum semidefinite rank

For an undirected simple graph G, the minimum rank among all positive semidefinite matrices with graph G is called the minimum semidefinite rank (msr) of G. In this paper, we show that the msr of a given graph may be determined from the msr of a related bipartite graph. Finding the msr of a given bipartite graph is then shown to be equivalent to determining which digraphs encode the zero/nonzero pattern of a unitary matrix. We provide an algorithm to construct unitary matrices with a certain pattern, and use previous results to give a lower bound for the msr of certain bipartite graphs.     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

Partitioned quasi-Newton methods for nonlinear equality constrained optimization

We derive new quasi-Newton updates for the (nonlinear) equality constrained minimization problem. The new updates satisfy a quasi-Newton equation, maintain positive definiteness on the null space of the active constraint matrix, and satisfy a minimum change condition. The application of the updates is not restricted to a small neighbourhood of the solution. In addition to derivation and motivational remarks, we discuss various numerical subtleties and provide results of numerical experiments.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the US Department of Energy under grant DE-FG02-86ER25013.A000, and by the US Army Research Office through the Mathematical Sciences Institute, Cornell University.