陳正剛臺灣大學：工業工程學研究所許博為Hsu, Po-WeiPo-WeiHsu2007-11-232018-06-292007-11-232018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/49103在本篇研究當中，我們針對多反應曲面(Multiple response surfaces)的最佳化問題提供了一個較為直接的數學建構的方式，將此多目標的最佳化問題轉化成一個四次的非線性規劃問題。大部份的非線性規劃方法在使用上常需具備兩個前提：首先，假設起始解為已知或起始解已在可行解區域內，另一個假設是可行解區域或最佳化目標式為凸性(convex)。因此我們根據脊線分析(Ridge Analysis) 以及中心混成設計(Central Composite Design)的概念，發展了一個找到初始解的方法。此外，透過我們所發展的脊線搜尋法(Ridge Search Algorithm)改善了在大多數搜尋法中搜索路徑曲折(zigzagging)的現象。雖然我們無法去說明脊線搜尋法在所有的非線性規劃問題上都是非常有效率的，但在我們遇到的問題中，它表現的非常好。而與最陡坡度法(Steepest Descent Method)的比較中證實，脊線搜尋法的確能更有效率的收斂，並得到更好的解。將脊線搜尋法推展到非線性規劃的問題上時，我們利用投影或微調的方式對脊線搜尋法的改善路徑加以修正，並且配合上Zoutendijk搜尋法，讓問題能夠有效率的解決。為了驗證我們的方法，我們提供了一個半導體可製造性設計(Design for Manufacturability)的研究實例，在此實例中包括了三個積體電路的設計參數，以及十個各自擁有目標值及規格區間的電性測試項目。經由我們所建置的獨立系統可以對此一多反應曲面最佳化問題提供解決方案，並且能將整個方法應用到其他的領域。In this research, we propose a more straightforward formulation for multiple responses optimization. The formulation turns the multiple responses optimization problem into a quartic nonlinear programming (NLP) problem. Most of NLP methods have two hypotheses: First, the initial set of the search is known and is in the feasible region; and the second, the feasible region or the objective function is convex. We develop a method to search for feasible initial solution based on the idea of ridge analysis and central composite designs (CCD). Furthermore, we develop a Ridge Search Algorithm (RSA) to avoid the zigzagging behavior, which exists in most search methods. Though we are not able to show the RSA is effective for all nonlinear optimization problems, it has been shown quite effective in our problem. Compared with Steepest Descent Method (SDM), the RSA converges effectively and gets better result. We extend the RSA to solve the nonlinear constrained problem by projecting and/or tuning the improvement path found by RSA. Through combination of Ridge projection and Zoutendijk methods, we successfully solve the NLP problem effectively. A real semiconductor DFM problem is also provided to verify our methods. The case has 3 IC layout design factors and 10 ET items with desired targets and specification windows. With our stand-alone software system, we can successfully provide solutions to this problem and apply the proposed methods in different types of applications.Abstract i 論文摘要 iii Tables of Contents iv List of Figures v List of Tables vii 1 Introduction 1 1.1 Background 1 1.2 Problem Description and Formulation 3 1.3 Current NLP Methods 5 1.3.1. Methods of Line Search 5 1.3.2. Methods of Feasible Direction 7 1.4 Research Objectives 9 1.5 Thesis Organization 9 2 Ridge Projection Method 10 2.1 Ridge Search Method 10 2.2 Search of Initial Feasible Solutions 19 2.3 Ridge Projection 22 2.4 Combination of the Ridge Projection and the Zoutendijk Method 29 3 Case Study of Semiconductor DFM Problem 34 3.1 Geometric Layout Design Problem 34 3.2 Solutions of DFM Problem 36 4 Conclusion 46 Reference 47 Appendix A. Ridge Analysis 49 Appendix B. Problem Formulations of DFM Cases 52 Appendix C. Class Diagram 56en-US脊線分析脊線搜尋法可製造性設計Ridge Search AlgorithmRidge AnalysisDFMNLPthesis