COURSE OUTLINE: MH4701

Course Title

Mathematical Programming

Course Code

MH4701

Offered Study Year 4, Semester 1
Course Coordinator Chua Chek Beng (Assoc Prof) cbchua@ntu.edu.sg 6513 7467
Pre-requisites MH2100, MH3701ORMH1803, MH3701
AU 4
Contact hours Lectures: 39, Tutorials: 12, Laboratories: 6
Approved for delivery from
Last revised 23 Feb 2020, 06:34

Course Aims

This math elective course aims to introduce you to the basic nonlinear optimization models, and the theory and analysis of the algorithms commonly used to solve these models. With the knowledge and skills acquired from analysing standard algorithms for basic nonlinear optimization models, you will be able to extend your understanding and appreciation to other solution algorithms for more general nonlinear optimization models that you will encounter in your professional work, in areas such as statistics, finance, artificial intelligence, logistics, healthcare, etc.

Intended Learning Outcomes

Upon successfully completing this course, you should be able to:

  1. State and prove necessary optimality conditions and sufficient optimality conditions for a) unconstrained optimization models, b) set-constrained optimization models, and c) constrained optimization models.
  2. State and prove the convergence of a) Newton’s method, b) the steepest decent method, c) the Newton descent method, d) the conditional gradient method, e) the augmented Lagrangian method, and f) the barrier method.
  3. Apply the above algorithms to solve basic nonlinear optimization models.
  4. Analyse the convergence and convergence rates of the above algorithms when applied to basic nonlinear optimization models.

Course Content

One-dimensional optimization: sectioning methods, Newton’s method.

Unconstrained optimization: optimality conditions, steepest descent method, Newton descent method.

Set-constrained optimization: optimality conditions, conditional gradient method

Constrained optimization: Lagrange multiplier theory, Karush-Kuhn-Tucker theory, augmented Lagrangian method, barrier method.

Assessment

Component Course ILOs tested SPMS-MAS Graduate Attributes tested Weighting Team / Individual Assessment Rubrics
Continuous Assessment
Tutorials
Homework 1 2, 4 1. a, b, c, d
2. a, b
3. a
5. a
8 individual See Appendix for rubric
Homework 2 1, 2, 3, 4 1. a, b, c, d
2. a, b
3. a
5. a
8 individual See Appendix for rubric
Mid-semester Quiz
Essay 1 3, 4 1. a, b, c
2. c
3. a
12 individual See Appendix for rubric
Essay 2 1, 3 1. a, b, c
2. c
3. a
12 individual See Appendix for rubric
Examination (2 hours)
Essay 1, 2, 3, 4 1. a, b, c
2. c
3. a
60 individual See Appendix for rubric
Total 100%

These are the relevant SPMS-MAS Graduate Attributes.

1. Competence

a. Independently process and interpret mathematical theories and methodologies, and apply them to solve problems

b. Formulate mathematical statements precisely using rigorous mathematical language

c. Discover patterns by abstraction from examples

d. Use computer technology to solve problems, and to communicate mathematical ideas

2. Creativity

a. Critically assess the applicability of mathematical tools in the workplace

b. Build on the connection between subfields of mathematics to tackle new problems

c. Develop new applications of existing techniques

3. Communication

a. Present mathematics ideas logically and coherently at the appropriate level for the intended audience

5. Character

a. Act in socially responsible and ethical ways in line with the societal expectations of a mathematics professional, particularly in relation to analysis of data, computer security, numerical computations and algorithms

Formative Feedback

Comments on your answers to the questions in your homework assignments and in-class tests will be written on your submissions and returned to you upon grading.

Learning and Teaching Approach

Lectures
(39 hours)

The basic theories and solution techniques will explained to you in the lectures. You will see illustrative examples which either motivate or reinforce your learning of the algorithms and theorems. The lecturer will occasionally conduct short discussions with the whole class, which serves to promote your critical thinking skills.

Tutorials
(12 hours)

You will participate in problem-solving tutorial sessions, where problems are designed based on the theories and solution techniques that you should pick up in the lectures prior to each tutorial session. You are expected to attempt the problems before attending the tutorial sessions, so that you are well-prepared to actively participate in the discussions. The tutor will facilitate the discussions in the tutorial sessions, guiding the class as a whole towards complete and acceptable solutions to the problems.
The homework assignments provide a check on your level of mastery of the theories and solution techniques. You are encouraged to discuss the homework assignments with your classmates as a form of peer-to-peer learning. However, you are required to write up the solutions on your own in a clear and logical manner.

Laboratories
(6 hours)

You will learn how to model real-world optimization problems as nonlinear programs, and solve instances of these models in the lab sessions. The optimization problem will be introduced and the nonlinear programming model explained at the beginning of the lab session. You will then have hands-on experience in building a nonlinear programming model, and solve it using a solver of your choice.

Reading and References

Dimitri P. Bertsekas, ‘Nonlinear Programming’, Second Edition, Athena Scientific, ISBN 1886529000

Course Policies and Student Responsibilities

(1) General
Students are expected to attend all lecture, tutorial, lab classes, and in-class tests punctually, and complete all scheduled homework assignments by the due dates. Students are expected to take responsibility to follow up with course notes, homework assignments, and course related announcements for assessments they have missed. Students are expected to prepare for and participate in all tutorial discussions and activities.

(2) Absenteeism
A missed test will be given a mark of zero, unless prior permission is given by the course coordinator, or a leave of absence is approved by the School. If you miss an in-class test, you must inform the course coordinator via email within 2 working days of the test.

(3) Homework Assignments
You are required to complete all homework assignments by the due dates. Late submissions of homework assignments will draw late penalties.

Academic Integrity

Good academic work depends on honesty and ethical behaviour. The quality of your work as a student relies on adhering to the principles of academic integrity and to the NTU Honour Code, a set of values shared by the whole university community. Truth, Trust and Justice are at the core of NTU’s shared values.

As a student, it is important that you recognize your responsibilities in understanding and applying the principles of academic integrity in all the work you do at NTU. Not knowing what is involved in maintaining academic integrity does not excuse academic dishonesty. You need to actively equip yourself with strategies to avoid all forms of academic dishonesty, including plagiarism, academic fraud, collusion and cheating. If you are uncertain of the definitions of any of these terms, you should go to the Academic Integrity website for more information. Consult your instructor(s) if you need any clarification about the requirements of academic integrity in the course.

Course Instructors

Instructor Office Location Phone Email
Chua Chek Beng (Assoc Prof) SPMS-MAS-05-21 6513 7467 cbchua@ntu.edu.sg

Planned Weekly Schedule

Week Topic Course ILO Readings/ Activities
1

Mathematical background and elementary convex analysis

2

Lecture notes chapters 1 and 2

2

Mathematical background and elementary convex analysis

1, 2

Lecture notes chapters 1 and 2

3

Mathematical background and elementary convex analysis

1, 2

Lecture notes chapters 1 and 2

4

One-dimensional and unconstrained optimization

1, 2, 3, 4

Lecture notes chapters 3–6

5

One-dimensional and unconstrained optimization

1, 2, 3, 4

Lecture notes chapters 3–6

6

One-dimensional and unconstrained optimization

1, 2, 3, 4

Lecture notes chapters 3–6

7

Set-constrained optimization

1, 2, 3, 4

Lecture notes chapters 7 and 8

8

Set-constrained optimization

1, 2, 3, 4

Lecture notes chapters 7 and 8

9

Constrained optimization

1, 2, 3, 4

Lecture notes chapters 7 and 8

10

Constrained optimization

1, 2, 3, 4

Lecture notes chapters 7 and 8

11

Constrained optimization

1, 2, 3, 4

Lecture notes chapters 7 and 8

12

Constrained optimization

1, 2, 3, 4

Lecture notes chapters 7 and 8

13

Constrained optimization

1, 2, 3, 4

Lecture notes chapters 7 and 8

Appendix 1: Assessment Rubrics

Rubric for Tutorials: Homework 1 (8%)

Grade

Description

A

The answer demonstrates full understanding of the problem and the solution process. All arguments are logical and presented with the appropriate use of English and mathematical symbols. The answer is completely correct.

B

The answer demonstrates traits found in the descriptions of both “A” and “C” grades.

C

The answer demonstrates some understanding of the problem and the solution process. Some arguments are logical and they are sometimes presented with the appropriate use of English and of mathematical symbols. The answer is partially correct.

D

The answer demonstrates traits found in the descriptions of both “C” and “F” grades.

F

The answer demonstrate no understanding of the problem or the solution process. Arguments are mostly not logical or they are presented with the inappropriate use of English and of mathematical symbols. The answer is completely incorrect.

Rubric for Tutorials: Homework 2 (8%)

Grade

Description

A

The answer demonstrates full understanding of the problem and the solution process. All arguments are logical and presented with the appropriate use of English and mathematical symbols. The answer is completely correct.

B

The answer demonstrates traits found in the descriptions of both “A” and “C” grades.

C

The answer demonstrates some understanding of the problem and the solution process. Some arguments are logical and they are sometimes presented with the appropriate use of English and of mathematical symbols. The answer is partially correct.

D

The answer demonstrates traits found in the descriptions of both “C” and “F” grades.

F

The answer demonstrate no understanding of the problem or the solution process. Arguments are mostly not logical or they are presented with the inappropriate use of English and of mathematical symbols. The answer is completely incorrect.

Rubric for Mid-semester Quiz: Essay 1 (12%)

Grade

Description

A

The answer demonstrates full understanding of the problem and the solution process. All arguments are logical and presented with the appropriate use of English and mathematical symbols. The answer is completely correct.

B

The answer demonstrates traits found in the descriptions of both “A” and “C” grades.

C

The answer demonstrates some understanding of the problem and the solution process. Some arguments are logical and they are sometimes presented with the appropriate use of English and of mathematical symbols. The answer is partially correct.

D

The answer demonstrates traits found in the descriptions of both “C” and “F” grades.

F

The answer demonstrate no understanding of the problem or the solution process. Arguments are mostly not logical or they are presented with the inappropriate use of English and of mathematical symbols. The answer is completely incorrect.

Rubric for Mid-semester Quiz: Essay 2 (12%)

Grade

Description

A

The answer demonstrates full understanding of the problem and the solution process. All arguments are logical and presented with the appropriate use of English and mathematical symbols. The answer is completely correct.

B

The answer demonstrates traits found in the descriptions of both “A” and “C” grades.

C

The answer demonstrates some understanding of the problem and the solution process. Some arguments are logical and they are sometimes presented with the appropriate use of English and of mathematical symbols. The answer is partially correct.

D

The answer demonstrates traits found in the descriptions of both “C” and “F” grades.

F

The answer demonstrate no understanding of the problem or the solution process. Arguments are mostly not logical or they are presented with the inappropriate use of English and of mathematical symbols. The answer is completely incorrect.

Rubric for Examination: Essay (60%)

Grade

Description

A

The answer demonstrates full understanding of the problem and the solution process. All arguments are logical and presented with the appropriate use of English and mathematical symbols. The answer is completely correct.

B

The answer demonstrates traits found in the descriptions of both “A” and “C” grades.

C

The answer demonstrates some understanding of the problem and the solution process. Some arguments are logical and they are sometimes presented with the appropriate use of English and of mathematical symbols. The answer is partially correct.

D

The answer demonstrates traits found in the descriptions of both “C” and “F” grades.

F

The answer demonstrate no understanding of the problem or the solution process. Arguments are mostly not logical or they are presented with the inappropriate use of English and of mathematical symbols. The answer is completely incorrect.