以逐段線性方法求解幾何規劃問題

Abstract

逐段線性方法 (piecewise linearization method) 常運用於資料回歸, 網路分析, 運籌管理與統計學等領域。1950年代早期, 便已知引進0-1變數將凹函數(concave function)線性化。然而此線性化程序亦有其缺點, 即需要使用大量的0-1變數線性化凹函數, 因此在線性化之後, 其原問題之規模亦會相對激增。

在使用傳統逐段線性方法時, 若將凹函數以m個斷點(break point)線性化, 則需引進m-1個0-1變數。當斷點個數增加時, 其運算將非常耗時, 並將造成相當大的運算負擔。

本論文提出一新的逐段線性方法, 其所使用的0-1變數個數, 由傳統的m-1 減少為 log2 (m-1), 此新方法具有以下之特性: (i) 以較簡易與有效率的方式表達逐段線性函數; (ii) 使用較少之0-1變數; (iii) 經實驗結果證明, 此新方法較傳統方法快速且有效率, 特別是當所使用之斷點相當多時。此外, 本論文並將所提出之方法運用於求解幾何規劃問題(geometric programs)與非線性分數問題(nonlinear fractional programs)。

The piecewise linearization methods have been applied in numerous applications, including data fitting, network analysis, logistics, and statistics. In the early 1950s, they have been recognized that a concave function can be linearized by introducing 0--1 variables.

Most textbooks in Operations Research offer some methods of expressing linear approximations in this manner. Many methods of linearization have also been developed in recent literature.

Nevertheless, the transformed linear approach often encounters a severe shortcoming. Standard procedures for linearizing typically involve a radical increase in the number of binary variables. Consequently, the gains to be derived from dealing with linear functions are quite likely to be nullified by the increased problem size.

For linearizing a concave function with m break points, the conventional methods require to use m-1 binary variables. However, when m becomes large, the computation will be very time-consuming and may cause heavy computational burden.

This dissertation proposes a novel technique in which only log2 (m-1) binary variables are used. The proposed method has the following features: (i) it uses more convenient and efficient way to express a piecewise linear function; (ii) less number of 0--1 variables are used; (iii) the omputational results show that the proposed method is much efficient and faster than the conventional one especially when the number of break points becomes large.

The proposed method has been applied to solve the two major problems, geometric programs (GP) and nonlinear fractional programs (NFP), which are popular in engineering design and management science. The efficiency and feasibility of the proposed methods can be verified through illustrations.