Multi-Dimensional Rank-one Convexification

R1Convexification{dimp,dimc,dirtype<:RankOneDirections{dimp},T1,T2,R} <: Convexification

Datastructure that is used as an equivalent to GrahamScan in the multidimensional rank-one relaxation setting. Bundles rank-one direction discretization as well as a tolerance and the convexification grid.

Constructor

R1Convexification(axes_diag::AbstractRange,axes_off::AbstractRange;dirtype=ℛ¹Direction,dim=2,tol=1e-4)
R1Convexification(grid::GradientGrid,r1dirs,tol)

Fields

• grid::GradientGrid{dimc,T1,R}
• dirs::dirtype
• tol::T1

GradientGrid{dimc,T,R<:AbstractRange{T}}

Lightweight implementation of a structured convexification grid in multiple dimensions. Computes the requested convexification grid node adhoc and therefore is especially suited for threading (no cache misses). Implements the Base.Iterator interface and other Base functions such as, length,size,getindex,lastindex,firstindex,eltype,axes Within the parameterization dimc denote the convexification dimensions, T the used number type and R the number type of the start, step and end value of the axes ranges.

Constructor

GradientGrid(axes::NTuple{dimc,R}) where dimc

• axes::R is a tuple of discretizations with the order of Tensor{2,2}([x1 y1;x2 y2])

Fields

• axes::NTuple{dimc,R}
• indices::CartesianIndices{dimc,NTuple{dimc,Base.OneTo{Int64}}}

ParametrizedR1Directions{dimp,T} <: RankOneDirections{dimp}

Direction datastructure that computes the reduced rank-one directions in the dimp physical dimensions and dimp² convexification dimensions. Implements the Base.Iterator interface and other utility functions. This datastructure only computes the first neighborhood rank-one directions and utilizes the symmetry of the dimp² dimensionality. Since they are quite small in 2² and 3² the directions are precomputed and stored in dirs.

Constructor

ParametrizedR1Directions(2)
ParametrizedR1Directions(3)

Fields

• dirs::Vector{Tuple{Vec{dimp,T},Vec{dimp,T}}}

ℛ¹Direction{dimp,dimc} <: RankOneDirections{dimp}

Lightweight implementation that computes all rank-one directions within a grid::GradientGrid adhoc. Therefore, also suited for threading purposes, since this avoids cache misses. Implements the Base.Iterator interface and other utility functions. Within the parameterization dimp and dimc denote the physical dimensions of the problem and the convexification dimensions, respectively.

Constructor

ℛ¹Direction(b::GradientGrid)

• b::GradientGrid is a deformation grid discretization

Fields

• a_axes::NTuple{dimp,UnitRange{Int}}
• b_axes::NTuple{dimp,UnitRange{Int}}
• indices::CartesianIndices{dimc,NTuple{dimc,Base.OneTo{Int64}}}

ℛ¹DirectionBuffered{dimp,dimc,T} <: RankOneDirections{dimp}

Heavyweight implementation that computes all rank-one directions within a grid::GradientGridBuffered within the constructor. Implements the Base.Iterator interface and other utility functions. Within the parameterization dimp and dimc denote the physical dimensions of the problem and the convexification dimensions, respectively.

Constructor

ℛ¹DirectionBuffered(dirs::ℛ¹Direction)

• dirs::ℛ¹Direction collects the reference dirs direction and caches them in the grid field

Fields

• grid::AbstractArray{Tuple{Vec{dimp,T},Vec{dimp,T}},dimc}

GradientGridBuffered{dimc,T,dimp}

Heavyweight implementation of a structured convexification grid in multiple dimensions. Computes the requested convexification grid within the constructor and only accesses thereafter the grid field. Implements the Base.Iterator interface and other Base functions such as, length,size,getindex,lastindex,firstindex,eltype,axes Within the parameterization dimc denote the convexification dimensions, T the used number type and dimp the physical dimensions of the problem.

Constructor

GradientGridBuffered(axes::NTuple{dimc}) where dimc

• axes::StepRangeLen{T,R,R} is a tuple of discretizations with the order of Tensor{2,2}([x1 y1;x2 y2]

Fields

• grid::AbstractArray{Tensor{2,dimp,T,dimc},dimc}
• indices::CartesianIndices{dimc,NTuple{dimc,Base.OneTo{Int64}}}

convexify!(r1convexification::R1Convexification,r1buffer::R1ConvexificationBuffer,W::FUN,xargs::Vararg{Any,XN};buildtree=true,maxk=20) where {FUN,XN}

Multi-dimensional parallelized implementation of the rank-one convexification. If buildtree=true the lamination tree is saved in the r1buffer.laminatetree. Note that the interpolation objects within r1buffer are overwritten in this routine. The approximated rank-one convex envelope is saved in r1buffer.W_rk1

convexify!(f, x, ctr, h, y)

Rank-one line convexification algorithm in multiple dimensions without deletion, but in $\mathcal{O}(N)$

HROC{dimp,R1Dir<:RankOneDirections{dimp},T} <: AbstractConvexification

Holds the specification for performing rank-one convexification by the upper bound described in this paper. Useable by constructing an instance of this type, as well as a buffer by build_buffer and calling convexify as usual.

Constructors

HROC(maxlevel::Int,n_convexpoints::Int,dir::R1Dir,GLcheck::Bool,start::Tensor{2,dimp,T,dimc},stop::Tensor{2,dimp,T,dimc})
HROC(start::Tensor{2,dimp},stop::Tensor{2,dimp};maxlevel=10,l=1,dirs=ParametrizedR1Directions(dimp;l=l),GLcheck=true,n_convexpoints=1000)

Fields

• maxlevel::Int
• n_convexpoints::Int
• dirs::R1Dir
• GLcheck::Bool
• startF::Vector{T}
• endF::Vector{T}

convexify(hroc::HROC, buffer::HROCBuffer, W::FUN, F::T1, xargs::Vararg{Any,XN}) -> bt::BinaryLaminationTree

Performs a hierarchical rank one convexification (HROC) based on the H-sequence characterization of the convex envelope. Note that the output of the algorithm is only an upper bound. For a class of problems the provided hull matches the rank-one convex envelope. The return of the algorithm can be used to call eval which evaluates the constructed binary lamination tree in terms of semi convex envelope value and its derivatives.

convexify(prev_bt::BinaryLaminationTree,hroc::HROC, buffer::HROCBuffer, W::FUN, F::T1, xargs::Vararg{Any,XN}) -> bt::BinaryLaminationTree

Performs a hierarchical rank one convexification (HROC) based and enforces laminate continuity by preferring the previous laminate direction.