检索结果-内蒙古大学图书馆

Complexity Analysis and Algorithm Design of Pooling Problem

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2018年第2期6卷 249-266页

作者： Yu-Hong Dai Rui Diao Kai Fu State Key Laboratory of Scientific and Engineering Computing Institute of Computational Mathematics and Scientific/Engineering ComputingAcademy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing 100190China

The pooling problem,also called the blending problem,is fundamental in production planning of *** can be formulated as an optimization problem similar with the minimum-cost flow ***,Alfaki and Haugland(J Glob Optim 56:897–916,2013)proved the strong NP-hardness of the pooling problem in general *** also pointed out that it was an open problem to determine the computational complexity of the pooling problem with a fixed number of *** this paper,we prove that the pooling problem is still strongly NP-hard even with only one *** means the quality is an essential difference between minimum-cost flow problem and the pooling *** solving large-scale pooling problems in real applications,we adopt the non-monotone strategy to improve the traditional successive linear programming *** convergence of the algorithm is *** numerical experiments show that the non-monotone strategy is effective to push the algorithm to explore the global minimizer or provide a good local *** results for real problems from factories show that the proposed algorithm is competitive to the one embedded in the famous commercial software Aspen PIMS.

关键词： Pooling problem Complexity analysis Successive linear programming Non-monotone

Analytic approximations of Von Krmn plate under arbitrary uniform pressure—equations in integral form

学校读者我要写书评

暂无评论

Science China(Physics,Mechanics & Astronomy) 2018年第1期61卷 57-67页

作者： XiaoXu Zhong ShiJun Liao School of Naval Architecture Ocean and Civil Engineering Shanghai Jiao Tong University Collaborative Innovative Center for Advanced Ship and Deep-Sea Exploration State Key Laboratory of Ocean Engineering Ministry-of-Education Key Laboratory of Scientific and Engineering Computing

Analytic approximations of the Von Karman＇s plate equations in integral form for a circular plate under external uniform pressure to arbitrary magnitude are successfully obtained by means of the homotopy analysis method （HAM）, an analytic approximation technique for highly nonlinear problems. Two HAM-based approaches are proposed for either a given external uniform pressure Q or a given central deflection, respectively. Both of them are valid for uniform pressure to arbitrary magnitude by choosing proper values of the so-called convergence-control parameters c1 and c2 in the frame of the HAM. Besides, it is found that the HAM- based iteration approaches generally converge much faster than the interpolation iterative method. Furthermore, we prove that the interpolation iterative method is a special case of the first-order HAM iteration approach for a given external uniform pressure Q when c1= -0 and c2 = -1, where 0 denotes the interpolation iterative parameter. Therefore, according to the convergence theorem of Zheng and Zhou about the interpolation iterative method, the HAM-based approaches are valid for uniform pressure to arbitrary magnitude at least in the special case c1 = -0 and c2= -1. In addition, we prove that the HAM approach for the Von karman＇s plate equations in differential form is just a special case of the HAM for the Von karman＇s plate equations in integral form mentioned in this paper. All of these illustrate the validity and great potential of the HAM for highly nonlinear problems, and its superiority over perturbation techniques.

关键词： circular plate high nonlinearity homotopy analysis method

Phase transition analysis for covariance based massive random access with massive MIMO

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Chen, Zhilin Sohrabi, Foad Liu, Ya-Feng Yu, Wei The Edward S. Rogers Sr. Department of Electrical and Computer Engineering University of Toronto TorontoONM5S 3G4 Canada The State Key Laboratory of Scientific and Engineering Computing Institute of Computational Mathematics and Scientific Engineering Computing Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing100190 China

This paper considers a massive random access problem in which a large number of sporadically active devices wish to communicate with a base station (BS) equipped with massive multiple-input multiple-output (MIMO) antennas. Each device is preassigned a unique signature sequence, and the BS identifies the active devices by detecting which sequences are transmitted. This device activity detection problem can be formulated as a maximum likelihood estimation (MLE) problem for which the sample covariance matrix of the received signal is a sufficient statistic. The goal of this paper is to characterize the feasible set of problem parameters under which this covariance based approach is able to successfully recover the device activities in the massive MIMO regime. Through an analysis of the asymptotic behaviors of MLE via its associated Fisher information matrix, this paper derives a necessary and sufficient condition on the Fisher information matrix to ensure a vanishing probability of detection error as the number of antennas goes to infinity, based on which a numerical phase transition analysis is obtained. This condition is also examined from a perspective of covariance matching, which relates the phase transition analysis to a recently derived scaling law. Further, we provide a characterization of the distribution of the estimation error in MLE, based on which the error probabilities in device activity detection can be accurately predicted. Finally, this paper studies a random access scheme with joint device activity and data detection and analyzes its performance in a similar way. Copyright © 2020, The Authors. All rights reserved.

关键词： Maximum likelihood estimation

Shape correspondence using anisotropic Chebyshev spectral CNNs

学校读者我要写书评

暂无评论

Shape correspondence using anisotropic Chebyshev spectral CN...

Conference on Computer Vision and Pattern Recognition (CVPR)

作者： Qinsong Li Shengjun Liu Ling Hu Xinru Liu Institute of Engineering Modeling and Scientific Computing Central South University State Key Laboratory of High Performance Manufacturing Complex Central South University School of Mathematics and Computational Science Hunan First Normal University

ISBN: (数字)9781728171685

ISBN: (纸本)9781728171692

Establishing correspondence between shapes is a very important and active research topic in many domains. Due to the powerful ability of deep learning on geometric data, lots of attractive results have been achieved by convolutional neural networks (CNNs). In this paper, we propose a novel architecture for shape correspondence, termed Anisotropic Chebyshev spectral CNNs (ACSCNNs), based on a new extension of the manifold convolution operator. The extended convolution operators aggregate the local features of signals by a set of oriented kernels around each point, which allows to much more comprehensively capture the intrinsic signal information. Rather than using fixed oriented kernels in the spatial domain in previous CNNs, in our framework, the kernels are learned by spectral filtering, based on the eigen-decompositions of multiple Anisotropic Laplace-Beltrami Operators. To reduce the computational complexity, we employ an explicit expansion of the Chebyshev polynomial basis to represent the spectral filters whose expansion coefficients are trainable. Through the benchmark experiments of shape correspondence, our architecture is demonstrated to be efficient and be able to provide better than the state-of-the-art results in several datasets even if using constant functions as inputs.

关键词： Shape Manifolds Convolution Kernel Machine learning Eigenvalues and eigenfunctions Chebyshev approximation

SNIG PROPERTY OF MATRIX LOW-RANK FACTORIZATION MODEL

学校读者我要写书评

暂无评论

Journal of Computational Mathematics 2018年第3期36卷 374-390页

作者： Hong Wang Xin Liu Xiaojun Chen Yaxiang Yuan Department of Applied Mathematics The Hong Kong Polytechnic University Hong Kong China State Key Laboratory of Scientific and Engineering Computing Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190 China State Key Laboratory of Scientific and Engineering Computing Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190 China

Recently, the matrix factorization model attracts increasing attentions in handling large-scale rank minimization problems, which is essentially a nonconvex minimization problem. Specifically, it is a quadratic least squares problem and consequently a quartic polynomial optimization problem. In this paper, we introduce a concept of the SNIG （＂Second-order Necessary optimality Implies Global optimality＂） condition which stands for the property that any second-order stationary point of the matrix factorization model must be a global minimizer. Some scenarios under which the SNIG condition holds are presented. Furthermore, we illustrate by an example when the SNIG condition may fail.

关键词： Low rank factorization Nonconvex optimization Second-order optimality condition Global minimizer

High order asymptotic preserving Hermite WENO fast sweeping method for the steady-state SN transport equation

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Ren, Yupeng Xing, Yulong Wang, Dean Qiu, Jianxian School of Mathematical Sciences Xiamen University XiamenFujian361005 China Department of Mathematics Ohio State University ColumbusOH43210 United States Department of Mechanical and Aerospace Engineering Ohio State University ColumbusOH43210 United States School of Mathematical Sciences Fujian Provincial Key Laboratory of Mathematical Modeling and High-Performance Scientific Computing Xiamen University XiamenFujian361005 China

In this paper, we propose to combine the fifth order Hermite weighted essentially non-oscillatory (HWENO) scheme and fast sweeping method (FSM) for the solution of the steady-state SN transport equation in the finite volume framework. It is well-known that the SN transport equation asymptotically converges to a macroscopic diffusion equation in the limit of optically thick systems with small absorption and sources. Numerical methods which can preserve the asymptotic limit are referred to as asymptotic preserving methods. In the one-dimensional case, we provide the analysis to demonstrate the asymptotic preserving property of the high order finite volume HWENO method, by showing that its cell-edge and cell-average fluxes possess the thick diffusion limit. Numerical results in both one- and two- dimensions are presented to validate its asymptotic preserving property. A hybrid strategy to compute the nonlinear weights in the HWENO reconstruction is introduced to save computational cost. Extensive one- and two-dimensional numerical experiments are performed to verify the accuracy, asymptotic preserving property and positivity of the proposed HWENO FSM. Copyright © 2021, The Authors. All rights reserved.

关键词： Diffusion

Seeking Consensus on Subspaces in Federated Principal Component Analysis

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Wang, Lei Liu, Xin Zhang, Yin State Key Laboratory of Scientific and Engineering Computing Academy of Mathematics and Systems Science Chinese Academy of Sciences University of Chinese Academy of Sciences Beijing China School of Data Science The Chinese University of Hong Kong Shenzhen China

In this paper, we develop an algorithm for federated principal component analysis (PCA) with emphases on both communication efficiency and data privacy. Generally speaking, federated PCA algorithms based on direct adaptations of classic iterative methods, such as simultaneous subspace iterations (SSI), are unable to preserve data privacy, while algorithms based on variable-splitting and consensus-seeking, such as alternating direction methods of multipliers (ADMM), lack in communication-efficiency. In this work, we propose a novel consensus-seeking formulation by equalizing subspaces spanned by splitting variables instead of equalizing variables themselves, thus greatly relaxing feasibility restrictions and allowing much faster convergence. Then we develop an ADMM-like algorithm with several special features to make it practically efficient, including a low-rank multiplier formula and techniques for treating subproblems. We establish that the proposed algorithm can better protect data privacy than classic methods adapted to the federated PCA setting. We derive convergence results, including a worst-case complexity estimate, for the proposed ADMM-like algorithm in the presence of the nonlinear equality constraints. Extensive empirical results are presented to show that the new algorithm, while enhancing data privacy, requires far fewer rounds of communication than existing peer algorithms for federated PCA. Copyright © 2020, The Authors. All rights reserved.

关键词： Principal component analysis

Optimal network slicing for service-oriented networks with flexible routing and guaranteed E2E latency

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Chen, Wei-Kun Liu, Ya-Feng de Domenico, Antonio Luo, Zhi-Quan Dai, Yu-Hong The School of Mathematics and Statistics Beijing Key Laboratory on MCAACI Beijing Institute of Technology Beijing100081 China The State Key Laboratory of Scientific and Engineering Computing Institute of Computational Mathematics and Scientific/Engineering Computing Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing100190 China The Huawei Technologies Co. Ltd France Research Center Boulogne-Billancourt92100 France The Shenzhen Research Institute of Big Data The Chinese University of Hong Kong Shenzhen518172 China

Network function virtualization is a promising technology to simultaneously support multiple services with diverse characteristics and requirements in the 5G and beyond networks. In particular, each service consists of a predetermined sequence of functions, called service function chain (SFC), running on a cloud environment. To make different service slices work properly in harmony, it is crucial to appropriately select the cloud nodes to deploy the functions in the SFC and flexibly route the flow of the services such that these functions are processed in the order defined in the corresponding SFC, the end-to-end (E2E) latency constraints of all services are guaranteed, and all cloud and communication resource budget constraints are respected. In this paper, we first propose a new mixed binary linear program (MBLP) formulation of the above network slicing problem that optimizes the system energy efficiency while jointly considers the E2E latency requirement, resource budget, flow routing, and functional instantiation. Then, we develop another MBLP formulation and show that the two formulations are equivalent in the sense that they share the same optimal solution. However, since the numbers of variables and constraints in the second problem formulation are significantly smaller than those in the first one, solving the second problem formulation is more computationally efficient especially when the dimension of the corresponding network is large. Numerical results demonstrate the advantage of the proposed formulations compared with the existing ones. Copyright © 2020, The Authors. All rights reserved.

关键词： Network function virtualization

Low-order moments of the velocity gradient in homogeneous compressible turbulence

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Yang, PingFan Fang, Jian Fang, Le Pumir, Alain Xu, Haitao The State Key Laboratory of Nonlinear Mechanics Institute of Mechanics Chinese Academy of Sciences Beijing100190 China School of Engineering Sciences University of Chinese Academy of Sciences Beijing100049 China Center for Combustion Energy School of Aerospace Engineering Tsinghua University Beijing100084 China Scientific Computing Department STFC Daresbury Laboratory WarringtonWA4 4AD United Kingdom LCS Ecole Centrale de Pékin Beihang University Beijing100191 China Laboratoire de Physique Ecole Normale Supérieure de Lyon CNRS Université de Lyon LyonF-69007 France Max Planck Institute for Dynamics and Self-Organization GöttingenD-37077 Germany

We derive from first principles analytic relations for the second and third order moments of the velocity gradient mij = ∂ui/∂xj in compressible turbulence, which generalize known relations in incompressible flows. These relations, although derived for homogeneous flows, hold approximately for a mixing layer. We also discuss how to apply these relations to determine all the second and third moments of the velocity gradient experimentally. Copyright © 2022, The Authors. All rights reserved.

关键词： Incompressible flow