\begin{algorithm}\label{mainalgorithm} (See Algorithm 5.1 of \cite{Potra})
Given $\beta_1 < \beta_2$ with $\beta_2^2/(2(1-\beta_2)^2) \leq
\beta_1 < \beta_2 < \beta_2/(1-\beta_2) < 1$.  Choose $(X_0,y_0,Y_0,
\tau_0,\kappa_0) \in \mathcal{N}(\beta_1, \mu_0)$ with $(n+1) \mu_0
= {\rm{Tr}}(X_0 Y_0) + \tau_0 \kappa_0$. For $k = 0, 1, \ldots$,
{\textcolor{black}{perform}} ($a1$) through ($a5$):
\begin{description}
\item[\hspace{5pt} ($a1$)] Set $X = X_k$, $y = y_k$, $Y = Y_k$, $\tau =
\tau_k$, $\kappa = \kappa_k$, and define
\begin{eqnarray*}
r_i & := & {\rm{Tr}}(A_i X) - b_i \tau, \quad i = 1, \ldots, m, \\
s & := & \sum_{i=1}^m y_i A_i + Y, \\
\gamma & := & \kappa - b^T y.
\end{eqnarray*}
\item[\hspace{5pt} ($a2$)] If $\max \{({\rm{Tr}}(XY) + \tau
\kappa)/\tau^2 , | r_1/\tau |, \ldots, | r_m /\tau |, \| s/\tau \|  \} \leq \epsilon$, then
report $(X/\tau, y/\tau, Y/\tau)$ as an approximate solution to the LSDFP, and terminate.
If $\tau$ is sufficiently small, terminate with no optimal solutions
to the LSDFP.
\item[\hspace{5pt} ($a3$)] {\bf{[Predictor Step]}} Find the solution $(\Delta X_p,\Delta y_p, \Delta Y_p,\Delta \tau_p,
\Delta \kappa_p)$ of the linear system (\ref{sys1})-(\ref{sys5}), with
$\sigma = 0$, $\overline{r}_i = r_i, i = 1, \ldots, m$, $\overline{s} = s$ and $\overline{\gamma} = \gamma$. \newline
Define
\begin{eqnarray*}
\overline{X} = X + \overline{\alpha} \Delta X_p,\ \ \overline{y} = y + \overline{\alpha} \Delta y_p, \ \ \overline{Y} = Y +
\overline{\alpha} \Delta Y_p,\ \  \overline{\tau} = \tau +
\overline{\alpha}\Delta \tau_p,\ \ \overline{\kappa} = \kappa +
\overline{\alpha}\Delta \kappa_p,
\end{eqnarray*}
\noindent where the {\textcolor{black}{step length}} $\overline{\alpha}$ satisfies
\begin{eqnarray}\label{steplengthinequality}
\alpha_1 \leq \overline{\alpha} \leq \alpha_2.
\end{eqnarray}
Here,
\begin{eqnarray}
\alpha_1 & = & \frac{2}{\sqrt{1 + 4 \delta/(\beta_2 - \beta_1)} +1},
\label{steplengthinequality1}\\
\delta & = & \frac{1}{\mu} \left\| \left[ \begin{array}{cc}
                                                Y & 0 \\
                                                0 & \kappa
                                            \end{array}\right]^{1/2}
\left[ \begin{array}{cc}
            \Delta X_p & 0  \\
            0 & \Delta \tau_p
        \end{array} \right]
\left[ \begin{array}{cc}
          \Delta Y_p   & 0 \\
            0 & \Delta \kappa_p 
        \end{array} \right]
\left[ \begin{array}{cc}
           Y    & 0 \\
            0 & \kappa 
        \end{array} \right]^{-1/2} \right\|_F,
        \label{steplengthinequality2}
\end{eqnarray}
where 
\begin{eqnarray*}
\mu = \frac{{\rm{Tr}}(XY) + \tau \kappa}{n + 1},
\end{eqnarray*}
and
\begin{eqnarray*}
& & \alpha_2 = \max \{ \tilde{\alpha} \in [0,1] \ ; \ (X+ \alpha \Delta X_p, y + \alpha \Delta y_p,  Y +
\alpha \Delta Y_p, \tau + \alpha \Delta \tau_p, \kappa + \alpha \Delta \kappa_p)
\\ 
& & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \in \mathcal{N}(\beta_2,(1-\alpha)\mu)\ \forall\ \alpha \in
[0,\tilde{\alpha}]\}.
\end{eqnarray*}
\item[\hspace{5pt} ($a4$)] {\bf{[Corrector Step]}} Find the solution $(\Delta X_c, \Delta y_c, \Delta Y_c, \Delta \tau_c, \Delta \kappa_c)$ of the
linear system (\ref{sys1})-(\ref{sys5}), with $\sigma = 1 -
\overline{\alpha}$, $\overline{r}_i = 0, i = 1, \ldots, m$, $\overline{s} = 0$ and $\overline{\gamma} = 0$.  Set
\begin{eqnarray*}
\begin{array}{c}
X_+ = \overline{X} + \Delta X_c,\ \ y_+ = \overline{y} + \Delta y_c,\ \ Y_+ = \overline{Y} + \Delta Y_c, \ \ \tau_+ =
\overline{\tau} + \Delta \tau_c,\ \ \kappa_+ = \overline{\kappa} +
\Delta \kappa_c, \\
\mu_+ = (1 - \overline{\alpha})\mu.
\end{array}
\end{eqnarray*}
\item[\hspace{5pt} ($a5$)] Set
\begin{eqnarray*}
\begin{array}{c}
X_{k+1} = X_+,\ \ y_{k+1} = y_+, \ \ Y_{k+1} = Y_+, \ \ \tau_{k+1} = \tau_+, \ \
\kappa_{k+1} = \kappa_+,\\
\mu_{k+1} = \mu_+.
\end{array}
\end{eqnarray*}
\end{description}
\end{algorithm}

\begin{algorithm}
(See Algorithm 5.1 of \cite{Potra})
Given $\beta_1 < \beta_2$ with $\beta_2^2/(2(1-\beta_2)^2) \leq
\beta_1 < \beta_2 < \beta_2/(1-\beta_2) < 1$. Choose $(X_0,y_0,Y_0,
\tau_0,\kappa_0) \in \mathcal{N}(\beta_1, \mu_0)$ with $(n+1) \mu_0
= {\rm{Tr}}(X_0 Y_0) + \tau_0 \kappa_0$. For $k = 0, 1, \ldots$,
{\textcolor{black}{perform}} ($a1$) through ($a5$):
\begin{description}
\item[\hspace{5pt} ($a1$)] Set $X = X_k$, $y = y_k$, $Y = Y_k$, $\tau =
\tau_k$, $\kappa = \kappa_k$, and define
\begin{eqnarray*}
r_i & := & {\rm{Tr}}(A_i X) - b_i \tau, \quad i = 1, \ldots, m, \\
s & := & \sum_{i=1}^m y_i A_i + Y, \\
\gamma & := & \kappa - b^T y.
\end{eqnarray*}
\item[\hspace{5pt} ($a2$)] If $\max \{({\rm{Tr}}(XY) + \tau
\kappa)/\tau^2 , | r_1/\tau |, \ldots, | r_m /\tau |, \| s/\tau \| \} \leq \epsilon$, then
report $(X/\tau, y/\tau, Y/\tau)$ as an approximate solution to the LSDFP, and terminate.
If $\tau$ is sufficiently small, terminate with no optimal solutions
to the LSDFP.
\item[\hspace{5pt} ($a3$)] {\bf{[Predictor Step]}} Find the solution $(\Delta X_p,\Delta y_p, \Delta Y_p,\Delta \tau_p,
\Delta \kappa_p)$ of the linear system (\ref{sys1})-(\ref{sys5}), with
$\sigma = 0$, $\overline{r}_i = r_i, i = 1, \ldots, m$, $\overline{s} = s$ and $\overline{\gamma} = \gamma$. \newline
Define
\begin{eqnarray*}
\overline{X} = X + \overline{\alpha} \Delta X_p,\ \ \overline{y} = y + \overline{\alpha} \Delta y_p, \ \ \overline{Y} = Y +
\overline{\alpha} \Delta Y_p,\ \ \overline{\tau} = \tau +
\overline{\alpha}\Delta \tau_p,\ \ \overline{\kappa} = \kappa +
\overline{\alpha}\Delta \kappa_p,
\end{eqnarray*}
\noindent where the {\textcolor{black}{step length}} $\overline{\alpha}$ satisfies
\begin{eqnarray*}
\alpha_1 \leq \overline{\alpha} \leq \alpha_2.
\end{eqnarray*}
Here,
\begin{eqnarray*}
\alpha_1 & = & \frac{2}{\sqrt{1 + 4 \delta/(\beta_2 - \beta_1)} +1},
\\
\delta & = & \frac{1}{\mu} \left\| \left[ \begin{array}
{cc}
Y & 0 \\
0 & \kappa
\end{array}\right]^{1/2}
\left[ \begin{array}
{cc}
\Delta X_p & 0 \\
0 & \Delta \tau_p
\end{array} \right]
\left[ \begin{array}
{cc}
\Delta Y_p & 0 \\
0 & \Delta \kappa_p
\end{array} \right]
\left[ \begin{array}
{cc}
Y & 0 \\
0 & \kappa
\end{array} \right]^{-1/2} \right\|_F,
\end{eqnarray*}
where
\begin{eqnarray*}
\mu = \frac{{\rm{Tr}}(XY) + \tau \kappa}{n + 1},
\end{eqnarray*}
and
\begin{eqnarray*}
& & \alpha_2 = \max \{ \tilde{\alpha} \in [0,1] \ ; \ (X+ \alpha \Delta X_p, y + \alpha \Delta y_p, Y +
\alpha \Delta Y_p, \tau + \alpha \Delta \tau_p, \kappa + \alpha \Delta \kappa_p)
\\
& & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \in \mathcal{N}(\beta_2,(1-\alpha)\mu)\ \forall\ \alpha \in
[0,\tilde{\alpha}]\}.
\end{eqnarray*}
\item[\hspace{5pt} ($a4$)] {\bf{[Corrector Step]}} Find the solution $(\Delta X_c, \Delta y_c, \Delta Y_c, \Delta \tau_c, \Delta \kappa_c)$ of the
linear system (\ref{sys1})-(\ref{sys5}), with $\sigma = 1 -
\overline{\alpha}$, $\overline{r}_i = 0, i = 1, \ldots, m$, $\overline{s} = 0$ and $\overline{\gamma} = 0$. Set
\begin{eqnarray*}
\begin{array}
{c}
X_+ = \overline{X} + \Delta X_c,\ \ y_+ = \overline{y} + \Delta y_c,\ \ Y_+ = \overline{Y} + \Delta Y_c, \ \ \tau_+ =
\overline{\tau} + \Delta \tau_c,\ \ \kappa_+ = \overline{\kappa} +
\Delta \kappa_c, \\
\mu_+ = (1 - \overline{\alpha})\mu.
\end{array}
\end{eqnarray*}
\item[\hspace{5pt} ($a5$)] Set
\begin{eqnarray*}
\begin{array}
{c}
X_{k+1} = X_+,\ \ y_{k+1} = y_+, \ \ Y_{k+1} = Y_+, \ \ \tau_{k+1} = \tau_+, \ \
\kappa_{k+1} = \kappa_+,\\
\mu_{k+1} = \mu_+.
\end{array}
\end{eqnarray*}
\end{description}
\end{algorithm}
{
    "title": "superlinear convergence of an interior point algorithm on linear   semi-definite feasibility problems with application to linear matrix   inequalities",
    "id": "2211.08215",
    "abstract": "in the literature, besides the assumption of strict complementarity, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the hkm direction, its dual or the nt direction, to solve semi-definite programs (sdps) is shown by (i) assuming that the given sdp is nondegenerate and making modifications to these algorithms [10], or (ii) considering special classes of sdps, such as the class of linear semi-definite feasibility problems (lsdfps) and requiring the initial iterate to the algorithm to satisfy certain conditions [26, 27]. otherwise, these algorithms are not easy to implement even though they are shown to have polynomial iteration complexities and superlinear convergence [14]. the conditions in [26, 27] that the initial iterate to the algorithm is required to satisfy to have superlinear convergence when solving lsdfps however are not practical. in this paper, we propose a practical initial iterate to an implementable infeasible interior point algorithm that guarantees superlinear convergence when the algorithm is used to solve the homogeneous feasibility model of an lsdfp.",
    "categories": "math.oc",
    "doi": "",
    "created": "2022-11-15",
    "updated": "2024-01-12",
    "authors": [
        "chee-khian sim"
    ],
    "affiliation": [],
    "url": "https://arxiv.org/abs/2211.08215"
}
{
    "ToxicityFilter": {
        "text_to_toxicity_attributes": {
            "Reference_Sim.bib": {
                "toxicity_score": 0.012503231,
                "severe_toxicity_score": 0.0015163422,
                "identity_attack_score": 0.0015169121,
                "insult_score": 0.0081208795,
                "profanity_score": 0.02030538,
                "threat_score": 0.0063950317,
                "sexually_explicit_score": 0.015452018,
                "flirtation_score": 0.45581096
            },
            "LMI_Interior_Point_Superlinear_Preprint.bbl": {
                "toxicity_score": 0.030388435,
                "severe_toxicity_score": 0.0026512146,
                "identity_attack_score": 0.0030338243,
                "insult_score": 0.0116169015,
                "profanity_score": 0.029888187,
                "threat_score": 0.008362788,
                "sexually_explicit_score": 0.02665768,
                "flirtation_score": 0.3085165
            },
            "LMI_Interior_Point_Superlinear_Preprint.tex": {
                "toxicity_score": 0.01218908,
                "severe_toxicity_score": 0.0011634827,
                "identity_attack_score": 0.0037367835,
                "insult_score": 0.007664877,
                "profanity_score": 0.015454767,
                "threat_score": 0.007586042,
                "sexually_explicit_score": 0.01250316,
                "flirtation_score": 0.21971871
            }
        },
        "reason": null
    }
}
{
    "num_done": {
        "figure": 0,
        "algorithm": 2
    }
}
{
    "NonTrivialRenderingFilter": {
        "white_pixels_ratio": 95.05148933594356,
        "hash": "03ef0101ff9fefef",
        "most_frequent_color_ratio": 95.05148933594356
    }
}