CSE260 Optimization (Spring semester 2008): project 2

Project 2 consists of reviewing a research paper with some optimisation content. You can either choose one paper from the list below or suggest to me a paper yourselves. Send me your review (handwritten, if you prefer) as a PDF file using as email subject [CSE260] Project 2.

Your review should be 1-2 typed pages long and contain the following:

• A summary of the paper, no more than 1/3 of a page long.
• A brief description of the optimisation material in the paper, i.e., a statement of the optimisation problem and why it is necessary, and a description of the method applied to solve it.
• Your evaluation of the optimisation material in the paper in relation to what we have seen in the course. Here are some suggestions for questions to ask (not all may apply): is the problem constrained/unconstrained/smooth/line-search/trust-region...? If it uses a line search, does it satisfy the Wolfe (or other) conditions? Does the paper use a standard optimisation algorithm, or are there ad-hoc modifications, and if so what are the consequences? Are there better choices of algorithm (take into account ease of implementation, scalability wrt problem size, etc.)? Is the empirical evaluation fair and conclusive (competing methods are often presented at a disadvantage)? What is the stopping condition or convergence criterion? Does the problem have a unique optimum? How important is the optimisation part in the paper's main objectives?

You don't need to read the papers in their entirety, just to get an idea of what they deal with, and then focus on the optimisation part.

The list of papers, classified by type:

• Original references for an optimisation method:

  1. William C. Davidon: "Variable metric method for minimization". SIAM J. Opt. 1(1):1-17 (1991).
     Originally published as Argonne National Laboratory Research and Development Report, ANL-5990 (Rev.), Argonne, IL, 1959.
  2. R. Hooke and T. A. Jeeves: "``Direct Search'' Solution of Numerical and Statistical Problems". J. ACM 8(2):212-229 (Apr. 1961).
  3. Donald W. Marquardt: "An algorithm for least-squares estimation of nonlinear parameters". J. SIAM 11(2):431-441 (Jun. 1963).
  4. R. Fletcher and M. J. D. Powell: "A rapidly convergent descent method for minimization". Computer J. 6(2):163-168 (Jul. 1963).
  5. R. Fletcher and C. M. Reeves: "Function minimization by conjugate gradients". Computer J. 7(2):149-154 (Jul. 1964).
  6. M. J. D. Powell: "An efficient method for finding the minimum of a function of several variables without calculating derivatives ". Computer J. 7(2):155-162 (Jul. 1964).
  7. Donald Goldfarb: "A family of variable-metric methods derived by variational means". Math. Comp. 24(109):23-26 (Jan. 1970).
  8. C. G. Broyden: "The convergence of a class of double-rank minimization algorithms. 1. General considerations". J. Institute of Mathematics and its Applications 6(1):76-90 (Mar. 1970).
  9. D. F. Shanno: "Conditioning of quasi-Newton methods for function minimization". Math. Comp. 24(111):647-656 (Jul. 1970).
  10. R. Fletcher: "A new approach to variable metric algorithms". Computer J. 13(3):317-322 (Aug. 1970).
  11. John E. Dennis, Jr. et al.: "An adaptive nonlinear least-squares algorithm". ACM Trans. Mathematical Software 7(3):348-368 (Sep. 1981).

• Machine learning:

  1. John W. Sammon, Jr.: "A nonlinear mapping for data structure analysis". IEEE Trans. Computers C-18(5): 401-409 (May 1969).
  2. R. Battiti: "Accelerated back-propagation learning: two optimization methods". Complex Systems 3(4):331-342 (1989).
  3. Barak A. Pearlmutter: "Fast exact multiplication by the Hessian". Neural Computation 6(1):147-160 (Jan. 1992).
  4. R. Battiti: "1st-order and 2nd-order methods for learning -- between steepest descent and Newton method". Neural Computation 4(2):141-166 (Mar. 1992).
  5. Martin F. Møller: "A scaled conjugate gradient algorithm for fast supervised learning". Neural Networks 6(4):525-533 (1993).
  6. John Skilling: "Bayesian numerical analysis". In Physics and Probability: Essays in Honor of Edwin T. Jaynes (W. T. Grandy, Jr. and P. Milonni, eds.), Cambridge Univ. Press, 1993.
  7. Jeng-Neng Hwang et al.: "Regression modeling in back-propagation and projection pursuit learning". IEEE Trans. Neural Networks 5(3):342-353 (May 1994).
  8. S. Kollias and D. Anastassiou: "An adaptive least squares algorithm for the efficient training of artificial neural networks". IEEE Trans. Circuits and Systems 36(8):1092-1101 (Aug. 1989).
  9. Martin T. Hagan and Mohammad B. Menhaj: "Training Feedforward Networks with the Marquardt Algorithm". IEEE Trans. Neural Networks 5(6):989-993 (Nov. 1994).
  10. P. Patrick van der Smagt: "Minimisation methods for training feedforward neural networks". Neural Networks 7(1):1-11 (1994).
  11. Lei Xu and Michel I. Jordan: "On convergence properties of the EM algorithm for Gaussian mixtures". Neural Computation 8(1):129-151 (Jan. 1996).
  12. Seán McLoone and George Irwin: "Fast parallel off-line training of multilayer perceptrons". IEEE Trans. Neural Networks 8(3):646-653 (May 1997).
  13. Seán McLoone et al.: "A hybrid linear/nonlinear training algorithm for feedforward neural networks". IEEE Trans. Neural Networks 9(4):669-684 (Jul. 1998).
  14. Aapo Hyvärinen: "Fast and robust fixed-point algorithms for independent component analysis". IEEE Trans. Neural Networks 10(3):626-634 (Oct. 1999).
  15. Miguel Á. Carreira-Perpiñán: "Mode-finding for mixtures of Gaussian distributions". IEEE Trans. Pattern Analysis and Machine Intelligence 22(11):1318-1323 (Nov. 2000).
  16. Nic Schraudolph, Jin Yu and Simon Guenter: "A stochastic quasi-Newton method for online convex optimization". AISTATS'2007.

• Other:

  1. S. E. Levinson and C. E. Schmidt: "Adaptive computation of articulatory parameters from the speech signal". J. Acoust. Soc. Am. 74(4):1145-1154 (Oct. 1983).
  2. A. A. Goldenberg and B. Benhabib and R. G. Fenton: "A complete generalized solution to the inverse kinematics of robots". IEEE J. Robotics and Automation RA-1(1): 14-20 (Mar. 1985).
  3. I. M. Navon and D. M. Legler: "Conjugate-gradient methods for large-scale minimization in meteorology". Monthly Weather Review 115(8): 1479-1502 (Aug. 1987).
  4. M. Guay and D. D. McLean: "Optimization and sensitivity analysis for multiresponse parameter estimation in systems of ordinary differential equations". Computers & Chemical Engineering 19(12):1271-1285 (Dec. 1995).

• Software implementation:

  1. Interactive Educational Modules in Computational Science from UIUC: Optimization. These are Java applets implementing optimisation methods. You have to review the following methods: steepest descent, Newton, BFGS, conjugate gradient, Gauss-Newton, Levenberg-Marquardt.

UC Merced | EECS | MACP's Home Page