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

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

r-循环阵的逆阵或广义逆阵

在应用数学和其他学科(如数理统计、固态物理等)中,都将遇到求循环阵的逆阵或广义逆阵的问题.如何求非奇异循环阵的逆阵?文[1]提出了一种算法而无证明,文[2]则给出了这种算法的一个证明,文[3]又提出一种新算法,但上述两种算法的计算量大,实际使用时是很繁的.针对这一情况,文[4]除了对[1]中提出的方法重新给了一个初等证明外,还导出了一些特殊循环阵的逆阵公式.关于求奇异循环阵的广义逆阵的问题,则除了[3]中给出了某类特殊的奇异循环阵的 Moor-Penrose 逆阵外,还未见到有文章论述求奇异循环阵的广义逆阵的一般方法.本文给出了 r-循环阵的逆阵或一个反射 g 逆阵的公式和具体算法.特别,这个公式可用来求通常的循环阵及反循环阵的逆阵和 Moor-Penrose 逆阵.文[3]、[4]中的各个公式可用本文的统一方法推广到 r-循环阵的情形.     

自动机的半群结构

本文从循环自动机A出发,在输入半群I中诱导出一个右同余π_o,定义一个同构于A的自动机A(I/π_o),然后在I中定义π_o的同余化子N,讨论N/π_o中的Green关系,从而刻画A的自同态半群和自同构群,对于循环自动机给出Bavel提出的一个公开问题的解答.最后给出求循环自动机的自同态半群和自同构群,循环自动机到任意自动机的一切同态以及任意自动机的自同态半群和自同构群等的算法.     

自由构形幂零基的一个算法

给出求自由构形幂零基的一个算法 ,从而肯定地回答了Orlik的3个问题 ,并用此算法证明了Orlik的一个猜测成立的充分条件.     

在两循环矩阵类中求解线性方程组反问题的快速算法

本文利用多项式最大公因式 ,给出了线性方程组的反问题在 r-循环矩阵类和对称 r-循环矩阵类中有唯一解的充要条件 ,进而得到线性方程组在 r循环矩阵类和对称 r-循环矩阵类中的反问题求唯一解的算法 .最后给出了应用该算法的数值例子 .     

某些特殊循环矩阵的逆

贵刊1986年第10期,姚存峰给出了求循环矩阵的逆矩阵的一个方法。此法虽然解决了循环矩阵的求逆问题,但在实际应用中因有大量的三角函数运算等问题,因此此法使用起来不太方便.本文就某些特殊类型的循环矩阵的求逆问题进行探讨,给出一些简便方法. 设循环矩阵A为     

并行技术在约束凸规划化问题的对偶算法中的应用

用 Rosen(196 1)的投影梯度的方法求解约束凸规划化问题的对偶问题 ,在计算投影梯度方向时 ,涉及求关于原始变量的最小化问题的最优解 .我们用并行梯度分布算法 (PGD)计算出这一极小化问题的近似解 ,证明近似解可以达到任何给定的精度 ,并说明当精度选取合适时 ,Rosen方法仍然是收敛的     

对称r-循环矩阵的快速算法和并行算法

借助于快速付立叶变换(FFT),给出了一种判断对称r-循环线性系统是否有解的快速算法,并且在有解的情况下求出其解,该算法的计算复杂度为O(nlogn),且具有很好的并行性,若使用n台处理机并行处理该算法则只需要O(logn)步.当r=0时,对称r-循环矩阵变成一个上三角型Hankel矩阵,我们也给出了此类矩阵求逆的一种算法.最后将该算法推广到线性同余系统,其运算量仅为O(nlogn).     

三对角矩阵求逆的算法

研究了一般的非奇三对角矩阵的求逆,并给出了一个求逆矩阵的简单算法.首先研究了具有Doolittle分解的三对角矩阵的求逆,得到一个求逆的算法,然后将该算法推广到一般的非奇三对角矩阵上.最后给出了该算法与其它求逆方法的比较,可以看到该算法一方面计算量低,另一方面适用于不需任何附加条件的一般的非奇三对角矩阵.     

两类r-循环矩阵求逆的快速算法

本文利用多项式的最大公因式给出的求r-循环矩阵和对称r-循环矩阵求逆的快速算法。该方法不需要计算三角函数并且具有很少的计算量。     

Rosen's Gradient Projection with discrete steps

In 1960, J. B. Rosen gave a famous Gradient Projection Method in [1]. But the convergence of the algorithm has not been proved for a long time. Many authors paid much attention to this problem, such as X.S. Zhang proved in [2] (1984) that the limit point of {x _k} which is generated by Rosen's algorithm is a K-T piont for a 3-dimensional caes, if {x _k} is convergent. D. Z. Du proved in [3] (1986) that Rosen's algorithm is convergent for 4-dimensional. In [4] (1986), the author of this paper gave a general proof of the convergence of Rosen's Gradient Projection Method for ann-dimensional case. As Rosen's method requires exact line search, we know that exact line search is very difficult on computer. In this paper a line search method of discrete steps are presented and the convergence of the algorithm is proved.     

Two new algorithms for solving optimization problems with one linear objective function and finitely many constraints of fuzzy relation inequalities

This paper studies the optimization model of a linear objective function subject to a system of fuzzy relation inequalities (FRI) with the max-Einstein composition operator. If its feasible domain is non-empty, then we show that its feasible solution set is completely determined by a maximum solution and a finite number of minimal solutions. Also, an efficient algorithm is proposed to solve the model based on the structure of FRI path, the concept of partial solution, and the branch-and-bound approach. The algorithm finds an optimal solution of the model without explicitly generating all the minimal solutions. Some sufficient conditions are given that under them, some of the optimal components of the model are directly determined. Some procedures are presented to reduce the search domain of an optimal solution of the original problem based on the conditions. Then the reduced domain is decomposed (if possible) into several sub-domains with smaller dimensions that finding the components of the optimal solution in each sub-domain is very easy. In order to obtain an optimal solution of the original problem, we propose another more efficient algorithm which combines the first algorithm, these procedures, and the decomposition method. Furthermore, sufficient conditions are suggested that under them, the problem has a unique optimal solution. Also, a comparison between the recently proposed algorithm and the known ones will be made.     

关于求线性规划初始可行基的生成算法

本文用反例证明了文「１」提出的求线性规划寝可行基的生成算法有错误,并给出了修正的生成算法。     

基于时间切片叠加的警车巡逻路线规划

在城市中,有效的安排警车巡逻对于降低犯罪率,预防潜在犯罪案件发生和及时处理案件具有十分重要的意义.通过一些必要简化首先确定了巡逻方案应当满足的条件以及方案的评价体系.通过随机贪心算法求解足够多的可行静态解,并引入时间片叠加的思想在静态解的基础上应用深度优先搜索算法,将求解动态巡逻问题转化为在有向连通图中寻找使目标函数达到最大的约束环路的问题,最终求得动态巡逻方案.最后,通过实例对模型进行了验证和评价.     

A primal-dual projection method for solving systems of linear inequalities

An algorithm is described for finding a feasible point for a system of linear inequalities. If the solution set has nonempty interior, termination occurs after a finite number of iterations. The algorithm is a projection-type method, similar to the relaxation methods of Agmon, Motzkin, and Schoenberg. It differs from the previous methods in that it solves for a certain “dual” solution in addition to a primal solution.     

Simplicial Branch-and-Reduce Algorithm for Convex Programs with a Multiplicative Constraint

Optimization problems that involve products of convex functions in the objective function or in the constraints arise in a variety of applications. These problems are difficult global optimization problems. During the past 15 years, however, a number of practical algorithms have been proposed for globally solving these types of problems. In this article, we present and validate a branch-and-reduce algorithm for finding a global optimal solution to a convex program that contains an additional constraint on the product of several convex functions. To globally solve this problem, the algorithm instead globally solves an equivalent master problem. At any stage of the algorithm, a disconnected set consisting of a union of simplices is constructed. This set is guaranteed to contain a portion of the boundary of the feasible region of the master problem where a global optimal solution lies. The algorithm uses a new branch-and-reduce scheme to iteratively reduce the sizes of these sets until a global optimal solution is found. Several potential computational advantages of the algorithm are explained, and a numerical example is solved.     

Conic approximation to quadratic optimization with linear complementarity constraints

This paper proposes a conic approximation algorithm for solving quadratic optimization problems with linear complementarity constraints.We provide a conic reformulation and its dual for the original problem such that these three problems share the same optimal objective value. Moreover, we show that the conic reformulation problem is attainable when the original problem has a nonempty and bounded feasible domain. Since the conic reformulation is in general a hard problem, some conic relaxations are further considered. We offer a condition under which both the semidefinite relaxation and its dual problem become strictly feasible for finding a lower bound in polynomial time. For more general cases, by adaptively refining the outer approximation of the feasible set, we propose a conic approximation algorithm to identify an optimal solution or an \(\epsilon \)-optimal solution of the original problem. A convergence proof is given under simple assumptions. Some computational results are included to illustrate the effectiveness of the proposed algorithm.     

Canonical dual approach to solving the maximum cut problem

This paper presents a canonical dual approach for finding either an optimal or approximate solution to the maximum cut problem (MAX CUT). We show that, by introducing a linear perturbation term to the objective function, the maximum cut problem is perturbed to have a dual problem which is a concave maximization problem over a convex feasible domain under certain conditions. Consequently, some global optimality conditions are derived for finding an optimal or approximate solution. A gradient decent algorithm is proposed for this purpose and computational examples are provided to illustrate the proposed approach.