SE 305 Optimization Methods

Fall 2007

This course is no longer offered as part of the program

Catalog Description Single-variable unconstrained optimization, necessary and sufficient conditions for unconstrained minima. Region-elimination algorithms and methods requiring the derivatives. Multiple-variable unconstrained optimization. The Simplex method, Hooke-Jeeves, and the conjugate direction method. The steepest descent and Newton algorithms. Constrained optimization: Karush-Kuhn-Tucker conditions for optimality, algorithms for constrained optimization, approximation and the reduced gradient method.

Course Objectives The aim of the course is to

1. Introduce methods, algorithms, and solution procedures that are used to solve nonlinear optimization problems.
2. Expose students to some specialized software for the solution of such problems.
3. Formulate and develop mathematical models for the solution of real world problems in the area of industrial engineering.

Lab Content The lab will be dedicated to various activities that are going to supplement the class discussions as well as modeling and software implementation.  We will utilize the lab to solve examples, carry quizzes and exams, discuss formulation cases, and cover GAMS coding and issues related to the choice of the GAMS solver and the output format.  For the formulation and modeling part, we will go through Chapter 13 in the textbook which is very helpful for gaining an insight on proper modeling and formulation in practical settings.

1. Formulate engineering problems as nonlinear optimization problems.
2. Know the necessary and sufficient optimality criteria for unconstrained and constrained non-linear programming problems.
3. Use numerical optimization methods (interval halving, golden section, quadratic estimation, Powell’s, Newton-Raphson, bisection, and secant methods) to find the optimal solution for unconstrained NLP - functions of single variable.
4. Use numerical optimization methods (the simplex, the Hooke-Jeeves, Powell’s conjugate direction, steepest descent and Newton’s methods) to find the optimal solution for unconstrained NLP.
5. Use Lagrange multipliers to find the optimal solution for non-linear programs constrained by equations.
6. Use the penalty function method to find the optimal solution to NLP problems.
7. Use the method of gradient projection to find the optimal solution for linearly-constrained non-linear objective functions.
8. Know some of the commercially available solution packages such as GAMS, MATLAB, or Excel Solver and know how to use them to solve NLP problems.

Topics

1. Introduction to Optimization (1.5 lectures) (pdf): Application of optimization in engineering including operations and planning and design and the statement of the nonlinear programming problem.
   This topic is covered in Chapter 1.
2. Optimality Criteria (8 lectures) (pdf): Necessary and sufficient conditions for optimality in unconstrained optimization, Lagrange multipliers, shadow prices, and the KT necessary and sufficient conditions for optimality in constrained optimization.
   This topic is covered in Sections 2.1, 2.2, 3.1, 5.1, 5.2, 5.3, 5.4, 5.5, 5.6, 5.7.
3. Optimization Methods for Unconstrained Functions of Single Variable (4.5 lectures) (pdf): Bracketing the minimum, region elimination methods including golden section and Fibonacci methods, polynomial approximation methods including quadratic estimation and Powell’s methods, and methods requiring derivatives including Newton-Raphson and bisection.
   This topic is covered in Sections 2.3, 2.4, 2.5 and handouts.
4. Optimization Methods for Unconstrained Functions of Several Variables (6 lectures) (pdf): Direct search methods including the simplex, the Hooke-Jeeves and the Powell’s conjugate direction methods, and gradient based methods including steepest descent, Newton, quasi Newton , and conjugate gradient methods.
   This topic is covered in Sections 3.2, 3.3.
5. Penalty Functions (pdf) and Generalized Lagrange Multiplier Method (4 lectures): The penalty concept, exterior and interior penalty functions, the penalty function algorithms, and the generalized Lagrange multiplier method for non-differentiable functions.
   The topic on penalty functions is covered in Chapter 6 from Belegundu and Chandrupatla (1999) instead of Chapter 6 of the textbook and Section 5.8 of the textbook.
6. Reduced Gradient Method (6 lectures) (pdf): Basic variables as functions of nonbasic variables, reduced gradient, computation of direction and step size, and the change in the basic solution.
   This topic is covered from Section 14.2 in Avriel, Nonlinear Programming: Analysis and Methods, 2003.

• Methods of Feasible Directions: Direction generation methods based on linearization (pdf)
• Successive Linear Programming: The linearization method works by replacing the nonlinear functions in the NLP by linear functions at some selected estimate of the solution (pdf)
• Successive Quadratic Programming: The successive quadratic method works by converting the general function to a quadratic function (pdf)
• Gradient Projection Method: We need to find a search direction that lies on the constraint and is a descent direction (pdf)
• Augmented Lagrangian Penalty Functions: They can recover an exact optimum for finite penalty parameter values and they enjoy the property of being differentiable (pdf)
• Powel's conjugate directions

Applications of nonlinear modeling in industry

• Quadratic assignment problem
• Data fitting
• Solution of systems of nonlinear equations using mathematical programming
• System reliability improvement (redundancy allocation)
• Solution of system of Linear Equations using NLP modeling
• Location problem

Sample Exam

• Exam sample 1
• Exam sample 2

Supplementary illustrations

• Illustrative Example of Using the Steepest Descent Method to Solve the Log Barrier Function
• Tests of Matrix Definiteness
• Interpretation of the Lagrange multipliers
• Exterior penalty example using Excel Solver (xls)
• Inverse barrier example using Excel Solver (xls)
• Fibonacci method in Excel (xls)
• Golden section method in Excel (xls)
• Video tutorial on the application of Quasi Newton on Excel
• Video tutorial on the application of the conjugate gradient method on Excel

Prerequisite/Co-Requisite ISE 303 Operations Research I

References

1. Lecture notes
2. Reklaitis et al, Engineering Optimization: Methods and Applications, Wiley
3. Belegundu and Chandrupatla, Optimization Concepts and Applications in Engineering, Prentice Hall
4. Bazaraa, Sherali, Shetty, Nonlinear Programming, Theory and Algorithm, Wiley
5. Rao, Engineering Optimization: Theory and Practice, Wiley

Computer Usage

1. Every student has to have a Blackboard account; this is essential since homework solutions, grades, etc will be posted in the course Blackboard.
2. Basic knowledge of MATLAB and Excel will be required.
3. GAMS will be used as a solution package for NLP problems.

Method of assessment

Instructor Dr Muhammad Al-Salamah

                        Office: 22/436               Phone: 1627      email: salamah@kfupm.edu.sa

                        Office Hours: Saturdays and Mondays    from 10 to 11 am
                                             Sundays                          from 1 to 2 pm

Institution Industrial and Systems Engineering, Department of Systems Engineering, King Fahd University of Petroleum and Minerals

الوصف: دالة في متغير واحد الغير مقيده ، الشروط الضرورية والكافية للقيمة الصغرى الغير المقيدة. الخوارزميات التي تتطلب المشتقات. طرق إيجاد القيمة الصغرى لدالة غير مقيدة في أكثر من متغير. دالة مقيدة من أكثر من متغير.

المادة: طرق حل النماذج الغير الخطية (تم إلغاء المادة من البرنامج)
مدرس المادة: الدكتور محمد بن فهد السلامة

برنامج الهندسة الصناعية و النظم
قسم هندسة النظم
جامعة الملك فهد للبترول و المعادن