多项式分裂可行问题

本文研究多项式分裂可行问题,即由多项式不等式定义的分裂可行问题,包括凸与非凸、可行与不可行的问题;给出多项式分裂可行问题解集的半定松弛表示;研究其半定松弛化问题的性质;并基于这些性质建立求解多项式分裂可行问题的半定松弛算法.本文在较为一般的条件下证明了,如果分裂可行问题有解,则可通过本文建立的算法求得一个解点;如果问题...     

0-1多项式规划问题的SDP松弛方法(英)

本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法. 我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛, 该 松弛产生的界比标准线性松弛产生的界更紧. 我们还利用 拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP 松弛的新方法.     

图的特征多项式的若干性质

图的特征多项式有许多性质，本文给出了特征多项式的指数表达式，特征多项式的导数的几个不同表达式以及高阶导数的图论意义。     

矩阵及其多项式的若干问题研究

利用多项式理论、线性空间理论研究了矩阵及其多项式的一些性质.     

箱覆盖问题的半定松驰算法

箱覆盖问题是NP困难问题中的经典问题，得到了广泛地研究，九十年代以来，半定松驰策略被用来求解组合优化问题，取得了很好的结果[13]，本文首次给箱覆盖问题的半定松驰算法，算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。     

张量A和A~k的Z-特征值的关系及其应用

给出了张量A和A的k次幂A~k的Z-特征值的关系,作为应用,给出了弱对称非负张量Z-谱半径的新下界估计式,改进了某些已有结果.     

张量的一个新S-型特征值定位集及其应用

通过分裂集合N={1,2,…,n}为子集S及其补集S得到张量的一个比文献中Qi和Li等给出的定位集更小的新S-型特征值定位集,并由该定位集得到了张量正定性判定的一个充分条件和非负张量谱半径的一个更优上界.     

关于树的谱半径的一个注记

图的邻接矩阵的最大特征值称为图的谱半径．对于n≥8,1≤k≤n＋23,本文确定了n个顶点和至少有惫个顶点度不少于3的树中具有谱半径最大的树．     

不同尺度下多项式滤波器的优化算法

１　　引　言 在小波分析的应用中,紧支撑正交对称的小波是非常可贵的．尤其是对称性,它在实际应用中具有非常重要的意义．但Daubechies的具有紧支撑正交小波无任何对称性和反对称性（除Haar小波外）．为了克服这一不足,崔锦泰和王建忠［１］提出了样条小波,样条小波用失去正交性换来了小波的对称性．A.Cohen［２］等引入了双正交小波似乎解决了这一问题,但它需要两个对偶的小波．匡正［３］等采用了小波的分式滤波器构造出了既正交又对称的小波,但却没有有限的支撑区间．本文欲采用优化的方法给出了一种构造具有任意正则性的多项式…     

单背包问题的半定松弛算法

首先给出了单背包问题的秩1半定松驰规划，然后在此基础上提出了求解该问题的半定松驰随机算法KSSD。分析结果表明：（1）当σ＞0.19时，算法KSSD的近似比就会超过0.27。（2）算法KSSD中的参数θ对某种大规模情形将不起作用。     

Unconstrained and constrained global optimization of polynomial functions in one variable

In Floudas and Visweswaran (1990), a new global optimization algorithm (GOP) was proposed for solving constrained nonconvex problems involving quadratic and polynomial functions in the objective function and/or constraints. In this paper, the application of this algorithm to the special case of polynomial functions of one variable is discussed. The special nature of polynomial functions enables considerable simplification of the GOP algorithm. The primal problem is shown to reduce to a simple function evaluation, while the relaxed dual problem is equivalent to the simultaneous solution of two linear equations in two variables. In addition, the one-to-one correspondence between the x and y variables in the problem enables the iterative improvement of the bounds used in the relaxed dual problem. The simplified approach is illustrated through a simple example that shows the significant improvement in the underestimating function obtained from the application of the modified algorithm. The application of the algorithm to several unconstrained and constrained polynomial function problems is demonstrated.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.     

求解多项式规划的一个全局最优化算法

提出一个求解带箱子约束的一般多项式规划问题的全局最优化算法, 该算法包含两个阶段, 在第一个阶段, 利用局部最优化算法找到一个局部最优解. 在第二阶段, 利用一个在单位球上致密的向量序列, 将多元多项式转化为一元多项式, 通过求解一元多项式的根, 找到一个比当前局部最优解更好的点作为初始点, 回到第一个 阶段, 从而得到一个更好的局部最优解, 通过两个阶段的循环最终找到问题的全局最优解, 并给出了算法收敛性分析. 最后, 数值结果表明了算法是有效的.     

Some remarks on the deterministic particle swarm optimization algorithm

In this paper, we give a simple proof for the convergence of the deterministic particle swarm optimization algorithm under the weak chaotic assumption and remark that the weak chaotic assumption does not relax the stagnation assumption in essence. Under the spectral radius assumption, we propose a convergence criterion for the deterministic particle swarm optimization algorithm in terms of the personal best and neighborhood best position of the particle that incorporates the stagnation assumption or the weak chaotic assumption as a special case.     

A -functional and the rate of convergence of some linear polynomial operators

We show that the -functional

where , is equivalent to the rate of convergence of a certain linear polynomial operator. This operator stems from a Riesz-type summability process of expansion by Legendre polynomials. We use the operator above to obtain a linear polynomial approximation operator with a rate comparable to that of the best polynomial approximation.

     

Some results on the ordering of the Laplacian spectral radii of unicyclic graphs

A unicyclic graph is a graph whose number of edges is equal to the number of vertices. Guo Shu-Guang [S.G. Guo, The largest Laplacian spectral radius of unicyclic graph, Appl. Math. J. Chinese Univ. Ser. A. 16 (2) (2001) 131–135] determined the first four largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices. In this paper, we extend this ordering by determining the fifth to the ninth largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices.     

GMRES and the minimal polynomial

We present a qualitative model for the convergence behaviour of the Generalised Minimal Residual (GMRES) method for solving nonsingular systems of linear equationsAx =b in finite and infinite dimensional spaces. One application of our methods is the solution of discretised infinite dimensional problems, such as integral equations, where the constants in the asymptotic bounds are independent of the mesh size.Our model provides simple, general bounds that explain the convergence of GMRES as follows: If the eigenvalues ofA consist of a single cluster plus outliers then the convergence factor is bounded by the cluster radius, while the asymptotic error constant reflects the non-normality ofA and the distance of the outliers from the cluster. If the eigenvalues ofA consist of several close clusters, then GMRES treats the clusters as a single big cluster, and the convergence factor is the radius of this big cluster. We exhibit matrices for which these bounds are tight.Our bounds also lead to a simpler proof of existing r-superlinear convergence results in Hilbert space.This research was partially supported by National Science Foundation grants DMS-9122745, DMS-9423705, CCR-9102853, CCR-9400921, DMS-9321938, DMS-9020915, and DMS-9403224.     

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation.