lines 8-214 of file: example/abs_normal/abs_min_quad.hpp

{xrst_begin abs_min_quad}
{xrst_spell
   affine
   dbl
   iterated
   lll
   maxitr
   minimizer
   qp
}
abs_normal: Minimize a Linear Abs-normal Approximation
######################################################

Syntax
******

| *ok* = ``abs_min_quad`` (
| |tab| *level* , *n* , *m* , *s* ,
| |tab| *g_hat* , *g_jac* , *hessian* , *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_quad.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`
and a positive definite matrix :math:`H \in \B{R}^{n \times n}`.
This routine solves the problem

.. math::

   \begin{array}{lll}
   \R{minimize} &
      \Delta x^T H \Delta x / 2 + \tilde{f}( \hat{x} + \Delta x ) &
      \R{w.r.t} \; \Delta x \in \B{R}^n
   \\
   \R{subject \; to} & | \Delta 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 3.
If *level*  == 0 ,
no tracing of the optimization is printed.
If *level*  >= 1 ,
a trace of each iteration of ``abs_min_quad`` is printed.
If *level*  >= 2 ,
a trace of the :ref:`qp_box-name` sub-problem is printed.
If *level*  >= 3 ,
a trace of the :ref:`qp_interior-name` sub-problem is printed.

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} )`.

hessian
*******
This vector has size *n* * *n* .
It is a :ref:`row-major<glossary@Row-major Representation>` representation
of the matrix :math:`H \in \B{R}^{n \times n}`.

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

.. math::

   | \Delta x | \leq b_j

for :math:`j = 0 , \ldots , n-1`.

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::

   \Delta x^T H \Delta x / 2 + \tilde{f}( \hat{x} + \Delta x)

maxitr
******
This is a vector with size 2.
The value *maxitr* [0] is the maximum number of
``abs_min_quad`` iterations to try before giving up on convergence.
The value *maxitr* [1] is the maximum number of iterations in
the :ref:`qp_interior<qp_interior@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 the objective with respect to the trust region.

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}
   & \Delta x^T H \Delta x / 2 +
      \max \{ p_k ( \hat{x} + \Delta x) \W{:} k = 0 , \ldots , K-1 \}
   & \R{w.r.t} \; \Delta x
   \\
   \R{subject \; to} & - b \leq \Delta 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_quad.cpp
   example/abs_normal/abs_min_quad.xrst
}
Example
*******
The file :ref:`abs_min_quad.cpp-name` contains an example and test of
``abs_min_quad`` .

{xrst_end abs_min_quad}
