Fordham University

Computer code for "The worst 1-PS for rational curves with a unibranch singularity" by Jackson and Swinarski

Example 2: The KKT matrix equation

We compute the KKT matrix equation for three examples.

Example 2a First, we compute the KKT matrix for the semigroup \( \langle 2,3 \rangle\) with \(N=3\) and \(I = \emptyset\), and the Unsimplified Problem. 

Macaulay2, version 1.24.05
with packages: ConwayPolynomials, Elimination, IntegralClosure, InverseSystems, Isomorphism,
               LLLBases, MinimalPrimes, OnlineLookup, PrimaryDecomposition, ReesAlgebra,
               Saturation, TangentCone, Truncations, Varieties

i1 : load "Worst1PS.m2"

i2 : -- Example 2a
     KKTmatrix(3,{2,3},{})

o2 = | -1 0  8 2 |
     | 3  -1 4 2 |
     | -2 2  2 2 |
     | 0  -1 0 2 |

              4       4
o2 : Matrix QQ  <-- QQ

i3 : avector(3,{2,3})

o3 = {2, 3, 2, 1}

o3 : List

i4 : KKTsolutionVector(3,{2,3},{})

      36  6   8  8
o4 = {--, -, --, -}
      35  5  35  5

o4 : List
Thus, the KKT matrix equation for this face is \[ \left[\begin{array}{rrrr} -1 & 0 & 8 & 2 \\ 3 & -1 & 4 & 2 \\ -2 & 2 & 2& 2 \\ -0 & -1 & 0 & 2 \\ \end{array} \right] \left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = \left[ \begin{array}{r} 4\\ 6\\ 4 \\ 2 \end{array} \right] \] and it has solution \(x = \left(\frac{36}{35},\frac{6}{5},\frac{8}{35},\frac{8}{5}\right).\) Since all of these coordinates are nonnegative, we conclude that the optimal solution to the Unsimplified Problem lies on this face for this value of \(N\).

Example 2b We continue the Macaulay2 session started above and compute the KKT matrix for the same semigroup, \(N\), and face \(I\), but for the Simplified Problem. The left hand side of the matrix equation is the same as before; only the right hand side changes. 

i5 : -- Example 2b
     avector(3,{2,3},Simp=>true)

o5 = {2, 3, 2, 2}

o5 : List

i6 : KKTsolutionVector(3,{2,3},{},Simp=>true)

      22  2   1  11
o6 = {--, -, --, --}
      35  5  35   5

o6 : List
Thus, the KKT matrix equation for this face is \[ \left[\begin{array}{rrrr} -1 & 0 & 8 & 2 \\ 3 & -1 & 4 & 2 \\ -2 & 2 & 2& 2 \\ -0 & -1 & 0 & 2 \\ \end{array} \right] \left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = \left[ \begin{array}{r} 4\\ 6\\ 4 \\ 4 \end{array} \right] \] and it has solution \(x = \left(\frac{22}{35},\frac{2}{5},\frac{1}{35},\frac{11}{5}\right).\) Since all of these coordinates are nonnegative, we conclude that the optimal solution to the Simplified Problem lies on this face for this value of \(N\).

Example 2c We compute the KKT matrix for the semigroup \( \langle 4,9 \rangle\) with \(N=14\) and \(I = \{7,8,10\}\), and the Simplified Problem. 

i7 : -- Example 2c
     KKTmatrix(14,{4,9},{7,10})

o7 = | -4 0  0  0  0  0  34 0  0  42 0  0  0  52 2 |
     | 8  -1 0  0  0  0  26 0  0  34 0  0  0  44 2 |
     | -4 5  -3 0  0  0  18 0  0  26 0  0  0  36 2 |
     | 0  -4 4  -1 0  0  16 0  0  24 0  0  0  34 2 |
     | 0  0  -1 4  -3 0  10 0  0  18 0  0  0  28 2 |
     | 0  0  0  -3 4  -1 8  0  0  16 0  0  0  26 2 |
     | 0  0  0  0  -1 4  2  0  0  10 0  0  0  20 2 |
     | 0  0  0  0  0  -3 0  -2 0  8  0  0  0  18 2 |
     | 0  0  0  0  0  0  0  3  -1 6  0  0  0  16 2 |
     | 0  0  0  0  0  0  0  -1 3  2  0  0  0  12 2 |
     | 0  0  0  0  0  0  0  0  -2 0  -2 0  0  10 2 |
     | 0  0  0  0  0  0  0  0  0  0  3  -1 0  8  2 |
     | 0  0  0  0  0  0  0  0  0  0  -1 3  -1 4  2 |
     | 0  0  0  0  0  0  0  0  0  0  0  -2 2  2  2 |
     | 0  0  0  0  0  0  0  0  0  0  0  0  -1 0  2 |

              15       15
o7 : Matrix QQ   <-- QQ

i8 : avector(14,{4,9},Simp=>true)

o8 = {4, 8, 5, 4, 4, 4, 4, 2, 3, 3, 2, 3, 3, 2, 2}

o8 : List

i9 : KKTsolutionVector(14,{4,9},{7,10},Simp=>true)

      205561  280694  54604  663836  193490   81040   3353    160    4686   1442  17890  24552 
o9 = {------, ------, -----, ------, ------, ------, ------, -----, -----, -----, -----, -----,
      204306  102153  18027  306459  102153  102153  102153  34051  34051  34051  34051  34051 
     --------------------------------------------------------------------------------------------
     14312   3084  75258
     -----, -----, -----}
     34051  34051  34051
Thus, the KKT matrix equation for this face is \[ \left[\begin{array}{rrrrrrrrrrrrrrr} -4 & 0 & 0 & 0 & 0 & 0 & 34 & 0 & 0 & 42 & 0 & 0 & 0 & 52 & 2\\ 8 & -1 & 0 & 0 & 0 & 0 & 26 & 0 & 0 & 34 & 0 & 0 & 0 & 44 & 2\\ -4 & 5 & -3 & 0 & 0 & 0 & 18 & 0 & 0 & 26 & 0 & 0 & 0 & 36 & 2\\ 0 & -4 & 4 & -1 & 0 & 0 & 16 & 0 & 0 & 24 & 0 & 0 & 0 & 34 & 2\\ 0 & 0 & -1 & 4 & -3 & 0 & 10 & 0 & 0 & 18 & 0 & 0 & 0 & 28 & 2\\ 0 & 0 & 0 & -3 & 4 & -1 & 8 & 0 & 0 & 16 & 0 & 0 & 0 & 26 & 2\\ 0 & 0 & 0 & 0 & -1 & 4 & 2 & 0 & 0 & 10 & 0 & 0 & 0 & 20 & 2\\ 0 & 0 & 0 & 0 & 0 & -3 & 0 & -2 & 0 & 8 & 0 & 0 & 0 & 18 & 2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & -1 & 6 & 0 & 0 & 0 & 16 & 2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 3 & 2 & 0 & 0 & 0 & 12 & 2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 & 0 & -2 & 0 & 0 & 10 & 2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & -1 & 0 & 8 & 2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 3 & -1 & 4 & 2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 & 2 & 2 & 2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 2 \end{array} \right] \left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ x_8 \\ x_9 \\ x_{10} \\ x_{11} \\ x_{12} \\ x_{13} \\ x_{14} \\ x_{15} \end{array} \right] = \left[ \begin{array}{r} 4\\ 8\\ 5\\ 4\\ 4\\ 4\\ 4\\ 2\\ 3\\ 3\\ 2\\ 3\\ 3\\ 2\\ 2 \end{array} \right] \] Here, the coordinates \(x_7\), \(x_8\), and \(x_{10}\) correspond to parameters on this face of the cone \(W\), while the remaining coordinates are KKT multipliers. Since \(x_7\), \(x_8\), and \(x_{10}\) are positive, and the remaining coordinates of \(x\) are nonnegative, we conclude that optimal solution to the Simplified Problem lies on this face for this value of \(N\), and on no smaller face.