臺灣博碩士論文加值系統

逐段線性方法 (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.

中文摘要 i
Abstract ii
誌謝 iv
Table of Contents v
List of Tables vii
List of Figures viii
Chapter 1 Introduction 1
1.1 Research Background 1
1.2 Literature Reviews 2
1.2.1 Conventional Piecewise Linearization Methods 4
1.2.2 Geometric Programs 10
1.2.3 Nonlinear Fractional Programs 12
1.3 Research Objectives 13
1.4 Structure of the Dissertation 14
Chapter 2 A Novel Piecewise Linearization (NPL) Method 16
2.1 Preliminary and Theorem 16
2.2 Enhanced Algorithm for Refining Break Points 34
2.3 Discussion 38
Chapter 3 NPL in Geometric Programs 40
3.1 Problem Formulation 40
3.2 The Proposed Method 42
3.3 Numerical Examples 45
3.4 Discussion 56
Chapter 4 NPL in Nonlinear Fractional Programs 57
4.1 Problem Formulation 57
4.2 The Proposed Method 58
4.3 Numerical Examples 62
4.4 Discussion 64
Chapter 5 Concluding Remarks 65
5.1 Summary 65
5.2 Further Extensions 66
References 68

[1] Atamt‥urk, A., "Flow pack facets of the single node fixed-charge flow polytope", Operations Research Letters 29 (3) (2001) 107–114.
[2] Avriel, M., Diewert, W.E., Schaible, S., Zang, I., Generalized Concavity, Mathematical Concepts in Science and Engineering, Springer-Verlag, New York, 1988.
[3] Balakrishnan, A., Magnanti, T.L., Wong, R.T., "A dual-ascent procedure for large-scale uncapacitated network design", Operations Research 37 (5) (1989) 716–740.
[4] Bazaraa, M.S., Sherali, H.D., Shetty, C.M., Nonlinear Programming: Theory and Algorithms, 2e, Wiley, New York, 1993.
[5] Benson, H.P., "Global optimization algorithm for the nonlinear sum of ratios problem", Journal of Optimization Theory and Applications 112 (1) (2002) 1–29.
[6] Benson, H.P., "Using concave envelops to globally solve the nonlinear sum of ratios problem", Journal of Global Optimization 22 (1–4) (2002) 343–364.
[7] Benson, H.P., "On the global optimization of sums of linear fractional functions over a convex set", Journal of Optimization Theory and Applications 121 (1) (2004) 19–39.
[8] Boor, C.D., A Practical Guide to Splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York, 2001.
[9] Boyd, S.P., Kim, S.J., Patil, D.D., Horowitz, M.A., "Digital circuit optimization via geometric programming", Operations Research 53 (6) (2005) 899–932.
[10] Chandra, S., Chandramohan, M., "A branch and bound method for integer nonlinear fractional programs", Z. Angew. Math. Mech. 60 (12) (1980) 735–737.
[11] Chiang, M., Boyd, S.P., "Geometric programming duals of channel capacity and rate distortion", IEEE Transactions on Information Theorey 50 (2) (2004) 245–258.
[12] Chu, C., Wong, D.F., "VLSI circuit performance optimization by geometric programming", Annals of Operations Research 105 (2001) 37–60.
[13] Clasen, R., "The solution of the chemical equilibrium programming problem with generalized benders decomposition", Operations Research 32 (1) (1984) 70–79.
[14] Coello, C.A.C., Cort`es, N.C., "Hybridizing a genetic algorithm with an artificial immune system for global optimization", Engineering Optimization 36 (5) (2004) 607–634.
[15] Craven, B.D., Fractional Programming, Heldermann, Berlin, 1988.
[16] Crouzeix, J.P., Ferland, J.A., Schaible, S., "An algorithm for generalized fractional programming", Journal of Optimization Theory and Applications 47 (1) (1985) 35–49.
[17] Croxton, K.L., Gendron, B., Magnanti, T.L., "A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems", Management Science 49 (9) (2003) 1268–1273.
[18] Dantzig, G.B., "On the significance of solving linear programming problems with some integer variables", Econometrica 28 (1960) 30–44.
[19] Dutta, A., Rama, D., "An optimization model of communications satellite planning", IEEE Transactions on Communications 40 (9) (1992) 1463–1473.
[20] Floudas, C.A., Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications, Oxford University Press, 1995.
[21] Floudas, C.A., Deterministic Global Optimization: Theory, Methods and Applications, Kluwer Academic Publishers, Boston, 2000.
[22] Geoffrion, A.M., "Objective function approximations in mathematical programming", Mathematical Programming 13 (1977) 23–37.
[23] Golinski, J., "An adaptive optimization system applied to machine synthesis", Mechanism and Machine Synthesis 8 (1973) 419–436.
[24] Grunspan, M., Thomas, M.E., "Hyperbolic integer programming", Naval Research Logistics Quarterly 20 (1973) 341–356.
[25] G‥uder, F., Morris, J.G., "Optimal objective function approximation for separable convex quadratic programming", Mathematical Programrning 67 (1) (1994) 133–142.
[26] Hajiaghayi, M.T., Mahdian, M., Mirrokni, V.S., "The facility location problem with general cost functions", Networks 42 (1) (2003) 42–47.
[27] Hershenson, M., Boyd, S.P., Lee, T., "Optimal design of a CMOS op-amp via geometric programming", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 20 (1) (2001) 1–21.
[28] Hillier, F.S., Lieberman, G.J., Introduction to Operations Research, 8e, McGraw-Hill Science, New York, 2005.
[29] Holmberg, K., Hellstrand, J., "Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound", Operations Research 46 (2) (1998) 247–259.
[30] Horst, R., Tuy, H., Global Optimization: Deterministic Approaches, 3e, Springer-Verlag, New York, 2003.
[31] Ibaraki, T., "Parametric approaches to fractional programs", Mathematical Programming 26 (1983) 345–362.
[32] Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V., "Greedy facility location algorithms analyzed using dual fitting with factor-revealing", Journal of the ACM 50 (6) (2003) 795–824.
[33] Jha, N., "A discrete data base multiple objective optimization of milling operation through geometric programming", Journal of Engineering for Industry 112 (1990) 368–374.
[34] Kandukuri, S., Boyd, S.P., "Optimal power control in interference-limited fading wireless channels with outage-probability specifications", IEEE Transactions on Wireless Communications 1 (1) (2002) 46–55.
[35] Klein, E.M., Sim, S.H., "Discharge allocation for hydro-electric generating stations", European Journal of Operational Research 73 (1) (1994) 132–138.
[36] Kontogiorgis, S., "Practical piecewise-linear approximation for monotropic optimization", INFORMS Journal on Computing 12 (4) (2000) 324–340.
[37] Konno, H., Fukaishi, K., "A branch-and-bound algorithm for solving low-rank linear multiplicative and fractional programming problems", Journal of Global Optimization 18 (3) (2000) 283–299.
[38] Konno, H., Kuno, T., Yajima, Y., "Global minimization of a generalized convex multiplicative function", Journal of Global Optimization 4 (1) (1994) 47–62.
[39] Li, H.-L., "A global approach for general 0–1 fractional programming", European Journal of Operational Research 73 (1994) 590–596.
[40] Li, H.-L., "Notes: an efficient method for solving linear goal programming problems", Journal of Optimization Theory and Applications 90 (1996) 465–469.
[41] Li, H.-L., Chang, C.-T., "An approximate approach of global optimization for polynomial programming problems", European Journal of Operational Research 107 (1998) 625–632.
[42] Li, H.-L., Huang, C.H., Lu, H.C., "An effective linear approximation method for separable functions", submitted to Operations Research Letters (2006).
[43] Li, H.-L., Lu, H.C., Huang, C.H., "Technical note: a superior representation method for piecewise linear functions", submitted to INFORMS Journal on Computing (2007).
[44] Li, H.-L., Tsai, J.F., "Treating free variables in generalized geometric global optimization programs", Journal of Global Optimization 33 (1) (2005) 1–13.
[45] Li, H.-L., Yu, C.-S., "A global optimization method for nonconvex separable programming problems", European Journal of Operational Research 117 (2) (1999) 275–292.
[46] Maranas, C.D., Floudas, C.A., "Global optimization in generalized geometric programming", Computers and Chemical Engineering 21 (1997) 351–370.
[47] Moh, T.-S., Chang, T.-S., Hakimi, S., "Globally optimal floorplanning for a layout problem", IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 43 (29) (1996) 713–720.
[48] Mohan, S., Hershenson, M., Boyd, S.P., Lee, T., "Simple accurate expressions for planar spiral inductances", IEEE Journal of Solid-State Circuit 34 (10) (1999) 1419–1424.
[49] Mohan, S., Hershenson, M., Boyd, S.P., Lee, T., "Bandwidth extension in CMOS with optimized on-chip inductors", IEEE Journal of Solid-State Circuits 35 (3) (2000) 346–355.
[50] Ortega, F., Wolsey, L.A., "A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem", Networks 41 (3) (2003) 143–158.
[51] Padberg, M., "Approximating separable nonlinear functions via mixed zero-one programs", Operations Research Letters 27 (2000) 1–5.
[52] Quesada, I., Grossmann, I., "A global optimization algorithm for linear fractional and bilinear programs", Journal of Global Optimization 6 (1) (1995) 39–76.
[53] Ravindran, A., Ragsdell, K.M., Reklaitis, G.V., Engineering Optimization, Methods and Applications, 2e, John Wiley and Sons, New York, 2006.
[54] Rosen, J.B., Pardolas, P.M., "Global minimization of large-scale constrained concave quadratic problems by separable programming", Mathematical Programming 34 (2) (1986) 163–174.
[55] Rosenberg, E., "Optimization module sizing in VLSI floorplanning by nonlinear programming", ZOR-Methods and Models of Operations Research 33 (2) (1989) 131–143.
[56] Sandgren, E., "Nonlinear integer and discrete programming in mechanical design", Proceedings of the ASME Design Technology Conference (1988) 95–105.
[57] Sandgren, E., "Nonlinear integer and discrete programming in mechanical design optimization", Journal of Mechanical Design, Transactions of the ASME 112 (2) (1990) 223–229.
[58] Schaible, S., "Duality in fractional programming: a unified approach", Operations Research 24 (1976) 452–461.
[59] Schaible, S., Fractional Programming, in: Horst, R., Pardalos, P.M. (Eds.), Handbook of Global Optimization, pp. 495–608. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995.
[60] Sherali, H.D., Tuncbilek, C.H., "A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique", Journal of Global Optimization 2 (1992) 101–112.
[61] Sherali, H.D., Adams, W.P., Driscoll, P.J., "Exploiting special structures in constructing a hierarchy of relaxations for 0–1 mixed integer problems", Operations Research 46 (1998) 396–405.
[62] Sonmez, A., Baykasoglu, A., Dereli, T., Flz, I., "Dynamic optimization of multipass milling operations via geometric programming", International Journal of Machine Tools and Manufacture 39 (2) (1999) 297–320.
[63] Thakur, L.S., "Error analysis for convex separable programs: the piecewise linear approximation and the bounds on the optimal objective value", SIAM Journal on Applied Mathematics 34 (4) (1978) 704–714.
[64] Topaloglu, H., Powell, W.B., "An algorithm for approximating piecewise linear concave functions from sample gradients", Operations Research Letters 31 (2003) 66–76.
[65] Tsai, J.-F., Li, H.-L., Hu, N.-Z., "Global optimization for signomial discrete programming problems in engineering design", Engineering Optimization 34 (6) (2002) 613–622.
[66] Vajda, S., Mathematical Programming, Addison-Wesley, New York, 1964.
[67] Wall, T., Greening, D., Woolsey, R., "Solving complex chemical equilibria using a geometric-programming based technique", Operations Research 34 (3) (1986) 345–355.