Global Escape Strategies for Maximizing Quadratic Forms over a Simplex

Consider the problem of maximizing a quadratic formover the standard simplex.Problems of this type occur, e.g., in the search for the maximum (weighted)clique in an undirected graph.In this paper, copositivity-based escape proceduresfrom inefficient local solutions are rephrased into lower-dimensionalsubproblems which are again of the same type. As a result, analgorithm is obtained which tries to exploit favourable data constellationsin a systematic way, and to avoid the worst-case behaviourof such NP-hard problems whenever possible. First results onfinding large cliques in DIMACS benchmark graphs are encouraging.     

The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems

We prove that the existence of a polynomial time-approximation algorithm (where < 1 is a fixed constant)for a class of independent set problems, leads to a polynomial timeapproximation algorithm with approximation ratio strictly smallerthan 2 for vertex covering, while the non-existence of such analgorithm induces a lower bound on the ratio of every polynomialtime approximation algorithm for vertex covering. We also prove asimilar result for a (maximization) convex programming problemincluding quadratic programming as subproblem.     

企业生产安全投入与监管的演化博弈

针对企业生产安全控制问题,建立企业与政府安全生产主管部门之间的博弈模型,利用演化博弈理论的多总体复制子动态方程,给出了企业安全投入与政府监管在博弈互动中的群体演化选择趋势,揭示了经济参数对演化博弈过程的影响规律.研究表明:企业安全投入成本C、企业无安全投入导致的经济损失F、政府安全监管成本D、政府不作为的损失G等经济参数对博弈双方的策略选择有重要影响,特别是C与F、D与G的大小关系,直接决定企业与政府的演化博弈规律,当F>C且G>D时,形成循环的演化博弈趋势,最有利于政府对企业生产安全进行监管.C/F和D/G分别为安全生产社会环境对企业安全投入和政府监管行为产生抑制或促进作用的群体选择总体比例临界值.     

外卖食品安全问题的演化博弈分析

运用演化博弈论的方法对外卖商家之间,订餐平台监管部门和外卖商家之间相互作用时策略选择行为进行分析.结果表明:当外卖商家生产不合格的外卖收益大于生产合格外卖的收益、订餐平台监督部门对生产不合格外卖的商家处罚力度过轻或对外卖合格性的检测成本过高时,不合格外卖生产必然发生.要确保外卖商家生产合格外卖,就必须对生产不合格外卖的商家进行严惩,降低生产不合格外卖的预期收益.同时,要加强订餐平台建设,降低监管成本,保证监管部门严格执法.     

无界域上不定二次规划的一个算法

本文给出了无界域上不定二次规划一个算法 ,该算法将不定二次规划转化为一系列凸二次规划 ,并证明了算法的收敛性 .     

New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints

In Floudas and Visweswaran (1990, 1993), a deterministic global optimization approach was proposed for solving certain classes of nonconvex optimization problems. An algorithm, GOP, was presented for the solution of the problem through a series ofprimal andrelaxed dual problems that provide valid upper and lower bounds respectively on the global solution. The algorithm was proved to have finite convergence to an -global optimum. In this paper, new theoretical properties are presented that help to enhance the computational performance of the GOP algorithm applied to problems of special structure. The effect of the new properties is illustrated through application of the GOP algorithm to a difficult indefinite quadratic problem, a multiperiod tankage quality problem that occurs frequently in the modeling of refinery processes, and a set of pooling/blending problems from the literature. In addition, extensive computational experience is reported for randomly generated concave and indefinite quadratic programming problems of different sizes. The results show that the properties help to make the algorithm computationally efficient for fairly large problems.     

两类零售企业竞争策略选择的演化博弈分析

运用演化博弈理论分析了在同一市场两类零售企业行为的演化过程.根据两类企业竞争策略的复制者动态方程,分析了两类企业策略选择的演化均衡特征,并分析了一些主要参数对企业竞争策略选择的影响.结果表明,企业的相对实力和两企业竞争成本的乘积对企业行为的演化起着至关重要的作用.     

The social diversification of fashion

We propose a model to investigate the dynamics of fashion traits purely driven by social interactions. We assume that people adapt their style to maximize social success, and we describe the interaction as a repeated group game in which the payoffs reflect the social norms dictated by fashion. On one hand, the tendency to imitate the trendy stereotypes opposed to the tendency to diverge from them to proclaim identity; on the other hand, the exploitation of sex appeal for dating success opposed to the moral principles of the society. These opposing forces promote diversity in fashion traits, as predicted by the modeling framework of adaptive dynamics. Our results link the so-called horizontal dynamics—the primary driver of fashion evolution, compared with the vertical dynamics accounting for interclass and economic drivers—to style variety.     

师徒制知识共享敌意的演化趋势研究

师徒制知识共享作为组织内知识转移,尤其是隐性知识转移的重要方式,却在组织内更多以知识囤积或知识排斥的知识共享敌意形式存在。基于师徒制知识共享敌意的效用分析,采用复制动态的非对称演化博弈刻画了组织内师徒制知识共享敌意的演化趋势。研究发现,当师傅群成员知识囤积的负效用超过其正效用、且徒弟群成员知识排斥的负效用大于其所付出的成本时,才能通过有效降低师徒制知识共享敌意来提高师徒制知识共享对组织的贡献程度;组织采用一定的激励机制对于降低师徒制知识共享敌意的发生效果显著。     

Generation of disjointly constrained bilinear programming test problems

This paper describes a technique for generating disjointly constrained bilinear programming test problems with known solutions and properties. The proposed construction technique applies a simple random transformation of variables to a separable bilinear programming problem that is constructed by combining disjoint low-dimensional bilinear programs.     

基于三方博弈的绿色技术创新演化研究

基于有限理性假设,构建了绿色技术创新演化过程中政府、企业和公众三方的博弈模型,应用MATLAB软件进行仿真研究,探讨不同参数对促进绿色技术创新演化的影响。研究发现：政府支持绿色技术创新能够获得的收益、政府给予企业奖励与罚金的高低、公众参与监督所需付出的成本,以及公众给予政府的负反馈程度等,都直接影响政府、企业、公众三方最终的决策,政府、企业、公众三方最终的策略选择不受自身初始意愿改变及其他两方初始意愿高低的影响。基于仿真研究,从政府、企业、公众三个维度,提出了促进绿色技术创新演化的相关建议。     

The structure of stratified systems and the structure of mobility: A first approximation to a structural theory of vertical mobility

This essay summarizes an inquiry that explores relations between the structure of stratified systems and the processes of vertical mobility. The inquiry considers economic stratification (the distribution of wealth) and is directed to determining whether the structural properties of stratification systems are sufficient to generate basic patterns in vertical mobility observed in empirical research, especially, the rank‐distance effect. In particular, the question is whether these patterns can be generated even if movement is constrained by nothing more than the size of the population over which wealth is distributed and the total amount of wealth to be distributed. Our results show that the rank‐distance effect emerges even under these minimal assumptions and, further, that rates and distances of vertical mobility are closely related to changes in these boundary parameters of a stratified system. The basic theory developed to relate structure and mobility provides results that are highly consistent with many empirical observations. It also challenges existing claims concerning the nature of the mechanisms determining the relative status immobility of most people in large scale systems. The theory implies that the way in which system structure constrains opportunity for movement is, by itself, sufficient to produce this result and others commonly observed.     

An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets

Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1(k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n-2k-2. Then G has a spanning k-ended tree.     

有限理性条件下演化博弈行为分析

基于博弈双方有限理性的假设,运用动力系统的相关理论和方法对一般2×2非对称演化博弈过程建立了动态复制方程,并对博弈双方在演化过程中的行为进行了分析,得出博弈双方交互系统均衡点及稳定性相应的结论及其全部动力学行为.     

供应链网络道德风险演化与仿真研究

针对目前供应链网络存在的越来越严重的道德风险问题,利用演化博弈和系统动力学理论,从供应链网络结构入手,对其演化过程进行了研究。首先基于供应商之间合作过程中的诚信和败德行为,建立供应链网络同级企业间道德风险的演化博弈模型,并分析了其演化路径。其次通过对制造商和供应商之间博弈的动态性分析,建立供应链网络上下游企业间道德风险演化的SD模型,并对其演化过程进行了仿真分析。研究结果表明:供应链网络道德风险的演化结果取决于网络内败德企业获得的超额收益、收益调整程度、惩罚力度和惩罚机制。另外,罚款力度大小与供应链网络道德风险演化的动态性密切相关;动态惩罚机制在其演化的波动性控制方面,具有明显效果。     

基于系统动力学的拆迁行为演化博弈分析

为研究征收拆迁中政府和被拆迁人的拆迁行为选择及其影响因素,在政府和被拆迁人具有有限理性的前提下,构建了拆迁行为的演化博弈模型,对政府和被拆迁人策略选择的互动行为及稳定状态进行了分析。在此基础上,进一步建立系统动力学模型进行仿真,分析不同因素对拆迁中双方行为的动态影响。结果表明:政府的行政成本和外部缺失对政府的决策有明显的影响;拆迁补偿费用和斗争成本对被拆迁人的行为有显著影响。可以从合理制定拆迁补偿费用、完善沟通机制、制定科学应对机制以及提升政府公信力等方面促进拆迁项目的顺利进行。     

种群模型在生物进化研究中的应用

介绍了进化动力学的基本知识和研究现状,把表型特征引入种群动力学模型,进而推导出进化适应动力学模型;总结了如何建立适应度函数以及分析研究进化动力学行为的一般理论和方法,并列举实例,模拟分析验证前面所陈述的理论方法,模拟结果说明收获对生物进化产生重要影响,并有效解释了物种多样性。     

Schrodinger算子的极大耗散扩张

本文研究Ｓｃｈｒｏｄｉｎｇｅｒ算子的极大耗散扩张，引入广义不定度规空间，得到在自然边界空间中，Ｓｃｈｒｏｄｉｎｇｅｒ算子极大耗散扩张表示形式，为进一步研究非线性Ｓｃｈｒｏｄｉｎｇｅｒ方程无穷维动力系统的长期混沌行为作准备。     

虚拟科技创新团队知识转移稳定性研究——基于演化博弈视角

虚拟科技创新团队作为一种优势资源的有效整合机制和从事创新性工作的知识密集型组织,知识的有效转移和持续流动是其成功的关键。本文运用演化博弈论的方法,将转移效应、制度因素、成本损失等影响知识转移的主要因素作为研究问题的关注角度,以知识转移效用函数为切入点,对虚拟科技创新团队知识转移的条件进行分析,系统研究了团队内部知识转移的稳定性、持续性以及演化趋势,并在此基础上提出了改善虚拟科技创新团队知识转移的对策建议。     

Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems

In Balas and Niehaus (1996), we have developed a heuristic for generating large cliques in an arbitrary graph, by repeatedly taking two cliques and finding a maximum clique in the subgraph induced by the union of their vertex sets, an operation executable in polynomial time through bipartite matching in the complement of the subgraph. Aggarwal, Orlin and Tai (1997) recognized that the latter operation can be embedded into the framework of a genetic algorithm as an optimized crossover operation. Inspired by their approach, we examine variations of each element of the genetic algorithm—selection, population replacement and mutation—and develop a steady-state genetic algorithm that performs better than its competitors on most problems.