图的最大二等分问题的非线性规划算法

基于图的最大二等分问题的半定规划松驰模型 ,本文提出一个非线性规划算法求解该模型 ,得到该半定规划松驰模型的一个次优解 ,并且给出算法的收敛性证明 .数值试验表明该方法可以有效地求解图的最大二等分问题的松驰模型     

求解最大割问题的半定规划松驰的序列线性规划方法

本文基于最大割问题的半定规划松弛,利用矩阵分解的方法给出了与半定规划松弛等价的非线性规划模型,提出一种序列线性规划方法求解该模型.并在适当的条件下,证明了算法的全局收敛性.数值实验表明:序列线性规划方法在时间上要优于半定规划的内点算法.所以序列线性规划方法能更有效地求解大规模的最大割问题的半定规划松弛.     

电路二等分问题的一个强化半定松驰模型

由于电路二等分问题在超大规模集成电路 (VLSI)设计中的基础地位 ,电路二等分半定松驰问题一直引人关注 .能否找到更好的半定规划模型 ,使其为电路二等分问题提供一个更好的下界 ,成为一个重要的研究方向 ;本文在已有半定规划松驰模型的基础上 ,通过增加非线性约束 ,得出电路二等分问题的等价模型 ,再利用提升技巧 ,得到一个强化半定规划松驰模型 .理论证明该模型给出了原有问题的一个更好的下界 ,数值实验也说明了这一点 .     

基于改进的不动点迭代算法的低秩Gram矩阵的恢复

仿射限制条件下的低秩矩阵的恢复问题广泛地出现在控制、信号处理及系统识别等许多领域中.此问题可以凸松弛为带仿射限制条件的矩阵核范数的极小化问题.尽管后者能够转化为标准的半定规划问题求解,但是对于规模较大的矩阵其产生的计算量也很大.为此提出一种新的求解Gram矩阵核范数极小化问题的一阶算法-改进的不动点迭代算法(FPC-BB),并给出了算法的收敛性分析.算法以不动点迭代算法(FPC)中的算子分裂技术为基础,通过改进阈值算子Tv来求解低秩Gram矩阵的恢复问题.同时,还引入Barzilai-Borwein技术进行参数的选取,提高了算法的收敛速度.数值实验显示算法不仅能够很快地将低秩Gram矩阵精确地恢复出来,对于一些非低秩矩阵的恢复问题也能得出较好的结果.     

一种求解半定规划的邻近外梯度算法

本文提出了一种求解半定规划的邻近外梯度算法.通过转化半定规划的最优性条件为变分不等式,在变分不等式满足单调性和Lipschitz连续的前提下,构造包含原投影区域的半空间,产生邻近点序列来逼近变分不等式的解,简化了投影的求解过程.将该算法应用到教育测评问题中,数值实验结果表明,该方法是解大规模半定规划问题的一种可行方法.     

最大割问题和最大平分割问题基于半定规划松弛的近似算法

考虑每条边具有非负权重的无向图, 最大割问题要求将顶点集划分为两个集合使得它们之间的边的权重之和最大. 当最大割问题半定规划松弛的最优解落到二维空间时, Goemans将近似比从0.87856...改进为0.88456. 依赖于半定规划松弛的目标值与总权和的比值的曲线, 此曲线的最低点为0.88456, 当半定规划松弛的目标值与总权和的比值在0.5到0.9044之间时, 利用Gegenbauer多项式舍入技巧, 改进了Zwick的近似比曲线. 进一步, 考虑最大割问题的重要变形------最大平分割问题, 在此问题中增加了划分的两部分的点数相等的要求. 同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形, 并利用前述的Gegenbauer多项式舍入技巧得到0.7091-近似算法.     

基于半定规划松弛的凸二层规划问题算法研究

提出使用凸松弛的方法求解二层规划问题,通过对一般带有二次约束的二次规划问题的半定规划松弛的探讨,研究了使用半定规划(SDP)松弛结合传统的分枝定界法求解带有凸二次下层问题的二层二次规划问题,相比常用的线性松弛方法,半定规划松弛方法可快速缩小分枝节点的上下界间隙,从而比以往的分枝定界法能够更快地获得问题的全局最优解.     

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

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

半定矩阵秩极小的非凸精确松弛

本文主要研究半定矩阵秩极小问题(P)的非凸精确松弛及其性质.首先,为求解问题(P),我们引入其Schatten p-范数(0＜p＜1)松弛,记为(Sp).其次,通过定义半定限制等距常数和半定限制正交常数,我们给出了问题(P)有唯—解的充分条件.最后,利用半定限制等距性质,我们给出了问题(P)和(Sp)有相同唯一解的充分条件.特别地,对任意0＜p＜1,我们还得到—个一致的精确恢复条件.     

稠密k-子图问题的双非负松弛

稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。     

An Isometric Plane Method for Linear Programming

In this paper the following canonical form of a general LP problem, $${\rm max} \ Z=C^TX,$$ $${\rm subject} \ {\rm to} \ AX\geq b$$is considered for $X\in R^n$. The constraints form an arbitrary convex polyhedron $\Omega^m$ in $R^n$. In $\Omega^m$ a strictly interior point is successively moved to a higher isometric plane from a lower one along the gradient function value maximum is found or the infinite value of the objective function is concluded. For an $m\ast n$ matrix $A$ the arithmetic operations of a movement are $O(mn)$ in our algorithm. The algorithm enables one to solve linear equations with ill conditions as well as a general LP problem. Some interesting examples illustrate the efficiency of the algorithm.     

High-Dimensional Shape Fitting in Linear Time

Let $P$ be a set of $n$ points in $\Re^d$. The {\em radius} of a $k$-dimensional flat ${\cal F}$ with respect to $P$, which we denote by ${\cal RD}({\cal F},P)$, is defined to be $\max_{p \in P} \mathop{\rm dist}({\cal F},p)$, where $\mathop{\rm dist}({\cal F},p)$ denotes the Euclidean distance between $p$ and its projection onto ${\cal F}$. The $k$-flat radius of $P$, which we denote by ${R^{\rm opt}_k}(P)$, is the minimum, over all $k$-dimensional flats ${\cal F}$, of ${\cal RD}({\cal F},P)$. We consider the problem of computing ${R^{\rm opt}_k}(P)$ for a given set of points $P$. We are interested in the high-dimensional case where $d$ is a part of the input and not a constant. This problem is NP-hard even for $k = 1$. We present an algorithm that, given $P$ and a parameter $0 < \eps \leq 1$, returns a $k$-flat ${\cal F}$ such that ${\cal RD}({\cal F},P) \leq (1 + \eps) {R^{\rm opt}_k}(P)$. The algorithm runs in $O(nd C_{\eps,k})$ time, where $C_{\eps,k}$ is a constant that depends only on $\eps$ and $k$. Thus the algorithm runs in time linear in the size of the point set and is a substantial improvement over previous known algorithms, whose running time is of the order of $d n^{O(k/\eps^c)}$, where $c$ is an appropriate constant.     

预知工件大小上界的平行机排序问题

平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡,大型计算中的并行计算,柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:C_(max)(极小化机器最大负载makespan)和C_(min)(极大化机器最小负载).在不同的目标下,针对m台平行机的一般情况均给出了问题的下界并设计了半在线算法,某些情况下设计的算法是最优算法.     

Limiting behavior for arrays of row-wise upper extended negatively dependent random variables

Our aim is to obtain deterministic bounds for the row sum elements of a random triangular array introducing, thereunto, a dependence structure for triangular arrays of random variables which extend the concepts of upper and lower extended negatively dependence already known for random variables. Concretely, for triangular arrays \({\{X_{n,k}, 1 \leqq k \leqq n, n \geqq 1\}}\) of row-wise upper extended negatively dependent random variables with dominating sequence \({\{M_{n}, n \geqq 1\}}\) weakly mean dominated by a random variable X and sequences \({\{b_{n}\}}\) of positive constants, conditions are stated to ensure the deterministic boundedness of \({\Sigma^{n}_{k=1}(X_{n,k} - {\mathbb E}X_{n,k})/\sqrt{b_{n} {\rm Log} n}}\), where \({{\rm Log} n := {\rm log} {\rm max}\{n, e\}}\). In particular, a sufficient moment condition is given permitting us to achieve our goal under the rate of the so called “Law of the Logarithm”.     

Pinchings and Norms of Scaled Triangular Matrices

Suppose U is an upper-triangular matrix, and D a nonsingular diagonal matrix whose diagonal entries appear in nondescending order of magnitude down the diagonal. It is proved that $$\|D^{-1}UD\|\ge\|U\|$$ for any matrix norm that is reduced by a pinching. In addition to known examples -weakly unitarily invariant norms - we show that any matrix norm defined by $$\| A \|^{\underline{\underline {{\rm def}}} } \mathop {\max }\limits_{x \ne 0,y \ne 0} {{{\mathop{\rm Re}\nolimits} (x^*Ay)} \over {\phi (x)\psi (y)}},$$ where θ (.) and y (.) are two absolute vector norms, has this property. This includes l p operator norms as a special case.     

倾斜对中的倾斜双模

Tilting pair was introduced by Miyashita in 2001 as a generalization of tilting module. In this paper, we construct a tilting left Endh（C）-right Endh（T）-bimodule for a given tilting pairs （C,T） in modh, where A is an Artin algebra.     

Universal approach to the Takesaki-Takai $\gamma $-duality for crossed products

In this article, we generalize and simplify the proof of the Takesaki-Takai $\gamma $-duality theorem. Assume a morphism \textbf{\textit{$\omega \; :\; G\to Aut\left({\rm A}\right)$}} is a projective representation of the locally compact Abel group \textbf{\textit{$G$}} in \textbf{\textit{$Aut\left({\rm A}\right)$}}, mapping $\gamma \; :\; G\to G$ is continuous, and $\left({\rm A},\; G,\; \omega \right)$ is a dynamic system then there exists isomorphism \[\Upsilon \; :\; Env_{\hat{\omega }} {}^{\gamma } \left(L^{1} \left(\hat{G},\; Env_{\omega } {}^{\gamma } \left(L^{1} \left(G,\; {\rm A}\right)\right)\right)\right)\to {\rm A}\otimes LK\left(L^{2} \left(G\right)\right) \] which is the equivariant for the double dual action \[\hat{\hat{\omega }}\; :\; G\to Aut\left(Env_{\hat{\omega }} {}^{\gamma } \left(L^{1} \left(\hat{G},\; Env_{\omega } {}^{\gamma } \left(L^{1} \left(G,\; {\rm A}\right)\right)\right)\right)\right).\] These results deepen our understanding of the representation theory and are especially interesting given their possible applications to problems of the quantum theory.     

非退化扩散过程的水平集和极集

设X(t)(t∈R )是一个d维非退化扩散过程．本文得到了比原有结果更一般的非退化扩散过程极性的充分条件,证明了对任意u∈Rd,紧集E(0, ∞),有若d=1,则对任意紧集F(?)R, 若d≥2,则对任意紧集E ∈(0, ∞), 其中B(Rd)为Rd上的Borel σ-代数,dim和Dim分别表示Hausdorff维数和Packing 维数．     

About the maximal rank of 3-tensors over the real and the complex number field

Tensor data are becoming important recently in various application fields. In this paper, we consider the maximal rank problem of 3-tensors and extend Atkinson and Stephens’ and Atkinson and Lloyd’s results over the real number field. We also prove the assertion of Atkinson and Stephens: ${{\rm max.rank}_{\mathbb{R}}(m,n,p) \leq m+\lfloor p/2\rfloor n}$ , ${{\rm max.rank}_{\mathbb{R}}(n,n,p) \leq (p+1)n/2}$ if p is even, ${{\rm max.rank}_{\mathbb{F}}(n,n,3)\leq 2n-1}$ if ${\mathbb{F}=\mathbb{C}}$ or n is odd, and ${{\rm max.rank}_{\mathbb{F}}(m,n,3)\leq m+n-1}$ if m < n where ${\mathbb{F}}$ stands for ${\mathbb{R}}$ or ${\mathbb{C}}$ .