CSE 543T Algorithms for Nonlinear Optimization: Homework 1

Due: Oct 3, 11:59pm I. (20%): Problem 1.1.4 II. (30%) Problem 1.2.1

III. (50%)

The Mathematics and Computer Science (MCS) Division of the Argonne National Laboratory is a major research force in mathematical optimization. They have maintained the NEOS optimization server and released various high-performance optimization packages. Learn how to use them and evaluate several unconstrained optimization methods in this homework.

1. AMPL (www.ampl.com) is one of the most popular languages for modeling optimization problems. NEOS (http://neos-server.org/neos/) is an optimization server that allows users to submit their problems (in AMPL format and others) to a collection of solvers.

(25%)

a. Study the example AMPL models in http://www.ampl.com/EXAMPLES/ to learn how to model a problem in AMPL. Visit the NEOS server, find out the solver

list and how to submit a problem in AMPL to a solver.

b. Download the following three unconstrained problems dqrtic.mod, eigenbls.mod, freuroth.mod,

from: https://vanderbei.princeton.edu/ampl/nlmodels/cute/index.html

Submit each of them to the bound constrained solver, L-BFGS- B, on NEOS. Report the following:

2.

b.1 Briefly explain the main algorithm of L-BFGS-B.

b.2 Generate a table that lists the solution time (an estimate will do) and solution quality of the three problems.

The Rastrigin Function is a highly nonlinear function with many local minima. A description of the function can be found at http://tracer.lcc.uma.es/problems/rastrigin/rastrigin.html. (25%)

a. Write an AMPL model for minimizing the Rastrigin function. Specify a random non-zero starting point (you can choose anything you like, such as all x’s = 1.0)

b. Use L-BFGS-B (through NEOS) to solve the Rastrigin problem. Generate a table that lists the solution time and solution quality, for n = 10, 20, 50, 100, 1000, 10000. Compare their performance and discuss your observation. If a solver fails to return a solution for a problem instance, report “failed” in the table.

 Note 1: In your homework report, you only need to provide answers to Problem 1.1.4, Problem 1.2.1, 1.b, and 2.b.

Note 2: Do not wait until the last day to collect data on the NEOS server. The NEOS server may get very busy and your job may be queued for a long time before getting processed.