跳到主要內容

臺灣博碩士論文加值系統

(44.211.117.197) 您好!臺灣時間:2024/05/21 03:08
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張書豪
論文名稱:預言者-修正者內點法的變形
論文名稱(外文):Varitions on th predictor-corrector interior point method
指導教授:紀美秀
學位類別:碩士
校院名稱:國立中正大學
系所名稱:應用數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:30
中文關鍵詞:內點法
外文關鍵詞:interior point methodpredictor-corrector
相關次數:
  • 被引用被引用:0
  • 點閱點閱:166
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在這篇文章中, 我們首先介紹預言者-修正者內點法, 並依據
這個方法做一些變形.
接著, 我們透過數值的實驗來觀察這些變形之間的差異.
最後, 再針對這些差異做出幾點結論.

In chapter 2 of this paper, we will introduce the basic
ideas of the interior point algorithms. Consider the problems
we would like to solve, and propose how to solve it based on
the logarithmic barrier function approach. Then compute some
kinds of the search directions and choose the step lengths.
Introduce an feasible interior-point algorithm, and its
iteration complexity. The last part of chapter 2, we would like to find a suitable parameter for the algorithm by Klee-Minty
problems. Then in chapter 3, write down some variate algorithms
we used, explain their characteristics and how to complete
the computer programs (By FORTRAN 77) for them. Chapter 4
is numerical experiments and conclusions. The first section is
about the experiment results for all algorithms. We will record the iteration numbers and CPU time of them. Then is the
conclusions.

1. Introduction 2
1.1 History}
1.2 What we want to do
2. Basic ideas of interior point methods 6
2.1 Introduction to IPMs
2.2 A predictor-corrector feasible interior-point algorithm
2.3 Complexity analysis of algorithm 1
2.4 Numerical experiment for algorithm 1
3. Variations of the interior-point algorithms 19
3.1 Change the search directions of algorithm 1
3.2 An infeasible-starting feasible interior-point algorithm
4. Numerical experiments and conclusions 24
4.1 Numerical results of these algorithms
4.2 Conclusions

[1] Adler, I., Karmarkar, N., Resende, M. G. C. and Veiga, G. (1989) "An implementation of Karmarkar's algorithm for linear programming", Mathematical Programming, 44, 297-335.
[2] Fang, S. C. and Puthenpura, S., Linear Optimization and Extensions: Theory and Algorithms, Prentice-Hill
International, Inc. (1993).
[3] Hertog, den D., Interior Point Approach to Linear, Quadratic and Convex Programming Algorithms and Complexity.
KLUWER ACADEMIC PUBLISHERS. (1994).
[4] Megiddo, N. and Shub, M. (1989) "Boundary behavior of interior point algorithms in linear programming",
Mathematicsof Operations Research, 14, 97-146.
[5] Mizuno, S., Todd, M.J. and Ye, Y., (1990) "On adaptive-step primal-dual interior-point algorithm for linear programming",
Technical Report No. 944, School of Operations Research
and Industrial Engineering, Cornell University, Ithaca, NY,
Mathematics of Operations Research 18, (1993), 964-981.
[6] Mizuno, S., Megiddo, N. and Kojima, M., "A primal-dual infeasible interior-point algorithm for linear programming,"
Mathematical Programming 61, (1993), 263-280.
[7] Mizuno, S., "Polynomiality of infeasible-interior-pointalgorithms for linear programming,"
Mathematical Programming 67, (1994), 109-119.
[8] Stephen G. Nash and Ariela Sofer, Linear and Nonlinear Programming, McGRAW-HILL INTERNATIONAL EDITIONS. (1996).
[9] Zhao, G. Sun, J. and Zhu J. (1995), "A primal-dual
affine scaling algorithm with necessary centering as a
safeguard", Optimization Vol.35, 333-343.
[10] Zhao, G., "On the choice of parameters for power-series interior point algorithms in linear programming",
Mathematical Programming 68 49-71, 1995.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top