Assignments

Homework Assignments

NOTE 1: Put your A# at the top of the first page. Do not write your name on your homework.

NOTE 2: Put the HW# at the top of the first page.

NOTE 3: Turn in homework in the ECE 6040 slot in room EL 102.

NOTE 4: When grading, use 5 pts per part of each problem.

NOTE 5: When grading put fraction NumPts/TotalPts at top of first page.

NOTE 6: Please turn in all graded papers by Wednesday, 13 December 2017 (and sooner if possible).

Final Project

Example project

Support Vector Machine

Background

The goal of this project is to choose a problem, formulate it as a convex optimization problem, and write computer code to solve the problem following the log-barrier interior-point method. The assignment has three parts: (1) doing the work; (2) giving an oral presentation about the project in class; (3) writing a report about the project.

Class presentations (Due: Monday, 11 December 2017, 7:30-9:20 AM)

Here is a list of the main points to be addressed in the class presentation. This should be a slide presentation with approximately one slide for each of the following topics. Some topics may require more than one slide. Please practice the presentation so that you can finish in 15 minutes leaving 5 minutes for questions. On the day you present in class, please come to class ten minutes early to load your presentation on the computer.

NOTE: We will only have 7-8 minutes per person. Focus your presentation on the most important parts of the learning experience, and please include results if you have them.

1. Describe the problem setting - what is field of the problem, what is the goal, etc.
2. Define and give the physical meaning of the variables, objective and constraints
3. Explain any relaxations or approximations that are used
4. State the problem as a convex optimization problem
5. State the log-barrier optimization problem and explain any generalized logarithms used
6. Show the modified KKT equations and describe any special structure that can be exploited in the solver
7. Discuss issues relating to initialization, line search, parameter selection, etc.
8. Show results and give a brief analysis - did it work, which constraints are active at the solution, etc.

Reports (Due: Wednesday, 13 December 2017)

Here are the sections that should be present in the report. Please address each item listed below (5 points each).

Title Page

Project title, author name and A#, date, etc.

Introduction

Describe the problem that you are solving.

Give some information about the setting and/or background for the problem.

Describe problem data that you are using.

Problem formulation

Define the problem variables. What do they mean physically?

Define the objective function. What does it measure physically?

Define the constraint functions. Give an interpretation for the constraints.

State the optimization problem mathematically.

Explain any relaxations or approximations that are used.

If necessary, transform the problem to a more convenient form.

Explain why the problem is convex.

What are the conditions for strong duality and do they hold for your problem?

Problem solution

What is the generalized logarithm for your problem?

For the barrier method, state the equality constrained log-barrier optimization problem.

What are the conditions for applying Newton's method to solve this equality constrained optimization problem, and are they satisfied for your problem?

Derive the (modified) KKT equations for your problem.

Derive the Newton equations that are solved to obtain the step direction.

Describe any structure that can be exploited in the solver (diagonally, sparsity, efficient transforms, etc.)

Implementation issues

Explain how you initialized your algorithm?

Describe any special considerations that are used in the backtracking line search.

List the parameters used in the inner and outer loops of the barrier method: $\alpha$, $\beta$, $\mu$, $\varepsilon$, etc.

Include a source code listing.

Results and analysis

Give a tabulated printout of the important variables for an example run of your solver. (When you run CVX, a table of important algorithm parameters is provided.) Your table should include the value of t, ...

Use appropriate plots to show the convergence of Newton's method applied to the log-barrier problem.

Using appropriate plots or tables, show the solution of the problem.

Provide an analysis of the solution. For example, what is the optimal value, what constraints are active/inactive at the optimal point, etc.