INFORMATION, LAB 2

TMA946 Applied optimization / MAN280 Optimization

Michael Patriksson

18 februari 2002

Preparations

In part II there are some exercises which we recommend that you prepare by formulating the KKT-conditions in advance. If you feel a slight anxiety in the proximity of computers, you may want to take a look at MATLABs optdemo in advance.

Part I: Unconstrained optimization

In this part of the lab, you will solve some unconstrained problems using steepest descent and newtons method. The latter exists in three different version, with unit step (the classic version), Newtons modified method which includes a line-search, and the Levenberg-Marquardt modification, where the eigenvalues of the Hessian matrix are modified in order to make it positive definite. The methods are implemented in MATLAB. The purpose of this laboration is to graphically illustrate the methods in order to give insight into the behaviour.

Startup: Download the tar-file from the course homepage, and follow the instructions given there. Move to the directory ILP (by giving the command cd ILP) and start MATLAB by simply typing matlab. Once MATLAB starts up, type ilpmeny in the command window.

The laboration is menu-driven and mostly self-explaining. The following selections may be done:

Setting  Default value
Starting point  0 0
termination criterion  Gradient length
Function to be minimized  Function 1
Maximal number of iterations 200
Printing of iteration data  On
Method  Stepest descent

You may choose to take 1, 10 or 100 iterations at a time and follow the algorithm search path in the graph.§q

Exercises

In all these exercises, the function is to be minimized.

1. Study function 1

f(x_{1}, x_{2}) = 2(x_{1} + 1)^{2} + 8(x_{2} + 3)^{2} + 5x_{1} + x_{2}

(a) Solve using Steepest Descent and Newtons method (unit step). Start in the points (10, 10) and (−5, −5) as well as in some starting point of your own choice. Toward which point does the methods converge? How many iterations are required?

(b) Is the obtained point an optimal point (globally or locally)?

(c) Why does newton always converge in one iteration?

2. Study function 2 (Rosenbrocks function)

f(x_{1}, x_{2}) = 100(x_{2} − x_{1}^{2})^{2} + (1 − x_{1})^{2}

(a) Solve using steepest descent and newtons method (all versions). start in the point (−1.5, −1.5). Towards which point does the methods converge? How many iterations are required?

(b) Is the function convex? Is the obtained point a global optimum?

(c) Choose some starting points on your own and study the methods behaviour.

3. Study function 4

f(x_{1}, x_{2}) = x_{1}^{3} + 2x_{2}^{3} − 27x_{1} − 6x_{2}

(a) Start in the point (0, 0) and solve using steepest descent and Newtons method (unit step). Why does not Newtons method work? Try the Levenberg-Marquardt modification and study that methods behaviour.

(b) Start in some arbitrarily chosen points. How many stationary points do you find. Which kinds of stationary points.

Those who wish to play further may test the other functions. These are:

(3) f(x_{1}, x_{2}) = −5e^{− \frac{x^{2}_{1}+x^{2}_{2}}{10}} + 4e^{− \frac{x^{2}_{1}+x^{2}_{2}}{100}} − 5^{− \frac{(x_{1}−5)^{2}+(x_{2}+4)^{2}}{10}} − 5^{− \frac{(x_{1}+4)^{2}+(x_{2}−5)^{2}}{10}} − 4^{− \frac{(x_{1}+4)^{2}+(x_{2}−5)^{2}}{100}}

(5) f(x_{1}, x_{2}) = −4e^{− \frac{(x_{1}+2)^{2}+(x_{2}+1)^{2}}{10}} + 4e^{− \frac{(x_{1}+2)^{2}+(x_{2}+1)^{2}}{100}} + 0.01((x_{1} + 2)^{2} + (x_{2} + 1)^{2}) + 0.01x_{1}

(6) f(x_{1}, x_{2}) = (x_{1}^{3} − x_{2})^{2} + 2(x_{1} − x_{2})^{4}

(7) f(x_{1}, x_{2}) = −5 cos(0.2(1 + \frac{x_{2}^{2}−0.5}{x_{1}^{2}+0.5}) + 0.001x_{2}^{4} + 0.003x_{1}^{4} + 2x_{1}

(8) f(x_{1}, x_{2}) = 2(x_{2} − x_{1}^{3})^{2} + 0.1(x_{1} + 2)^{2} + 0.5x_{2}^{2} + x_{1}^{2}x_{2}^{2}

Part II: Constrained optimization; MATLAB:s Optimization Toolbox

In this part of the lab, you are to use MATLABs optimization routines to solve some non-linear problems.

note! This part of the lab should be prepared by formulating the KKT-conditions. To save you and us some computer related trouble we have included the functions as upg1f, upg1g, upg2f and upg2g for the objective function and constraints of the two problems. Try help fmincon to see how the non-linear minimization routine is used.

Exercises

1. Given the problem

max x_{1} − 2x_{1}^{2} + 2x_{2} − x_{2}^{2} + x_{1}x_{2}
då x_{1}^{2} − x_{2} ≤ 0
2x_{1} − x_{2} ≥ 0

(a) Solve the problem using fmincon

(b) State the KKT-conditions, examine the convexity of the problem and verify that the obtained solution is a global maximum.

2. Given the problem

min x_{1}
då (x_{1} − 1)^{2} + (x_{2} + 2)^{2} ≤ 16
x_{1}^{2}  +  x_{2}^{2}  ≥ 13

Solve the problem at least five times from different starting points. Describe what happens. Which point is the best one. can you guarantee that this is a global maximum. Fun points to try are (1, 1), (0, 0), (3.7, 0) and (−1, −1)

Part III: Constrained optimization: penalty methods

Consider the problem

minimize f(x),
då g(x) ≤ 0^{m},

where f and g are continuous functions. Penalty methods are generally of one of two different kinds: exterior and interior penalty methods, depending in if the methods generally give an infeasible of strictly feasible sequence of iteration points. We have implemented one method of each kind in MATLAB.

In order to run the programs, you should move from the library ILP to the libraries ILP/EPA (exterior) or ILP/IPA (interior). Both algorithms are started by typing dispatch in matlabs command window.

Note that the problem is given with the constraints on “≤”-form, while Nash-Sofer describes the methods using the “≥”-form.

The exterior penalty method (“penalty method” in Nash-Sofer) works with the relaxation

minimize_{x∈ℜ^{n}} f(x) + ρ_{k}ψ(x),

where ρ_{k} > 0 and ρ_{k} → +∞ when k → +∞, and the penalty function is the quadratic function

ψ(x) := ∑_{i=1}^{m} (max{0, g_{i}(x)})^{2} .

The interior penalty method (“barrier method” in Nash-Sofer) works with the relaxation

minimize_{x∈ℜ^{n}} f(x) + μ_{k}ϕ(x),

where μ_{k} > 0 and μ_{k} → 0 when k → +∞, and where the penalty function is the function

ϕ(x) := − ∑_{i=1}^{m} log(−g_{i}(x)).

In order to avoid numerical problems one usually lets the sequences ρ_{k} and μ_{k} converge slowly.

There are three problems available for both these methods:

(1)

minimoize f(x) := ∥x∥^{2},
då g_{1}(x) := −x_{1} + 2 ≤ 0,
g_{2}(x) := −x_{2}/3 + 1/3 ≤ 0.

(2)

minimize f(x) := x_{1} sin(x_{1}) + x_{2} sin(x_{2}),
då g_{1}(x) := x_{1} + 1/3 ≤ 0,
g_{2}(x) := sin(x_{2}) − x_{1} ≤ 0,
g_{3}(x) := −x_{2}/3 + 1/4 ≤ 0,
g_{4}(x) := ∥x − (1, 1)^{T}∥^{2}/5 − 1 ≤ 0.

(3)

minimize f(x) := x_{1}x_{2},
då g_{1}(x) := ∥x∥^{2}/5 − 5 ≤ 0,
g_{2}(x) := −x_{1} − x_{2} ≤ 0.

Exercises

1. Use both methods for the problems 2 and 3. Tell us which points the two algorithms converge to for both problems.

2. Does the methods converge towards a global optimum, a local optimum or something else?

3. Which optima exists for the problems?