- The course project is intended to lead the student towards some advanced research topics in optimization, algorithmic techniques and their applications
.- You may refer to various major published sources, the course references, and related periodicals to choose a project topic.

- A project can be any of the following:

- a theoretical study of an optimization problem or optimization method,

- an original survey of an optimization topic, related background, techniques, algorithms, open problems, etc.,

- experimental implementation of optimization algorithms.

- The grading will be based on timeliness, clarity of presentation, documentation, coding (if applicable), and the extent of originality .

Time
Table:

**Project
Proposal (by the end of the 2nd month in the term) **

- Choose a project topic:

- start thinking about this as early as possible. It might take some time until you decide on a suitable topic.

- A suggested list of project topics and sources appears below.

- Consult with me about the suitability of your chosen project topic, especially if it is not on the suggested list.

- Email me one or two paragraphs explaining what the topic is about, a few tentative sources that you plan to use, and the motivation behind choosing that particular topic.

- Submit the final hard copy written version of your project report. This should include pointers to your accessible on-line documents and codes (if applicable).
- Give a 15-minute presentation of your project in class. This may include a demo of impelmentation, theoretical and empirical results.

Some Past Projects:

- Parameter Optimization in Computer Vision Modeling, by Yulia Kotseruba, 2012.

- [Wireless] Network Coding Optimization, by Alireza Moghaddam, 2012.
- Integrating Prior Knowledge in Time Series Allignment [in Signal Processing]: Prior Optimized Time Warping, by Xiaoguang Yan, 2012.

- A Study on Kernel Functions for Text-Processing, by Celso Kaestner, 2012.

- A Study on a Newton-type Algorithm and its Application in Machine Learning, by Ying Li, 2012.
- Resource Allocation in the Cloud by using Distributed Optimization Techniques, by Hongbin Lu, 2012.

- Small Approximation of epsilon-Pareto Sets of Team Formation in Social Networks, by Morteza Zihayat, 2012.

Suggested new project topics and reading list:

- Project 1: A linear system of equations Ax = b
can be solved by either direct methods (Gaussian elimination, LU
decomposition ...) or
by
iterative methods (preconditioned conjugate gradient ...). Direct
methods are more suitable for dense small systems. Iterative methods
are preferable for large sparse systems such as social networks. These
methods are based on minimizing the convex quadratic
function f(x) = 1/2 x
^{T}Ax - b^{T}x by iterative gradient methods (assuming A is positive semidefinite, such as the Laplacian of a graph). These methods are an alternative to the Ellipsoid and Interior Point Methods for general convex optimization that we study in Slides 6 and 7. Research papers: [1,2]. General background sources: [3,4,5].

- Project 2: Graph cuts and flows. Research papers: [6, 7]. General background sources: [3, 4, 5].

- Project 3: Linear
Programming: alternative weakly polynomial-time algorithms than the Ellipsoid and Interior Point Methods, and the
quest for a strongly polynomial-time algorithm. Research papers: [8, 9, 10]. Additional sources: [11, 12].

- Project 4: Multiplicative weights update: a combinatorial method for solving Semidefinite Programs. Research papers: [13, 14]. General source: [15].

- Project 5: Several sub-topics in Computer Science Theory for the Information Age. General Source: [16].

- J. Kelner, L. Orecchia, A. Sidford, "A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time," Proc. Symposium on Theory of Computing (STOC), 2013.

- J. Dunagan, N. Harvey, "Iteratively Constructing Preconditioners via the Conjugate Gradient Method," STOC 2007.

- J. Shewchuk, "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain," 1994.
- C. Godsil, G. Royle, "Algebraic Graph Theory," Springer, 2001.

- D. Spielman, "Lecture Notes: Spectral Graph Theory," 2012.

- P. Christiano, J. Kelner, A. Madry, D. Spielman, S.-H. Teng, "Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs," STOC 2011.
- S. Arora, S. Rao, U. Vazirani, "Expander Flows, Geometric Embeddings and Graph Partitioning," STOC 2004.

- M. Barasz, S. Vempala, "A New Approach to Strongly Polynomial Linear Programming," Innovations in Computer Science, 2010.
- J. Kelner, D. Spielman, "A Randomized Polynomial-Time Simplex Algorithm for Linear Programming," STOC 2005.
- J. Dunagan, S. Vempala, "A Simple Polynomial-time Rescaling Algorithm for Solving Linear Programs," STOC 2004.
- E. Tardos, "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Resaerch 34(2), pp: 250-256, 1986.
- E. Hazan, "Lecture Notes: Polynomial Time Algorithms for Linear Programming," 2011.

- S. Arora, E. Hazan, S. Kale, "The Multiplicative Weights Update Method: a Meta Algorithm and Applications," Journal of Theory of Computing, 2010.
- S. Arora, S. Kale, "A Combinatorial, Primal-Dual approach to Semidefinite Programs," STOC 2007.
- L. Lovasz, "Lecture Note: Semidefinite programs and combinatorial optimization," 1995.

- J. Hopcroft, R. Kannan, "Computer Science Theory for the Information Age," to be published soon.