非负约束稀疏优化问题的一个等价性条件

加权l₁最小化是稀疏优化的主流方法之一。本文对带非负约束的l₀最小化问题与加权l₁最小化问题的解之间的关系进行了研究,给出了加权l₁最小化问题的约束矩阵和目标函数的系数是"s-权优"的定义,并通过该定义给出了加权l₁最小化问题的解是带非负约束的l₀最小化问题的解的条件。进一步,本文给出了"s-权优"的充分条件及其具体表示形式,并对其上下界进行了可计算的有效估计。     

关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G₁,G₂,且|G₁|≥2,|G₂|≥2,则称T是G的一个非平凡点割。假定G是一个不含非平凡（k-1）点割的（k-1）-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t> $ \frac{k}{2}$的整数,若G是一个不含（K₂+tK₁）的k-连通图,且G中任意两个不同点对v,w,有d（v）+d（w）≥ $\frac{{3k}}{2} $+t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有$\frac{{\left| {V\left( G \right)} \right|}}{2} $条边使得收缩其中任意一条边后仍是拟k-连通的。     

微分算子和边界双摄动的高阶椭圆型方程的狄立克雷问题

本文研究了在边界和算子摄动相结合的情况下高阶椭圆型方程解的渐近式的构造.如果非摄动问题A₀不在谱上,则摄动问题A_ε的渐近解可按小参数ε的次幂展开;如果A₀在谱上,则在A_ε的渐近解中出现有小参数ε的负幂;同时给出了有关的余项的估计.     

带松弛条件的图的强边着色

给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c：E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ'_(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。在图G中,如果mad(G) < 3并且Δ≤4,那么χ'_(1,0)(G)≤3Δ。并证明如果G是平面图,最大度Δ≥4并且围长最少为7,那么χ'_(1,0)(G)≤3Δ-1。     

外平面图的弱完备染色

假设G=（V,E,F）是一个平面图。如果e₁和e₂是G中两条相邻边且在关联的面的边界上连续出现,那么称e₁和e₂面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χ_vef（G）。2016年,Fabrici等人猜想：每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。     

基于马氏链拟合的一种非负变权组合预测算法及其应用

通过马氏链拟合的方法求取一种新的非负时变权组合预测算法公式.主要工作是:一、对组合预测问题以最小误差为准则给出了马氏链的状态和状态概率初步估计;二、用马氏链拟合状态概率分布时变规律,通过约束多元自回归模型导出了一步转移概率阵的LS解;三、给出一种非负时变权组合预测公式并举一应用实例.     

求解单位L∞范数下带值约束的最大权完美匹配逆问题的算法

通过研究单位L_∞范数下的带值约束的最大权完美匹配逆问题的性质,将单位L_∞范数下最大权完美匹配逆问题转化为求解最大平均交替圈问题,给出一个求解该类问题的一个强多项式时间算法,其时间复杂度为O(n⁴).并通过一个算例,验证了给出的算法的有效性.     

一般Brown桥的解析解、数值解及仿真

对任意区间[t₀,t₁]任意初值为x₀和终值为x₁的Brown桥,即随机微分方程dx=(x₁-x)/(t₁-t)dt+dB(t) x(t₀)=x₀,给出其解析解(包括随机积分解和Fourier级数解),及Milstein数值解并进行期望和方差分析,求得期望函数、期望±标准差曲线和95%置信区间边界曲线.并对不同Brown运动对应的不同轨线实现进行仿真模拟.对一个非真实的近似解加以辨别.     

重大事故规避的危险品运输车辆路径优化研究

基于重大事故规避的思想,建立以最大事故后果最小及运输成本最小为双目标,且事故后果基于实时装载量的危险品运输车辆路径优化模型。基于ε-约束法,设计可求得帕累托最优解的精确算法,该算法包含通过性质求ε下界、规避被支配解的预处理及不可行路径禁止约束3处改进。进一步设计处理大规模问题的多项式时间近似算法,并分析了算法的近似比。最后通过算例对模型和算法进行测试,并通过出灵敏度分析给出管理启示。     

具有非局部效应的时滞SEIR系统的周期行波解

该文研究了一类具有非局部效应和非线性发生率的时滞SEIR系统的周期行波解.首先,定义基本再生数R₀并构造适当的上下解,将周期行波解的存在性转化为闭凸集上非单调算子的不动点问题,利用Schauder不动点定理结合极限理论建立该系统周期行波解的存在性.其次,利用反证法结合比较原理,建立当基本再生数R₀<1时该系统周期行波解的不存在性.     

Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

An extremal problem on potentially Kr,s-graphic sequences

We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(K_r,s,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(K_r,s,n) is potentially K_r,s-graphic, where K_r,s is a r×s complete bipartite graph, i.e., π has a realization G containing K_r,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially K_r,s-graphic, and then we determine σ(K_r,r,n) for r=3,4.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法

逻辑回归是经典的分类方法,广泛应用于数据挖掘、机器学习和计算机视觉.现研究带有程。模约束的逻辑回归问题.这类问题广泛用于分类问题中的特征提取,且一般是NP-难的.为了求解这类问题,提出了嵌套BB(Barzilai and Borwein)算法的分裂增广拉格朗日算法(SALM-BB).该算法在迭代中交替地求解一个无约束凸优化问题和一个带程。模约束的二次优化问题.然后借助BB算法求解无约束凸优化问题.通过简单的等价变形直接得到带程。模约束二次优化问题的精确解,并且给出了算法的收敛性定理.最后通过数值实验来测试SALM-BB算法对稀疏逻辑回归问题的计算精确性.数据来源包括真实的UCI数据和模拟数据.数值实验表明,相对于一阶算法SLEP,SALM-BB能够得到更低的平均逻辑损失和错分率.     

Aspects of semiorders within interval orders

Let s_k(n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an s_k(n)-point semiorder. When k = 1, s₁(n) = n since all interval orders with no two-point antichains are chains. Given (c₁,...,c₅) = (1, 2, 3, 4), it is shown that s₂(n) = c_n for n 4, s₃(n) = c_n for n 5, and for all positive n, s₂ (n+4) =s₂(n)+3, s₃(n+5) = s₃(n)+3. Hence s₂ has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s₃ has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...].

Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern.     

A note on a property of a weak self-similar perfect set

Let S be a compact, weak self-similar perfect set based on a system of weak contractions f_j, j=1,…,m each of which is characterized by a variable contraction coefficient _j(l) as d(f_j(x),f_j(y)) _j(l)d(x,y), d(x,y)<l, l>0. If the relation ∑^m_j=1j(l₀)<1 holds at at least one point l₀, then every nonempty compact metric space is a continuous image of the set S.     

Invariant record processes and applications to best choice modelling

Let X₁, X₂,…be identically distributed random variables from an unknown continuous distribution. Further let I_r(1), I_r(2),…be a sequence of indicator functions defined on X₁, X₂,…by I_r(k) = 0 if k < r, I_r(k) = 1 if X_k is a r-record AND = 0 otherwise. Suppose that we observe X₁, X₂,… at times T₁ < T₂ <… where the T_k's are realisations of some regular counting process (N(τ)) defined on the positive half-line. Having observed [0, τ], say, the problem is to predict the future behaviour of the counting processes (R_r(τ, s))_sτ = # r-records in [τ, s]. More specifically the objective of this paper is to show that these processes can be (inhomogeneous) Poisson processes even if (N(τ))_τ0 has dependent increments.

The strong link between optimal selection and optimal stopping of record sequences or record processes, perhaps not fully recognized so far, is pointed out in this paper. It is shown to lead to a unification of the treatment of problems which, at first sight, are rather different. Moreover the stopping of record processes in continuous time can lead to rigorous and elegant solutions in cases where dynamic programming is bound to fail. Several examples will be given to facilitate a comparison with other methods.     

On the occupation time of an iterated process having no local time

We study the asymptotic behaviour of the occupation time process ∫^t₀ I_A(W₁(L₂(s)))ds, t 0, where W₁ is a standard Wiener process and L₂ is a Wiener local time process at zero that is independent from W₁. We prove limit laws, as well as almost sure upper and lower class theorems. Possible extensions of the obtained results are also discussed.     

Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals

Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I.