CS5321 Project

1. Options
2. Requirements
3. Topics
4. Presentation schedule

1. Application:
   Introduce an application that uses numerical optimization to solve the problem. How the problems are formulated? What is the assumption? What are the special properties of the problem? Which methods have been used to solve this problem? If the idea is from some papers of books, you need to propose a different method to solve it.

2. Algorithm:
   Introduce a numerical optimization algorithm or techniques (or a kind of algorithms and techniques) that hasn’t been mentioned in class. Where can it be applied? What are its strengths and limitations? Does it have future? If the idea is from some papers of books, you need to propose an improvement method.

3. Software survey:
   Study software for solving a particular type of optimization problems. You need to test the software with some simple applications. What is the performance and usability for each package or each program? (Compare at least two packages or programs.)

4. Implementation:
   Implement a complete algorithm in the textbook. You can use any language, including Matlab. Describe the implementation details, such as data structure, program flow, etc. What assumptions do you make? What improvement do you make? How do you test it? What is the performance?

You need to write a proposal to introduce your project. In your proposal, you should include

1. The title of your project.
2. The type of your project.
3. A brief introduction of your project.
4. The reasons why you choose this topic.
5. The plan of how to proceed the project.

Presentation

You need to prepare a short presentation about 15-20 minutes to introduce your project. The date and time will be arranged later.

Report

Please write a short report to summarize your project. It need not be very formal, but should be clearly shown what you have done. The report should include

1. Background introduction. (This part you can copy from your proposal.)
2. Literature review of others' work. (What have you surveyed?)
3. Summary on your work. (What have you done?)
4. Conclusion and future works.
5. List of references

• Jiming Peng, Yu Wei, "Approximating K-means-type Clustering via Semidefinite Programming". SIAM J. on Optimization, Vol. 18, No. 1. (February 2007), pp. 186-205. link
• Z. Wang, S. Zheng, S. Boyd, Y. Ye, "Further Relaxations of the SDP Approach to Sensor Network Localization", 2007 preprint. link
• Steven C.H. Hoi and Rong Jin, Active Kernel Learning, ICML 2008 link
• Alexandre d'Aspremont, "Smooth Optimization with Approximate Gradient", arXiv.org > math > arXiv:math/0512344 link
• Kocvara: On the Solution of Large-Scale SDP Problems by the Modified Barrier Method Using Iterative Solvers, Math Prog. 109, 2007
• Juan Pablo Vielma, Shabbir Ahmed, George Nemhauser, " Mixed-Integer Models for Nonseparable Piecewise Linear Optimization: Unifying Framework and Extensions" link
• Roummel F. Marcia, "On solving sparse symmetric linear systems whose definiteness is unknown", link
• Silvia Bonettini · Valeria Ruggiero, Some iterative methods for the solution of a symmetric indefinite KKT system, Comput Optim Appl (2007) 38:3-25 link
• Brian Kulis, Arun C. Surendran, John C. Platt, "Fast Low-Rank Semidefinite Programming for Embedding and Clustering" link
• Dongmin Kim, Suvrit Sra and Inderjit S. Dhillon, "Fast Newton-type Methods for the Least Squares Nonnegative Matrix Approximation Problem", link
• Chih-Jen Lin, "Projected Gradient Methods for Non-negative Matrix Factorization", link
• Liang Xiong, Fei Wang, and Changshui Zhang, "Semi-definite Manifold Alignment", link
• Kilian Q. Weinberger and Lawrence K. Saul, "Unsupervised Learning of Image Manifolds by Semidefinite Programming", link
• T.-H. Chan, W.-K. Ma, C-.Y. Chi, and Y. Wang, "A convex analysis framework for blind separation of non-negative sources," IEEE Trans. Signal Process., vol. 56, no. 10, pp. 5120-5134, Oct. 2008. link
• Daniel A. Spielman, and Shang-Hua Teng, "Smoothed Analysis of Termination of Linear Programming Algorithms" link
• Moustapha Diaby, "The traveling salesman problem: A Linear programming formulation of", link

• Everyone has 20 minutes to present the project.
• Attedence to all presentations is required. Abscence without important reasons will cause grade deduction.

last update: 4/16/2009