Generalized-norm conjugate direction solver

Norm Options

Our solver framework allows easy interchangeability between several norms. Although the code allows easy switching of the optimization measure, we recommend a thorough understanding of the theoretical and numerical caveats that result from the application of each solver criterion.

Norm		Description
L2		Conventional $L_2$ norm, utilizing the new solver framework
L1		$L_1$ norm with discontinuous $1^{st}$ and $2^{nd}$ order derivatives
Huber		Huber $L_1$/$L_2$ norm with with $1^{st}$ order derivative continuity
Hybrid		$L_1$/$L_2$ hybrid norm with $1^{st}$ and $2^{nd}$ order derivative continuity

The equations below summarize the analytical formulation for the listed norms above. $C, C', {\text and} C''$ represent the norm function, its first-order derivative and its second-order derivative, respectively. Figure 1 shows these norm functions along with their derivatives. Note discontinuous derivatives and zero-valued curvatures in some cases. These analytical forms are used in the Taylor series expansion for the adapted conjugate-direction plane-search.

L2 (Least Squares):

$$C( r ) = r^2/2 \notag$$ (1)

$$C' (r) = r$$ (2)

$$C'' (r) = 1 \notag$$ (3)

L1:

$$C( r ) = \vert r \vert \notag$$ (4)

$$C' (r) = {\rm sgn}(r)$$ (5)

$$C'' (r) = \quad \infty \notag$$ (6)

Huber:

$$C( r ) = \begin{cases} \vert r\vert-\vert r_t\vert/2 \quad\quad &\vert... ...{2 r_t} \quad \quad &\vert{r}/{r_t}\vert < 1 \end{cases} \notag$$ (7)

$$C' (r) = \begin{cases} {\rm sgn} ({r}/{r_t} ) \quad& \vert{r}/{r_t}\vert \ge 1 \\ {r}/{r_t} \quad &\vert{r}/{r_t}\vert < 1 \end{cases}$$ (8)

$$C'' (r) = \begin{cases} 0 \quad\quad &\vert{r}/{r_t}\vert \ge 1 \\ {1}/{r_t} \quad\quad &\vert{r}/{r_t}\vert < 1 \end{cases} \notag$$ (9)

Hybrid:

$$C( r ) = r_t^2 \left ( \sqrt{ 1+ {r^2}/{r_t^2} } -1 \right ) \notag$$ (10)

$$C' (r) = \frac{r}{\sqrt{1+ {r^2}/{r_t^2}}}$$ (11)

$$C'' (r) = \frac{1}{(1+ {r^2}/{r_t^2})^{\frac{3}{2} } } \notag$$ (12)

l2-norm,l1-norm,huber-norm,hybrid-norm
Figure 1. Norm functions and their first and second derivatives plotted for $r=-250,250$ interval, with $r_t=100$ where applicable. Rows from top to bottom are representing (a)$L_2$, (b) $L_1$, (c) Huber, and (d) Hybrid. Columns from left to right are representing norm function, first-order derivative, second-order derivative. [ER]

The choice of norm is specified as an input argument to our solver. A further benefit of this implementation is that other norms can be added with minimal modification to the overall solver framework. To add a new norm, all that is necessary is adding the appropriate definition of the norm and its derivatives in the code.

Generalized-norm conjugate direction solver