Prev | Next |

@(@\newcommand{\W}[1]{ \; #1 \; } \newcommand{\R}[1]{ {\rm #1} } \newcommand{\B}[1]{ {\bf #1} } \newcommand{\D}[2]{ \frac{\partial #1}{\partial #2} } \newcommand{\DD}[3]{ \frac{\partial^2 #1}{\partial #2 \partial #3} } \newcommand{\Dpow}[2]{ \frac{\partial^{#1}}{\partial {#2}^{#1}} } \newcommand{\dpow}[2]{ \frac{ {\rm d}^{#1}}{{\rm d}\, {#2}^{#1}} }@)@

*ok* = abs_min_quad(

*level*, *n*, *m*, *s*,

*g_hat*, *g_jac*, *hessian*, *bound*, *epsilon*, *maxitr*, *delta_x*

)

template<classDblVector,classSizeVector> boolabs_min_quad( size_t level , size_t n , size_t m , size_t s ,constDblVector& g_hat ,constDblVector& g_jac ,constDblVector& hessian ,constDblVector& bound ,constDblVector& epsilon ,constSizeVector& maxitr , DblVector& delta_x )

This following is a link to the source code for this example: abs_min_quad.hpp .

We are given a point @(@ \hat{x} \in \B{R}^n @)@ and use the notation @(@ \tilde{f} (x) @)@ for the abs-normal approximation for f(x) near @(@ \hat{x} @)@. We are also given a vector @(@ b \in \B{R}_+^n @)@ and a positive definite matrix @(@ H \in \B{R}^{n \times n} @)@. This routine solves the problem @[@ \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} @]@

is a SimpleVector class with elements of type

`double`

.
is a SimpleVector class with elements of type

`size_t`

.
We use the notation

*f*

for the original function; see
f
.
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 qp_box
sub-problem is printed.
If
*level* >= 3

,
a trace of the qp_interior
sub-problem is printed.
This is the dimension of the domain space for

*f*

; see
n
.
This is the dimension of the range space for

*f*

; see
m
. This must be one so that @(@
f
@)@
is an objective function.
This is the number of absolute value terms in

*f*

; see
s
.
We use the notation

*g*

for the abs-normal representation of
*f*

;
see g
.
This vector has size

*m* + *s*

and is the value of
*g(x, u)*

at @(@
x = \hat{x}
@)@ and @(@
u = a( \hat{x} )
@)@.
This vector has size

`(`*m* + *s*) * (*n* + *s*)

and is the Jacobian of
@(@
g(x, u)
@)@ at @(@
x = \hat{x}
@)@ and @(@
u = a( \hat{x} )
@)@.
This vector has size

*n* * *n*

.
It is a row-major
representation
of the matrix @(@
H \in \B{R}^{n \times n}
@)@.
This vector has size

*n*

and is the vector @(@
b \in \B{R}^n
@)@.
The trust region is defined as the set of @(@
\Delta x
@)@ such that
@[@
| \Delta x | \leq b_j
@]@
for @(@
j = 0 , \ldots , n-1
@)@.
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.
@[@
\Delta x^T H \Delta x / 2 + \tilde{f}( \hat{x} + \Delta x)
@]@
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 qp_interior
sub-problems.
This vector @(@ \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.
We use the notation @[@ \sigma (x) = \R{sign} ( z[ x , a(x) ] ) @]@ where a(x) and z(x, u) are as defined in the abs-normal representation of @(@ f(x) @)@.

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

At iteration @(@ k @)@, we solve the problem @[@ \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 @(@ x_K @)@ at which the new affine approximation @(@ p_K (x) @)@ is constructed. This process is iterated until the difference @(@ x_K - x_{K-1} @)@ is small enough.

The file abs_min_quad.cpp contains an example and test of

`abs_min_quad`

.
It returns true if the test passes and false otherwise.
Input File: example/abs_normal/abs_min_quad.hpp