Non-Smooth Optimization Using Abs-normal Quadratic Approximations

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

Prototype

template <class DblVector, class SizeVector>
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_quad.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.

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_quad is printed. If level >= 2 , a trace of each iteration of the abs_min_quad sub-problem is printed. If level >= 3 , a trace of the qp_box sub-problem is printed. If level >= 4 , a trace of the qp_interior sub-problem is printed.

f
This is the original function for the abs-normal form; 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 .

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_quad iterations to try before giving up on convergence. The value maxitr[1] is the maximum number of iterations in the abs_min_quad sub-problem. The value maxitr[2] is the maximum number of iterations in the qp_interior 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_quad 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_quad.cpp contains an example and test of min_nso_quad. It returns true if the test passes and false otherwise.