Approximation of non-monotone multivalued differential inclusions

An approximation of non-monotone, multivalued differential inclusions,the so-called hemivariationa] inequalities, is presented. Arelation between the approximation problem and the problem offinding a substationary point of an approximation of the correspondingpotential function is also established. This relation makesit possible to solve the approximated problem by using nonsmooth,non-convex optimization methods. Some numerical experimentsare also presented.     

Large solutions to non-monotone semilinear elliptic systems

We present the existence of entire large positive radial solutions for the non-monotonic system Δu=p(|x|)g(v), Δv=q(|x|)f(u) on Rn where n?3. The functions f and g satisfy a Keller-Osserman type condition while nonnegative functions p and q are required to satisfy the decay conditions and . Further, p and q are such that min(p,q) does not have compact support.     

Efficient hybrid encryption from ID-based encryption

This paper deals with generic transformations from ID-based key encapsulation mechanisms (IBKEM) to hybrid public-key encryption (PKE). The best generic transformation known until now is by Boneh and Katz and requires roughly 704-bit overhead in the ciphertext. We present new generic transformations that are applicable to partitioned IBKEMs. A partitioned IBKEM is an IBKEM that provides some extra structure. Such IBKEMs are quite natural and in fact nearly all known IBKEMs have this additional property. Our first transformation yields chosen-ciphertext secure PKE schemes from selective-ID secure partitioned IBKEMs with a 256-bit overhead in ciphertext size plus one extra exponentiation in encryption/decryption. As the central tool a Chameleon Hash function is used to map the identities. We also propose other methods to remove the use of Chameleon Hash, which may be of independent technical interest. Applying our transformations to existing IBKEMs we propose a number of novel PKE schemes with different trade-offs. In some concrete instantiations the Chameleon Hash can be made “implicit” which results in improved efficiency by eliminating the additional exponentiation. Since our transformations preserve the public verifiability property of the IBE schemes it is possible to extend our results to build threshold hybrid PKE schemes. We show an analogue generic transformation in the threshold setting and present a concrete scheme which results in the most efficient threshold PKE scheme in the standard model.     

On the existence of non-monotone non-oscillating wavefronts

We present a monostable delayed reaction–diffusion equation with the unimodal birth function which admits only non-monotone wavefronts. Moreover, these fronts are either eventually monotone (in particular, such is the minimal wave) or slowly oscillating. Hence, for the Mackey–Glass type diffusive equations, we answer affirmatively the question about the existence of non-monotone non-oscillating wavefronts. As it was recently established by Hasik et al. and Ducrot et al., the same question has a negative answer for the KPP-Fisher equation with a single delay.     

A space efficient direct access data structure

Given a file T, we suggest a data structure based on pruning a Huffman shaped Wavelet tree (WT) according to the underlying skeleton Huffman tree that enables direct access to the i-th element of T. This pruned WT is especially designed to support faster random access and save memory storage, at the price of less effective rank and select operations, as compared to the original Huffman shaped WT. The savings are significant only if the underlying alphabet is large enough. We give empirical evidence that when memory storage is of main concern, our suggested data structure generally outperforms other direct access techniques such as those due to Külekci, dacs and sampling, with a slowdown as compared to dacs and fixed length encoding.     

Global dynamics of a nonlocal population model with age structure in a bounded domain:A non-monotone case

We study the global dynamics of a nonlocal population model with age structure in a bounded domain. We mainly concern with the case where the birth rate decreases as the mature population size become large. The analysis is rather subtle and it is inadequate to apply the powerful theory of monotone dynamical systems. By using the method of super-sub solutions, combined with the careful analysis of the kernel function in the nonlocal term, we prove nonexistence, existence and uniqueness of positive steady states of the model.Moreover, due to the mature individuals do not diffuse, the solution semiflow to the model is not compact. To overcome the difficulty of non-compactness in describing the global asymptotic stability of the unique positive steady state, we first establish an appropriate comparison principle. With the help of the comparison principle,we can employ the theory of dissipative systems to obtain the global asymptotic stability of the unique positive steady state. The main results are illustrated with the nonlocal Nicholson's blowflies equation and the nonlocal Mackey-Glass equation.     

Deterministic homogenization of non-linear non-monotone degenerate elliptic operators

Deterministic homogenization has been till now applied to the study of monotone operators, the determination of the limiting problem being systematically based on the monotonicity of the operator under consideration. Here we mean to show that deterministic homogenization also tackle non-monotone operators. More precisely, under an abstract general hypothesis, we study the homogenization of non-linear non-monotone degenerate elliptic operators. We obtain some general homogenization result, which result is applied to the resolution of several concrete homogenization problems such as the periodic homogenization and the almost periodic homogenization problems. Our main tool is the theory of homogenization structures.     

A generalized worst-case complexity analysis for non-monotone line searches

We study the worst-case complexity of a non-monotone line search framework that covers a wide variety of known techniques published in the literature. In this framework, the non-monotonicity is controlled by a sequence of nonnegative parameters. We obtain complexity bounds to achieve approximate first-order optimality even when this sequence is not summable.

     

求解低秩矩阵恢复问题的非单调交替梯度方向法

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了...     

有界约束半光滑方程组的非单调投影信赖域方法

投影信赖域策略结合非单调线搜索算法解有界约束非线性半光滑方程组.基于简单有界约束的非线性优化问题构建信赖域子问题,半光滑类牛顿步在可行域投影得到投影牛顿的试探步,获得新的搜索方向,结合非单调线搜索技术得到回代步,获得新的步长.在合理的条件下,证明算法不仅具有整体收敛性且保持超线性收敛速率.引入非单调技术能克服高度非线性的病态问题,加速收敛性进程,得到超线性收敛速率.     

Traveling waves for nonlocal and non-monotone delayed reaction-diffusion equations

We study the existence of traveling wave solutions for a nonlocal and non-monotone delayed reaction-diffusion equation. Based on the construction of two associated auxiliary reaction diffusion equations with monotonicity and by using the traveling wavefronts of the auxiliary equations, the existence of the positive traveling wave solutions for c 〉 c. is obtained. Also, the exponential asymptotic behavior in the negative infinity was established. Moreover, we apply our results to some reactiondiffusion equations with spatio-temporal delay to obtain the existence of traveling waves. These results cover, complement and/or improve some existing ones in the literature.     

On the existence of oscillating solutions in non-monotone Mean-Field Games

For non-monotone single and two-populations time-dependent Mean-Field Game systems we obtain the existence of an infinite number of branches of non-trivial solutions. These non-trivial solutions are in particular shown to exhibit an oscillatory behaviour when they are close to the trivial (constant) one. The existence of such branches is derived using local and global bifurcation methods, that rely on the analysis of eigenfunction expansions of solutions to the associated linearized problem. Numerical analysis is performed on two different models to observe the oscillatory behaviour of solutions predicted by bifurcation theory, and to study further properties of branches far away from bifurcation points.     

The gap between monotone and non-monotone circuit complexity is exponential

A. A. Razborov has shown that there exists a polynomial time computable monotone Boolean function whose monotone circuit complexity is at leastn ^{c losn} . We observe that this lower bound can be improved to exp(cn ^1/6–o(1)). The proof is immediate by combining the Alon—Boppana version of another argument of Razborov with results of Grötschel—Lovász—Schrijver on the Lovász — capacity, of a graph.     

Preconditioning non-monotone gradient methods for retrieval of seismic reflection signals

The core problem in seismic exploration is to invert the subsurface reflectivity from the surface recorded seismic data. However, most of the seismic inverse problems are ill-posed by nature. To overcome the ill-posedness, different regularized least squares methods are introduced in the literature. In this paper, we developed a preconditioning non-monotone gradient method, proved it converges with R-superlinear rate and applied it to seismic deconvolution and imaging. Numerical examples demonstrate that the method is efficient. It helps to improve the resolution of the seismic inversions.     

On the worst-case evaluation complexity of non-monotone line search algorithms

A general class of non-monotone line search algorithms has been proposed by Sachs and Sachs (Control Cybern 40:1059–1075, 2011) for smooth unconstrained optimization, generalizing various non-monotone step size rules such as the modified Armijo rule of Zhang and Hager (SIAM J Optim 14:1043–1056, 2004). In this paper, the worst-case complexity of this class of non-monotone algorithms is studied. The analysis is carried out in the context of non-convex, convex and strongly convex objectives with Lipschitz continuous gradients. Despite de nonmonotonicity in the decrease of function values, the complexity bounds obtained agree in order with the bounds already established for monotone algorithms.     

A new non-monotone self-adaptive trust region method for unconstrained optimization

In this paper, based on a simple model of trust region sub-problem, we combine the trust region method with the non-monotone and self-adaptive techniques to propose a new non-monotone self-adaptive trust region algorithm for unconstrained optimization. By use of the simple model, the new method needs less memory capacitance, computational complexity and CPU time. The convergence results of the method are proved under certain conditions. Numerical results show that the new method is effective and attractive for large-scale optimization problems.