2010 AMSC 607 /CMSC 764 Term Project Information

Summary: The purpose is for you to become an expert on one of the papers in the list posted on October 12. You will experiment with the algorithm discussed in the paper, or illustrate the theory described there, and identify open questions that could be the topic of further research. Optionally, you will present the paper to the class, instead of taking the final exam.

For your project, choose a paper from the list below and study it, reading background papers as necessary.

You may choose to do Part 1 only, for 100 points. In this case you will also take a final exam.

You may choose to do both Part 1 and Part 2, for 200 points. In this case you need not take the final exam.

Doing only Part 2 is not an option.

Deadlines and points:

  • By October 26, you should send me email with the number of the paper you have chosen. Indicate whether you want to present the paper to the class.
    I will send you email telling you either that the paper has been assigned to you, or that another student requested that paper before you did.
    If you change your mind about the paper assigned to you, you need to send your request after 9:30 on October 26.
  • Part 1 is due at 11 am, Tuesday December 14.
  • There will be a 15% penalty if Part 1 is turned in up to 24 hours late, 30% penalty for projects turned in 24--48 hours late, etc.
  • Your Part 2 presentation date will be given in my email message to you.

    • What to submit for Part 1: Your project must have these 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.
  • Assume that your audience has read and understood the paper, so just talk about additional aspects, such as how the paper fits into the literature, what experiments you performed or extensions you thought about,
  • Include a list of open research problems related to your paper or problem.
  • A list of references, including html links if available.
  • Your Matlab code, including the testing program.

    • How to submit: Submit Part 1 by e-mail.

  • The slides and references should be in pdf format.
    Microsoft-formatted documents (Word, Excel, Powerpoint, etc.) will not be accepted; submit a pdf 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 or plain text.
  • The entire set of files should be bundled into a single file (in tar, zip, or gzip format) and attached to the e-mail. rar is a Microsoft format and will not be accepted.
    • I'll acknowledge your submission by e-mail after I have successfully extracted the files.

    Some questions that will be asked while evaluating Part 1:

  • 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 large enough to be readable when projected? More precisely, is it about as large as the type I use in class?
  • 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: Lateness or plagiarism puts you in danger of failing the course. 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.

    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.

    Part 2 If you choose a 200 point project, then you will also give a half-hour talk (20 minutes + 10 minutes for questions) during class, explaining the contents of your paper. Email me your slides (pdf) before your presentation. I will assign time slots in order, Dec 9, Dec 7, Dec 2, Nov 30, Nov 23, unless you have a specific request for an early date. Your grade will be based on the clarity and quality of your slides and your oral presentation, including how well your fellow students understand what you say.

    Choose a paper from this list:

  • Not Available P01. Nathan Krislock and Henry Wolkowicz,
    Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions,
    pdf
  • Not Available P02. Florian A. Potra,
    A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points,
    Mathematical Programming Volume 67, Numbers 1-3, 383-406, DOI: 10.1007/BF01582228 pdf
  • Not Available P03. E. Acar, D. M. Dunlavy and T. G. Kolda,
    A Scalable Optimization Approach for Fitting Canonical Tensor Decompositions,
    Journal of Chemometrics, in press. pdf
  • Available P04. Kim-Chuan Toh, Michael J. Todd, and Reha H. Tutuncu,
    On the implementation and usage of SDPT3 a Matlab software package for semidefinite-quadratic-linear programming, version 4.0,
    pdf
  • Not Available P05. Stephen Becker, Emmanuel Candès, Michael Grant,
    Templates for Convex Cone Problems with Applications to Sparse Signal Recovery,
    pdf
  • Not Available P06. Zaiwen Wen, Donald Goldfarb, Wotao Yin,
    Alternating Direction Augmented Lagrangian Methods for semidefinite programming,
    pdf
  • Not Available P07. Donald R. Jones,
    A Taxonomy of Global Optimization Methods Based on Response Surfaces,
    Journal of Global Optimization,
    Volume 21, Number 4, 345-383, DOI: 10.1023/A:1012771025575 pdf
  • Not Available P08. Jaco F. Schutte and Albert A. Groenwold,
    A Study of Global Optimization Using Particle Swarms,
    Journal of Global Optimization Volume 31, Number 1, 93-108, DOI: 10.1007/s10898-003-6454-x pdf
  • Not Available P09. Panos M. Pardalos,
    Recent developments and trends in global optimization,
    Journal of Computational and Applied Mathematics Volume 124, Issues 1-2, 1 December 2000, Pages 209-228 doi:10.1016/S0377-0427(00)00425-8 pdf
  • Available P10. M. Locatelli,
    Simulated Annealing Algorithms for Continuous Global Optimization: Convergence Conditions,
    Journal of Optimization Theory and Applications Volume 104, Number 1, 121-133, DOI: 10.1023/A:1004680806815 pdf
  • Available P11. Kenji Ueda and Nobuo Yamashita,
    Convergence Properties of the Regularized Newton Method for the Unconstrained Nonconvex Optimization,
    Applied Mathematics & Optimization Volume 62, Number 1, 27-46, DOI: 10.1007/s00245-009-9094-9 pdf
  • Available P12. K. Ammari and B. Chentouf,
    Further Results on the Robust Regulation of a One-Dimensional Dam-River System,
    Journal of Optimization Theory and Applications DOI: 10.1007/s10957-010-9729-7 pdf
  • Not Available P13. A. Miele, T. Wang, J. A. Mathwig and M. Ciarcià,
    Collision Avoidance for an Aircraft in Abort Landing: Trajectory Optimization and Guidance,
    Journal of Optimization Theory and Applications Volume 146, Number 2, 233-254, DOI: 10.1007/s10957-010-9669-2 pdf
  • Available P14. M. Fukuda, B.J. Braams, M. Nakata, M.L. Overton, J.K. Percus, M. Yamashita and Z. Zhao,
    Large-Scale Semidefinite Programs in Electronic Structure Calculation,
    Math. Programming 109 (2007), pp. 553-580. pdf
  • Not Available P15. M.V. Nayakkankuppam and M.L. Overton,
    Conditioning of Semidefinite Programs,
    Math Programming 85 (1999), pp. 525-540 pdf
  • Available P16. Pierre Girardeau,
    A Comparison of Sample-based Stochastic Optimal Control Methods,
    pdf
  • Available P17. Cosmin Petra and Mihai Anitescu,
    A Preconditioning Technique for Schur Complement Systems Arising in Stochastic Optimization,
    pdf
  • Not Available P18. István Deák, Imre Pólik, András Prékopa, Tamás Terlaky,
    Convex Approximations in Stochastic Programming by Semidefinite Programming,
    pdf
  • Available P19. Paul Tseng,
    Approximation accuracy, gradient methods, and error bound for structured convex optimization,
    Math. Program., Ser. B DOI 10.1007/s10107-010-0394-2 pdf
  • Available P20. Sunyoung Kim, Masakazu Kojima, Martin Mevissen, Makoto Yamashita,
    Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion,
    Math. Program., Ser. A DOI 10.1007/s10107-010-0402-6 pdf
  • Not Available P21. Simon P. Schurr, Dianne P. O'Leary, and Andre L. Tits,
    A Polynomial-Time Interior-Point Method for Conic Optimization, with Inexact Barrier Evaluations,
    SIAM Journal on Optimization, 20:1 (2009) 548-571. DOI: 10.1137/080722825 pdf
  • Not Available P22. Jin Hyuk Jung and Dianne P. O'Leary,
    Implementing an Interior Point Method for Linear Programs on a CPU-GPU System,
    Electronic Transactions on Numerical Analysis, 28 (2008) 174-189. pdf
  • Not Available P23. Armin Pruessner and Dianne P. O'Leary,
    Blind Deconvolution Using a Regularized Structured Total Least Norm Approach,
    SIAM J. on Matrix Analysis and Applications, 24 (2003) 1018-1037. pdf
  • Not Available P24. Dianne P. O'Leary and Bert W. Rust
    Variable Projection for Nonlinear Least Squares Problems
    pdf. Code: varpro.m Sample programs: varpro_example.m and adaex.m
  • Available P25. Haw-ren Fang and Dianne P. O'Leary,
    Modified Cholesky Algorithms: A Catalog with New Approaches,
    Mathematical Programming A, (2007) DOI:10.1007/s10107-007-0177-6 pdf
  • Not Available P26. Luke B. Winternitz, Stacey O. Nicholls, Andre L. Tits, Dianne P. O'Leary,
    A Constraint-Reduced Variant of Mehrotra's Predictor-Corrector Algorithm,
    pdf
  • Not Available P27. Jin Hyuk Jung, Dianne P. O'Leary, and Andre' L. Tits,
    Adaptive Constraint Reduction for Training Support Vector Machines,
    Electronic Transactions on Numerical Analysis, 31 (2008) 156-177. pdf

    • 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.
  • 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 ....