# elsa problems¶

## Problem¶

template<typename data_t = real_t>
class elsa::Problem : public elsa::Cloneable<Problem<real_t>>

Class representing a generic optimization problem consisting of data term and regularization term(s).

This class represents a generic optimization problem, which consists of a data term and (optionally) of one (or many) regularization terms,

$$\argmin_x D(x) + \sum_{i=1}^n \lambda_i R(x)$$. Here, the data term $$D(x)$$ is represented through a Functional (or it derivatives), the regularization terms are represented by RegularizationTerms, which encapsulate regularization parameters $$\lambda_i$$ (scalar values) and the actual regularization terms $$R(x)$$ (Functionals or its derivatives).
Author

Matthias Wieczorek - initial code

Author

Maximilian Hornung - modularization

Author

Tobias Lasser - rewrite, modernization

Template Parameters
• data_t: data type for the domain and range of the problem, defaulting to real_t

Public Functions

Problem(const Functional<data_t> &dataTerm, const std::vector<RegularizationTerm<data_t>> &regTerms, const DataContainer<data_t> &x0)

Constructor for optimization problem, accepting a data and multiple regularization terms, and an initial guess x0.

Parameters
• [in] dataTerm: functional expressing the data term

• [in] regTerms: vector of RegularizationTerms (weight and functional)

• [in] x0: initial value for the current estimated solution

Problem(const Functional<data_t> &dataTerm, const std::vector<RegularizationTerm<data_t>> &regTerms)

Constructor for optimization problem, accepting a data and multiple regularization terms.

Parameters
• [in] dataTerm: functional expressing the data term

• [in] regTerms: vector of RegularizationTerms (weight and functional)

Problem(const Functional<data_t> &dataTerm, const RegularizationTerm<data_t> &regTerm, const DataContainer<data_t> &x0)

Constructor for optimization problem, accepting a data and one regularization term, and an initial guess x0.

Parameters
• [in] dataTerm: functional expressing the data term

• [in] regTerm: RegularizationTerm (weight and functional)

• [in] x0: initial value for the current estimated solution

Problem(const Functional<data_t> &dataTerm, const RegularizationTerm<data_t> &regTerm)

Constructor for optimization problem, accepting a data and one regularization term.

Parameters
• [in] dataTerm: functional expressing the data term

• [in] regTerm: RegularizationTerm (weight and functional)

Problem(const Functional<data_t> &dataTerm, const DataContainer<data_t> &x0)

Constructor for optimization problem, accepting a data term and an initial guess x0.

Parameters
• [in] dataTerm: functional expressing the data term

• [in] x0: initial value for the current estimated solution

Problem(const Functional<data_t> &dataTerm)

Constructor for optimization problem, accepting a data term.

Parameters
• [in] dataTerm: functional expressing the data term

~Problem() override = default

default destructor

const Functional<data_t> &getDataTerm() const

return the data term

const std::vector<RegularizationTerm<data_t>> &getRegularizationTerms() const

return the vector of regularization terms

const DataContainer<data_t> &getCurrentSolution() const

return the current estimated solution (const version)

DataContainer<data_t> &getCurrentSolution()

return the current estimated solution

data_t evaluate()

evaluate the problem at the current estimated solution

Please note: this method calls the method _evaluate that has to be overridden in derived classes.

Return

the value of the problem evaluated at the current estimated solution

DataContainer<data_t> getGradient()

return the gradient of the problem at the current estimated solution

Return

DataContainer (in the domain of the problem) containing the result of the gradient at the current solution

void getGradient(DataContainer<data_t> &result)

compute the gradient of the problem at the current estimated solution

Please note: this method calls the method _getGradient that has to be overridden in derived classes.

Parameters
• [out] result: output DataContainer containing the gradient (in the domain of the problem)

LinearOperator<data_t> getHessian() const

return the Hessian of the problem at the current estimated solution

Please note: this method calls the method _getHessian that has to be overridden in derived classes.

Return

a LinearOperator (the Hessian)

data_t getLipschitzConstant(index_t nIterations = 5) const

return the Lipschitz Constant of the problem at the current estimated solution

Please note: this method calls the method getLipschitzConstantImpl that has to be overridden in derived classes which want to provide a more specific way of computing the Lipschitz constant, e.g. by not using power iteration or where the hessian is already approximated as a diagonal matrix.

Return

data_t (the Lipschitz Constant)

Parameters
• [in] nIterations: number of iterations to compute the lipschitz constant using power iteration.

Protected Functions

Problem(const Problem<data_t> &problem)

protected copy constructor, simplifies cloning (of the subclasses primarily)

data_t evaluateImpl()

the evaluation of the optimization problem

void getGradientImpl(DataContainer<data_t> &result)

the getGradient method for the optimization problem

LinearOperator<data_t> getHessianImpl() const

the getHessian method for the optimization problem

data_t getLipschitzConstantImpl(index_t nIterations) const

the getLipschitzConstant method for the optimization problem

Problem<data_t> *cloneImpl() const override

implement the polymorphic clone operation

bool isEqual(const Problem<data_t> &other) const override

implement the polymorphic comparison operation

Protected Attributes

std::unique_ptr<Functional<data_t>> _dataTerm = {}

the data term

std::vector<RegularizationTerm<data_t>> _regTerms = {}

the regularization terms

DataContainer<data_t> _currentSolution

the current estimated solution

## RegularizationTerm¶

template<typename data_t = real_t>
class elsa::RegularizationTerm

Class representing a regularization term (a scalar parameter and a functional).

This class represents a regularization term, consisting of a regularization parameter (a scalar) and a term (represented as a

Functional). It is just a light-weight wrapper with no added functionality.
Author

Maximilian Hornung - initial code

Author

Tobias Lasser - modernization

Template Parameters
• data_t: data type for the domain and range of the problem, defaulting to real_t

Public Functions

RegularizationTerm(data_t weight, const Functional<data_t> &functional)

Constructor for the regularization term, accepting a weight and a functional.

Parameters
• weight: the regularization parameter

• functional: the actual term

RegularizationTerm(const RegularizationTerm<data_t> &other)

copy constructor

RegularizationTerm<data_t> &operator=(const RegularizationTerm<data_t> &other)

copy assignment

RegularizationTerm(RegularizationTerm<data_t> &&other) noexcept

move constructor

RegularizationTerm<data_t> &operator=(RegularizationTerm<data_t> &&other) noexcept

move assignment

~RegularizationTerm() = default

the default destructor

data_t getWeight() const

return the weight of the regularization term (the regularization parameter)

Functional<data_t> &getFunctional() const

return the functional of the regularization term

bool operator==(const RegularizationTerm<data_t> &other) const

comparison operator

bool operator!=(const RegularizationTerm<data_t> &other) const

negative comparison operator

Private Members

data_t _weight

the weight / regularization parameter

std::unique_ptr<Functional<data_t>> _functional

the functional of the regularization term

## WLSProblem¶

template<typename data_t = real_t>
class elsa::WLSProblem : public elsa::Problem<real_t>

Class representing a weighted least squares problem.

This class represents a weighted least squares optimization problem, i.e.

$$\argmin_x \frac{1}{2} \| Ax - b \|_{W,2}^2$$, where $$W$$ is a weighting (scaling) operator, $$A$$ is a linear operator and $$b$$ is a data vector.
Author

Jakob Vogel - initial code

Author

Matthias Wieczorek - rewrite

Author

Tobias Lasser - another rewrite, modernization

Author

Nikola Dinev - added conversion constructor

Template Parameters
• data_t: data type for the domain and range of the problem, defaulting to real_t

Public Functions

WLSProblem(const Scaling<data_t> &W, const LinearOperator<data_t> &A, const DataContainer<data_t> &b, const DataContainer<data_t> &x0)

Constructor for the wls problem, accepting W, A, b, and an initial guess x0.

Parameters
• [in] W: scaling operator for weighting

• [in] A: linear operator

• [in] b: data vector

• [in] x0: initial value for the current estimated solution

WLSProblem(const Scaling<data_t> &W, const LinearOperator<data_t> &A, const DataContainer<data_t> &b)

Constructor for the wls problem, accepting W, A, and b.

Parameters
• [in] W: scaling operator for weighting

• [in] A: linear operator

• [in] b: data vector

WLSProblem(const LinearOperator<data_t> &A, const DataContainer<data_t> &b, const DataContainer<data_t> &x0)

Constructor for the (w)ls problem, accepting A, b, and an initial guess x0 (no weights)

Parameters
• [in] A: linear operator

• [in] b: data vector

• [in] x0: initial value for the current estimated solution

WLSProblem(const LinearOperator<data_t> &A, const DataContainer<data_t> &b)

Constructor for the (w)ls problem, accepting A and b (no weights)

Parameters
• [in] A: linear operator

• [in] b: data vector

WLSProblem(const Problem<data_t> &problem)

Constructor for converting a general optimization problem to a WLS problem.

Only problems that consist exclusively of (Weighted)

L2NormPow2 terms can be converted. The (Weighted)L2NormPow2 should be acting on a LinearResidual.
Parameters
• [in] problem: the problem to be converted

Acts as a copy constructor if the supplied optimization problem is a quadric problem.

~WLSProblem() override = default

default destructor

Protected Functions

WLSProblem<data_t> *cloneImpl() const override

implement the polymorphic clone operation

Private Static Functions

std::unique_ptr<Functional<data_t>> wlsFromProblem(const Problem<data_t> &problem)

converts an optimization problem to a (Weighted)L2NormPow2 functional

## TikhonovProblem¶

template<typename data_t = real_t>
class elsa::TikhonovProblem : public elsa::Problem<real_t>

Class representing a Tikhonov regularized weighted least squares problem.

This class represents a Tikhonov regularized weighted least squares problem. Some common examples are:

• $$\argmin_x \frac{1}{2} \| Ax - b \|_2^2 + \lambda \| x \|_2^2$$

• $$\argmin_x \frac{1}{2} \| Ax - b \|_2^2 + \lambda \| x - x^* \|_2^2$$

• $$\argmin_x \frac{1}{2} \| Ax - b \|_2^2 + \lambda \| Lx \|_2^2$$

• $$\argmin_x \frac{1}{2} \| Ax - b \|_2^2 + \lambda \| L(x - x^*) \|_2^2$$, where $$A$$ is a linear operator and $$b$$ and $$x^*$$ are data vectors, $$\lambda$$ is the regularization weight, and $$L$$ is a discretized differential operator.

Author

Nikola Dinev

Template Parameters
• data_t: data type for the domain and range of the problem, defaulting to real_t

This class supports a wider range of problems - any problem of the form $$\argmin_x \frac{1}{2} \| Ax - b \|_{W,2}^2 + \sum_{i=1}^n \lambda_i \| B_ix - x^*_i \|_{V_i,2}^2$$ is considered a Tikhonov problem. Here $$A$$ and $$B_i$$ are linear operators, $$b$$ and $$x^*_i$$ are data vectors, $$\lambda_i$$ are the regularization weights, and $$W$$ and $$V_i$$ are scaling operators.

Public Functions

TikhonovProblem(const WLSProblem<data_t> &wlsProblem, const std::vector<RegularizationTerm<data_t>> &regTerms)

Constructor for a Tikhonov problem.

Parameters
• [in] wlsProblem: a wls problem specifying the data term and the initial solution

• [in] regTerms: the regularization terms, all should be of type L2NormPow2 or WeightedL2NormPow2

TikhonovProblem(const WLSProblem<data_t> &wlsProblem, const RegularizationTerm<data_t> &regTerm)

Constructor for a Tikhonov problem.

Parameters
• [in] wlsProblem: a wls problem specifying the data term and the initial solution

• [in] regTerm: the regularization term, should be of type L2NormPow2 or WeightedL2NormPow2

~TikhonovProblem() override = default

default destructor

Protected Functions

TikhonovProblem(const TikhonovProblem<data_t>&) = default

default copy constructor, hidden from non-derived classes to prevent potential slicing

TikhonovProblem<data_t> *cloneImpl() const override

implement the polymorphic clone operation

template<typename data_t = real_t>
class elsa::QuadricProblem : public elsa::Problem<real_t>

This class represents a quadric problem, i.e.

$$\argmin_x \frac{1}{2} x^tAx - x^tb$$ where $$A$$ is a symmetric positive-definite operator and $$b$$ is a data vector.
Author

Nikola Dinev

Template Parameters
• data_t: data type for the domain and range of the problem, defaulting to real_t

Public Functions

QuadricProblem(const LinearOperator<data_t> &A, const DataContainer<data_t> &b, const DataContainer<data_t> &x0, bool spdA)

Constructor for the quadric problem accepting A, b, and an initial guess x0.

$$\argmin_x \frac{1}{2} x^tAx - x^tb$$ if $$A$$ is spd, and $$\argmin_x \frac{1}{2} x^tA^tAx - x^tA^tb$$ if $$A$$ is not spd
Parameters
• [in] A: linear operator

• [in] b: data vector

• [in] x0: initial value for the current estimated solution

• [in] spdA: flag whether A is symmetric positive-definite

Please note: For a general complex operator

$$A$$, it does not necessarily hold that $$A^*A$$ is spd. Therefore, QuadricProblem is restricted to the non-complex variants.
Warning

A must be nonsingular even if it is not spd.

QuadricProblem(const LinearOperator<data_t> &A, const DataContainer<data_t> &b, bool spdA)

Constructor for the quadric problem accepting A and b.

$$\argmin_x \frac{1}{2} x^tAx - x^tb$$ if $$A$$ is spd, and $$\argmin_x \frac{1}{2} x^tA^tAx - x^tA^tb$$ if $$A$$ is not spd
Parameters
• [in] A: linear operator

• [in] b: data vector

• [in] spdA: flag whether A is symmetric positive-definite

Please note: For a general complex operator

$$A$$, it does not necessarily hold that $$A^*A$$ is spd. Therefore, QuadricProblem is restricted to the non-complex variants.
Warning

A must be nonsingular even if it is not spd.

QuadricProblem(const Quadric<data_t> &quadric, const DataContainer<data_t> &x0)

Constructor for the quadric problem accepting a quadric and an initial guess x0.

Parameters
• [in] quadric: a Quadric containing the entire problem formulation

• [in] x0: initial value for the current estimated solution

QuadricProblem(const Quadric<data_t> &quadric)

Parameters
• [in] quadric: a Quadric containing the entire problem formulation

QuadricProblem(const Problem<data_t> &problem)

Constructor for converting a general optimization problem to a quadric one.

Only problems that consist exclusively of

Quadric and (Weighted)L2NormPow2 terms can be converted. If (Weighted)L2NormPow2 terms are present, they should be acting on a LinearResidual.
Parameters
• [in] problem: the problem to be converted

Acts as a copy constructor if the supplied optimization problem is a quadric problem.

Protected Functions

QuadricProblem<data_t> *cloneImpl() const override

implement the polymorphic clone operation

Private Static Functions

LinearResidual<data_t> getGradientExpression(const RegularizationTerm<data_t> &regTerm)

returns an expression for calculating the gradient of the regularization term

std::unique_ptr<Quadric<data_t>> quadricFromProblem(const Problem<data_t> &problem)

converts an optimization problem to a quadric