AMSC 607 /CMSC 764 Term Project Information

For your project, do one of the following:

  • Option 1. Choose a recent paper on semidefinite programming or conic optimization. Summarize it and demonstrate the ideas in a Matlab code.
  • Option 2. Choose an application problem that is a SDP or a conic optimization problem. Solve it using Matlab, measuring performance as a function of problem characteristics such as size, etc.

    • Deadlines and points:

  • By November 16, you should send me e-mail with the title and a short description of your project.
  • The project is due at 12 noon, Thursday December 14.
  • It is worth 100 points.
  • There will be a 15% penalty for projects turned in up to 24 hours late, 30% penalty for projects turned in 24--48 hours late, etc.

    • What to submit for the project: Your project must have these four components:

  • A written discussion, in the form of at most 40 slides, prepared as if you were giving a 40-50 minute talk on your project. (I will stop reading at the 40th slide.) The first slide gives only the title, your name, and possibly a reference to a single paper.
  • A list of open research problems related to your paper or problem.
  • Your Matlab code.
  • A list of references, including html links.

    • How to submit: Submit your project by e-mail. The time stamp on the e-mail will determine whether the project is on time or late.

  • The slides, open questions, and references should be in plain text, html, pdf, or ps format. Please format the slides "4-up" (4 slides per side of paper) if possible.
    Microsoft-formatted documents (Word, Excel, Powerpoint, etc.) will not be accepted; submit a pdf or ps file for these.
  • The Matlab programs should be in plain text, stored in files that can actually be run by Matlab.
  • Data files should be in .mat format.
  • The entire set of files should be bundled into a single file (in tar, zip, or gzip format) and attached to the e-mail.
    • I'll acknowledge your submission by e-mail after I have successfully extracted the files.

    Some questions that will be asked while evaluating a project:

  • Overall:
  • Does the project demonstrate understanding of the material?
  • Are the ideas presented clearly?
  • (For an "A") Does the project show evidence of independent thought?
  • The slide presentation:
  • Is it clear and correct? Was it spell-checked?
  • Would other students in the class be able to understand it?
  • Is jargon explained, if it was not discussed in class?
  • Are the slides easy to read? Do they contain an appropriate amount of material?
  • Is all notation defined clearly?
  • Is all type at least 28pt?
  • Is there a good evaluation of the material in the paper or the performance of the methods?
  • The open questions:
  • Are the questions reasonable and interesting?
  • Do the questions show evidence of independent thought?
  • The references:
  • Are the references complete and appropriate?
  • Are the html links included (if available)?
  • The Matlab code:
  • Is it well designed and well documented?
  • Is it easy for me to run and to understand what it does?
  • Are the experiments well designed?

    • Warning: The only failing grades I have given on term projects have been for lateness or for plagiarism. If you use someone's ideas, cite the source. If you use a direct quote, use quotation marks and cite the source. And don't expect a good grade on a project that is mostly someone else's work.

    How to get started: Each person is required to have a unique project, so tell me your idea, and I will add it to the list of claimed topics on this page. If you can't think of a topic, check the Survival Guide for Optimization for journals and other sources of information, especially Optimization Online, which is an excellent source of papers. If you don't have any ideas after that, let's talk.

    A note on software:
    Matlab does not have internal software for solving these problems, but there are several Matlab packages available on the web. I advise you to find one and modify it (if necessary) for your purposes rather than writing one from scratch.

    Projects chosen by students this semester: Your project must be unique, so either pick a different topic or check with me to make sure that your ideas are sufficiently different from what other students chose.

  • Avoiding numerical cancellation in the IPM for solving SDPs. J. Sturm
  • Lagrangian Dual Interior-Point Methods for SDP Mituhiro Fukuda, Masakazu Kojima, and Masayuki Shida
  • First and 2nd order methods for SDP R. Montiero
  • Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems K-C Toh

  • Unsupervised Learning of Image Manifolds by SDP. Weinberger and Saul,
  • Invariant Pattern Recognition by SDP Machines. Thore Graepel, Ralf Herbrich
  • Ensemble Pruning Via Semi-definite Programming. Yi Zhang, Samuel Burer, W. Nick Street
  • Learning the Kernel Matrix with SDP. Kocvara and Stingl
  • Growing well-connected graphs. Arpita Ghosh and Stephen Boyd
  • Semidefinite relaxation for detection of 16-QAM signaling in MIMO channels Weisel, Eldar, Shamai
  • On The Design of Real and Complex FIR Filters with Flatness and Peak Error Constraints Using SDP. S. C. Chan and K. M. Tsui
  • Clustering via Minimum Volume Ellipsoids R. Shioda and L. Tuncel
  • SDP approaches for sensor network localization with noisy measurements Biswas, Liang, Toh, Wang, Ye
  • Binary partitioning, perceptual grouping, and restoration with semidefinite programming Keuchel, J.; Schnorr, C.; Schellewald, C.; Cremers, D
  • The application of SDP for detection in CDMA P.H. Tan and L. K. Rasmussen
  • Optimal compactions gain by eigenvalue minimization C. Popeea and B. Dumitrescu
  • Constructing self-concordant barriers for convex cones Y. Nesterov
  • Distributed transmit beamforming in cellular networks A. Ekbal and J.M. Cioffi
  • ...