CS5321 Numerical Optimization Project

Tentative schedule

1. Choose at most three papers you would like to study and send them to TA by April 7.
2. TA will make teams according to your preferences, and announce the results by April 14. Each team has at most 3 members.
3. You can propose to change teams or papers before April 21.
4. After April 21, TA will announce the dates of presentations, which should start around the end of May.
5. Email your final report to me by June 19.
   (If you are graduating this semeter and you want to get your grade by June 11, you need to submit your report by June 9.)

Requirements and grading policy

1. Every team needs to prepare a presentation in English. Each team member needs to present at least 15 minutes.
2. Every student needs to give scores, 0-100, and suggestions/questions to the presentations made by other teams. The score will be collected after the presentation.
3. Everyone submits its own final report in English, including
   • A short summary of the paper,
   • Experiments you had done about this paper,
   • Small examples to explain the theory and idea in the paper,
   • Reference: other papers or webpages that you read to help you finish this project,
   • Matlab code or C code you developed (in separated files).
     (If its a team effort to write the code, describe the work breakdown.)
   The report, besides the codes, should be limited to 6 pages.
4. Your grade of the project is based on 3 parts
   • Your presentation (10%),
   • The scores and feedbacks you give to other teams (10%),
   • Your final report (10%).
   The presentation score will be from other students and me. I will grade your scores to other teams.

Paper list

1. Haw-ren Fang and Dianne P. O'Leary, Modified Cholesky Algorithms: A Catalog with New Approaches, Mathematical Programming A, (2007)
2. Yasushi Narushima, Hiroshi Yabe and John A. Ford, A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM J. Optim. 21, pp. 212-230
3. H.-r. Fang and Y. Saad, Two Classes of Multisecant Methods for Nonlinear Acceleration, Journal of Numerical Linear Algebra with Applications, Vol. 16, pp. 197-221. 2009.
4. 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
5. Spielman, Daniel; Teng, Shang-Hua, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, pp. 296–305,
6. Haw-ren Fang, Sven Ley?er, and Todd S. Munson, A Pivoting Algorithm for Linear Programs with Complementarity Constraints, Optimization Methods and Software
7. S. Yun, and K.-C. Toh, A coordinate gradient descent method for L1-regularized convex minimization, Computational Optimization and Applications, April 2009.
8. Nathan Krislock and Henry Wolkowicz, Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions. pdf
9. 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
10. Istvan Deak, Imre Polik, Andras Prekopa, and Tamas Terlaky, Convex Approximations in Stochastic Programming by Semidefinite Programming. pdf
11. Stephen Becker, Emmanuel Candes, and Michael Grant, Templates for Convex Cone Problems with Applications to Sparse Signal Recovery, pdf
12. 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.
13. 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
14. N. S. Aybat and G. Iyengar, A First-Order Smoothed Penalty Method for Compressed Sensing, SIAM J. Optim. 21, pp. 287-313
15. Chunqi Chang, Yeung Sam Hung, and Zhi Ding, A new optimization algorithm for network component analysis based on convex programming 2009 IEEE International Conference on Acoustics, Speech and Signal Processing.
16. Bernard Chazelle, Natural Algorithms, SODA 2009
17. 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.
18. 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.
19. Chi-Kong Ng, Duan Li, and Lian-Sheng Zhang Global Descent Method for Global Optimization, SIAM J. Optim. 20, pp. 3161-3184
20. Hideaki Iiduka, Fixed point optimization algorithm and its application to power control in CDMA data networks, Mathematical programming, 5 November 2010
21. A Tutorial on Integer Programming (link)