----------------------------------------------------------
lines 8-203 of file: example/abs_normal/abs_min_linear.hpp
----------------------------------------------------------

{xrst_begin abs_min_linear}
{xrst_spell
   dbl
   lll
   maxitr
}
abs_normal: Minimize a Linear Abs-normal Approximation
######################################################

Syntax
******
| *ok* = ``abs_min_linear`` (
| |tab| *level* , *n* , *m* , *s* ,
| |tab| *g_hat* , *g_jac* , *bound* , *epsilon* , *maxitr* , *delta_x*
| )

Prototype
*********
{xrst_literal
   // BEGIN PROTOTYPE
   // END PROTOTYPE
}

Source
******
This following is a link to the source code for this example:
:ref:`abs_min_linear.hpp-name` .

Purpose
*******
We are given a point :math:`\hat{x} \in \B{R}^n` and
use the notation :math:`\tilde{f} (x)` for the abs-normal
:ref:`approximation for f(x)<abs_normal_fun@Abs-normal Approximation@Approximating f(x)>`
near :math:`\hat{x}`.
We are also given a vector :math:`b \in \B{R}_+^n`.
This routine solves the problem

.. math::

   \begin{array}{lll}
   \R{minimize} & \tilde{f}(x) & \R{w.r.t} \; x \in \B{R}^n
   \\
   \R{subject \; to} & | x_j - \hat{x}_j | \leq b_j & j = 0 , \ldots , n-1
   \end{array}

DblVector
*********
is a :ref:`SimpleVector-name` class with elements of type ``double`` .

SizeVector
**********
is a :ref:`SimpleVector-name` class with elements of type ``size_t`` .

f
*
We use the notation *f* for the original function; see
:ref:`abs_normal_fun@f` .

level
*****
This value is less that or equal 4.
If *level*  == 0 ,
no tracing of the optimization is printed.
If *level*  >= 1 ,
a trace of each iteration of ``abs_min_linear`` is printed.
If *level*  >= 2 ,
a trace of the :ref:`lp_box-name` sub-problem is printed.
If *level*  >= 3 ,
a trace of the objective and primal variables :math:`x` are printed
at each :ref:`simplex_method-name` iteration.
If *level*  == 4 ,
the simplex tableau is printed at each simplex iteration.

n
*
This is the dimension of the domain space for *f* ; see
:ref:`abs_normal_fun@f@n` .

m
*
This is the dimension of the range space for *f* ; see
:ref:`abs_normal_fun@f@m` . This must be one so that :math:`f`
is an objective function.

s
*
This is the number of absolute value terms in *f* ; see
:ref:`abs_normal_fun@f@s` .

g
*
We use the notation *g* for the abs-normal representation of *f* ;
see :ref:`abs_normal_fun@g` .

g_hat
*****
This vector has size *m* + *s* and is the value of
*g* ( *x* , *u* ) at :math:`x = \hat{x}` and :math:`u = a( \hat{x} )`.

g_jac
*****
This vector has size ( *m* + *s* ) * ( *n* + *s* ) and is the Jacobian of
:math:`g(x, u)` at :math:`x = \hat{x}` and :math:`u = a( \hat{x} )`.

bound
*****
This vector has size *n*
and we denote its value by :math:`b \in \B{R}^n`.
The trust region is defined as the set of :math:`x` such that

.. math::

   | x_j - \hat{x}_j | \leq b_j

for :math:`j = 0 , \ldots , n-1`,
where :math:`x` is the point that we are approximating :math:`f(x)`.

epsilon
*******
The value *epsilon* [0] is convergence criteria in terms
of the infinity norm of the difference of *delta_x*
between iterations.
The value *epsilon* [1] is convergence criteria in terms
of the derivative of the objective; i.e., :math:`\tilde{f}(x)`.

maxitr
******
This is a vector with size 2.
The value *maxitr* [0] is the maximum number of
``abs_min_linear`` iterations to try before giving up on convergence.
The value *maxitr* [1] is the maximum number of iterations in
the :ref:`simplex_method<simplex_method@maxitr>` sub-problems.

delta_x
*******
This vector :math:`\Delta x` has size *n* .
The input value of its elements does not matter.
Upon return,
the approximate minimizer of :math:`\tilde{f}(x)`
with respect to the trust region
is :math:`x = \hat{x} + \Delta x`.

Method
******

sigma
=====
We use the notation

.. math::

   \sigma (x) = \R{sign} ( z[ x , a(x) ] )

where
:ref:`abs_normal_fun@a@a(x)` and
:ref:`abs_normal_fun@g@z(x, u)`
are as defined in the abs-normal representation of :math:`f(x)`.

Cutting Planes
==============
At each iteration,
we are given affine functions :math:`p_k (x)`
such that :math:`p_k ( x_k ) = \tilde{f}( x_k )`  and
:math:`p_k^{(1)} ( x_k )` is the derivative
:math:`\tilde{f}^{(1)} ( x_k )`
corresponding to :math:`\sigma ( x_k )`.

Iteration
=========
At iteration :math:`k`, we solve the problem

.. math::

   \begin{array}{lll}
   \R{minimize}
      & \max \{ p_k (x) \W{:} k = 0 , \ldots , K-1 \}
      & \R{w.r.t} \; x
   \\
   \R{subject \; to} & - b \leq x \leq + b
   \end{array}

The solution is the new point :math:`x_K`
at which the new affine approximation
:math:`p_K (x)` is constructed.
This process is iterated until the difference
:math:`x_K - x_{K-1}` is small enough.
{xrst_toc_hidden
   example/abs_normal/abs_min_linear.cpp
   example/abs_normal/abs_min_linear.xrst
}
Example
*******
The file :ref:`abs_min_linear.cpp-name` contains an example and test of
``abs_min_linear`` .

{xrst_end abs_min_linear}