American Institute of Mathematical Sciences

Advanced
  • Previous Article
    An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints
  • JIMO Home
  • This Issue
  • Next Article
    A new switching time optimization technique for multi-switching systems
doi: 10.3934/jimo.2021212
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Distributionally robust chance constrained svm model with $\ell_2$-Wasserstein distance

Qing Ma and  Yanjun Wang ,

School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China

* Corresponding author: wangyanjun@mail.shufe.edu.cn

Received  April 2021 Revised  November 2021 Early access December 2021

In this paper, we propose a distributionally robust chance-constrained SVM model with $ \ell_2 $-Wasserstein ambiguity. We present equivalent formulations of distributionally robust chance constraints based on $ \ell_2 $-Wasserstein ambiguity. In terms of this method, the distributionally robust chance-constrained SVM model can be transformed into a solvable linear 0-1 mixed integer programming problem when the $ \ell_2 $-Wasserstein distance is discrete form. The DRCC-SVM model could be transformed into a tractable 0-1 mixed-integer SOCP programming problem for the continuous case. Finally, numerical experiments are given to illustrate the effectiveness and feasibility of our model.

Keywords: Robust, chance-constrained optimization, support vector machine, Wasserstein distance, uncertainty.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.
Citation: Qing Ma, Yanjun Wang. Distributionally robust chance constrained svm model with $\ell_2$-Wasserstein distance. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2021212
References:
[1]

G. Aurora and M. C. Victoria, Towards energy efficiency smart buildings models based on in telligent data analytics, Procedia Computer Science, 83 (2016), 994-999. 

[2]

Y. Q. Bai and K. J. Shen, Alternating direction method of multipliers for $\ell_1$-$\ell_2$ regularized logistic regression model, J. Oper. Res. Soc. China, 4 (2016), 243-253.  doi: 10.1007/s40305-015-0090-2.

[3]

Y. Q. Bai, Y. J. Shen and K. J. Shen, Consensus proximal support vector machine for classficication problems with sparse solutions, J. Oper. Res. Soc. China, 2 (2014), 57-79.  doi: 10.1007/s40305-014-0037-z.

[4]

C. Bhattacharyya, Robust classification of noisy data using second order cone programming approach, In Intelligent Sensing and Information Processing, IEEE, (2004), 433–438.

[5]

J. Blanchet, L. Chen and X. Y. Zhou, Distributionally robust mean-variance portfolio selection with wasserstein distances, preprint, arXiv: 1802.04885.

[6]

G. C. Calafiore and L. Ghaoui, On distributionally robust chance-constrained linear programs, J. Optim. Theory Appl., 130 (2006), 1-22.  doi: 10.1007/s10957-006-9084-x.

[7]

S. Chao, X. Huang and F. You, Data-driven robust optimization based on kernel learning, Computers and Chemical Engineering, 106 (2017), 464-479. 

[8]

A. Charnes, W. W. Cooper and G. H. Symonds, Cost horizons and certainty equivalents: An approach to stochastic programming of heating oil, Management Science, 4 (1958), 235-263.  doi: 10.1287/mnsc.4.3.235.

[9]

C. Cortes and V. Vapnik, Support-vector networks, Machine Learning, 20 (1995), 273-297.  doi: 10.1007/BF00994018.

[10]

M. D. Dias and A. R. Neto, Training soft margin support vector machines by simulated annealing: A dual approach, Expert Systems with Applications, 87 (2017), 157-169. 

[11]

E. Erdogan and G. Iyengar, Ambiguous chance constrained problems and robust optimization, Math. Program., 107 (2006), 37-61.  doi: 10.1007/s10107-005-0678-0.

[12]

P. M. Esfahani and D. Kuhn, Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations, Math. Program., 171 (2018), 115-166.  doi: 10.1007/s10107-017-1172-1.

[13]

R. Gao and A. J. Kleywegt, Distributionally robust stochastic optimization with wasserstein distance, preprint, arXiv: 1604.02199.

[14]

Y. Guo, K. Baker, E. Dall'Anese, Z. C. Hu and T. H. Summers, Data-based distributionally robust stochastic optimal power flow-Part I: Methodologies, IEEE Transactions on Power Systems, 34 (2019), 1483-1492.  doi: 10.1109/TPWRS.2018.2878385.

[15]

Y. Guo, K. Baker, E. Dall'Anese, Z. C. Hu and T. H. Summers, Data-based distributionally robust stochastic optimal power flow-Part II: Case studies, IEEE Transactions on Power Systems, 34 (2018), 1493-1503. 

[16]

P. Georg and W. David, Ambiguity in portfolio selection, Quant. Finance, 7 (2007), 435-442.  doi: 10.1080/14697680701455410.

[17]

B. Han, C. Shang and D. Huang, Multiple kernel learning-aided robust optimization: Learning algorithm, computational tractability, and usage in multi-stage decision-making, European J. Oper. Res., 292 (2021), 1004-1018.  doi: 10.1016/j.ejor.2020.11.027.

[18]

R. Jagannathan, Chance-constrained programming with joint constraints, Operations Res., 22 (1974), 358-372.  doi: 10.1287/opre.22.2.358.

[19]

R. Ji and M. A. Lejeune, Data-driven optimization of reward-risk ratio measures, INFORMS J. Comput., 33 (2021), 1120-1137.  doi: 10.1287/ijoc.2020.1002.

[20]

S. Justin and G. Leonidas, Convolutional wasserstein distances: Efficient optimal transportation on geometric domains, ACM Transactions on Graphics, 34 (2015), 1-11. 

[21]

G. R. Lanckriet, L. Ghaoui, C. Bhattacharyya and M. I. Jordan, A robust minimax approach to classification, J. Mach. Learn. Res., 3 (2003), 555-582. 

[22]

B. Piccoli and F. Rossi, On properties of the generalized Wasserstein distance, Arch. Ration. Mech. Anal., 222 (2016), 1339-1365.  doi: 10.1007/s00205-016-1026-7.

[23]

P. K. Shivaswamy, C. Bhattacharyya and A. J. Smola, Second order cone programming approaches for handling missing and uncertain data, J. Mach. Learn. Res., 7 (2006), 1283-1314. 

[24]

H. Xu, C. Caramanis and S. Mannor, Robustness and regularization of support vector machines, J. Mach. Learn. Res., 10 (2009), 1485-1510. 

[25]

S. Zymler, D. Kuhn and B. Rustem, Distributionally robust joint chance constraints with second-order moment information, Math. Program., 137 (2013), 167-198.  doi: 10.1007/s10107-011-0494-7.

[26]

S. Zymler, D. Kuhn and B. Rustem, Worst-case value at risk of nonlinear portfolios, Management Science, 59 (2013), 172-188.  doi: 10.1287/mnsc.1120.1615.

show all references

References:
[1]

G. Aurora and M. C. Victoria, Towards energy efficiency smart buildings models based on in telligent data analytics, Procedia Computer Science, 83 (2016), 994-999. 

[2]

Y. Q. Bai and K. J. Shen, Alternating direction method of multipliers for $\ell_1$-$\ell_2$ regularized logistic regression model, J. Oper. Res. Soc. China, 4 (2016), 243-253.  doi: 10.1007/s40305-015-0090-2.

[3]

Y. Q. Bai, Y. J. Shen and K. J. Shen, Consensus proximal support vector machine for classficication problems with sparse solutions, J. Oper. Res. Soc. China, 2 (2014), 57-79.  doi: 10.1007/s40305-014-0037-z.

[4]

C. Bhattacharyya, Robust classification of noisy data using second order cone programming approach, In Intelligent Sensing and Information Processing, IEEE, (2004), 433–438.

[5]

J. Blanchet, L. Chen and X. Y. Zhou, Distributionally robust mean-variance portfolio selection with wasserstein distances, preprint, arXiv: 1802.04885.

[6]

G. C. Calafiore and L. Ghaoui, On distributionally robust chance-constrained linear programs, J. Optim. Theory Appl., 130 (2006), 1-22.  doi: 10.1007/s10957-006-9084-x.

[7]

S. Chao, X. Huang and F. You, Data-driven robust optimization based on kernel learning, Computers and Chemical Engineering, 106 (2017), 464-479. 

[8]

A. Charnes, W. W. Cooper and G. H. Symonds, Cost horizons and certainty equivalents: An approach to stochastic programming of heating oil, Management Science, 4 (1958), 235-263.  doi: 10.1287/mnsc.4.3.235.

[9]

C. Cortes and V. Vapnik, Support-vector networks, Machine Learning, 20 (1995), 273-297.  doi: 10.1007/BF00994018.

[10]

M. D. Dias and A. R. Neto, Training soft margin support vector machines by simulated annealing: A dual approach, Expert Systems with Applications, 87 (2017), 157-169. 

[11]

E. Erdogan and G. Iyengar, Ambiguous chance constrained problems and robust optimization, Math. Program., 107 (2006), 37-61.  doi: 10.1007/s10107-005-0678-0.

[12]

P. M. Esfahani and D. Kuhn, Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations, Math. Program., 171 (2018), 115-166.  doi: 10.1007/s10107-017-1172-1.

[13]

R. Gao and A. J. Kleywegt, Distributionally robust stochastic optimization with wasserstein distance, preprint, arXiv: 1604.02199.

[14]

Y. Guo, K. Baker, E. Dall'Anese, Z. C. Hu and T. H. Summers, Data-based distributionally robust stochastic optimal power flow-Part I: Methodologies, IEEE Transactions on Power Systems, 34 (2019), 1483-1492.  doi: 10.1109/TPWRS.2018.2878385.

[15]

Y. Guo, K. Baker, E. Dall'Anese, Z. C. Hu and T. H. Summers, Data-based distributionally robust stochastic optimal power flow-Part II: Case studies, IEEE Transactions on Power Systems, 34 (2018), 1493-1503. 

[16]

P. Georg and W. David, Ambiguity in portfolio selection, Quant. Finance, 7 (2007), 435-442.  doi: 10.1080/14697680701455410.

[17]

B. Han, C. Shang and D. Huang, Multiple kernel learning-aided robust optimization: Learning algorithm, computational tractability, and usage in multi-stage decision-making, European J. Oper. Res., 292 (2021), 1004-1018.  doi: 10.1016/j.ejor.2020.11.027.

[18]

R. Jagannathan, Chance-constrained programming with joint constraints, Operations Res., 22 (1974), 358-372.  doi: 10.1287/opre.22.2.358.

[19]

R. Ji and M. A. Lejeune, Data-driven optimization of reward-risk ratio measures, INFORMS J. Comput., 33 (2021), 1120-1137.  doi: 10.1287/ijoc.2020.1002.

[20]

S. Justin and G. Leonidas, Convolutional wasserstein distances: Efficient optimal transportation on geometric domains, ACM Transactions on Graphics, 34 (2015), 1-11. 

[21]

G. R. Lanckriet, L. Ghaoui, C. Bhattacharyya and M. I. Jordan, A robust minimax approach to classification, J. Mach. Learn. Res., 3 (2003), 555-582. 

[22]

B. Piccoli and F. Rossi, On properties of the generalized Wasserstein distance, Arch. Ration. Mech. Anal., 222 (2016), 1339-1365.  doi: 10.1007/s00205-016-1026-7.

[23]

P. K. Shivaswamy, C. Bhattacharyya and A. J. Smola, Second order cone programming approaches for handling missing and uncertain data, J. Mach. Learn. Res., 7 (2006), 1283-1314. 

[24]

H. Xu, C. Caramanis and S. Mannor, Robustness and regularization of support vector machines, J. Mach. Learn. Res., 10 (2009), 1485-1510. 

[25]

S. Zymler, D. Kuhn and B. Rustem, Distributionally robust joint chance constraints with second-order moment information, Math. Program., 137 (2013), 167-198.  doi: 10.1007/s10107-011-0494-7.

[26]

S. Zymler, D. Kuhn and B. Rustem, Worst-case value at risk of nonlinear portfolios, Management Science, 59 (2013), 172-188.  doi: 10.1287/mnsc.1120.1615.

Table 1.  Mean performance comparison
AUC (S.E.)
Classical SVM 0.9039 0.0046
$ \ell_2 $-Wasserstein SVM 0.9105 0.0020
Table Options

Download as excel

AUC (S.E.)
Classical SVM 0.9039 0.0046
$ \ell_2 $-Wasserstein SVM 0.9105 0.0020
Table 2.  UCI Database
Date set classification numbers feature
Sonar 2 208 60
Pima 2 267 22
Heart 2 270 12
BUPA Liver 2 345 6
Ionosphere 2 351 34
Australian 2 690 14
Breast Cancer 2 699 13
Bank 2 4521 16
Table Options

Download as excel

Date set classification numbers feature
Sonar 2 208 60
Pima 2 267 22
Heart 2 270 12
BUPA Liver 2 345 6
Ionosphere 2 351 34
Australian 2 690 14
Breast Cancer 2 699 13
Bank 2 4521 16
Table 3.   
Classic SVM $ \ell_2 $-Wasserstein SVM Soft margin SVM
Data set n Accuracy (S.E.) Accuracy (S.E.) Accuracy (S.E.)
Sonar 50 0.814 0.0064 0.801 0.0050 0.799 0.0049
Sonar 70 0.856 0.0045 0.851 0.0041 0.850 0.0040
Sonar 100 0.872 0.0038 0.862 0.0033 0.860 0.0032
Pima 50 0.732 0.0055 0.723 0.0048 0.722 0.0047
Pima 70 0.745 0.0051 0.741 0.0043 0.741 0.0043
Pima 100 0.751 0.0046 0.743 0.0034 0.743 0.0034
Heart 50 0.791 0.0027 0.788 0.0025 0.787 0.0024
Heart 70 0.821 0.0024 0.815 0.0020 0.814 0.0018
Heart 100 0.833 0.0016 0.831 0.0011 0.827 0.0009
BUPA Liver 50 0.773 0.0035 0.768 0.0033 0.765 0.0028
BUPA Liver 70 0.789 0.0032 0.788 0.0031 0.788 0.0031
BUPA Liver 100 0.801 0.0025 0.801 0.0024 0.799 0.0023
Ionosphere 50 0.812 0.0054 0.810 0.0051 0.808 0.0050
Ionosphere 70 0.834 0.0037 0.842 0.0035 0.832 0.0035
Ionosphere 100 0.852 0.0033 0.848 0.0022 0.845 0.0020
Australian 50 0.812 0.0022 0.810 0.0020 0.807 0.0015
Australian 70 0.823 0.0019 0.832 0.0016 0.822 0.0015
Australian 100 0.833 0.0015 0.830 0.0013 0.830 0.0013
Breast Cancer 50 0.952 0.0023 0.951 0.0022 0.951 0.0022
Breast Cancer 70 0.955 0.0020 0.955 0.0018 0.952 0.0017
Breast Cancer 100 0.964 0.0016 0.969 0.0011 0.952 0.0009
Table Options

Download as excel

Classic SVM $ \ell_2 $-Wasserstein SVM Soft margin SVM
Data set n Accuracy (S.E.) Accuracy (S.E.) Accuracy (S.E.)
Sonar 50 0.814 0.0064 0.801 0.0050 0.799 0.0049
Sonar 70 0.856 0.0045 0.851 0.0041 0.850 0.0040
Sonar 100 0.872 0.0038 0.862 0.0033 0.860 0.0032
Pima 50 0.732 0.0055 0.723 0.0048 0.722 0.0047
Pima 70 0.745 0.0051 0.741 0.0043 0.741 0.0043
Pima 100 0.751 0.0046 0.743 0.0034 0.743 0.0034
Heart 50 0.791 0.0027 0.788 0.0025 0.787 0.0024
Heart 70 0.821 0.0024 0.815 0.0020 0.814 0.0018
Heart 100 0.833 0.0016 0.831 0.0011 0.827 0.0009
BUPA Liver 50 0.773 0.0035 0.768 0.0033 0.765 0.0028
BUPA Liver 70 0.789 0.0032 0.788 0.0031 0.788 0.0031
BUPA Liver 100 0.801 0.0025 0.801 0.0024 0.799 0.0023
Ionosphere 50 0.812 0.0054 0.810 0.0051 0.808 0.0050
Ionosphere 70 0.834 0.0037 0.842 0.0035 0.832 0.0035
Ionosphere 100 0.852 0.0033 0.848 0.0022 0.845 0.0020
Australian 50 0.812 0.0022 0.810 0.0020 0.807 0.0015
Australian 70 0.823 0.0019 0.832 0.0016 0.822 0.0015
Australian 100 0.833 0.0015 0.830 0.0013 0.830 0.0013
Breast Cancer 50 0.952 0.0023 0.951 0.0022 0.951 0.0022
Breast Cancer 70 0.955 0.0020 0.955 0.0018 0.952 0.0017
Breast Cancer 100 0.964 0.0016 0.969 0.0011 0.952 0.0009
Table 4.   
Data set n Classic SVM L2-Wasserstein SVM Soft-margin SVM
Accuracy Accuracy (10% noise) Accuracy Accuracy (10% noise) Accuracy Accuracy (10% noise)
Bank 100 0.8421 0.7870 0.8841 0.8842 0.8823 0.8743
200 0.8377 0.7798 0.8844 0.8846 0.8823 0.8773
300 0.8379 0.7785 0.8846 0.8845 0.8824 0.8768
400 0.8377 0.7757 0.8850 0.8847 0.8821 0.8763
500 0.8407 0.7735 0.8853 0.8854 0.8833 0.8765
600 0.8389 0.7759 0.8855 0.8852 0.8831 0.8775
Table Options

Download as excel

Data set n Classic SVM L2-Wasserstein SVM Soft-margin SVM
Accuracy Accuracy (10% noise) Accuracy Accuracy (10% noise) Accuracy Accuracy (10% noise)
Bank 100 0.8421 0.7870 0.8841 0.8842 0.8823 0.8743
200 0.8377 0.7798 0.8844 0.8846 0.8823 0.8773
300 0.8379 0.7785 0.8846 0.8845 0.8824 0.8768
400 0.8377 0.7757 0.8850 0.8847 0.8821 0.8763
500 0.8407 0.7735 0.8853 0.8854 0.8833 0.8765
600 0.8389 0.7759 0.8855 0.8852 0.8831 0.8775
[1]

Yu Chen, Yonggang Li, Bei Sun, Chunhua Yang, Hongqiu Zhu. Multi-objective chance-constrained blending optimization of zinc smelter under stochastic uncertainty. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021169
[2]

Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial and Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099
[3]

Ning Lu, Ying Liu. Application of support vector machine model in wind power prediction based on particle swarm optimization. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1267-1276. doi: 10.3934/dcdss.2015.8.1267
[4]

Editorial Office. RETRACTION: Peng Zhang, Chance-constrained multiperiod mean absolute deviation uncertain portfolio selection. Journal of Industrial and Management Optimization, 2019, 15 (2) : 537-564. doi: 10.3934/jimo.2018056
[5]

Yubo Yuan, Weiguo Fan, Dongmei Pu. Spline function smooth support vector machine for classification. Journal of Industrial and Management Optimization, 2007, 3 (3) : 529-542. doi: 10.3934/jimo.2007.3.529
[6]

Yubo Yuan. Canonical duality solution for alternating support vector machine. Journal of Industrial and Management Optimization, 2012, 8 (3) : 611-621. doi: 10.3934/jimo.2012.8.611
[7]

Ke-Wei Ding, Nan-Jing Huang, Yi-Bin Xiao. Distributionally robust chance constrained problems under general moments information. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2923-2942. doi: 10.3934/jimo.2019087
[8]

Amin Reza Kalantari Khalil Abad, Farnaz Barzinpour, Seyed Hamid Reza Pasandideh. A novel separate chance-constrained programming model to design a sustainable medical ventilator supply chain network during the Covid-19 pandemic. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021234
[9]

Pooja Louhan, S. K. Suneja. On fractional vector optimization over cones with support functions. Journal of Industrial and Management Optimization, 2017, 13 (2) : 549-572. doi: 10.3934/jimo.2016031
[10]

Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018
[11]

Jian Luo, Shu-Cherng Fang, Yanqin Bai, Zhibin Deng. Fuzzy quadratic surface support vector machine based on fisher discriminant analysis. Journal of Industrial and Management Optimization, 2016, 12 (1) : 357-373. doi: 10.3934/jimo.2016.12.357
[12]

Xin Li, Ziguan Cui, Linhui Sun, Guanming Lu, Debnath Narayan. Research on iterative repair algorithm of Hyperchaotic image based on support vector machine. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1199-1218. doi: 10.3934/dcdss.2019083
[13]

Fatemeh Bazikar, Saeed Ketabchi, Hossein Moosaei. Smooth augmented Lagrangian method for twin bounded support vector machine. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021027
[14]

Xin Yan, Hongmiao Zhu. A kernel-free fuzzy support vector machine with Universum. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021184
[15]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1835-1861. doi: 10.3934/jimo.2021046
[16]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[17]

Jutamas Kerdkaew, Rabian Wangkeeree. Characterizing robust weak sharp solution sets of convex optimization problems with uncertainty. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2651-2673. doi: 10.3934/jimo.2019074
[18]

Huiqin Zhang, JinChun Wang, Meng Wang, Xudong Chen. Integration of cuckoo search and fuzzy support vector machine for intelligent diagnosis of production process quality. Journal of Industrial and Management Optimization, 2022, 18 (1) : 195-217. doi: 10.3934/jimo.2020150
[19]

Qianru Zhai, Ye Tian, Jingyue Zhou. A SMOTE-based quadratic surface support vector machine for imbalanced classification with mislabeled information. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021230
[20]

Giovanni P. Crespi, Ivan Ginchev, Matteo Rocca. Two approaches toward constrained vector optimization and identity of the solutions. Journal of Industrial and Management Optimization, 2005, 1 (4) : 549-563. doi: 10.3934/jimo.2005.1.549

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (286)
  • HTML views (179)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy