doi: 10.3934/jimo.2019015

Statistical inference of semidefinite programming with multiple parameters

School of Mathematical Sciences, Dalian University of Technology, Dalian, 116024, China

* Corresponding author: Jiani Wang

Received  May 2018 Revised  October 2018 Published  March 2019

Fund Project: Jiani Wang is supported by NNSFC grant Nos. 11571059, 11731013 and 91330206

The parameters in the semidefinite programming problems generated by the average of a sample, may lead to the deviation of the optimal value and optimal solutions due to the uncertainty of the data. The statistical properties of estimates of the optimal value and the optimal solutions are given in this paper, when the estimated parameters are both in the objective function and in the constraints. This analysis is mainly based on the theory of the linear programming and the perturbation theory of the semidefinite programming.

Citation: Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019015
References:
[1]

F. AlizadehJ. P. A. Haeberly and M. L. Overton, Complementarity and nondegeneracy in semidefinite programming, Mathematical Programming, 77 (1997), 111-128.  doi: 10.1007/BF02614432.  Google Scholar

[2]

H. Bauer, Measure and Integration Theory (Vol. 26), Walter de Gruyter, Berlin, 2001. doi: 10.1515/9783110866209.  Google Scholar

[3]

P. Billingsley, Probability and Measure (3rd ed.), Wiley series in probability and mathematical statistics, New York, 1995.  Google Scholar

[4]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4612-1394-9.  Google Scholar

[5]

M. W. Browne, Fitting the factor analysis model, ETS Research Report Series, 1967 (1967), i–43. Google Scholar

[6]

E. J. Candés and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational mathematics, 9 (2009), 717-772.  doi: 10.1007/s10208-009-9045-5.  Google Scholar

[7]

M. DürB. Jargalsaikhan and G. Still, Genericity results in linear conic programming–a tour d'horizon, Mathematics of Operations Research, 42 (2017), 77-94.  doi: 10.1287/moor.2016.0793.  Google Scholar

[8]

H. Fischer, A History of the Central Limit Theorem: From Classical to Modern Probability Theory, Springer, New York, 2011. doi: 10.1007/978-0-387-87857-7.  Google Scholar

[9]

A. Hald, A History of Mathematical Statistics from 1750 to 1930, Wiley, 1998.  Google Scholar

[10]

J.-B. Hiriart-Urruty, Fundamentals of Convex Analysis, Springer-Verlag, New York, 2001. doi: 10.1007/978-3-642-56468-0.  Google Scholar

[11]

H. B. Mann and A. Wald, On stochastic limit and order relationships, Annals of Mathematical Statistics, 14 (1943), 217-226.  doi: 10.1214/aoms/1177731415.  Google Scholar

[12]

A. Shapiro, Rank-reducibility of a symmetric matrix and sampling theory of minimum trace factor analysis, Psychometrika, 47 (1982), 187-199.  doi: 10.1007/BF02296274.  Google Scholar

[13]

A. Shapiro, Statistical inference of semidefinite programming, Mathematical Programming, (2018), 1–21, Available from: http://www.optimization-online.org/DB\_HTML/2017/01/5842.html. doi: 10.1007/s10107-018-1250-z.  Google Scholar

[14]

A. Shapiro and K. Scheinberg, Duality and optimality conditions, in Handbook of Semidefinite Programming, Springer, Boston, MA, 27 (2000), 66–110. doi: 10.1007/978-1-4615-4381-7_4.  Google Scholar

[15]

A. Shapiro and J. M. F. Ten Berge, Statistical inference of minimum rank factor analysis, Psychometrika, 67 (2002), 79-94.  doi: 10.1007/BF02294710.  Google Scholar

[16]

E. Slutsky, Uber stochastische asymptoten und grenzwerte, Metron, 5 (1925), 3-89.   Google Scholar

[17]

M. J. Todd, Semidefinite optimization, Acta Numerica, 10 (2001), 515-560.  doi: 10.1017/S0962492901000071.  Google Scholar

[18] A. W. Van der Vaart, Asymptotic Statistics, Cambridge University Press, New York, 1998.  doi: 10.1017/CBO9780511802256.  Google Scholar

show all references

References:
[1]

F. AlizadehJ. P. A. Haeberly and M. L. Overton, Complementarity and nondegeneracy in semidefinite programming, Mathematical Programming, 77 (1997), 111-128.  doi: 10.1007/BF02614432.  Google Scholar

[2]

H. Bauer, Measure and Integration Theory (Vol. 26), Walter de Gruyter, Berlin, 2001. doi: 10.1515/9783110866209.  Google Scholar

[3]

P. Billingsley, Probability and Measure (3rd ed.), Wiley series in probability and mathematical statistics, New York, 1995.  Google Scholar

[4]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4612-1394-9.  Google Scholar

[5]

M. W. Browne, Fitting the factor analysis model, ETS Research Report Series, 1967 (1967), i–43. Google Scholar

[6]

E. J. Candés and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational mathematics, 9 (2009), 717-772.  doi: 10.1007/s10208-009-9045-5.  Google Scholar

[7]

M. DürB. Jargalsaikhan and G. Still, Genericity results in linear conic programming–a tour d'horizon, Mathematics of Operations Research, 42 (2017), 77-94.  doi: 10.1287/moor.2016.0793.  Google Scholar

[8]

H. Fischer, A History of the Central Limit Theorem: From Classical to Modern Probability Theory, Springer, New York, 2011. doi: 10.1007/978-0-387-87857-7.  Google Scholar

[9]

A. Hald, A History of Mathematical Statistics from 1750 to 1930, Wiley, 1998.  Google Scholar

[10]

J.-B. Hiriart-Urruty, Fundamentals of Convex Analysis, Springer-Verlag, New York, 2001. doi: 10.1007/978-3-642-56468-0.  Google Scholar

[11]

H. B. Mann and A. Wald, On stochastic limit and order relationships, Annals of Mathematical Statistics, 14 (1943), 217-226.  doi: 10.1214/aoms/1177731415.  Google Scholar

[12]

A. Shapiro, Rank-reducibility of a symmetric matrix and sampling theory of minimum trace factor analysis, Psychometrika, 47 (1982), 187-199.  doi: 10.1007/BF02296274.  Google Scholar

[13]

A. Shapiro, Statistical inference of semidefinite programming, Mathematical Programming, (2018), 1–21, Available from: http://www.optimization-online.org/DB\_HTML/2017/01/5842.html. doi: 10.1007/s10107-018-1250-z.  Google Scholar

[14]

A. Shapiro and K. Scheinberg, Duality and optimality conditions, in Handbook of Semidefinite Programming, Springer, Boston, MA, 27 (2000), 66–110. doi: 10.1007/978-1-4615-4381-7_4.  Google Scholar

[15]

A. Shapiro and J. M. F. Ten Berge, Statistical inference of minimum rank factor analysis, Psychometrika, 67 (2002), 79-94.  doi: 10.1007/BF02294710.  Google Scholar

[16]

E. Slutsky, Uber stochastische asymptoten und grenzwerte, Metron, 5 (1925), 3-89.   Google Scholar

[17]

M. J. Todd, Semidefinite optimization, Acta Numerica, 10 (2001), 515-560.  doi: 10.1017/S0962492901000071.  Google Scholar

[18] A. W. Van der Vaart, Asymptotic Statistics, Cambridge University Press, New York, 1998.  doi: 10.1017/CBO9780511802256.  Google Scholar
Table 1.  $ \hat{\vartheta}_N $ in the case that the optimal solution is not unique
N Bias SD SE CP
100 -0.01575607 0.09802304 0.1026943 0.959
300 -0.008588234 0.05875263 0.05928791 0.947
800 -0.005730269 0.03494695 0.03630683 0.953
N Bias SD SE CP
100 -0.01575607 0.09802304 0.1026943 0.959
300 -0.008588234 0.05875263 0.05928791 0.947
800 -0.005730269 0.03494695 0.03630683 0.953
Table 2.  $ \hat{\vartheta}_N $ with the unique optimal solution
N Bias SD SE CP
100 -0.008575782 0.2752905 0.283196 0.954
300 0.000433069 0.1598366 0.1635033 0.953
800 0.002228357 0.1022441 0.1001249 0.948
N Bias SD SE CP
100 -0.008575782 0.2752905 0.283196 0.954
300 0.000433069 0.1598366 0.1635033 0.953
800 0.002228357 0.1022441 0.1001249 0.948
Table 3.  $ \hat{x}_N $ with the unique optimal solution
N x Bias SD SE CP
100 $ x_1 $ 0.001119686 0.1960365 0.2006396 0.956
$ x_2 $ -0.005239017 0.2040734 0.2006396 0.951
400 $ x_1 $ 0.003114901 0.09937129 0.1003198 0.948
$ x_2 $ 0.004845715 0.1005173 0.1003198 0.946
1000 $ x_1 $ -0.0001884376 0.06216153 0.06344781 0.943
$ x_2 $ 0.005075925 0.06360439 0.06344781 0.952
N x Bias SD SE CP
100 $ x_1 $ 0.001119686 0.1960365 0.2006396 0.956
$ x_2 $ -0.005239017 0.2040734 0.2006396 0.951
400 $ x_1 $ 0.003114901 0.09937129 0.1003198 0.948
$ x_2 $ 0.004845715 0.1005173 0.1003198 0.946
1000 $ x_1 $ -0.0001884376 0.06216153 0.06344781 0.943
$ x_2 $ 0.005075925 0.06360439 0.06344781 0.952
[1]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[2]

Jiang-Xia Nan, Deng-Feng Li. Linear programming technique for solving interval-valued constraint matrix games. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1059-1070. doi: 10.3934/jimo.2014.10.1059

[3]

Evangelos Evangelou. Approximate Bayesian inference for geostatistical generalised linear models. Foundations of Data Science, 2019, 1 (1) : 39-60. doi: 10.3934/fods.2019002

[4]

Behrouz Kheirfam. Multi-parametric sensitivity analysis of the constraint matrix in piecewise linear fractional programming. Journal of Industrial & Management Optimization, 2010, 6 (2) : 347-361. doi: 10.3934/jimo.2010.6.347

[5]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477

[6]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323

[7]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[8]

Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863

[9]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

[10]

Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003

[11]

Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019041

[12]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020024

[13]

Mark S. Gockenbach, Akhtar A. Khan. Identification of Lamé parameters in linear elasticity: a fixed point approach. Journal of Industrial & Management Optimization, 2005, 1 (4) : 487-497. doi: 10.3934/jimo.2005.1.487

[14]

Tomasz Komorowski. Long time asymptotics of a degenerate linear kinetic transport equation. Kinetic & Related Models, 2014, 7 (1) : 79-108. doi: 10.3934/krm.2014.7.79

[15]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[16]

Sun-Sig Byun, Hongbin Chen, Mijoung Kim, Lihe Wang. Lp regularity theory for linear elliptic systems. Discrete & Continuous Dynamical Systems - A, 2007, 18 (1) : 121-134. doi: 10.3934/dcds.2007.18.121

[17]

Roman Šimon Hilscher. On general Sturmian theory for abnormal linear Hamiltonian systems. Conference Publications, 2011, 2011 (Special) : 684-691. doi: 10.3934/proc.2011.2011.684

[18]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187

[19]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127

[20]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020034

2018 Impact Factor: 1.025

Article outline

Figures and Tables

[Back to Top]