A new Lagrangian net algorithm for solving max-bisection problems

The max-bisection problem is an NP-hard combinatorial optimization problem. In this paper, a new Lagrangian net algorithm is proposed to solve max-bisection problems. First, we relax the bisection constraints to the objective function by introducing the penalty function method. Second, a bisection solution is calculated by a discrete Hopfield neural network (DHNN). The increasing penalty factor can help the DHNN to escape from the local minimum and to get a satisfying bisection. The convergence analysis of the proposed algorithm is also presented. Finally, numerical results of large-scale G-set problems show that the proposed method can find a better optimal solutions.     

A Modified Bisection Simplex Method for Linear Programming

1.IntroductionThebisectionmethod,proposedinanearlierpaperbytheauth..[7]texploitsinformationoftheoptimalvaluetospeedupthesolutionprocess-However,themethodrequiresabracketontheoptimalvalueaspartofitsinput,anditspromisinglygoodperformancedependsonwhetherasuitablebracketisavailable;itmayevenfaltosolveaproblemiftheinitialintervalprovideddoesnotcontaintheoptimalvalueactuallyInthispaper,themethodismodifiedformoregeneralpurposeuse-Organizedinanalternativesimplerform,thenewversionnolongerneed8anybrathe…     

A robust Lagrangian-DNN method for a class of quadratic optimization problems

The Lagrangian-doubly nonnegative (DNN) relaxation has recently been shown to provide effective lower bounds for a large class of nonconvex quadratic optimization problems (QAPs) using the bisection method combined with first-order methods by Kim et al. (Math Program 156:161–187, 2016). While the bisection method has demonstrated the computational efficiency, determining the validity of a computed lower bound for the QOP depends on a prescribed parameter \(\epsilon > 0\). To improve the performance of the bisection method for the Lagrangian-DNN relaxation, we propose a new technique that guarantees the validity of the computed lower bound at each iteration of the bisection method for any choice of \(\epsilon > 0\). It also accelerates the bisection method. Moreover, we present a method to retrieve a primal-dual pair of optimal solutions of the Lagrangian-DNN relaxation using the primal-dual interior-point method. As a result, the method provides a better lower bound and substantially increases the robustness as well as the effectiveness of the bisection method. Computational results on binary QOPs, multiple knapsack problems, maximal stable set problems, and quadratic assignment problems illustrate the robustness of the proposed method. In particular, a tight bound for QAPs with size \(n=50\) could be obtained.     

函数方程求根的一种新型大范围收敛迭代法

1引言实际解函数方程f(x)=0(z∈[α,β],f(α)f(β)＜0,f(x~*)=0)时,人们常常希望选用那些仅计算函数值,具有大范围收敛性且效率较高的方法,特别对那些表示式复杂的函数以及病态函数．例如,那种仅在的某个充分小邻域内连续,而在该邻域之外光滑性很差的函数；那种在初始含根区间(α,β)上起伏多变的函数；那种|f(α)|和|f(β)|差别甚大,而x~*又十分靠近绝对值较大者一端的函数等等,这种欲望就更加强烈．     

An infinite precision bracketing algorithm with guaranteed convergence

The computational cost of a bracketing algorithm in the bit model of computation is analyzed, when working with a finite arithmetic of unbounded accuracy. The complexity measure used here is the number of bit operations, seen as a function of the required absolute error of the result. In this model the convergence of the classical bisection method (as well as that of any bracketing method which requires the function sign) is not ensured when no information on the behaviour of the function is available. A modified bisection algorithm with guaranteed convergence is proposed and an upper bound to its computational cost is given.     

A Fast and Effective Algorithm for the Feedback Arc Set Problem

A divide-and-conquer approach for the feedback arc set is presented. The divide step is performed by solving a minimum bisection problem. Two strategies are used to solve minimum bisection problem: A heuristic based on the stochastic evolution methodology, and a heuristic based on dynamic clustering. Empirical results are presented to compare our method with other approaches. An algorithm to construct test cases for the feedback arc set problem with known optimal number of feedback arcs, is also presented.     

LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semidefinite approaches for large sparse instances, we set up a common branch-and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities of the bisection cut polytope described in a recent study by the authors. While the problem specific cuts help to strengthen the linear relaxation significantly, the semidefinite bound profits much more from separating the cycle inequalities of the cut polytope on a slightly enlarged support. Extensive numerical experiments show that this semidefinite branch-and-cut approach without problem specific cuts is a superior choice to the classical simplex approach exploiting bisection specific inequalities on a clear majority of our large sparse test instances from VLSI design and numerical optimization.     

Graph bisection algorithms with good average case behavior

In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixedd≧3, all sufficiently largen and allb=o(n ^{1?1/[(d+1)/2]}), the algorithm finds the minimum bisection for almost alld-regular labelled simple graphs with 2n nodes and bisection widthb. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection widtho(n ^2/3). The algorithm differs from other graph bisection heuristics (as well as from many heuristics for other NP-complete problems) in several respects. Most notably:

1. the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimum bisection,
2. whenever the algorithm produces a bisection, it is guaranteed to be optimal (i.e., the algorithm also produces a proof that the bisection it outputs is an optimal bisection),
3. the algorithm works well both theoretically and experimentally,
4. the algorithm employs global methods such as network flow instead of local operations such as 2-changes, and
5. the algorithm works well for graphs with small bisections (as opposed to graphs with large bisections, for which arbitrary bisections are nearly optimal).

     

Bisecting de Bruijn and Kautz graphs

De Bruijn and Kautz graphs have been intensively studied as perspective interconnection networks of massively parallel computers. One of the crucial parameters of an interconnection network is its bisection width. It has an influence on both communication properties of the network and the algorithmic design. We prove optimal bounds on the edge and vertex bisection widths of the k-ary n-dimensional de Bruijn digraph. This generalizes known results for k = 2 and improves the upper bound for the vertex bisection width. We extend the method to prove optimal upper and lower bounds on the edge and vertex bisection widths of Kautz graphs.     

A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations

Summary A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations is presented in this paper, based on the non-zero value of the topological degree. Further, while the method does not compute the topological degree, it takes care of keeping its non-zero value during the bisections and thus results in a fast bisection algorithm.     

Determining zeroes of increasing Lipschitz functions

Summary We study the average case behavior of suitable algorithms to solve a nonlinear problem in numerical analysis: determining zeroes of increasing Lipschitz functions of one variable. The bisection method (which is optimal with respect to the maximal error over the whole class of functions) is far from being optimal in a more general sense: There are methods which behave like bisection in the worst case but which yield much better results on the average. We prove that the sequentially optimal algorithm found by Sukharev is also optimal in our average case setting.     

Numerical inversion of a general incomplete elliptic integral

We present a numerical method to invert a general incomplete elliptic integral with respect to its argument and/or amplitude. The method obtains a solution by bisection accelerated by half argument formulas and addition theorems to evaluate the incomplete elliptic integrals and Jacobian elliptic functions required in the process. If faster execution is desirable at the cost of complexity of the algorithm, the sequence of bisection is switched to allow an improvement by using Newton’s method, Halley’s method, or higher-order Schröder methods. In the improvement process, the elliptic integrals and functions are computed by using Maclaurin series expansion and addition theorems based on the values obtained at the end of the bisection. Also, the derivatives of the elliptic integrals and functions are recursively evaluated from their values. By adopting 0.2 as the critical value of the length of the solution interval to shift to the improvement process, we suppress the expected number of bisections to be as low as four on average. The typical number of applications of update formulas in the double precision environment is three for Newton’s method, and two for Halley’s method or higher-order Schröder methods. Whether the improvement process is added or not, our method requires none of the procedures to compute the incomplete elliptic integrals and Jacobian elliptic functions but only those to evaluate the complete elliptic integrals once at the beginning. As a result, it runs fairly quickly in general. For example, when using the improvement process, it is around 2–5 times faster than Newton’s method using Boyd’s starter (Boyd (2012) [25]) in inverting E(φ|m)$E\left(\phi \right|m)$, Legendre’s incomplete elliptic integral of the second kind.     

The multi-facility min-max Weber problem

An algorithm is presented to solve the problem of the locating a given number of facilities on the plane amongst given customers so that the maximum weighted distance from any facility to the customers it services is minimised. The algorithm successfully overcomes the allocation aspects of this problem by generating partitions of customers using a method originally designed for graph colouring embedded within a modified bisection search. Problems of 50 customers and three facilities can be solved in entirely acceptable computer times.     

On the eigenvalues of the saddle point matrices discretized from Navier–Stokes equations

In this paper, we proposed an implementation of stochastic perturbation of reduced gradient and bisection (SPRGB) method for optimizing a non-convex differentiable function subject to linear equality constraints and non-negativity bounds on the variables. In particular, at each iteration, we compute a search direction by reduced gradient, and optimal line search by bisection algorithm along this direction yields a decrease in the objective value. SPRGB method is desired to establish the global convergence of the algorithm. An implementation and tests of SPRGB algorithm are given, and some numerical results of large-scale problems are presented, which show the efficient of this approach.     

The Significant Order of Symmetric Tridiagonal Matrices

It is demonstrated that an eigenvalue of a symmetric tridiagonalmatrix as calculated by the Sturm sequence bisection procedure,is determined in general by a leading principal partition ofthe whole matrix. The order of this leading principal partitionis called the significant order of the matrix. The significantorder depends upon the specific eigenvalue being calculated,and upon the working precision of the computer. This numericalphenomenon may be employed to accelerate the bisection procedure.In applications it either indicates the adequacy or otherwiseof the working precision for finite matrices, or in the caseof theoretically infinite matrices, the effective truncationorder for the precision employed.     

Interval Newton/generalized bisection when there are singularities near roots

Interval Newton methods in conjunction with generalized bisection are important elemetns of algorithms which find theglobal optimum within a specified box X ⁿ of an objective function whose critical points are solutions to the system of nonlinear equationsF(X)=0with mathematical certainty, even in finite presision arithmetic. The overall efficiency of such a scheme depends on the power of the interval Newton method to reduce the widths of the coordinate intervals of the box. Thus, though the generalized bisection method will still converge in a box which contains a critical point at which the Jacobian matrix is singular, the process is much more costly in that case. Here, we propose modifications which make the generalized bisection method isolate singular solutions more efficiently. These modifications are based on an observation about the verification property of interval Newton methods and on techniques for detecting the singularity and removing the region containing it. The modifications assume no special structure forF. Additionally, one of the observations should also make the algorithm more efficient when finding nonsingular solutions. We present results of computational experiments.     

Sur la distance à l'instabilité de polynômes matriciels quadratiques

A bisection method is developed for computing the distance to instability of quadratic matrix polynomials. The computation takes rounding errors into account.     

社会化商务中消费者感知推荐信任的聚类方法研究

新兴社会化商务社会中人与人之间的高交互性及推荐信息的海量化和高动态性,对平台分析消费者感知信任提出了新的挑战。然而,对推荐信息进行聚类难以体现消费者主观性及主体间关系。本文将感知推荐信任聚类问题转化为复合网络划分问题,将主观逻辑方法与基于Normal矩阵的谱平分方法相结合构建社会化商务中消费者感知推荐信任的聚类方法。首先,将推荐信息转化为感知推荐信任,然后,从社交网络中抽取感知推荐信任相似度与关系亲密度网络,并构建Normal矩阵用谱平分方法进行划分。最后,通过多组仿真实验证明了该方法的实用性和有效性。该方法能够为社会化商务中消费者信任的分析提供新视角,为平台制定精准化营销策略提供支持。     

Can we approximate zeros of functions with nonzero topological degree?

The bisection method provides an affirmative answer for scalar functions. We show that the answer is negative for bivariate functions. This means, in particular, that an arbitrary continuation method cannot approximate a zero of every smooth bivariate function with nonzero topological degree.     

斜变换ST的演化生成与快速算法

１．引言 含有“斜”基向量的正交变换（斜变换 ＳＴ）概念是由 Ｅｎｏｍｏｔｏ ＆ Ｓｈｉｂａｔａ（１９７１）提出的［１］．斜向量是一个在其范围内呈均匀阶梯下降的离散锯齿波形．对于亮度逐渐改变的图象,用斜向量来表示是适合的． Ｅｎｏｍｏｔｏ 　＆ 　Ｓｈｉｂａｔａ仅考虑了斜向量长度为 ４和 ８的情况．Ｐｒａｔｔ等人利用递推性将 ＳＴ推广到 Ｎ＝ ２ｍ阶的情形,给出了 ＳＴ的一般定义［２］,并与其它变换进行了比较［３］．ＳＴ已成功地用在图象编码上,而且在非正弦类交换编码的应用中,斜变换的效果最好［２,３］． Ａｈ…