進階搜尋


下載電子全文  
系統識別號 U0026-2801201914461900
論文名稱(中文) 使用Robust 優化技巧以選擇具有最大獲益的基因型態
論文名稱(英文) Robust Optimization for Selection of Genotypes with Maximum Genetic Gain
校院名稱 成功大學
系所名稱(中) 數學系應用數學碩博士班
系所名稱(英) Department of Mathematics
學年度 107
學期 1
出版年 107
研究生(中文) 蔡幸樺
研究生(英文) Sing-Hua Cai
學號 L16054041
學位類別 碩士
語文別 英文
論文頁數 79頁
口試委員 指導教授-許瑞麟
口試委員-王逸琳
口試委員-林仁彥
中文關鍵字 半定規劃  線性規劃  二階錐規劃  錐鬆弛問題  Robust優化  擾動 
英文關鍵字 Semi-definite programming  Linear programming  Second-order cone programming  Conic relaxation  Robust optimization  perturbation 
學科別分類
中文摘要 在這篇論文中,我們首先回顧了三個在S. Safarina等人(2017) 中提出的錐鬆弛問題:半定規劃(SDP)、線性規劃(LP)及二階錐規劃(SOCP),目的是為了選擇最佳的基因型,以最大化基因的獲益。然而,我們考慮LP鬆弛問題的魯棒優化,並結合最陡峭上升法,以獲得不確定數據之平等部署(ED)問題的合適解。最後,我們進行了數值實驗,以測試所產生的擾動之可行性。
英文摘要 In this thesis, we first review the three conic relaxation: SDP (Semi-definite programming), LP (Linear programming), and SOCP (Second-order cone programming), proposed in S. Safarina et al.(2017) for the optimum selection of genotypes that maximize genetic gain.
Then, we consider the robust optimization to the LP relaxation and incorporate with a steepest ascent method to acquire an appropriate solution for the equal deployment(ED) problem subject to uncertainty data.
At last, we conduct numerical experiments to test the feasibility incurred by the perturbation.
論文目次 1 Introduction 1

2 Literature review 9

3 Conic Relaxation Problems for Selection of Genotypes with Maximum Genetic Gain 12
3.1 The SDP and the LP relaxation problems for the ED problem 19
3.2 The SOCP relaxation problem for the ED problem 32

4 Robust Optimization 35
4.1 Robust linear programming 35
4.2 Robust linear programming with ellipsoidal uncertainty 36
4.3 Robust linear programming for the ED problem 39

5 Steepest-ascent method 46
5.1 A steepest-decent method for M-convex functions 46
5.2 Steepest-ascent method for the ED problem 50
5.3 Steepest-ascent method for the Robust LP of the ED problem 54

6 Numerical results 63

7 Conclusion 75

References 76
參考文獻 [1]F. Alizadeh and D. Goldfarb. "Second-order cone programming." Mathematical programming, 95(1):3-51, 2003.
[2]J. Ahlinder, T.J. Mullin, and M. Yamashita. "Using semidefinite programming to optimize unequal deployment of genotypes to a clonal seed orchard." Tree genetics &
genomes, 10(1):27-34, 2014.
[3]L. Bomosssoul and D. Lindgren. "Optimal utilization of clones and genetic thinning of seed orchards." Silvae Genetica, 42:4-5, 1993.
[4]A. Ben-Tal and A. Nemirovski. "Robust solutions to uncertain linear programs." Operations Research Letters, 25,1-13, 1999.
[5]C.C. Cockerham. "Group inbreeding and coancestry." Genetics, 56(1):89-104, 1967.
[6]D. Charlesworth and B. Charlesworth. "Inbreeding depression and its evolutionary consequences." Annual review of ecology and systematics, 18(1):237-268, 1987.
[7]M.A. Duran and I.E. Grossmann. "An outer-approximation algorithm for a class of mixed-integer nonlinear programs." Mathematical programming, 36(3):307-339, 1986.
[8]方述誠, 邢文訓. "線性錐優化/運籌與管理科學叢書". 科學出版社, 111-112, 2013.
[9]M.X. Goemans and D.P. Williamson. "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming." J. Assoc. Comput. Mach., 42(6):1115–1145, 1995.
[10]B. Grundy, B. Villanueva, J.A. Wooliams. "Dynamic selection procedures for constrained inbreeding and their consequences for pedigree development." Genet. Res. 72(2), 159–168 , 1998.
[11]D. Hinrichs, M. Wetten, et al. "An algorithm to compute optimal genetic contributions in selection programs with large numbers of candidates." Journal of animal science, 84(12):3212–3218, 2006.
[12]J. Hallander and P. Waldmann. "Optimum contribution selection in large general tree breeding populations with an application to scots pine." Theoretical and applied genetics, 118(6):1133–1142, 2009.
[13]D. Hinrichs, T.H.E. Meuwissen. "Analyzing the effect of different approaches of penalized relationship in multistage selection schemes." J. Anim. Sci. 89(11), 3426–3432, 2011.
[14]S. Kim and M. Kojima. "Second order cone programming relaxation of nonconvex quadratic optimization problems." Optimization Methods and Software, 15(3-4):201–224, 2001.
[15]D. Lindgren, W.S. Libby, and F.L. Bondesson. "Deployment to plantations of numbers and proportions of clones with special emphasis on maximizing gain at a constant diversity." Theor. Appl. Genet., 77(6):825–831, 1989.
[16]B.L. Miller, "On minimizing nonseparable functions defined on the integers with an investory application." SIAM J. Appl. Math., vo1.21, 166-185, 1971.
[17]K. Murota. "Convexity and Steinitz's exchange property". Adv. Math., 124, 272–311, 1996.
[18]T.H.E. Meuwissen. "Maximizing the response of selection with a predefined rate of inbreeding." J. Anim. Sci., 75:934–940, 1997.
[19]K. Murota. "Algorithms in discrete convex analysis, IEICE Trans." Systems and Information,E83-D, 344–352, 2000.
[20]K. Murota. "Discrete Convex Analysis—An Introduction." Kyoritsu, Tokyo, 2001 (in Japanese).
[21]S. Moriguchi, K. Murota, and A. Shioura. "Scaling algorithms for M-convex function minimization." IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E85-A, 922–929, 2002.
[22]T.H.E. Meuwissen. "Gencont: an operational tool for controlling inbreeding in selection and conservation schemes." In Proceedings of the 7th Congress on Genetics Applied to Livestock Production, 19-23, 2002.
[23]K. Murota. "Discrete Convex Analysis." SIAM, Philadelphia, 2003.
[24]K. Murota. "On steepest descent algorithms for discrete convex functions." SIAM Journal on
Optimization, 14(3):699–707, 2004.
[25]T.J. Mullin, J. Hallander, O. Rosvall, and B. Andersson. "Using simulation to optimise tree breeding programmes in Europe: an introduction to POPSIM." Technical Report Nr. 711-2010, Arbetsrapport fran Skogforsk, 2010.
[26]T.J. Mullin. "OPSEL 1.0: A computer program for optimal selection in forest tree breeding by mathematical programming." Technical Report Nr. 841-2014, Arbetsrapport fran Skogforsk, 2014.
[27]T.J. Mullin and P. Belotti. "Using branch-and-bound algorithms to optimize selection of a fixed-size breeding population under a relatedness constraint." Tree genetics & genomes, 12(1):4, 2016.
[28]T.J. Mullin. "OPSEL 2.0: a computer program for optimal selection in tree breeding." Technical Report Nr. 954-2017, Arbetsrapport fran Skogforsk, 2017.
[29]R. Pong-Wong, J.A. Woolliams. "Optimisation of contribution of candidate parents to maximise genetic gain and restricting inbreeding using semidefinite programming. Genet." Sel. Evol. 39, 3–25, 2007.
[30]A. Shioura. "Minimization of an M-convex function." Discrete Appl. Math., 84, 215–220, 1998.
[31]S. Safarina, S. Moriguchi, T.J. Mullin, and M. Yamashita. "Conic relaxation approaches for equal deployment problems". arXiv preprint arXiv:1703.03155, 2017.
[32]P. Tseng. "Further results on approximating nonconvex quadratic optimization by semidefinite programming relaxation." SIAM Journal on Optimization, 14(1):268–283, 2003.
[33]N. Tsuchimura, S. Moriguchi, and K. Murota. "Discrete convex optimization solvers and demonstration softwares." Transactions of the Japan Society for Industrial and Applied Mathematic, 23(2):233–252, 2013. (In Japanese).
[34]S. Wright. "Coefficients of inbreeding and relationship." The American Naturalist, 56(645):330–338, 1922.
[35]C.G. Williams and O. Savolainen. "Inbreeding depression in conifers: implications for breeding strategy." Forest Science, 42(1):102–117, 1996.
[36]J. Woolliams. "Genetic contributions and inbreeding." In:Oldenbroek, K. (ed.)Utilisation and Conservation of Farm Animal Genetic Resources, 147–165. Wageningen Academic Publishers,Wageningen, 2007.
[37]M. Yamashita, K. Fujisawa, and M. Kojima. "Implementation and evaluation of SDPA6.0 (SemiDefinite Programming Algorithm 6.0)." Optim. Methods Softw., 18(4):491–505, 2003.
[38]M. Yamashita, K. Fujisawa, M. Fukuda, K. Kobayashi, K. Nakta, and M. Nakata. "Latest developments in the SDPA family for solving large-scale SDPs." In M. F. Anjos and J. B. Lasserre, editors, Handbook on Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, chapter 24, 687–714. Springer, NY, USA, 2012.
[39]M. Yamashita, T.J. Mullin, and S. Safarina. "An efficient second-order cone programming approach for optimal selection in tree breeding." Optimization Letters, 1-15, 2017.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2019-01-30起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2019-01-30起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw