Solved Math564 Project #3 : Minimum Cost Connecting Paths

We are tasked with providing a minimum loss layout of power transmission lines that extend from a central power station (z0) in a local community (P1) out to four additional outlying communities (P2, P3, P4, P5). The key decision is to locate two transfer stations within each community along with a main connecting grid as shown in the figure below. The first and final locations z0 and z9 are fixed established facilities. The power loss in any transmission line is proportional to the square of the length with proportionality constant dependent on the type of construction. Within each community the constant is β > 0, and between communities the constant is α > β. z0 z1 z2 z3 z4 z5 z6 z7 z8 z9 P1 P2 P3 P4 P5 The problem can be modeled as a Quadratic Program: max f(z) = β 2 X 4 k=0 ∥z2k − z2k+1∥ 2 + α 2 X 4 k=1 ∥z2k−1 − z2k∥ 2 s.t zk ∈ P1+⌊k/2⌋, k = 1, 2, . . . , 8 where z0 and z9 are given fixed locations in R 2 and each Pk is defined by given linear inequality constraints. The five polygons for this problem are defined as the convex hulls of the following vertex sets. P0 = conv{(2, 1),(6.2, 2.8),(7.7, 7.9),(2, 8),(0.4, 4.5)} P1 = conv{(9.9, 3.6)(11.6, 2.7),(13.2, 5.7),(10.4, 6.3)} P2 = conv{(15.5, 5.7),(16.3, 3.4),(18.2, 4.3),(18.2, 7.5),(16.1, 7.6)} P3 = conv{(21.6, 0.8),(23.5, 9.5),(21.7, 7.7)} P4 = conv{(23.7, 5.5),(24.9, 3.7),(27.6, 5.6),(25, 6.7)} If the vertices of a bounded polygon are listed in counter-clockwise order (as they are above), then we can construct a linear inequality constrained description of the polygon as follows. Suppose P = conv{(a1, b1), . . . ,(ap, bp)}, then P = {(x, y) ∈ R 2 | (bk+1 − bk)x + (ak − ak+1)y ≤ akbk+1 − bkak+1, k = 1, . . . , p}, where (ap+1, bp+1) := (a1, b1). P3-1 Task 1. Verify that the objective function is convex and coercive. Also, argue that the optimal locations of points z1, . . . , z8 will lie on the boundary of their respective polyhedra. Task 2. The general QP is min w q(w) = 1 2w TGw + w T c s.t. Aw ≥ b Aew = be w ∈ R n Compose a Matlab or python function that constructs the Quadratic Program matrices G, c, A, b, Ae, be for this class of problems. Include the possibility that polyhedra can be defined using both equality and inequality constraints. Task 3. Compose a Matlab or python function that solves a general constrained Quadratic Program. You code should take into account at least four possibilities: (a) The problem is a linear program (G = 0), in which case you can call a linear program solver; (b) The QP is unconstrained, in which case you can solve with a single Newton step; (c) The QP has only equality constraints, in which case you can use a CG method; and (d) The QP has at least one inequality constraint, in which case you can employ the Active Set Method. Task 4. Use your QP code to solve the transmission line problem with the given polyhedra. Let z0 = (4, 5), z9 = (26, 5) and β = 1. Solve for various values of α ≥ β. Discuss your findings. Task 5. Modify one of the intermediate community polyhedrons to be a single line segment. Solve this problem using a value of α of your choosing. (This task is intended to test your code’s ability to handle equality constraints.) Task 6. Compose and submit a short report on your results of Tasks 1, 4 and 5. P3-2 If you would like the LATEX code for producing the figure, then here it is: \definecolor{Amber}{RGB}{230,191,0} \begin{center}\begin{tikzpicture}[scale=0.6] \draw[thick,blue](2,1)--(6.2,2.8)--(7.7,7.9)--(2,8)--(0.4,4.5)--cycle; \draw[thick,blue](9.9,3.6)--(11.6,2.7)--(13.2,5.7)--(10.4,6.3)--cycle; \draw[thick,blue](15.5,5.7)--(16.3,3.4)--(18.2,4.3)--(18.2,7.5)-- (16.1,7.6)--cycle; \draw[thick,blue](21.6,0.8)--(23.5,9.5)--(21.7,7.7)--cycle; \draw[thick,blue](23.7,5.5)--(24.9,3.7)--(27.6,5.6)--(25,6.7)--cycle; \draw[ultra thick,Amber](4,5)--(7.2,6.2)--(10.3,5.6)--(13.2,5.7)-- (15.5,5.7)--(18.2,6.5)--(21.65,6.5)--(22.75,6)-- (23.7,5.5)--(26,5); \filldraw[black](4,5) circle (0.1) node[left]{$z_0$}; \filldraw[black](7.2,6.2) circle (0.1) node[below, xshift=6]{$z_1$}; \filldraw[black](10.3,5.6) circle (0.1) node[below, xshift=6]{$z_2$}; \filldraw[black](13.2,5.7) circle (0.1) node[below, xshift=6]{$z_3$}; \filldraw[black](15.5,5.7) circle (0.1) node[below, xshift=-6]{$z_4$}; \filldraw[black](18.2,6.5) circle (0.1) node[below, xshift=6]{$z_5$}; \filldraw[black](21.65,6.5) circle (0.1) node[below, xshift=-6]{$z_6$}; \filldraw[black](22.75,6) circle (0.1) node[above, xshift=9]{$z_7$}; \filldraw[black](23.7,5.5) circle (0.1) node[below, xshift=-3]{$z_8$}; \filldraw[black](26,5) circle (0.1) node[above, xshift=6]{$z_9$}; \node[blue] at(3,7){$P_1$}; \node[blue] at(11.5,4){$P_2$}; \node[blue] at(17,4.5){$P_3$}; \node[blue] at(22.5,7.5){$P_4$}; \end{tikzpicture}\end{center} P3-3