基于随机矩阵的差分代换算法的完备化

徐嘉, 姚勇

数学学报 ›› 2011, Vol. 54 ›› Issue (2) : 219-226.

PDF(530 KB)
PDF(530 KB)
数学学报 ›› 2011, Vol. 54 ›› Issue (2) : 219-226. DOI: 10.12386/A2011sxxb0023
论文

基于随机矩阵的差分代换算法的完备化

    徐嘉1, 姚勇2
作者信息 +

Completion of Difference Substitution Method Based on Stochastic Matrix

    Jia XU1, Yong YAO2
Author information +
文章历史 +

摘要

本文利用有限核原理,给出了基于随机矩阵的逐次差分代换方法 的一个完备化. 获得了判定多项式半正定性的完全算法.此算法可 进一步应用于计算有理函数的全局最优值.与常用的数值最优化方法不同的是, 本方法获得的是精确符号解.

 

Abstract

In this paper, the principle of finite kernel is used to complete the successive difference substitution. Then a complete algorithm for deciding positive semi-definite polynomial is presented. This algorithm can be applied further to compute the global optimization of rational function. Being different from any other common methods of numerical optimization, the method in this paper gets accurate symbolic solution.

 

关键词

逐次差分代换方法 / 不等式机器证明 / 完备化

Key words

method of successive difference substitution / automated proving for inequality / completion

引用本文

导出引用
徐嘉, 姚勇. 基于随机矩阵的差分代换算法的完备化. 数学学报, 2011, 54(2): 219-226 https://doi.org/10.12386/A2011sxxb0023
Jia XU, Yong YAO. Completion of Difference Substitution Method Based on Stochastic Matrix. Acta Mathematica Sinica, Chinese Series, 2011, 54(2): 219-226 https://doi.org/10.12386/A2011sxxb0023

参考文献


[1] Yang L., Solving Harder Problems with Lesser Mathematics, Proceedings of the 10th Asian Technology Conference in Mathematics, ATCM Inc, 2005, 37-46.

[2] Yang L., Difference Substitution and Automated Inequality Proving, J. of Guangzhou University (Natural Science Edition), 2006, 5(2): 1-7.

[3] Yang L., Xia B. C., Automated Proving and Discoverering on Inequalities, Beijing: Science Press, 2008, 22: 174.

[4] Yao Y., Successive Difference Substitution Based on Column Stochastic Matrix and Mechanical Decision for Positive Semi-definite Forms, Scientia Sinica Mathematica, 2010, 40(3): 251-264 (in Chinese). (Also see http://arxiv.org/abs/0904.4030v3)

[5] Yang L., Yao Y., Difference substitution matrices and decision on nonnegativity of polynomials, J. Sys. Sci. & Math. Scis., 2009, 29(9): 1169-1177 (in Chinese).

[6] Wu W. T., On Global-Optimization Problems, Proc. ASCM‘98, Lanzhou: Lanzhou University Press, 1998: 135-138 (in Chinese).

[7] Wu W. T., Mathematics Mechanization, Beijing: Science Press, 2003 (in Chinese).

[8] Yang L., A Symbolic Algorithm for Global Optimization and Finiteness Principle, In: Lin D. D. et al eds, Mathematics and Mathematics Mechanization, Jinan: Shandong Educational Publishing House, 2001: 210- 220 (in Chinese).

[9] Yang L., Xia S. H., An inequality-proving program applied to global optimization, Proceedings of ATCM 2000, W-C.Yang et al (eds.), ATCM, Inc., Blacksburg, 2000: 40-51. (Also see http://epatcm.any2any.us/EP/EP2000/ATCMP208/fullpaper.pdf)

[10] Joachim V. Z. G., Jurgen G., Modern Computer Algebra, Combridge: Combridge University Press, 1999: 369-370.

[11] Basu S., Pollack R., Roy M. F., Algorithms in Real Algebraic Geometry (2nd), New York, Berlin, Heidelberg: Springer-Verlag, 2006, 352.

[12] Collins G. E., Akritas A. G., Polynomial Real Root Isolation Using Descartes’ Rule of Signs, Poceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computations, New York: Yorktown Heights, 1976: 272-275.

[13] Parrilo P. A., Sturmfels B., Minimizing Polynomial Functions, arXiv: math/0103170.

[14] Yang L., Zhang J., A Practical program of automated proving for a class of geometric inequalities, In: Richter-Gebert J, Wand D eds. Automated Deduction in Geometry, LNAI 2061, Berlin: Springer-Verlag, 2001: 41-57.

[15] Yang L., Xia S. H., Automated Proving for a class of constructive geometric inequalities, Chinese J. Computer, 2003, 26(7): 769-778 (in Chinese).

[16] Canny J., The Complexity of Robot Motion Planning, Massachusetts: MIT Press, 1987.

[17] Xu J., Yao Y., Rationalizing Algorithm and Automated Proving for a Class of Inequalities Involving Radicals, Chinese J. Computer, 2008, 31(1): 24-31.

[18] Yao Y., Xu J., Descartes’ Law of Signs for Generalized Polynomials and Its Application in the Method of Descent, Acta Mathematica Sinica, Chinese Series, 2009, 52(4): 625-630.

[19] Chen S. L., Yao Y., Schur Subspace of Real Symmetric Forms and Application, Acta Mathematica Sinica, Chinese Series, 2007, 50(6): 1331-1348.

[20] Wang W. L., Wen J. J., Shi H. L., On the optimal values for inequalities involving power means, Acta Mathematica Sinica, Chinese Series, 2004, 47(6): 1053-1062.

[21] Chen S. L., Huang F. J., Schur decomposition for symmetric ternary forms and Rradable proof to inequalities, Acta Mathematica Sinica, Chinese Series, 2006, 49(3): 491-502.

基金

国家自然科学基金(90718041,11001228,10901116);中科院知识创新工程重要方向项目(KJCX-YW);西南民族大学中央高校基本科研业务费专项资金(09NZYZJ07)及人才引进项目(2009RC004)

PDF(530 KB)

789

Accesses

0

Citation

Detail

段落导航
相关文章

/