xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

MAST30013-matlab/latex代写

时间：2023-05-05

MAST30013 – Techniques in Operations Research

Semester 1, 2023

Group Project

Submissions: Solutions are to be submitted before the (strict) due date: 5pm Friday of

Week 11. A complete submission will consist of a LaTex typeset report in pdf form and

the Matlab files of your implementation.

Evaluation:

Reporting: You should present a coherent and self-contained report presenting your

algorithms and results for the questions below. Each student should contribute at least 5

pages to the report, and every page should name (as a footnote) the person responsible

for it.

Presentation: In the last week of class, groups will present their work in 5 minutes +

2 minutes for questions during the usual lecture times, and possibly one of the tutorials.

You are NOT expected to explain the problem in detail during the presentation. Instead,

focus on the innovative aspects of your methods and theory. Which solution algorithm did

you implement? What conclusions did you get? All group members are expected to speak

in order to get an oral mark.

Report Structure:

Introduction (Motivation, applications)

Background (Mathematical preliminaries)

Theory (Answers to Tasks 1-5)

Algorithms (Pseudo-code and descriptions)

Experimental setup (What instances are you testing and how will you evaluate the results?

Which algorithms will you compare and how? What hardware are you using?)

Experimental results (Graphs and tables)

Discussion and results (What do you conclude?)

Project Description

We are given N points y1, ..., yN on the plane and a convex and closed set X ⊂ R2. Our

objective is to find a point x ∈ X for which the distance to the nearest point yi is the

largest possible.

Tasks:

1. Model this problem as a constrained nonlinear “maxi-min” problem and then convert

the program to a “mini-max” problem.

1

2. For the mini-max version, characterise the set of points for which the objective func-

tion is NOT differentiable when X = R2. Illustrate the characterisation on the

following example: y1 = (0, 0), y2 = (1, 0), y3 = (0, 2), y4 = (4, 4). Include a figure

showing all non-differentiable points.

3. Let X = {(x1, x2) ∈ R2 : x2 ≥ 0, x21 + x22 ≤ 1}. For this X, rewrite the mini-max

problem as a nonlinear program with a smooth objective.

4. Write out all the KKT conditions for the program in (3). Explain why we can

essentially ignore points for which the constraints are not smooth.

5. Bonus question: Provide a geometric interpretation of the points that satisfy the

KKT conditions. (Hint: try X = R2 if that simplifies things).

6. Implement an algorithm for solving your model in (3). Do a computational study

(different initial solutions, parameter settings, etc.) for instances of different values of

N and various random sets of N points. Note, X stay fixed as defined. Compare your

algorithm with other algorithms or pre-existing optimisation functions in Matlab.

Important Notes

• You will be marked on the quality of your report. Make sure it is self contained and

follows the structure of a scientific report.

• It is the group’s responsibility to ensure that everyone contributes their fair share to

the project.

• It is recommended that members of the group share a Dropbox folder for their work

or use Overleaf. This is so that all group members can have access to all parts of the

project at any time.

• This project contains an extensive programming component. It is assumed that all

students are able to program in Matlab. The lecturer will not assist in issues relating

to the debugging of code.

• Students may research ideas on the web, but full credit to the relevant authors

must be given if the students use any of these ideas. Code may NOT be copied from

existing sources (except for code, eg., BFGS etc., provided by lecturer). Collaboration

between groups is NOT allowed.

• All code must be in Matlab. Code will not be marked directly, but marks may be

deducted for messy code or code that is not well commented. Code must be in a

form so that the lecturer can easily test your algorithm on an independent set of

instances.

Semester 1, 2023

Group Project

Submissions: Solutions are to be submitted before the (strict) due date: 5pm Friday of

Week 11. A complete submission will consist of a LaTex typeset report in pdf form and

the Matlab files of your implementation.

Evaluation:

Reporting: You should present a coherent and self-contained report presenting your

algorithms and results for the questions below. Each student should contribute at least 5

pages to the report, and every page should name (as a footnote) the person responsible

for it.

Presentation: In the last week of class, groups will present their work in 5 minutes +

2 minutes for questions during the usual lecture times, and possibly one of the tutorials.

You are NOT expected to explain the problem in detail during the presentation. Instead,

focus on the innovative aspects of your methods and theory. Which solution algorithm did

you implement? What conclusions did you get? All group members are expected to speak

in order to get an oral mark.

Report Structure:

Introduction (Motivation, applications)

Background (Mathematical preliminaries)

Theory (Answers to Tasks 1-5)

Algorithms (Pseudo-code and descriptions)

Experimental setup (What instances are you testing and how will you evaluate the results?

Which algorithms will you compare and how? What hardware are you using?)

Experimental results (Graphs and tables)

Discussion and results (What do you conclude?)

Project Description

We are given N points y1, ..., yN on the plane and a convex and closed set X ⊂ R2. Our

objective is to find a point x ∈ X for which the distance to the nearest point yi is the

largest possible.

Tasks:

1. Model this problem as a constrained nonlinear “maxi-min” problem and then convert

the program to a “mini-max” problem.

1

2. For the mini-max version, characterise the set of points for which the objective func-

tion is NOT differentiable when X = R2. Illustrate the characterisation on the

following example: y1 = (0, 0), y2 = (1, 0), y3 = (0, 2), y4 = (4, 4). Include a figure

showing all non-differentiable points.

3. Let X = {(x1, x2) ∈ R2 : x2 ≥ 0, x21 + x22 ≤ 1}. For this X, rewrite the mini-max

problem as a nonlinear program with a smooth objective.

4. Write out all the KKT conditions for the program in (3). Explain why we can

essentially ignore points for which the constraints are not smooth.

5. Bonus question: Provide a geometric interpretation of the points that satisfy the

KKT conditions. (Hint: try X = R2 if that simplifies things).

6. Implement an algorithm for solving your model in (3). Do a computational study

(different initial solutions, parameter settings, etc.) for instances of different values of

N and various random sets of N points. Note, X stay fixed as defined. Compare your

algorithm with other algorithms or pre-existing optimisation functions in Matlab.

Important Notes

• You will be marked on the quality of your report. Make sure it is self contained and

follows the structure of a scientific report.

• It is the group’s responsibility to ensure that everyone contributes their fair share to

the project.

• It is recommended that members of the group share a Dropbox folder for their work

or use Overleaf. This is so that all group members can have access to all parts of the

project at any time.

• This project contains an extensive programming component. It is assumed that all

students are able to program in Matlab. The lecturer will not assist in issues relating

to the debugging of code.

• Students may research ideas on the web, but full credit to the relevant authors

must be given if the students use any of these ideas. Code may NOT be copied from

existing sources (except for code, eg., BFGS etc., provided by lecturer). Collaboration

between groups is NOT allowed.

• All code must be in Matlab. Code will not be marked directly, but marks may be

deducted for messy code or code that is not well commented. Code must be in a

form so that the lecturer can easily test your algorithm on an independent set of

instances.