非线性约束条件下的梯度投影方法

§1.引言 考虑问题:其中R={x∈E~n|h_i(x)≤0,i=1,…,m},并且满足 (H1)h_i(x),i=1,…,m为一阶连续可微的凸函数;f(x)为一阶连续可微函数。 (H2)对A_x∈R:{△h_i(x)|i∈J_0(x)}为线性无关的向量组,其中J_0(x)={i|h_i(x)=0}。 对这类非线性约束的极值问题,以往的梯度投影方法是先对切面做梯度的投影,然后拉回到可行区域,原因是梯度在切面上的投影往往已不是可行方向。本文改变了以往     

STEINER MINIMAL TREES FOR BAR WAVES

A Steiner minimal tree (SMT) for a set of points P in the plane is a shortest networkinterconnecting P.The construction of a SMT for a general set P is known to be an NP-completeproblem.Recently,SMTs have been constructed for special sets P such as ladders,splitting trees,zigzag lines and co-circular points.In this paper we study SMTs for a wide class of point-sets calledmild bar wave.We show that a SMT for a mild bar wave must assume a special form,thus the numberof trees needed to be inspected is greatly reduced.Furthermore if a mild bar wave is also a mild rectan-gular wave,then we produce a Steiner tree constructible in linear time whose length can exceed thatof a SMT by an amount bounded by the difference in heights of the two endpoints of the rectangularwave,thus independent of the number of points.When a rectangular wave satisfies some otherconditions (including ladders as special cases),then the Steiner tree we produced is indeed a SMT.     

关于等价中介殆周期函数和Dohr殆周期函数

当且仅当Bohr殆周期是殆周期时,Hausdorff群中的连续复值函数是一个Bohr殆周期函数。     

陡度引理的强化与应用

陡度引理是利用一个直观的原理得到的、研究线性约束非线性规划算法收敛性的有力工具。本文讨论了它的强化形式与应用。     

为什么在线性规划的内点算法中要将目标函数非线性化?

本文通过讨论算法的收敛速度和时间复杂性的关系,提出理解和发展线性规划内点算法的一个新思想。     

阀门布局问题的一个最优性判别条件

给定非空点集x及其n对非空子集x_i,y_i,x_i∩y_i=φ(i=1,2,…,n)。找出一个图G,满足条件(a)V(G)=x;(b)对i=1,2,…,n,G皆有连通子图G_i,使x_i(?)V(G_i)和y_i∩V(G_i)=φ,且使|E(G)|最小。本文指出上述问题的一个最优性判别条件;并利用Hall定理及若干引理给出严格的数学证明。     

广义二分搜索及其在 LP 多项式算法复杂度证明中的应用

Khachiyan 和 Karmarkar 方法的提出,不仅解决了长期悬而未决的线性规划(LP)问题的多项式时间算法的存在性问题,而且开辟了优化算法设计上新的方法论体系.目前的兴趣之一是把这一方法论体系应用到一般的连续优化问题中去.一个组合优化问题,同一般优化问题一样,可以表达成一个二元组((?),c),其中(?)是可行解集合,c 是定义在(?)上的实目标函数.对于组合问题,一般地,(?)是离     

计算复杂性理论的近况与展望

本文是有关计算复杂性方面的综述,笔者参加了1985年到1986年间在美国加里福尼亚大学举行的有关这一理论方面的几次学术会议,就从这活动中得到的信息作一详细介绍,同时谈一些自己的看法。     

带基数约束的次模+超模(BP)函数最大化问题的流算法

本文研究在基数约束下具有单调性的次模+超模函数最大化问题的流模型。该问题在数据处理、机器学习和人工智能等方面都有广泛应用。借助于目标函数的收益递减率（$\gamma$）,我们设计了单轮读取数据的过滤-流算法,并结合次模、超模函数的全局曲率（$\kappa^{g}$）得到算法的近似比为$\min\left\{\frac{（1-\varepsilon）\gamma}{2^{\gamma}},1-\frac{\gamma}{2^{\gamma}（1-\kappa^{g}）^{2}}\right\}$。数值实验验证了过滤-流算法对BP最大化问题的有效性并且得出：次模函数和超模函数在同量级条件下,能保证在较少的时间内得到与贪婪算法相同的最优值。     

点到集映像和点到集映像族的连续化

一个最优化算法的迭代过程,可以看做一个点到集映像的取值过程。从这个观念出发,Zangwill建立了全局收敛定理,统一了许多算法的收敛性证明。但是,同一个算法可以看做许多不同的点到集映像的取值过程。事实上,把一点对应于从该点按算法可能达到的下一点的全体形成的点到集映像称为算法所对应的点到集映像,那么,任一点到集映像,若它的像集于任一点外都包含算法所对应的点到集映像的像集,其取值过程均包含了