检索结果-南通市图书馆

Learning to sample initial solution for solving 0-1 discrete optimization problem by local search

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China Mathematics 2024年第6期67卷 1317-1340页

作者： Xin Liu Jianyong Sun zongben xu School of Mathematics and Statistics Xi’an Jiaotong UniversityXi’an710049China

Local search methods are convenient alternatives for solving discrete optimization problems(DOPs).These easy-to-implement methods are able to find approximate optimal solutions within a tolerable time *** is known that the quality of the initial solution greatly affects the quality of the approximated solution found by a local search *** this paper,we propose to take the initial solution as a random variable and learn its preferable probability *** aim is to sample a good initial solution from the learned distribution so that the local search can find a high-quality *** develop two different deep network models to deal with DOPs established on set(the knapsack problem)and graph(the maximum clique problem),*** deep neural network learns the representation of an optimization problem instance and transforms the representation to its probability *** results show that given the initial solution sampled from the learned probability distribution,a local search method can acquire much better approximate solutions than the randomly-sampled initial solution on the synthesized knapsack instances and the Erd?s-Rényi random graph ***,with sampled initial solutions,a classical genetic algorithm can achieve better solutions than a random initialized population in solving the maximum clique problems on DIMACS ***,we emphasize that the developed models can generalize in dimensions and across graphs with various densities,which is an important advantage on generalizing deep-learning-based optimization algorithms.

关键词： discrete optimization deep learning graph convolutional network local search

New low-rank optimization model and algorithms for spectral compressed sensing

在线全文

学校读者我要写书评

暂无评论

Science China Mathematics 2024年第10期67卷 2409-2432页

作者： Zai Yang xunmeng Wu zongben xu School of Mathematics and Statistics Xi'an Jiaotong UniversityXi'an 710049China

In this paper, we investigate the recovery of an undamped spectrally sparse signal and its spectral components from a set of regularly spaced samples within the framework of spectral compressed sensing and super-resolution. We show that the existing Hankel-based optimization methods suffer from the fundamental limitation that the prior knowledge of undampedness cannot be exploited. We propose a new low-rank optimization model partially inspired by forward-backward processing for line spectral estimation and show its capability to restrict the spectral poles to the unit circle. We present convex relaxation approaches with the model and show their provable accuracy and robustness to bounded and sparse noise. All our results are generalized from one-dimensional to arbitrary-dimensional spectral compressed sensing. Numerical simulations are provided to corroborate our analysis and show the efficiency of our model and the advantageous performance of our approach in terms of accuracy and resolution compared with the state-of-the-art Hankel and atomic norm methods.

关键词： low-rank double Hankel model doubly enhanced matrix completion line spectral estimation spectral compressed sensing Kronecker's theorem

Learning to select the recombination operator for derivative-free optimization

在线全文

学校读者我要写书评

暂无评论

Science China Mathematics 2024年第6期67卷 1457-1480页

作者： Haotian Zhang Jianyong Sun Thomas Back zongben xu School of Mathematics and Statistics Xi’an Jiaotong UniversityXi’an710049China Leiden Institute of Advanced Computer Science Leiden UniversityLeiden2333 CANetherlands

Extensive studies on selecting recombination operators adaptively,namely,adaptive operator selection(AOS),during the search process of an evolutionary algorithm(EA),have shown that AOS is promising for improving EA's performance.A variety of heuristic mechanisms for AOS have been proposed in recent decades,which usually contain two main components:the feature extraction and the policy *** feature extraction refers to as extracting relevant features from the information collected during the search *** policy setting means to set a strategy(or policy)on how to select an operator from a pool of operators based on the extracted *** components are designed by hand in existing studies,which may not be efficient for adapting optimization *** this paper,a generalized framework is proposed for learning the components of AOS for one of the main streams of EAs,namely,differential evolution(DE).In the framework,the feature extraction is parameterized as a deep neural network(DNN),while a Dirichlet distribution is considered to be the policy.A reinforcement learning method,named policy gradient,is used to train the *** case studies,the proposed framework is applied to two DEs including the classic DE and a recently-proposed DE,which result in two new algorithms named PG-DE and PG-MPEDE,*** on the Congress of Evolutionary Computation(CEC)2018 test suite show that the proposed new algorithms perform significantly better than their ***,we prove theoretically that the considered classic methods are the special cases of the proposed framework.

关键词： evolutionary algorithm differential evolution adaptive operator selection reinforcement learning deep learning

A NEW ALGORITHM FOR COMPUTING THE INVERSE AND GENERALIZED INVERSE OF THE SCALED FACTOR CIRCULANT MATRIX

在线全文

学校读者我要写书评

暂无评论

Journal of Computational Mathematics 2008年第1期26卷 112-122页

作者： Zhaolin Jiang zongben xu School of Science Xi'an Jiaotong University Xi'an 710049 China and Department of Mathematics Linyi Teachers College Linyi 276005 China School of Science Xi'an Jiaotong University Xi'an 710049 China

A new algorithm for finding the inverse of a nonsingular scaled factor circulant matrix is presented by the Euclid＇s algorithm. Extension is made to compute the group inverse and the Moore-Penrose inverse of the singular scaled factor circulant matrix. Numerical examples are presented to demonstrate the implementation of the proposed algorithm.

关键词： Scaled factor circulant matrix Inverse Group inverse Moore-Penrose inverse

Learning capability of the truncated greedy algorithm

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2016年第5期59卷 49-63页

作者： Lin xu Shaobo LIN zongben xu Institute for Information and System Sciences Xi'an Jiaotong University College of Mathematics and Information Science Wenzhou University

Pure greedy algorithm(PGA), orthogonal greedy algorithm(OGA) and relaxed greedy algorithm(RGA) are three widely used greedy type algorithms in both nonlinear approximation and supervised *** this paper, we apply another variant of greedy-type algorithm, called the truncated greedy algorithm(TGA)in the realm of supervised learning and study its learning performance. We rigorously prove that TGA is better than PGA in the sense that TGA possesses the faster learning rate than PGA. Furthermore, in some special cases, we also prove that TGA outperforms OGA and RGA. All these theoretical assertions are verified by both toy simulations and real data experiments.

关键词： supervised learning learning theory generalization capability greedy algorithm truncated greedy algorithm

Nonlinear version of Holub's theorem and its application

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Chinese Science Bulletin 1998年第2期43卷 89-91页

作者： Jigen Peng zongben xu Research Center for Applied Mathematics Institute for Information and System Science Xi’an Jiaotong University Xi’an China

Holub proved that any bounded linear operator T or -T defined on Banach space L 1(μ) satisfies Daugavet equation1+‖T‖=Max{‖I+T‖, ‖I-T‖}.Holub’s theorem is generalized to the nonlinear case: any nonlinear Lipschitz operator f defined on Banach space l 1 satisfies1+L(f)=Max{L(I+f), L(I-f)},where L(f) is the Lipschitz constant of f. The generalized Holub theorem has important applications in characterizing the invertibility of nonlinear operator.

关键词： nonlinear Lipschitz operator Holub theorem Daugavet equation invertibility of operator.

The essential order of approximation for nearly exponential type neural networks

在线全文

学校读者我要写书评

暂无评论

Science in China(Series F) 2006年第4期49卷 446-460页

作者： xu zongben WANG Jianjun Institute for Information and System Science Xi'an Jiaotong University Xi'an 710049 China

For the nearly exponential type of feedforward neural networks （neFNNs）, it is revealed the essential order of their approximation. It is proven that for any continuous function defined on a compact set of Rd, there exists a three-layer neFNNs with fixed number of hidden neurons that attain the essential order. When the function to be approximated belongs to the α-Lipschitz family （0 〈α≤ 2）, the essential order of approxi- mation is shown to be O（n^-α） where n is any integer not less than the reciprocal of the predetermined approximation error. The upper bound and lower bound estimations on approximation precision of the neFNNs are provided. The obtained results not only characterize the intrinsic property of approximation of the neFNNs, but also uncover the implicit relationship between the precision （speed） and the number of hidden neurons of the neFNNs.

关键词： nearly exponential type neural networks the essential order of approximation the modulus of smoothness of a multivariate function.

Convergence of multi-block Bregman ADMM for nonconvex composite problems

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2018年第12期61卷 53-64页

作者： Fenghui WANG Wenfei CAO zongben xu School of Mathematics and Statistics Xi'an Jiaotong University Department of Mathematics Luoyang Normal University School of Mathematics and Information Science Shaanxi Normal University

The alternating direction method with multipliers(ADMM) is one of the most powerful and successful methods for solving various composite problems. The convergence of the conventional ADMM(i.e.,2-block) for convex objective functions has been stated for a long time, and its convergence for nonconvex objective functions has, however, been established very recently. The multi-block ADMM, a natural extension of ADMM, is a widely used scheme and has also been found very useful in solving various nonconvex optimization problems. It is thus expected to establish the convergence of the multi-block ADMM under nonconvex frameworks. In this paper, we first justify the convergence of 3-block Bregman ADMM. We next extend these results to the N-block case(N≥3), which underlines the feasibility of multi-block ADMM applications in nonconvex settings. Finally, we present a simulation study and a real-world application to support the correctness of the obtained theoretical assertions.

关键词： nonconvex regularization alternating direction method subanalytic function K-L inequality Bregman distance

The number of spanning trees in a new lexicographic product of graphs

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2014年第11期57卷 57-65页

作者： LIANG Dong LI Feng xu zongben Institute of Information and System Sciences School of Mathematics and Statistics Xi'an Jiaotong University Ministry of Education key Lab for Intelligent Networks and Network Security Xi'an Jiaotong University College of Computer Science Qinghai Normal University

The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only.

关键词： spanning trees lexicographic product Laplacian matrix reliable network graph