检索结果-南通市图书馆

On the complexity of sequentially lifting cover inequalities for the knapsack polytope

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Science China Mathematics 2021年第1期64卷 211-220页

作者： Wei-Kun Chen yu-hong dai School of Mathematics and Statistics Beijing Institute of TechnologyBeijing100081China LSEC ICMSECAcademy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing100190China School of Mathematical Sciences University of Chinese Academy of SciencesBeijing100049China

The well-known sequentially lifted cover inequality is widely employed in solving mixed integer ***,it is still an open question whether a sequentially lifted cover inequality can be computed in polynomial time for a given minimal cover(Gu et al.(1999)).We show that this problem is N P-hard,thus giving a negative answer to the question.

关键词： integer programming sequentially lifted cover inequality complexity lifting problem

维普期刊数据库

The Rate of Convergence of Augmented Lagrangian Method for Minimax Optimization Problems with Equality Constraints

在线全文

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2024年第2期12卷 265-297页

作者： yu-hong dai Li-Wei Zhang LSEC ICMSECAMSSChinese Academy of SciencesBeijing 100190China Institute of Operations Research and Control Theory School of Mathematical SciencesDalian University of TechnologyDalian 116024China

The augmented Lagrangian function and the corresponding augmented Lagrangian method are constructed for solving a class of minimax optimization problems with equality *** prove that,under the linear independence constraint qualification and the second-order sufficiency optimality condition for the lower level problem and the second-order sufficiency optimality condition for the minimax problem,for a given multiplier vectorμ,the rate of convergence of the augmented Lagrangian method is linear with respect to||μu-μ^(*)||and the ratio constant is proportional to 1/c when the ratio|μ-μ^(*)||/c is small enough,where c is the penalty parameter that exceeds a threshold c_(*)>O andμ^(*)is the multiplier corresponding to a local ***,we prove that the sequence of multiplier vectors generated by the augmented Lagrangian method has at least Q-linear convergence if the sequence of penalty parameters(ck)is bounded and the convergence rate is superlinear if(ck)is increasing to ***,we use a direct way to establish the rate of convergence of the augmented Lagrangian method for the minimax problem with a quadratic objective function and linear equality constraints.

关键词： Minimax optimization Augmented Lagrangian method Rate of convergence Second-order sufficiency optimality

Analysis of Sparse Quasi-Newton Updates with Positive Definite Matrix Completion

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2014年第1期2卷 39-56页

作者： yu-hong dai Nobuo Yamashita State Key Laboratory of Scientific and Engineering Computing Institute of Computational Mathematics and Scientific/Engineering ComputingAcademy of Mathematics and Systems ScienceChinese Academy of SciencesP.O.Box 2719Beijing 100080People’s Republic of China Department of Applied Mathematics and Physics Graduate School of InformaticsKyoto UniversityKyoto 606-8501Japan

Based on the idea of maximum determinant positive definite matrix completion,Yamashita(Math Prog 115(1):1–30,2008)proposed a new sparse quasi-Newton update,called MCQN,for unconstrained optimization problems with sparse Hessian *** exchange of the relaxation of the secant equation,the MCQN update avoids solving difficult subproblems and overcomes the ill-conditioning of approximate Hessian ***,local and superlinear convergence results were only established for the MCQN update with the DFP *** this paper,we extend the convergence result to the MCQN update with the whole Broyden’s convex *** results are also reported,which suggest some efficient ways of choosing the parameter in the MCQN update the Broyden’s family.

关键词： Quasi-Newton method Large-scale problems Sparsity Positive definite matrix completion Superlinear convergence

A Mini-Batch Proximal Stochastic Recursive Gradient Algorithm with Diagonal Barzilai–Borwein Stepsize

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2023年第2期11卷 277-307页

作者： Teng-Teng yu Xin-Wei Liu yu-hong dai Jie Sun School of Artificial Intelligence Hebei University of TechnologyTianjin 300401China Institute of Mathematics Hebei University of TechnologyTianjin 300401China LSEC ICMSECAcademy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing 100190China School of Business National University of SingaporeSingapore 119245Singapore

Many machine learning problems can be formulated as minimizing the sum of a function and a non-smooth regularization *** stochastic gradient methods are popular for solving such composite optimization *** propose a minibatch proximal stochastic recursive gradient algorithm SRG-DBB,which incorporates the diagonal Barzilai–Borwein(DBB)stepsize strategy to capture the local geometry of the *** linear convergence and complexity of SRG-DBB are analyzed for strongly convex *** further establish the linear convergence of SRGDBB under the non-strong convexity ***,it is proved that SRG-DBB converges sublinearly in the convex *** experiments on standard data sets indicate that the performance of SRG-DBB is better than or comparable to the proximal stochastic recursive gradient algorithm with best-tuned scalar stepsizes or BB ***,SRG-DBB is superior to some advanced mini-batch proximal stochastic gradient methods.

关键词： Stochastic recursive gradient Proximal gradient algorithm Barzilai-Borwein method Composite optimization

A Stochastic Approximation Frame Algorithm with Adaptive Directions

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Numerical Mathematics(Theory,Methods and Applications) 2008年第4期1卷 460-474页

作者： Zi Xu yu-hong dai Department of Mathematics College of Sciences Shanghai University Shang-hai 200444 PR. China. State Key Laboratory of Scientific and Engineering Computing Institute of Com-putational Mathematics and Scientific/Engineering Computing The Academy ofMathematics and Systems Science Chinese Academy of Sciences P.O.Box 2719Beijing 100190 P.R. China.

Stochastic approximation problem is to find some root or extremum of a nonlinear function for which only noisy measurements of the function are available. The classical algorithm for stochastic approximation problem is the Robbins-Monro （RM） algorithm, which uses the noisy evaluation of the negative gradient direction as the iterative direction. In order to accelerate the RM algorithm, this paper gives a flame algorithm using adaptive iterative directions. At each iteration, the new algorithm goes towards either the noisy evaluation of the negative gradient direction or some other directions under some switch criterions. Two feasible choices of the criterions are proposed and two corresponding frame algorithms are formed. Different choices of the directions under the same given switch criterion in the frame can also form different algorithms. We also proposed the simultanous perturbation difference forms for the two frame algorithms. The almost surely convergence of the new algorithms are all established. The numerical experiments show that the new algorithms are promising.

关键词： Stochastic approximation conjugate gradient adaptive directions.

维普期刊数据库

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

Enhancing cut selection through reinforcement learning

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Science China Mathematics 2024年第6期67卷 1377-1394页

作者： Shengchao Wang Liang Chen Lingfeng Niu yu-hong dai Academy of Mathematics and Systems Science Chinese Academy of SciencesBeijing100190China Research Center on Fictitious Economy and Data Science Chinese Academy of SciencesBeijing100190China

With the rapid development of artificial intelligence in recent years,applying various learning techniques to solve mixed-integer linear programming(MILP)problems has emerged as a burgeoning research *** from constructing end-to-end models directly,integrating learning approaches with some modules in the traditional methods for solving MILPs is also a promising *** cutting plane method is one of the fundamental algorithms used in modern MILP solvers,and the selection of appropriate cuts from the candidate cuts subset is crucial for enhancing *** to the reliance on expert knowledge and problem-specific heuristics,classical cut selection methods are not always transferable and often limit the scalability and generalizability of the cutting plane *** provide a more efficient and generalizable strategy,we propose a reinforcement learning(RL)framework to enhance cut selection in the solving process of ***,we design feature vectors to incorporate the inherent properties of MILP and computational information from the solver and represent MILP instances as bipartite ***,we choose the weighted metrics to approximate the proximity of feasible solutions to the convex hull and utilize the learning method to determine the weights assigned to each ***,a graph convolutional neural network is adopted with a self-attention mechanism to predict the value of weighting ***,we transform the cut selection process into a Markov decision process and utilize RL method to train the *** experiments are conducted based on a leading open-source MILP solver *** on both general and specific datasets validate the effectiveness and efficiency of our proposed approach.

关键词： reinforcement learning mixed-integer linear programming cutting plane method cut selection

维普期刊数据库

Intein-mediated Rapid Purification of Recombinant Human Pituitary Adenylate Cyclase Activating Polypeptide

在线全文

学校读者我要写书评

暂无评论

Acta Biochimica et Biophysica Sinica 2004年第11期36卷 759-766页

作者： Rong-jie yu, An hong, yun dai, and yuan GAOBio-engineering Institute of Jinan University, Guangzhou 510632, China Bio-engineering Institute of Jinan UniversityGuangzhou 510632 China

In order to obtain the recombinant human PACAP efficiently by intein-mediated single column purification, a gene encoding human PACAP was synthesized and cloned into Escherichia coli expression vector pKYB. The recomb... 详细信息

关键词： intein recombinant human pituitary adenylate cyclase activating peptide (rhPACAP) purification

Preface:Special Issue on Data-Driven Optimization Models and Algorithms

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2015年第4期3卷 389-390页

作者： Yan-Qin Bai yu-hong dai Nai-Hua Xiu Shanghai University Shanghai 200444China Chinese Academy of Sciences Beijing 100190China Beijing Jiaotong University Beijing 100044China

The growing demands of information age have speeded up the development of data *** research and application of data become more and more popular in many fields,such as information science,mathematics,operations research,statistics and computer *** is of theoretical significance to study the optimization models and algorithms driven by data,which is helpful to new business model,communication and network technology,intelligent transportation system,economic management and other related fields.

关键词： computer operations network