Based on the alternating direction method of multipliers (ADMM) and the sequential quadratic programming (SQP) method, this paper proposes a new efficient algorithm for two blocks nonconvex optimization with linear constrained. Firstly, taking SQP thought as the main line, the quadratic programming (QP) is decomposed into two independent small scale QP according to ADMM idea. Secondly, the new iteration point of the prime variable is generated by Armijo line search for the augmented Lagrange function. Finally, the dual variables are updated by an explicit expression. Thus, a new ADMM-SQP algorithm is constructed. Under the weaker conditions, the global convergence of the algorithm is analyzed. Some preliminary numerical results are reported to support the efficiency of the new algorithm.
Multi-instance learning is a special kind of machine learning problem, has received extensive attention and been researched on in recent years. Many different types of multi-instance learning algorithms have been proposed to deal with practical problems in various fields. This paper reviews the algorithm research and application of multi-instance learning in detail, introduces various background assumptions， and introduces multi-instance learning from three aspects: instance level, bag level, and embedded space. Finally we provide the algorithm extensions and major applications in several areas.
Nonparallel support vector machine (NSVM) is the extension of support vector machine (SVM), and it has been widely studied in recent years. The NSVM constructs nonparallel support hyperplanes for each class, which can describe the distribution of different classes, thus applicable to wider problems. However, the study of the relationship between NSVM and SVM is rarely. And to now, there is no NSVM could be degenerate or equivalent to the standard SVM. We start from this view of point, and construct a new NSVM model. Our model not only can be reduced to the standard SVM, preserves the sparsity and kernel scalability, but also can describe the distribution of the different classes. At last, we compare our model with start-of-art SVMs and NSVMs on benchmark datasets, and confirm the superiority of proposed NSVM.
In recent years, there have been frequent smog and heavy pollution incidents in the Beijing-Tianjin-Hebei (Jing-Jin-Ji) area, which have caused widespread concern in the country and society. Based on the data of 68 monitoring stations in the Jing-Jin-Ji area , this paper studied the main variation patterns of the annual data of PM2.5 hours in the Jing-Jin-Ji area, and the characteristics of the temporal and spatial changes. The effect of cumulative annual emissions of sulfur dioxide and nitrogen oxides on changes in PM2.5 concentrations has also been studied. The results show that the emission of nitrogen oxides contributes more to the concentration of PM2.5. The reduction of nitrogen oxides and other pollutants can effectively reduce the concentration of PM2.5 and improve air quality. In this paper, a functional data analysis method is used. Compared with the traditional statistical mean method, it can more effectively use the different data types collected to perform more detailed analysis and thus obtain more reliable conclusions.
In the take-out food industry, improper path planning by couriers often leads to low delivery efficiency. Most of the existing VRP research focuses on the optimization of express delivery and other industries, and there is a lack of optimization algorithm research for the food delivery with real-time characteristics. Aiming at the Online to Offline (O2O) take-out delivery routing optimization problem, this paper takes a comprehensive consideration of its dynamic delivery requirements, cargo differentiation and other characteristics as well as constraints such as time windows and cargo capacities, and establishes an O2O dynamic route optimization model of the take-out delivery personnel, in which the business districts are regarded as a delivery centre, and the number of delivery personnel and the total travel time by the delivery personnel are taken as the minimization targets. Using the method of periodically processing new orders, the resultant dynamic adjustment problem of the delivery personnel's route is converted into a series of static TSP sub-problems and thereby a phased heuristic real-time delivery routing optimization algorithm framework is designed, and a concrete algorithm and a numerical example are given. A set of test cases centered on business districts is generated on the basis of a number of widely used VRP instances, the algorithm is tested through simulation experiment and compared with other algorithms. The results show that the algorithm proposed in this paper can make full use of the delivery personnel near the location of the new orders to conduct the delivery, optimize the corresponding delivery route, and effectively reduce the number of delivery personnel for delivery and the total travel time by the delivery personnel.
The $k$-means problem is a very important problem in the field of machine learning and combinatorial optimization. It is a classic NP-hard problem, which is widely used in data mining, business production decision-making, image processing, biomedical technology, and more. As people in these fields pay more and more attention to personal privacy protection, which raises a question: In the case that decisions are usually made by artificial intelligence algorithms, how to ensure that as much information as possible is extracted from the data without revealing personal privacy? In the past ten years, experts and scholars have continuously studied and explored the $k$-means problem with privacy protection, and has also obtained many results with theoretical guiding significance and practical application value. In this paper we mainly introduce these differential privacy algorithms of the $k$-means problem for readers.
Low-rank tensor completion is widely used in data recovery, and the tensor completion model based on tensor train (TT) decomposition works well in color image, video and internet data recovery. This paper proposes a tensor completion model based on the third-order tensor TT decomposition. In this model, the sparse regularization and the spatio-temporal regularization are introduced to characterize the sparsity of the kernel tensor and the inherent block similarity of the data, respectively. According to the structural characteristics of the problem, some auxiliary variables are introduced to convert the original model into a separable form equivalently, and the method of combining proximal alternating minimization (PAM) and alternating direction multiplier method (ADMM) is used to solve the model. Numerical experiments show that the introduction of two regular terms is beneficial to improve the stability and practical effect of data recovery, and the proposed method is superior to other methods. When the sampling rate is low or the image is structurally missing, the presented method is more effective.
We consider the bounded inverse optimal value problem on minimum spanning tree under unit $l_{\infty}$ norm. Given an edge weighted connected undirected network $G=(V, E, w)$, a spanning tree $T^0$, a lower bound vector $\bm{l}$, an upper bound vector $\bm{u}$ and a value $K$, we aim to obtain a new weight vector $\bm{\bar{w}}$ satisfying the lower and upper bounds such that $T^0$ is a minimum spanning tree under the vector $\bm{\bar{w}}$ with weight $K$. The objective is to minimize the modification cost under unit $l_{\infty}$ norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop an $O(|V||E|)$ strongly polynomial time algorithm.
Driver scheduling is one of the indispensable core businesses in public transportation system. The driver scheduling problem has attracted much research interests and a large amount of scheduling approaches have been developed since the 1960s. This paper first introduces the driver scheduling problem and its common mathematical model; then, two kinds of solution modes are summarized whilst an overview of driver scheduling approaches are reported; finally, future research trends and directions are suggested.
Due to the difficulty in accurately estimating the basic infectious number $R_0$ and the low accuracy of single model prediction, the traditional epidemic infectious diseases studying is blocked and not widely implemented operationally. To overcome this challenge, this paper proposes a non-linear model with time varying transmission rate based on the support vector regression instead of basic infection number $R_0$. The non-linear model is applied to analyze and predict the COVID-19 outbreak in China. Firstly, the discrete values of the dynamic transmission rate are calculated. Secondly, the polynomial function, exponential function, hyperbolic function and power function are used to fit with the discrete values of the dynamic transmission rate and the corresponding prediction model is rebuilt on basis of the optimal sliding window period $k=3$. Then, on account of the evaluation indexes such as goodness of fitting, the best three prediction models are selected, and the prediction results are nonlinearly combined. Finally, the combined dynamic transmission rate model is used to analyze and predict the COVID-19 epidemic in Hubei province, outside-Hubei provinces, and the whole China. The empirical results show that the combined dynamic transmission rate model is in relatively good agreement with the COVID-19 epidemic data in different regions. The prediction of COVID-19 epidemic infection points in most provinces well reproduce the real situation. The goodness of fitting of the epidemic prediction curves in Hubei province, outside-Hubei provinces and the whole China from February 27, 2020 are 98.53%, 98.06% and 97.98%, respectively.
As a special abstract convex (concave) sets, radiant sets and co-radiant sets play the important roles in abstract convex analysis and the theory of multiobjective optimization problems. We first establish the equivalent characterizations for the radiant sets and co-radiant sets. Finally, we apply important properties to the characterization of the approximate solutions of the vector optimization problems, and obtain the equivalent characterization of the approximate solution sets.
This paper investigates a non-zero-sum stochastic differential investment and reinsurance game with delay effect between two competitive insurers, who aim to maximize the mean-variance utility of his terminal wealth relative to that of his competitor. By applying stochastic control theory, corresponding extended Hamilton-Jacobi-Bellman (HJB) system of equations are established. Furthermore, closed-form expressions for the Nash equilibrium investment and reinsurance strategies and the corresponding value functions are derived both in the classical risk model and its diffusion approximation. Finally, some numerical examples are conducted to illustrate the influence of model parameters on the equilibrium investment and reinsurance strategies and draw some economic interpretations from these results.
A combined response surface method is presented for expensive black-box global optimization, which can adaptively take sampling points during iterations. Under the framework of response surface method, the convex combination of the cubic radial basis function and the thin plate spline radial basis function is adopted as the response surface. In the initial phase of the algorithm, the global optimizer of the auxiliary function formed by the product of the response surface model and the power of the distance indicator function will be taken as the new sample point. In the following iterations, if the distance between the two response surface models of the two consecutive iterations is smaller than a given threshold, then the global optimizer of the current response surface model will be taken as the next sample point, otherwise the sampling strategy of the initial phase will be adopted. The effectiveness of the proposed algorithm is demonstrated by the results of the numerical experiments carried respectively on 7 standard test problems and 22 standard test problems.
A scaled incremental gradient algorithm for minimizing a sum of continuously differentiable functions is presented. At each iteration of the algorithm, the iterate is updated incrementally by a sequence of some steps, and each step is cyclically evaluates a normalized gradient of a single component function (or several component functions). Under some moderate assumptions, the convergence result of the algorithm employing the divergence step sizes is established. As applications, the new algorithm and the (unscaled) one proposed by Bertsekas D P, Tsitsikils J N are applied to solve the robust estimation problem and the source localization problem, respectively. Some numerical experiments show that the new algorithm is more effective and robust than the corresponding (unscaled) one.
As a feature extraction method, nonnegative tensor factorization has been widely used in image processing and pattern recognition for its advantages of preserving the internal structural features of data and strong interpretability. However, there are two problems in this method: one is that there is unnecessary correlation between the decomposed base images, which leads to more redundant information and takes up a lot of memory; the other is that the coding is not sparse enough, which leads to the expression of the image is not concise enough. These problems will greatly affect the accuracy of face recognition. In order to improve the accuracy of face recognition, a face recognition algorithm based on orthogonal and sparse constrained nonnegative tensor factorization is proposed. Firstly, orthogonal and sparse constraints are added to the traditional nonnegative tensor factorization to reduce the correlation between the base images and obtain sparse coding. Secondly, the original face image and the decomposed base image are used to calculate the low dimensional feature representation of the face. Finally, cosine similarity is used to measure the similarity between low-dimensional features and judge whether two face images represent the same person. Through experiments in AR database and ORL database, it is found that the improved algorithm can achieve better recognition effect.
