这个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.