Most Read

Published in last 1 year |  In last 2 years |  In last 3 years |  All Please wait a minute... For Selected: Download Citations EndNote Ris BibTeX Toggle Thumbnails Select An Overview of Stochastic Quasi-Newton Methods for Large-Scale Machine Learning Tian-De Guo, Yan Liu, Cong-Ying Han Journal of the Operations Research Society of China    2023, 11 (2): 245-275.   DOI: 10.1007/s40305-023-00453-9 Abstract （969）      PDF       Knowledge map    Save Numerous intriguing optimization problems arise as a result of the advancement of machine learning. The stochastic first-ordermethod is the predominant choicefor those problems due to its high efficiency. However, the negative effects of noisy gradient estimates and high nonlinearity of the loss function result in a slow convergence rate. Second-order algorithms have their typical advantages in dealing with highly nonlinear and ill-conditioning problems. This paper provides a review on recent developments in stochastic variants of quasi-Newton methods, which construct the Hessian approximations using only gradient information. We concentrate on BFGS-based methods in stochastic settings and highlight the algorithmic improvements that enable the algorithm to work in various scenarios. Future research on stochastic quasi-Newton methods should focus on enhancing its applicability, lowering the computational and storage costs, and improving the convergence rate. Reference | Related Articles | Metrics | Comments（0） Select Preface Tian-De Guo Journal of the Operations Research Society of China    2023, 11 (2): 243-244.   DOI: 10.1007/s40305-022-00452-2 Abstract （939）      PDF       Knowledge map    Save Related Articles | Metrics | Comments（0） Select Approximate Customized Proximal Point Algorithms for Separable Convex Optimization Hong-Mei Chen, Xing-Ju Cai, Ling-Ling Xu Journal of the Operations Research Society of China    2023, 11 (2): 383-408.   DOI: 10.1007/s40305-022-00412-w Abstract （929）      PDF       Knowledge map    Save Proximal point algorithm (PPA) is a useful algorithm framework and has good convergence properties. Themain difficulty is that the subproblems usually only have iterative solutions. In this paper, we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint. We design two types of inexact error criteria for the subproblems. The first one is absolutely summable error criterion, under which both subproblems can be solved inexactly. When one of the two subproblems is easily solved, we propose another novel error criterion which is easier to implement, namely relative error criterion. The relative error criterion only involves one parameter, which is more implementable. We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms. The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms. Reference | Related Articles | Metrics | Comments（0） Select Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization Yong-Yong Chen, Fang-Fang Xu Journal of the Operations Research Society of China    2023, 11 (2): 327-345.   DOI: 10.1007/s40305-020-00322-9 Abstract （922）      PDF       Knowledge map    Save Orthogonal nonnegative matrix factorization (ONMF) is widely used in blind image separation problem, document classification, and human face recognition. The model of ONMF can be efficiently solved by the alternating direction method of multipliers and hierarchical alternating least squares method. When the given matrix is huge, the cost of computation and communication is too high. Therefore, ONMF becomes challenging in the large-scale setting. The random projection is an efficient method of dimensionality reduction. In this paper, we apply the random projection to ONMF and propose two randomized algorithms. Numerical experiments show that our proposed algorithms perform well on both simulated and real data. Reference | Related Articles | Metrics | Comments（0） Select A Framework of Convergence Analysis of Mini-batch Stochastic Projected Gradient Methods Jian Gu, Xian-Tao Xiao Journal of the Operations Research Society of China    2023, 11 (2): 347-369.   DOI: 10.1007/s40305-019-00276-7 Abstract （915）      PDF       Knowledge map    Save In this paper, we establish a unified framework to study the almost sure global convergence and the expected convergencerates of a class ofmini-batch stochastic(projected) gradient (SG) methods, including two popular types of SG: stepsize diminished SG and batch size increased SG. We also show that the standard variance uniformly bounded assumption, which is frequently used in the literature to investigate the convergence of SG, is actually not required when the gradient of the objective function is Lipschitz continuous. Finally, we show that our framework can also be used for analyzing the convergence of a mini-batch stochastic extragradient method for stochastic variational inequality. Reference | Related Articles | Metrics | Comments（0） Select A Gradient Descent Method for Estimating the Markov Chain Choice Model Lei Fu, Dong-Dong Ge Journal of the Operations Research Society of China    2023, 11 (2): 371-381.   DOI: 10.1007/s40305-021-00365-6 Abstract （912）      PDF       Knowledge map    Save In this paper, we propose a gradient descent method to estimate the parameters in a Markov chain choice model. Particularly, we derive closed-form formula for the gradient of the log-likelihood function and show the convergence of the algorithm. Numerical experiments verify the efficiency of our approach by comparing with the expectation-maximization algorithm. We show that the similar result can be extended to a more general case that one does not have observation of the no-purchase data. Reference | Related Articles | Metrics | Comments（0） Select A Mini-Batch Proximal Stochastic Recursive Gradient Algorithm with Diagonal Barzilai–Borwein Stepsize Teng-Teng Yu, Xin-Wei Liu, Yu-Hong Dai, Jie Sun Journal of the Operations Research Society of China    2023, 11 (2): 277-307.   DOI: 10.1007/s40305-022-00436-2 Abstract （900）      PDF       Knowledge map    Save Many machine learning problems can be formulated as minimizing the sum of a function and a non-smooth regularization term. Proximal stochastic gradient methods are popular for solving such composite optimization problems. We 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 problem. The linear convergence and complexity of SRG-DBB are analyzed for strongly convex functions. We further establish the linear convergence of SRGDBB under the non-strong convexity condition. Moreover, it is proved that SRG-DBB converges sublinearly in the convex case. Numerical 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 stepsizes. Furthermore, SRG-DBB is superior to some advanced mini-batch proximal stochastic gradient methods. Reference | Related Articles | Metrics | Comments（0） Select An Automatic Fuzzy Clustering Algorithm for Discrete Elements Tai Vovan, Yen Nguyenhoang, Sang Danh Journal of the Operations Research Society of China    2023, 11 (2): 309-325.   DOI: 10.1007/s40305-021-00388-z Abstract （891）      PDF       Knowledge map    Save This research proposes a measure called cluster similar index (CSI) to evaluate the similarity of cluster for discrete elements. The CSI is used as a criterion to build the automatic fuzzy clustering algorithm. This algorithm can determine the suitable number of clusters, find the elements in each cluster, give the probability to belong to the clusters of each element, and evaluate the quality of the established clusters at the same time. The proposed algorithm can perform quickly and effectively by the established MATLAB procedure. Several numerical examples illustrate the proposed algorithm and show the advantages in comparing with the existing ones. Finally, applying the proposed algorithm in the image recognition shows potentiality in the reality of this research. Reference | Related Articles | Metrics | Comments（0） Select Variable Metric Method for Unconstrained Multiobjective Optimization Problems Jian Chen, Gao-Xi Li, Xin-Min Yang Journal of the Operations Research Society of China    2023, 11 (3): 409-438.   DOI: 10.1007/s40305-022-00447-z Abstract （105）      PDF       Knowledge map    Save In this paper, we propose a variable metric method for unconstrained multiobjective optimization problems (MOPs). First, a sequence of points is generated using different positive definite matrices in the generic framework. It is proved that accumulation points of the sequence are Pareto critical points. Then, without convexity assumption, strong convergence is established for the proposed method. Moreover, we use a common matrix to approximate the Hessian matrices of all objective functions, along which a new nonmonotone line search technique is proposed to achieve a local superlinear convergence rate. Finally, several numerical results demonstrate the effectiveness of the proposed method. Reference | Related Articles | Metrics | Comments（0） Select Convergence of Bregman Peaceman-Rachford Splitting Method for Nonconvex Nonseparable Optimization Peng-Jie Liu, Jin-Bao Jian, Bo He, Xian-Zhen Jiang Journal of the Operations Research Society of China    2023, 11 (4): 707-733.   DOI: 10.1007/s40305-022-00411-x Abstract （53）      PDF       Knowledge map    Save This work is about a splitting method for solving a nonconvex nonseparable optimization problem with linear constraints, where the objective function consists of two separable functions and a coupled term. First, based on the ideas from Bregman distance and Peaceman-Rachford splitting method, the Bregman Peaceman-Rachford splitting method with different relaxation factors for the multiplier is proposed. Second, the global and strong convergence of the proposed algorithm are proved under general conditions including the region of the two relaxation factors as well as the crucial Kurdyka-Łojasiewicz property. Third, when the associated Kurdyka-Łojasiewicz property function has a special structure, the sublinear and linear convergence rates of the proposed algorithm are guaranteed. Furthermore, some preliminary numerical results are shown to indicate the effectiveness of the proposed algorithm. Reference | Related Articles | Metrics | Comments（0） Select Extremal P8-Free/P9-Free Planar Graphs Yong-Xin Lan, Yong-Tang Shi Journal of the Operations Research Society of China    2023, 11 (3): 451-457.   DOI: 10.1007/s40305-021-00385-2 Abstract （52）      PDF       Knowledge map    Save An H-free graph is a graph not containing the given graph H as a subgraph. It is well known that the Turán number $ \mathrm{{ex}}_{}(n,H) $ is the maximum number of edges in an H-free graph on n vertices. Based on this definition, we define $ \mathrm{{ex}}_{_\mathcal {P}}(n,H) $ to restrict the graph classes to planar graphs, that is, $ \mathrm{{ex}}_{_\mathcal {P}}(n,H)=\max \{|E(G)|: G\in {\mathcal {G}} $, where $ {\mathcal {G}} $ is a family of all H-free planar graphs on n vertices. Obviously, we have $ \mathrm{{ex}}_{_{\mathcal {P}}}(n,H)=3n-6 $ if the graph H is not a planar graph. The study is initiated by Dowden (J Graph Theory 83:213–230, 2016), who obtained some results when H is considered as $ C_4 $ or $ C_5 $. In this paper, we determine the values of $ \mathrm{{ex}}_{_{\mathcal {P}}}(n,P_k) $ with $ k\in \{8,9\} $, where $ P_k $ is a path with k vertices. Reference | Related Articles | Metrics | Comments（0） Select Gallai's Conjecture on Path Decompositions Geng-Hua Fan, Jian-Feng Hou, Chui-Xiang Zhou Journal of the Operations Research Society of China    2023, 11 (3): 439-449.   DOI: 10.1007/s40305-022-00435-3 Abstract （49）      PDF       Knowledge map    Save Gallai's conjecture asserts that every connected graph on n vertices can be decomposed into at most $\frac{{n + 1}}{2}$ paths. The E-subgraph of a graph G, denoted by $ G_e $, is the subgraph induced by the vertices of even degree in G. A triangle pair is a graph consisting of two triangles with exactly one vertex in common. In this paper, it is proved that Gallai's conjecture is true for graphs G in which $ G_e $ contains no triangle pair and each block of $ G_e $ has maximum degree at most 3. Reference | Related Articles | Metrics | Comments（0） Select Degree Conditions on Copies of Forests in Graphs Xiao-Dong Chen, Shuai-Jun Chen, Ming-Chu Li Journal of the Operations Research Society of China    2023, 11 (3): 667-672.   DOI: 10.1007/s40305-022-00404-w Abstract （47）      PDF       Knowledge map    Save For a graph G, let $ \mu (G)=\min \{\max \{{d}(x),{d}(y)\}:x\ne y,xy\notin E(G), x,y\in V(G)\} $ if G is non-complete, otherwise, $ \mu (G)=+\infty. $ For a given positive number s, we call that a graph G satisfies Fan-type conditions if $ \mu (G)\geqslant s. $ Suppose $ \mu (G)\geqslant s, $ then a vertex v is called a small vertex if the degree of v in G is less than s. In this paper, we prove that for a forest F with m edges, if G is a graph of order $ n\geqslant |F| $ and $ \mu (G)\geqslant m $ with at most $ \max \{n-2m,0\} $ small vertices, then G contains a copy of F. We also give examples to illustrate both the bounds in our result are best possible. Reference | Related Articles | Metrics | Comments（0） Select Approximate Weak Minimal Solutions of Set-Valued Optimization Problems S. Khoshkhabar-amiranloo Journal of the Operations Research Society of China    2023, 11 (3): 673-692.   DOI: 10.1007/s40305-022-00401-z Abstract （47）      PDF       Knowledge map    Save This paper deals with approximate weak minimal solutions of set-valued optimization problems under vector and set optimality criteria. The relationships between various concepts of approximate weak minimal solutions are investigated. Some topological properties and existence theorems of these solutions are given. It is shown that for set-valued optimization problems with upper (outer) cone-semicontinuous objective values or closed objective maps the approximate weak minimal and strictly approximate lower weak minimal solution sets are closed. By using the polar cone and two scalarization processes, some necessary and sufficient optimality conditions in the sense of vector and set criteria are provided. Reference | Related Articles | Metrics | Comments（0） Select A Hybrid Conjugate Gradient Algorithm for Nonconvex Functions and Its Applications in Image Restoration Problems Gong-Lin Yuan, Ying-Jie Zhou, Meng-Xiang Zhang Journal of the Operations Research Society of China    2023, 11 (4): 759-781.   DOI: 10.1007/s40305-022-00424-6 Abstract （46）      PDF       Knowledge map    Save It is prominent that conjugate gradient method is a high-efficient solution way for large-scale optimization problems. However, most of the conjugate gradient methods do not have sufficient descent property. In this paper, without any line search, the presented method can generate sufficient descent directions and trust region property. While use some suitable conditions, the global convergence of the method is established with Armijo line search. Moreover, we study the proposed method for solving nonsmooth problems and establish its global convergence. The experiments show that the presented method can be applied to solve smooth and nonsmooth unconstrained problems, image restoration problems and Muskingum model successfully. Reference | Related Articles | Metrics | Comments（0） Select Characterizing Shadow Price via Lagrange Multiplier for Nonsmooth Problem Yan Gao Journal of the Operations Research Society of China    2023, 11 (4): 827-838.   DOI: 10.1007/s40305-022-00416-6 Abstract （46）      PDF       Knowledge map    Save In this paper, the relation between the shadow price and the Lagrange multiplier for nonsmooth optimization problem is explored. It is obtained that the Lagrange multipliers are upper bounds of the shadow price for a convex optimization problem and a class of Lipschtzian optimization problems. This result can be used in pricing mechanisms for nonsmooth situation. Several nonsmooth functions involved in this class of Lipschtzian optimizations are listed. Finally, an application to electricity pricing is discussed. Reference | Related Articles | Metrics | Comments（0） Select Sufficiency and Duality for Nonsmooth Interval-Valued Optimization Problems via Generalized Invex-Infine Functions Izhar Ahmad, Krishna Kummari, S. Al-Homidan Journal of the Operations Research Society of China    2023, 11 (3): 505-527.   DOI: 10.1007/s40305-021-00381-6 Abstract （44）      PDF       Knowledge map    Save In this paper, a new concept of generalized-affineness type of functions is introduced. This class of functions is more general than some of the corresponding ones discussed in Chuong (Nonlinear Anal Theory Methods Appl 75:5044–5052, 2018), Sach et al. (J Global Optim 27:51–81, 2003) and Nobakhtian (Comput Math Appl 51:1385–1394, 2006). These concepts are used to discuss the sufficient optimality conditions for the interval-valued programming problem in terms of the limiting/Mordukhovich subdifferential of locally Lipschitz functions. Furthermore, two types of dual problems, namely Mond–Weir type and mixed type duals are formulated for an interval-valued programming problem and usual duality theorems are derived. Our results improve and generalize the results appeared in Kummari and Ahmad (UPB Sci Bull Ser A 82(1):45–54, 2020). Reference | Related Articles | Metrics | Comments（0） Select Optimality Conditions for Generalized Convex Nonsmooth Uncertain Multi-objective Fractional Programming Xiao Pan, Guo-Lin Yu, Tian-Tian Gong Journal of the Operations Research Society of China    2023, 11 (4): 809-826.   DOI: 10.1007/s40305-022-00423-7 Abstract （43）      PDF       Knowledge map    Save This paper aims at studying optimality conditions of robust weak efficient solutions for a nonsmooth uncertain multi-objective fractional programming problem (NUMFP). The concepts of two types of generalized convex function pairs, called type-I functions and pseudo-quasi-type-I functions, are introduced in this paper for (NUMFP). Under the assumption that (NUMFP) satisfies the robust constraint qualification with respect to Clarke subdifferential, necessary optimality conditions of the robust weak efficient solution are given. Sufficient optimality conditions are obtained under pseudo-quasi-type-I generalized convexity assumption. Furthermore, we introduce the concept of robust weak saddle points to (NUMFP), and prove two theorems about robust weak saddle points. The main results in the present paper are verified by concrete examples. Reference | Related Articles | Metrics | Comments（0） Select Single-Machine Preemptive Scheduling with Release Dates Involving the Total Weighted Late Work Criterion Zhi-Chao Geng, Yuan Zhang Journal of the Operations Research Society of China    2023, 11 (3): 693-706.   DOI: 10.1007/s40305-022-00403-x Abstract （41）      PDF       Knowledge map    Save This paper investigates the preemptive scheduling with release dates on a single machine to minimize the total weighted late work. We firstly present an $ O(n\log n) $-time algorithm for the single-agent problem with disagreeable weights and due dates. And then, we extendedly study the two-agent Pareto-scheduling problem with jobs having a common due date to minimize each agent's total weighted late work, and give a polynomial-time algorithm that is based on the parameters analysis to generate the Pareto frontier. Reference | Related Articles | Metrics | Comments（0） Select Approximations for a Queueing Game Model with Join-the-Shortest-Queue Strategy Qi-Hui Bu, Li-Wei Liu, Jia-Shan Tang, Yi-Qiang Q. Zhao Journal of the Operations Research Society of China    2023, 11 (3): 489-504.   DOI: 10.1007/s40305-021-00382-5 Abstract （40）      PDF       Knowledge map    Save This paper investigates a partially observable queueing system with N nodes in which each node has a dedicated arrival stream. There is an extra arrival stream to balance the load of the system by routing its customers to the shortest queue. In addition, a reward-cost structure is considered to analyse customers' strategic behaviours. The equilibrium and socially optimal strategies are derived for the partially observable mean field limit model. Then, we show that the strategies obtained from the mean field model are good approximations to the model with finite N nodes. Finally, numerical experiments are provided to compare the equilibrium and socially optimal behaviours, including joining probabilities and social benefits for different system parameters. Reference | Related Articles | Metrics | Comments（0）