数学学报 2011, 54(2) 219-226 DOI:      ISSN: 0583-1431 CN: 11-2038/O1

本期目录 | 下期目录 | 过刊浏览 | 高级检索                                                            [打印本页]   [关闭]
论文
扩展功能
本文信息
Supporting info
PDF(530KB)
[HTML全文]
参考文献[PDF]
参考文献
服务与反馈
把本文推荐给朋友
加入我的书架
加入引用管理器
引用本文
Email Alert
文章反馈
浏览反馈信息
本文关键词相关文章
逐次差分代换方法
不等式机器证明
完备化
本文作者相关文章
徐嘉
姚勇
基于随机矩阵的差分代换算法的完备化
徐嘉1, 姚勇2
1. 西南民族大学计算机科学与技术学院 成都 610041;
2. 中国科学院成都计算机应用研究所 成都 610041
摘要
本文利用有限核原理,给出了基于随机矩阵的逐次差分代换方法 的一个完备化. 获得了判定多项式半正定性的完全算法.此算法可 进一步应用于计算有理函数的全局最优值.与常用的数值最优化方法不同的是, 本方法获得的是精确符号解.

 

关键词 逐次差分代换方法   不等式机器证明   完备化  
MSC2000 O178
Completion of Difference Substitution Method Based on Stochastic Matrix
Jia XU1, Yong YAO2
1. College of Computer Science and Technology, Southwest University for Nationalities, Chengdu 610041, P. R. China;
2. Chengdu Institute of Computer Applications, Chinese Academy of Sciences, Chengdu 610041, P. R. China
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.

 

Keywords: method of successive difference substitution   automated proving for inequality   completion  
收稿日期 2010-05-03 修回日期 2010-09-30 网络版发布日期  
DOI:
基金项目:

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

通讯作者:
作者简介:
作者Email: xujia8106@yahoo.cn; yaoyong@casit.ac.cn

参考文献:


[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.

本刊中的类似文章
1.洪家兴 ;刘嘉菳.本刊外文版6卷1期文章简介[J]. 数学学报, 1991,34(2): 286-288
2.董荣森.∩-弱完全分配格的完备化[J]. 数学学报, 1988,31(5): 584-594
3.仝道荣.可换格群的拓扑完备化[J]. 数学学报, 1986,29(2): 249-252
4.李才中;丁夏畦.空间L_p(E_n)的嵌入定理[J]. 数学学报, 1979,22(2): 258-260

Copyright by 数学学报