| 英文摘要 |
DC programming is a very important problem in non-convex programming. DC programming was first proposed by Pham Dinh Tao in 1985. Some important theoretical and algorithmic studies began to mature in 1994, and DC programming gradually began to attract great attention. Due to its excellent characteristics, its unique structure provides a long-term and meaningful research space. In the process of applying DC programming, researchers find that the data is often uncertain or random, so this paper mainly studies the algorithms and properties of DC programming with randomness in various situations. We first discuss a class of DC programming with random variables when sample is known in detail. Since DC programming itself is a non-convex problem, we construct a new function Concave-R function and prove that the concave approximation constructed by the Concave-R function is the most compact. We also construct the RDDC model with robustness and the CVaR-DC model with CVaR, respectively. We also prove that when the parameters tend to converge, the model with robustness RDDC and the model with robustness CVaR-DC under CVaR are equivalent. In the framework of branch-and-bound algorithm, Concave-R function is used to design specific algorithms for the model with robustness RDDC and the model with robustness CVaR-DC under CVaR, respectively. With the help of the Bonferroni inequality, we also construct a new convex approximation form of DC programming with joint probability constraints. Then we discuss the DC programming under the l〓-Wasserstein distance with randomness . We mainly study the case of p = 1 and p = 2. For l₁-Wasserstein DC programming with randomness, whether left or right random variables, the original problem can be transformed into a 0-1 mixed integer programming problem. Because mixed integer programming is a NP hard problem, we try to develop a new algorithm which will helps us to solve the model in polynomial time. When p = 2, the original problem is transformed into a solvable 0-1 mixed integer SOCP programming problem by using the cone duality theorem. Applying the above results to the SVM model with randomness, numerical experiments show that our algorithm is feasible and effective. Finally, we discuss DC programming with random variables under Φ-divergence. By using the properties of conjugate function, we construct a solvable DC programming model with random variables under Pearson divergence. At the same time, we extend the general Φ-divergence and define a new concept: Quasi-Φ difference to measure the difference between real probability and empirical probability based on samples. The DC programming model with random variables under the difference of Quasi-Φ is established and the VoD (Value of Data) value of Quasi-Φ difference is proved by calculation. That is, when the distance parameter approaches zero, the confidence level of the new model tends to the confidence level of the original model. The numerical experiments show that when the accuracy between classical one and ours are similar, in this case, our model has smaller variance and more robustness. KEYWORDS: DC programming, Concave-R function, Robustness, Wasserstein distance, Φ-divergence.
|
