簡易檢索 / 詳目顯示

研究生: 黎敬凡
論文名稱: 一個連續的方法在費雪-伯麥斯特函數上去解決二進位的二次的規畫問題
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. Introduction……………………………………………………………………1 2. Continuous Formulation based on p  function…………….2 3. Global continuation algorithm for BQP…………………………16 4. References………………………………………………………………………19 5. Appendix……………………………………………………………………………21

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

    下載圖示
    QR CODE