Operations Research (2): Optimization Algorithms


Operations Research (OR) is a field in which people use mathematical and engineering methods to study optimization problems in Business and Management, Economics, Computer Science, Civil Engineering, Electrical Engineering, etc.

The series of courses consists of three parts, we focus on deterministic optimization techniques, which is a major part of the field of OR.
As the second part of the series, we study some efficient algorithms for solving linear programs, integer programs, and nonlinear programs.
We also introduce the basic computer implementation of solving different programs, integer programs, and nonlinear programs and thus an example of algorithm application will be discussed.

What you will learn

Course Overview

In the first lecture, we briefly introduce the course and give a quick review about some basic knowledge of linear algebra, including Gaussian elimination, Gauss-Jordan elimination, and definition of linear independence.

The Simplex Method

Complicated linear programs were difficult to solve until Dr. George Dantzig developed the simplex method. In this week, we first introduce the standard form and the basic solutions of a linear program. With the above ideas, we focus on the simplex method and study how it efficiently solves a linear program. Finally, we discuss some properties of unbounded and infeasible problems, which can help us identify whether a problem has optimal solution.

The Branch-and-Bound Algorithm

Integer programming is a special case of linear programming, with some of the variables must only take integer values. In this week, we introduce the concept of linear relaxation and the Branch-and-Bound algorithm for solving integer programs.

Gradient Descent and Newton’s Method

In the past two weeks, we discuss the algorithms of solving linear and integer programs, while now we focus on nonlinear programs. In this week, we first review some necessary knowledge such as gradients and Hessians. Second, we introduce gradient descent and Newton’s method to solve nonlinear programs. We also compare these two methods in the end of the lesson.

What’s included