这个Assignment是用Matlab完成汤普森问题

APPLIED OPTIMIZATION METHODS 2019/20

(2)

min

x∈Rn¯

f(x)

s.t. hi(x) = 0, i = 1, . . . , m. ¯

For the generalized Thompson problem, there are ¯n = n·d decision variables and ¯m = n constraints.

In order to solve the general equality constrained optimisation problem, we can apply the sequential

quadratic programming (SQP) algorithm, which is described as follows:

Step 1. Choose an initial point x

(0), multipliers u

(0), a tolerance > 0, and set k = 0.

Step 2. Compute the direction dk and the next multipliers u

(k+1) as the optimal solution and the

multipliers, respectively, of the following quadratic optimisation problem

(3) min ∇f(x

(k)

)

Td +

1

2

d

T

Hf (x

(k)

) +Xm

i=1

u

(k)

i Hhi

(x

(k)

)

!

d

s.t. hi(x

(k)

) + ∇hi(x

(k)

)

Td = 0, i = 1, . . . , m.

Step 3. Update x

(k+1) = x

(k) + dk.

Step 4. If ||dk|| ≤ , stop. Otherwise, set k ← k + 1 and go to Step 2.

For this question, consider the following tasks.

1. Derive the KKT conditions of the quadratic optimisation problem (3) and show that dk

and u

(k+1) can be obtained by solving a system of linear equations in general.

2. Implement the SQP algorithm in Matlab for the generalized Thompson problem given the

dimension d, d ≥ 2, and the number of points n, n ≥ 2. Explain all necessary inputs of the

algorithm.

1

2 ASSIGNMENT

3. Solve the Thompson problem with d = 2 and n = 20 using different initial points and

multipliers. The tolerance should be set to = 1e

−6

. Discuss the convergence of the

algorithm. Visualise and analyse the solutions.

4. Modify the problem so that the (global) optimal solution can be unique when d = 2. Implement

the SQP algorithm in Matlab to solve the modified problem. Solve the Thompson

problem with d = 3 and n = 10 using different initial points and multipliers. Visualise and

analyse the solutions.

2. Question 2

In a chaotic warehouse organisation (used for example by Amazon), the same product may be

stored at different locations. This means that if an order of n different products needs to be

collected from the warehouse, it is possible to select, for each product, the most convenient of the

storage locations. Given a set of n products to be collected, and all the storage locations for each

product, the optimisation problem is then to identify the shortest tour from the depot to one of

the storage locations of every product and then back to the depot. For simplicity, let us assume

that storage locations are specified as (x, y) coordinates on a plane, and distances between storage

locations are simply Euclidean distances.

## 发表评论