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}} }@)@This is cppad-20221105 documentation. Here is a link to its current documentation .
abs_normal: Minimize a Linear Abs-normal Approximation

Syntax
ok = abs_min_quad(
    level, n, m, s,
    g_hat, g_jac, hessian, bound, epsilon, maxitr, delta_x
)

Prototype 

template <class DblVector, class SizeVector>
bool abs_min_quad(
    size_t            level   ,
    size_t            n       ,
    size_t            m       ,
    size_t            s       ,
    const DblVector&  g_hat   ,
    const DblVector&  g_jac   ,
    const DblVector&  hessian ,
    const DblVector&  bound   ,
    const DblVector&  epsilon ,
    const SizeVector& maxitr  ,
    DblVector&        delta_x )

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

Purpose
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} @]@

DblVector
is a SimpleVector class with elements of type double.

SizeVector
is a SimpleVector class with elements of type size_t.

f
We use the notation f for the original function; see 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 qp_box sub-problem is printed. If level >= 3 , a trace of the qp_interior sub-problem is printed.

n
This is the dimension of the domain space for f ; see n .

m
This is the dimension of the range space for f ; see m . This must be one so that @(@ f @)@ is an objective function.

s
This is the number of absolute value terms in f ; see s .

g
We use the notation g for the abs-normal representation of f ; see g .

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

g_jac
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} ) @)@.

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

bound
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 @)@.

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. @[@ \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 qp_interior sub-problems.

delta_x
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.

Method

sigma
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) @)@.

Cutting Planes
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 ) @)@.

Iteration
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.

Example
The file abs_min_quad.cpp contains an example and test of abs_min_quad.
Input File: example/abs_normal/abs_min_quad.hpp