一個連續的方法在費雪-伯麥斯特函數上去解決二進位的二次的規畫問題

A continuation approach for solving binary quadratic program based on generalized Fischer-Burmeister function

黎敬凡

指導教授 ： 陳界山

國立臺灣師範大學/理學院/數學系/碩士(2011年)

摘要

在這篇文章中，我們考慮用推廣的 費雪-伯麥斯特 函數在對 二進位的二次的規畫問題的連續方法。更精確的說，經由一個全域的連續方法我們將二進位的二次的規畫問題等價轉成求最小值的問題。這樣的連續方法在文獻 [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.

並列關鍵字

Nonlinear complementarity problem ； Fischer-Burmeister function ； Binary quadratic program

參考文獻

approach for the optimal solution of two scheduling problems, International Journal

[2] L. D. Berkovitz, Convexity and Optimization in IRn, John Wiley & Sons, Inc.,

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

[4] J.-S. Chen, The semismooth-related properties of a merit function and a descent