2008 AMSC 607 /CMSC 764 Term Project Information

Clarifications are colored red.

12-02-08 Notes

  • A note on accessing journals over the internet at UMD:
  • Some journals (e.g., SIAM journals) can be accessed just by being on the UMD domain and going to the journal's website.
  • Others (e.g., for-profit journals published by Springer, Elsevier, etc.) require that you go to the UMD library "research port" http://www.lib.umd.edu/ and connect to the journal from there.
  • And for really "old" things you might have to actually walk over to the Engineering and Physical Sciences Library, just like generations of scholars before you.
  • I will acknowledge receipt of your project as soon as I have saved the attachment(s) to your email.
  • Now is a good time to review the submission instructions and the grading criteria.
  • 12-04-08 If code exists to illustrate the results in the paper, use it. (There is little point in reinventing the wheel.) Then compare with other algorithms or generalize the method or ....

    • For your project, do one of the following:

  • Option 1. Choose a recent paper on optimization. ("Recent" means "published within the last two years".) Summarize it and demonstrate the ideas in a Matlab code. Semi-definite programming or conic optimization are particularly good areas.
  • Option 2. Write a Matlab program to solve an unconstrained optimization problem using the quasi-Newton method. Accumulate a (dense) factorization of B, and provide options for both line search and trust region. Develop a reasonable algorithm to initialize B, and also allow for use of a user estimate. Demonstrate that your program performs better than Mathworks' version on a variety of problems.
  • Option 3. Write a Matlab program to solve a large unconstrained optimization problem using the quasi-Newton method. Provide options for a sparse factorization of B as well as a limited-memory version, and provide options for both line search and trust region. Develop a reasonable algorithm to initialize B, and also allow for use of a user estimate. Demonstrate that your program performs better than Mathworks' version on a variety of problems with a large number of variables.

    • Deadlines and points:

  • By November 10, you should send me e-mail with the title and a short description of your project.
    I will send you email telling you whether the project is acceptable.
  • The project is due at 12 noon, Monday December 15.
  • 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, including the testing program.
  • A list of references, including html links if available.

    • How to submit: Submit your project by e-mail.

  • The slides, open questions, and references should be in plain text, html, pdf, or ps format.
    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, influenced by material in this course?
  • 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? More precisely, is all type at least as big as Powerpoint's 28pt type?
  • 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, or if you would like a minor exception from the guidelines, let's talk.

    A note on software:
    There are several Matlab packages available on the web for various types of constrained optimization problems. If Mathworks does not supply software for your problem, I advise you to find a package from the web 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.

  • Bert W. Rust and Dianne P. O'Leary, ``Residual Periodograms for Choosing Regularization Parameters for Ill-Posed Problems” Inverse Problems, 24 (2008) 034005 (30 pages). DOI:10.1088/0266-5611/24/3/034005
  • W. E. Leithead and Y. Zhang, O(n2)-operation approximation of covariance matrix inverse in gaussian process regression based on quasi-newton bfgs method, Communications in Statistics: Simulation and Computation, vol. 36, pp. 367-380(14), March 2007. http://pdfserve.informaworld.com/832808_731196578_772714353.pdf
  • 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
  • Hossein Mansouri, Cornelis Roos. A New Full-Newton step $O(n)$ Infeasible Interior-Point Algorithm for Semidefinite Optimization. link
  • Paul Tseng, "Second-order cone programming relaxation of sensor network localization" SIAM J. Opt. Vol. 18, No.1 (Feb. 2007). link
  • A. Globerson and T. Jaakkola, "Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations," in Advances in Neural Information Processing Systems, ed. J. C. Platt et al., vol. 20 (MIT Press, 2008), 553--560. link
    with applications to fuzzy logic: M.K. Luhandjula, "Fuzzy stochastic linear programming: Survey and future research directions," European Journal of Operational Research 174, no. 3 (November 1, 2006): 1353-1367, doi:10.1016/j.ejor.2005.07.019. link
  • Seung-Jean Kim, Koh, K., Lustig, M., Boyd, S., Gorinevsky, D., An Interior-Point Method for Large-Scale l1-Regularized Least Squares, IEEE J. of Selected Topics in Signal Processing, Dec. 2007 Volume: 1, Issue: 4 606-617 link
  • Chuanhai Liu and Scott A. Vander Wiel, Statistical Quasi-Newton: A new look at least change, SIAM Journal on Optimization, Vol. 18, Issue 4, pp. 1266-1285, 2007. link
  • L. Vandenberghe, S. Boyd, and K. Comanor, Generalized Chebyshev Bounds via Semidefinite Programming, SIAM Review, 49(1):52-64, March 2007. link
  • Z. Wang, S. Zheng, S. Boyd, Y. Ye, "Further Relaxations of the SDP Approach to Sensor Network Localization", 2007 preprint. link
  • Havary-Nassab, V., Shahbazpanahi, S., Grami, A., Zhi-Quan Luo, Distributed Beamforming for Relay Networks Based on Second-Order Statistics of the Channel State Information, IEEE Transactions on Signal Processing, Sept. 2008 Volume: 56, Issue: 9 4306-4316 link
  • Mario A. T. Figueiredo, Robert D. Nowak, and Stephen J. Wright, "Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems" IEEE Journal of Selected Topics in Signal Processing, vol. 1, issue 4, pp. 586-597, Dec. 2007 link
  • H. Mansouri, M. Zangiabadi, Y. Bai, C. Roos, "An Infeasible Interior-Point Algorithm with full-Newton Step for Linear Optimization" , 2008 link
  • Y. Wang and S. Boyd, Performance Bounds for Linear Stochastic Control, to appear in Systems and Control Letters, 2008 link
  • Steven C.H. Hoi and Rong Jin, Active Kernel Learning, ICML 2008 link
  • Rakitianskaia, A., Engelbrecht, A.P., Cooperative charged particle swarm optimiser, Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). 933-939 link
  • Samuel S Gross, Chuong B Do, Marina Sirota, Phylogeny-free approach to multiple informant de novo gene prediction link
  • Quek, T.Q.S.; Win, M.Z.; Hyundong Shin; Chiani, M. Optimal Power Allocation for Amplify-And-Forward Relay Networks via Conic Programming, Communications, 2007. ICC apos;07. IEEE International Conference on Volume , Issue , 24-28 June 2007 Page(s):5058 - 5063 Digital Object Identifier 10.1109/ICC.2007.835 link >
  • Miguel F. Anjos, Anthony Vannelli. "Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes" link
  • Implementing a dense quasi-Newton solver
  • Carlos Jabbour, Javier F. Pena, Juan C. Vera, Luis F. Zuluaga "An estimation-free, robust conditional value-at-risk portfolio allocation model" link
  • "Smooth Optimization with Approximate Gradient" by Alexandre d'Aspremont link
  • Stationarity results for generating set search for linearly constrained problems Tamara Kolda, Robert Michael Lewis, Virginia Torczon. Siam J. Optimization Vol 17 No 4 943-968. link