Submission:  Solutions are to be submitted before the (strict) due date:  4 pm, May 26.  A complete submission will consist of a LaTex typeset report in pdf form and the MatLab file(s) of your implementation.

Groups must be composed of a minimum of 3 and a maximum of 4 members. It is your responsibility to talk to your colleagues and create/find a group, as early as possible in the semester.

Evaluation:

Reporting:  You should present a coherent and self-contained report presenting your algorithms and results for the questions below.

Presentation: In Week 12, groups will present their work in 8 minutes + 2 minutes for questions. You are not expected to explain the problem in detail during the presentation. Instead, focus on the innovative aspects that your group has found:  Which solution algorithm(s) did you implement?  What conclusions did you make? At least two group members are expected to speak, and all must contribute to the structure of the presentation and in particular the slides and show up at the presentation.

Project Description:

Background

An online video sharing platform has m advertisements to be displayed over a period T.  Assume that the traffic visiting the platform in this period is constant. Let xi  for i = 1, 2, . . . , m represent the amount of time that ad i is displayed during the period.  The rate of clicking is modelled as Vi  = kxi(2)  for some constant k > 0. The ad revenue is proportional to the clicking rate, up to some maximum bi , that is,

Ri  = min{ai Vi , bi },

where ai  > 0 is some constant. Each ad has a minimum total display time ci .

The problem is to find the best time allocation {xi }i=1 ﹐ 2﹐,,,﹐m  so that the total revenue is maximised.

Tasks

1. Model the above problem as a constrained convex optimisation problem. Prove the problem is convex. You should explain each variable and constraint.

2. Derive KKT conditions for the model in (1).

3. Implement an algorithm for solving the model in (1).  Do a computational study (different initial solutions, parameter settings, etc.) for instances of different values of m and T, and various random sets {ai }, {bi } and {ci }.

4.  Can the problem be solved with other algorithms (e.g. a pre-existing optimisation function in Mat- Lab)? Compare your algorithm with the algorithm(s).

5. Bonus question:  The platform traffic varies over time.  How would you revise the model in (1)? (You do not need to solve the new problem.)