## 3 Custom Interior-Point Method for Solving FLPRC
### Efficient Newton Step Computation
#### 3.3.3 Third Elimination Step  
Equation (42) can be further broken down into smaller pieces, and solved efficiently. We rewrite Equation (42) as in (43)  
\[E\Delta\mathbf{r}_{k} = -g \tag{43}\] \[E = E_{d}+E_{r}\] \[E_{d} = A_{d}^{T}D_{d}A_{d}\] \[E_{r} = A_{r}^{T}D_{r}A_{r}\]The term \(A_{r}^{T}D_{r}A_{r}\) can be factorized as in Equation (44)  
\[A_{r}^{T}D_{r}A_{r}=\begin{bmatrix}A_{wb}^{T}&A_{ar}^{T}&A_{s}^{T}&A _{rp}^{T}\end{bmatrix}\begin{bmatrix}D_{wb}&O&O&O\\ O&D_{ar}&O&O\\ O&O&D_{s}&O\\ O&O&O&D_{rp}\end{bmatrix}\begin{bmatrix}A_{wb}\\ A_{ar}\\ A_{s}\\ A_{rp}\end{bmatrix}\] \[=A_{wb}^{T}D_{wb}A_{wb}+A_{ar}^{T}D_{ar}A_{ar}+A_{s}^{T}D_{s}A_{s} +A_{rp}^{T}D_{rp}A_{rp}\] \[=E_{wb}+E_{ar}+E_{s}+E_{rp}, \tag{44}\]  
where \(D_{wb},D_{ar},D_{s},D_{rp}\) are the diagonal matrices with entries with respect to _within-boundary_, _aspect-ratio_, _area_, and _relative-positioning_ constraints. We decompose \(\Delta\mathbf{r}_{k}\) with respect to \((\Delta\mathbf{x},\Delta y)\) and \((\Delta w,\Delta h)\) as \(\Delta\mathbf{r}_{k}=[\Delta\mathbf{r}_{(xy)k}^{T},\Delta\mathbf{r}_{(wh)k}^ {T}]^{T}\). Factorizing (43) into block elements with respect to \((\Delta\mathbf{x},\Delta y)\) and \((\Delta w,\Delta h)\) vectors, we have the following Equation (45)  
\[\begin{bmatrix}E_{11}&E_{12}\\ E_{21}&E_{22}\end{bmatrix}\begin{bmatrix}\Delta r_{(xy)k}\\ \Delta r_{(wh)k}\end{bmatrix}=\begin{bmatrix}g_{xy}\\ g_{wh}\end{bmatrix}, \tag{45}\]  
We discuss the \((m,n)\) block element \(E_{mn},m=1,2,n=1,2\). We define the \((m,n)\) block element of \(E_{d},E_{r},E_{wb},E_{ar},E_{s},E_{rp}\) as \(E_{mn}^{d},E_{mn}^{w},E_{mn}^{ar},E_{mn}^{s},E_{mn}^{rp}\).  
First, \(E_{mn}^{wh},E_{mn}^{w},E_{mn}^{s},m=1,2,n=1,2\) are all diagonal matrices because the block elements of \(A_{wb},A_{ar},D_{wb},D_{ar}\) are diagonal matrices. As for \(E_{mn}^{rp}\), the block elements of \(A_{rp}\) is a _sparse_ matrix, and \(D_{rp}\) is a diagonal matrix, so \(E_{mn}^{rp},m=1,2,n=1,2\) is a sparse symmetric matrix. Since \(E_{mn}^{r},m=1,2,n=1,2\) is the sum of these diagonal matrices and a sparse symmetric matrix, \(E_{mn}^{r},m=1,2,n=1,2\) is a sparse symmetric matrix. On the other hand, for \(E_{mn}^{d}\), since it has only the components related to \((x,y)\), \(E_{11}^{d}\) is a dense matrix, and the other block elements are \(E_{12}^{d},E_{21}^{d},E_{22}^{d}=O\). From the above, by taking the sum of each block element, \(E_{11}\) is a dense matrix, and the other block elements \(E_{12},E_{21}\), and \(E_{22}\) are sparse symmetric matrices.  
Speed-up is achieved using this structure. From the first equation in (45), we can obtain \(\Delta\mathbf{r}_{wh}\) as Equation (46):  
\[E_{11}\Delta\mathbf{r}_{(xy)k}+E_{12}\Delta\mathbf{r}_{(wh)k}=g_ {xy}\] \[\Leftrightarrow\Delta\mathbf{r}_{(wh)k}=E_{12}^{-1}(g_{xy}-E_{11} \Delta\mathbf{r}_{(xy)k}). \tag{46}\]  
Substituting this into the second equation in (45), we have Equation (47) to get \(\Delta\mathbf{r}_{xy}\):  
\[E_{21}\Delta\mathbf{r}_{(xy)k}+E_{22}(E_{12}^{-1}(g_{xy}-E_{11} \Delta\mathbf{r}_{(xy)k}))=g_{wh}\] \[\Leftrightarrow(E_{21}-E_{22}E_{12}^{-1}E_{11})\Delta\mathbf{r}_{( xy)k}=E_{22}E_{12}^{-1}g_{xy}-g_{wh}. \tag{47}\]  
Using this elimination, we can compute \(\Delta\mathbf{r}_{(xy)k}\) efficiently, we then compute the remaining variables \(\Delta\mathbf{r}_{(xy)k},\Delta\mathbf{d},\Delta\lambda\), which is faster than just solving the larger set of equations (33) using a standard factorization method.  
Note that all of the matrices are non-singular, if there exists an optimal solution of problem (15).