Non-Smooth Optimization Using Abs-normal Linear Approximations

Syntax
ok = min_nso_linear(      level, g, a, epsilon, maxitr, b_in, x_in, x_out )

Prototype

template <class DblVector, class SizeVector>
bool min_nso_linear(
size_t           level     ,
const DblVector& epsilon   ,
SizeVector       maxitr    ,
double           b_in      ,
const DblVector& x_in      ,
DblVector&       x_out     )

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

Purpose
Given a current that abs-normal representation g , a , for a function $f(x)$, this routine minimizes $f(x)$.

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 .

n
We use n to denote the dimension of the domain for f ; i.e., f.Domain() .

m
We use m to denote the dimension of the range for f ; i.e., f.Range() . This must be equal to one.

s
We use s to denote the number absolute terms in f .

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

g
This is the function g in the abs-normal representation of f .

a
This is the function a in the abs-normal representation of f .

epsilon
This is a vector with size 2. The value epsilon[0] is convergence criteria in terms of the infinity norm of the difference of x_out between iterations. The value epsilon[1] is convergence criteria in terms of the derivative of $f(x)$. This derivative is actually the average of the directional derivative in the direction of the sub-problem minimizer.

maxitr
This is a vector with size 3. The value maxitr[0] is the maximum number of min_nso_linear iterations to try before giving up on convergence. The value maxitr[1] is the maximum number of iterations in the abs_min_linear sub-problem. The value maxitr[2] is the maximum number of iterations in the simplex_method sub-problems.

b_in
This the initial bound on the trust region size. To be specific, if $b$ is the current trust region size, at each iteration affine approximation is minimized with respect to $\Delta x$ and subject to $$-b \leq \Delta x_j \leq b$$ for j = 0 , ..., n-1 . It must hold that b_in > epsilon[0] .

x_in
This vector x_out has size n . It is the starting point for the optimization procedure; i.e., the min_nso_linear iterations.

x_out
This vector x_out has size n . The input value of its elements does not matter. Upon return, it is the approximate minimizer of the abs-normal approximation for $f(x)$ over the trust region is $x = \hat{x} + \Delta x$.

Example
The file min_nso_linear.cpp contains an example and test of min_nso_linear. It returns true if the test passes and false otherwise.
Input File: example/abs_normal/min_nso_linear.hpp