研究生: |
黎敬凡 |
---|---|
論文名稱: |
一個連續的方法在費雪-伯麥斯特函數上去解決二進位的二次的規畫問題 A continuation approach for solving binary quadratic program based on generalized Fischer-Burmeister function |
指導教授: | 陳界山 |
學位類別: |
碩士 Master |
系所名稱: |
數學系 Department of Mathematics |
論文出版年: | 2011 |
畢業學年度: | 99 |
語文別: | 英文 |
論文頁數: | 25 |
中文關鍵詞: | 非線性互補問題 、費雪-伯麥斯特函數 、二進位的二次的規畫問題 |
英文關鍵詞: | Nonlinear complementarity problem, Fischer-Burmeister function, Binary quadratic program |
論文種類: | 學術論文 |
相關次數: | 點閱:158 下載:6 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在這篇文章中,我們考慮用推廣的 費雪-伯麥斯特 函數在對 二進位的二次的規畫問題的連續方法。更精確的說,經由一個全域的連續方法我們將二進位的二次的規畫問題等價轉成求最小值的問題。這樣的連續方法在文獻 [8] 已經
被提到了而且是用在費雪-伯麥斯特。我們觀察研究這個連續方法並再次應用在更推廣的叫做推廣的費雪-伯麥斯特函數中。
In the paper, we consider a continuation approach for the binary quadratic program(BQP) based on the generalized Fischer-Burmeister function. More specically, we recast the BQP as an equivalent minimization and then seeks its global minimizer via a global continuation method. Such approach had been considered in [8] which is based on the Fischer-Burmeister function. We investigate this continuation approach again by using a more general function, called the generalized Fischer-Burmeister function.
[1] B. Alidaee, G. Kochenberger and A. Ahmadian, 0−1 quadratic programming
approach for the optimal solution of two scheduling problems, International Journal
of Systems Science, vol. 25, pp. 401-408, 1994.
[2] L. D. Berkovitz, Convexity and Optimization in IRn, John Wiley & Sons, Inc.,
2002.
[3] S. Burer, R. Monterio and Y. Zhang, Rank-two relaxation heuristics for Max-
Cut and other binary quadratic programs, SIAM Journal on Optimization, vol. 12,
pp. 503-521, 2001.
[4] J.-S. Chen, The semismooth-related properties of a merit function and a descent
method for the nonlinear complementarity problem, Journal of Global Optimization,
vol. 36, pp. 565-580, 2006.
[5] J.-S. Chen, H.-T. Gao and S. Pan, An R-linearly convergent derivative-free algorithm
for the NCPs based on the generalized Fischer-Burmeister merit function,
Journal of Computational and Applied Mathematics, vol. 232, pp. 455-471, 2009.
[6] J.-S. Chen and S. Pan, A family of NCP-functions and a descent method for the
nonlinear complementarity problem, Computational Optimization and Applications,
vol. 40, pp. 389-404, 2008.
[7] J. Luo, K. Pattipati, P. Willett and F. Hasegawa, em Near-optimal multiuser
detection in synchronous CDMA using probabilistic data association, IEEE
Communications Letters, vol. 5, pp. 361-363, 2001.
[8] W. Murray and K.-M. Ng, An algorithm for nonlinear optimization problems with
binary variables Computational Optimization and Applications, vol. 47, pp. 257-288,
2010.
[9] K.-M. Ng, A continuation approach for solving nonlinear optimization problems with
discrete variables, Ph.D. thesis, Management Science and Engineering Department,
Stanford University, USA, 2002.
[10] S.-H. Pan, T. Tan and Y. Jiang, A global continuation algorithm for solving
binary quadratic programming problems, Computational Optimization and Applications,
vol. 41, pp. 349–362, 2008.
[11] P. M. Pardalos, Conyinuous approaches to discrete optimization problems, In:
Nonlinear Optimization and Applications, G. Di, F. Giannesi (eds.), pp. 313-328,
Plenum, New York, 1996.
[12] P. M. Pardalos and G. R. Rodgers, A branch and bound algorithm for maximum
clique problem, Computers and Operations Research, vol. 19, pp. 363-375, 1992.
[13] A. T. Philips and J. B. Rosen, A quadratic assignment formulation of the molecular
conformation problem, Journal of Global Optimization, vol. 4, pp. 229-241, 1994.
[14] S. Polijak and H. Wolkowicz, Convex relaxation of (0, 1)-quadratic programming,
Mathematics of Operations Research, vol. 3, pp. 550-561, 1995.