<commit_before>\documentclass[11pt]{article}
\usepackage{amsfonts,amssymb,amsthm,eucal,amsmath}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage{latexsym,url}
\usepackage{array}
\usepackage{subfig}
\usepackage{comment}
\usepackage{color}
\usepackage{tikz}
\usepackage{cprotect}
\usepackage{hyperref}
\usepackage[nameinlink,noabbrev]{cleveref}

\hypersetup{colorlinks=true,linkcolor=blue}
\newcommand{\myspace}{\vspace{.1in}\noindent}
\newcommand{\mymyspace}{\vspace{.1in}}
\usepackage[inner=30mm, outer=30mm, textheight=225mm]{geometry}
\creflabelformat{equation}{#2(#1)#3}
\crefname{equation}{}{}
\Crefname{equation}{}{}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{notn}[theorem]{Notation}
\newtheorem{cond}[theorem]{Condition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{rmk}[theorem]{Remark}
\newcommand{\co}{\negthinspace :}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\CP}{\mathbb{CP}}
\newcommand{\PSL}{\mathrm{PSL}_2(\mathbb{C})}
\newcommand{\area}{\operatorname{area}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\nt}{\negthinspace}
\newcommand{\TODO}{{\color{red} TODO}}

\title{A linear time direct solver for convex tridiagonal quadratic programs with bound constraints}
\author{<NAME>\thanks{Email: \{<EMAIL>.com, Otherlab, San Francisco, CA, United States}
\and <NAME>$^*$
\and <NAME>$^*$}
\date{Version 1, \today}

\begin{document}
\maketitle

\begin{abstract}
We present a linear time direct solver for symmetric positive definite tridiagonal quadratic programming with bound constraints.  Our algorithm is similar in structure to the
algorithm for linear time shortest paths in triangulated simple polygons by Lee and Preparata.  The algorithm is generalizable to other nonlinear convex programs of similar
structure, though we do not know of any such examples.
\end{abstract}

\section{Background}

Consider a symmetric positive definite tridiagonal quadratic program with bound constraints
\begin{align} \label{qp}
\begin{array}{cc}
\min          \qquad& \frac{1}{2} x^T A x + b^T x \\
\textrm{s.t.} & l \le x \le u
\end{array}
\end{align}
where $x,l,u \in \R^n$ and $A \in \R^{n \times n}$ is symmetric positive definite tridiagonal.  The problem is feasible iff $l \le u$, and can be solved efficiently using an interior point method (see \cite{gondzio2012interior}
for a survey).  Each Newton iteration requires an $O(n)$ tridiagonal direct solve; since interior point methods typically take between $O(1)$ and $O(\log n)$ iterations to converge \cite{colombo2008further}
this results in a quite fast method overall.  However, this peformance is not guaranteed, and any iterative method will require more iterations if greater accuracy is required.

In this paper, we present a linear time direct solver specialized for \cref{qp}.  We discovered this algorithm by accident: we intended to derive an linear time algorithm
for shortest paths (geodesics) in triangle strips immersed in three dimensions, but mistakenly wrote down a sum of squared lengths instead of the correct sum of unsquared lengths.  We then arrived at a linear time algorithm
using geometric intuition before realizing that our motivating problem was not a quadratic program after all.  In fact, essentially the same algorithm works in both cases, although an extra data structure is required
for quadratic programming.  The shortest path case is due to Lee and Preparata \cite{lee1984euclidean}, but to our knowledge its application to quadratic programming is unpublished.

We review the geometric case first.  Consider a sequence of segments $p_i q_i$ with $p_i, q_i \in \R^2$ for $i = 0, \ldots, n$, forming a quadrilateral strip.  Place an interpolated point
$r_i = (1-t_i) p_i + t_i q_i$ on each segment, where $0 \le t_i \le 1$.  Assume that the first and last points are fixed, so that $p_0 = q_0$ and $p_n = q_n$, and that no two segments intersect.
We seek to minimize the total length
\begin{align*}
L &= \sum_{i=0}^{n-1} \left\| r_i - r_{i+1} \right\|.
\end{align*}
The algorithm proceeds from $k = 0$ to $k = n-1$, where stage $k$ minimizes the length up to $r_k$ for the two extreme values $r_k = p_k, q_k$.  Since segments do not intersect, the optimal value
of $t_i$ for $i < k$ is a monotonic function of $x_k$, so the optimal path for any intermediate value $0 < t_k < 1$ lies between the optimal paths for $t_k = 0,1$.  Thus, our intermediate state has the form shown in
\cref{kite}: the two paths stay together for a certain distance, then curve apart in opposite directions.  Moving from $k$ to $k+1$ consists of adding new edges to each path, then eroding until
we restore convexity.  To determine whether to remove a vertex at index $j$ between $i$ and $k$, we compute a shortest path between $r_i$ and $r_k$ and compare it to the bounds on $r_j$, which takes $O(1)$ time.
For full details, see \cite{lee1984euclidean}.

\begin{figure}
\begin{center}
\begin{tikzpicture}[thick,line join=round,line cap=round,scale=.7]
  \draw (-6,.1) node[left]{$r_0$} -- (-4.5,1) -- (-3,-.2)  -- (-1.5,.7) -- (0,0) node[above]{$r_j$}; % shared
  \draw (0,0) -- (1.8,.6) -- (3.3,1.6) -- (4.2,3.5) node[right]{$p_k$};      % upper
  \draw (0,0) -- (1.5,-.4) -- (3,-1.6) -- (4.2,-3.5) node[right]{$q_k$};     % lower<commit_msg>Slight wording change<commit_after>\documentclass[11pt]{article}
\usepackage{amsfonts,amssymb,amsthm,eucal,amsmath}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage{latexsym,url}
\usepackage{array}
\usepackage{subfig}
\usepackage{comment}
\usepackage{color}
\usepackage{tikz}
\usepackage{cprotect}
\usepackage{hyperref}
\usepackage[nameinlink,noabbrev]{cleveref}

\hypersetup{colorlinks=true,linkcolor=blue}
\newcommand{\myspace}{\vspace{.1in}\noindent}
\newcommand{\mymyspace}{\vspace{.1in}}
\usepackage[inner=30mm, outer=30mm, textheight=225mm]{geometry}
\creflabelformat{equation}{#2(#1)#3}
\crefname{equation}{}{}
\Crefname{equation}{}{}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{notn}[theorem]{Notation}
\newtheorem{cond}[theorem]{Condition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{rmk}[theorem]{Remark}
\newcommand{\co}{\negthinspace :}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\CP}{\mathbb{CP}}
\newcommand{\PSL}{\mathrm{PSL}_2(\mathbb{C})}
\newcommand{\area}{\operatorname{area}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\nt}{\negthinspace}
\newcommand{\TODO}{{\color{red} TODO}}

\title{A linear time direct solver for convex tridiagonal quadratic programs with bound constraints}
\author{<NAME>\thanks{Email: \{<EMAIL>,<EMAIL>, Otherlab, San Francisco, CA, United States}
\and <NAME>$^*$
\and <NAME>$^*$}
\date{Version 1, \today}

\begin{document}
\maketitle

\begin{abstract}
We present a linear time direct solver for symmetric positive definite tridiagonal quadratic programming with bound constraints.  Our algorithm is similar in structure to the
algorithm for linear time shortest paths in triangulated simple polygons by Lee and Preparata.  The algorithm is generalizable to other nonlinear convex programs of similar
structure, though we do not know of any such examples.
\end{abstract}

\section{Background}

Consider a symmetric positive definite tridiagonal quadratic program with bound constraints
\begin{align} \label{qp}
\begin{array}{cc}
\min          \qquad& \frac{1}{2} x^T A x + b^T x \\
\textrm{s.t.} & l \le x \le u
\end{array}
\end{align}
where $x,l,u \in \R^n$ and $A \in \R^{n \times n}$ is symmetric positive definite tridiagonal.  The problem is feasible iff $l \le u$, and can be solved efficiently using an interior point method (see \cite{gondzio2012interior}
for a survey).  Each Newton iteration requires an $O(n)$ tridiagonal direct solve; since interior point methods typically take between $O(1)$ and $O(\log n)$ iterations to converge \cite{colombo2008further}
this results in a quite fast method overall.  However, this peformance is not guaranteed, and any iterative method will require more iterations if greater accuracy is required.

In this paper, we present a linear time direct solver specialized for \cref{qp}.  We discovered this algorithm by accident: we intended to derive an linear time algorithm
for shortest paths (geodesics) in triangle strips immersed in three dimensions, but mistakenly wrote down a sum of squared lengths instead of the correct sum of unsquared lengths.  We then arrived at a linear time algorithm
using geometric intuition before realizing that our motivating problem was not a quadratic program after all.  In fact, essentially the same algorithm works in both cases, although an extra data structure is required
for quadratic programming.  The shortest path case is due to Lee and Preparata \cite{lee1984euclidean}, but to our knowledge its application to quadratic programming is unpublished.

We review the geometric case first.  Consider a sequence of segments $p_i q_i$ with $p_i, q_i \in \R^2$ for $i = 0, \ldots, n$, forming a quadrilateral strip.  Place an interpolated point
$r_i = (1-t_i) p_i + t_i q_i$ on each segment, where $0 \le t_i \le 1$.  Assume that the first and last points are fixed, so that $p_0 = q_0$ and $p_n = q_n$, and that each quadrilateral is convex.
We seek to minimize the total length
\begin{align*}
L &= \sum_{i=0}^{n-1} \left\| r_i - r_{i+1} \right\|.
\end{align*}
The algorithm proceeds from $k = 0$ to $k = n-1$, where stage $k$ minimizes the length up to $r_k$ for the two extreme values $r_k = p_k, q_k$.  Since segments do not intersect, the optimal value
of $t_i$ for $i < k$ is a monotonic function of $x_k$, so the optimal path for any intermediate value $0 < t_k < 1$ lies between the optimal paths for $t_k = 0,1$.  Thus, our intermediate state has the form shown in
\cref{kite}: the two paths stay together for a certain distance, then curve apart in opposite directions.  Moving from $k$ to $k+1$ consists of adding new edges to each path, then eroding until
we restore convexity.  To determine whether to remove a vertex at index $j$ between $i$ and $k$, we compute a shortest path between $r_i$ and $r_k$ and compare it to the bounds on $r_j$, which takes $O(1)$ time.
For full details, see \cite{lee1984euclidean}.

\begin{figure}
\begin{center}
\begin{tikzpicture}[thick,line join=round,line cap=round,scale=.7]
  \draw (-6,.1) node[left]{$r_0$} -- (-4.5,1) -- (-3,-.2)  -- (-1.5,.7) -- (0,0) node[above]{$r_j$}; % shared
  \draw (0,0) -- (1.8,.6) -- (3.3,1.6) -- (4.2,3.5) node[right]{$p_k$};      % upper
  \draw (0,0) -- (1.5,-.4) -- (3,-1.6) -- (4.2,-3.5) node[right]{$q_k$};     % lower
{'fraction_non_alphanumeric': 0.1302317062002015, 'fraction_numerical': 0.017034526971334372, 'mean_word_length': 4.960698689956332, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5726371', 'n_tokens_mistral': 3574, 'n_tokens_neox': 3366, 'n_words': 1267}