abs_normal: Minimize a Linear Abs-normal Approximation

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

Prototype

template <class DblVector, class SizeVector>
bool abs_min_linear(
size_t            level   ,
size_t            n       ,
size_t            m       ,
size_t            s       ,
const DblVector&  g_hat   ,
const DblVector&  g_jac   ,
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_linear.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$. This routine solves the problem $$\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 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 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 lp_box sub-problem is printed. If level >= 3 , a trace of the objective and primal variables $x$ are printed at each simplex_method 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 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} )$.

bound
This vector has size n and we denote its value by $b \in \B{R}^n$. The trust region is defined as the set of $x$ such that $$| x_j - \hat{x}_j | \leq b_j$$ for $j = 0 , \ldots , n-1$, where $x$ is the point that we are approximating $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., $\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 simplex_method 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 $\tilde{f}(x)$ with respect to the trust region is $x = \hat{x} + \Delta x$.

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} & \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 $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_linear.cpp contains an example and test of abs_min_linear. It returns true if the test passes and false otherwise.
Input File: example/abs_normal/abs_min_linear.hpp