Lagrangian method
We want to minimize the partially-separable function $f : \mathbb{R}^n \to \mathbb{R}$
$$
\min_{x \in \mathbb{R}^n} f(x) = \sum\limits_{i=1}^{N_0} \hat{f}_i(U_i x),
$$
under partially-separable constraints
$$
c_j(x) = \sum_{i=1}^{N_j} \widehat{c}_{j,i}(U_{j,i} x) = 0, \quad \forall 1\leq j\leq m .
$$
For now, we only consider =0 constraints, and we will relie on slack variables to support inequality constraints.
We choose to solve the constrained problem with an augmented Lagrangian approach.
It produces a minimization method solving iteratively Langragian (unconstrained) problems
$$
L_{\mu}(x;\lambda) = \sum_{i=1}^{N_0} \widehat{f}_i(U_i x) + \lambda^\top c(x) + \mu ||c(x)||^2, \quad \lambda \in \mathbb{R}^m,
$$
with increasing Langrangian factor $\lambda$.
We plan to apply a partitioned trust-region method to solve successively the instances of the Lagrangian problems (may be extended to group partial separability, see the second section).
A Lagrangian problem has the following partially-separable structure:
$$
\min_{x \in \mathbb{R}^n} L_{\mu}(x;\lambda) = \sum_{i=1}^{N_0} \widehat{f}_i(U_i x) + \sum_{j=1}^m \sum_{i=1}^{N_j} \lambda_j \widehat{c}_{j,i}(U_{j,i} x) + \sum_{j=1}^m \sum_{i_1=1}^{N_j} \sum_{i_2=1}^{N_j} \underbrace{\mu \widehat{c}_{j,i_1}(U_{j,i_1}x) \widehat{c}_{j,i_2}(U_{j,i_2}x)}_{\widehat{h}_{j,i_1,i_2}(U_{j,i_1,i_2} x)},
$$
where there is: objective element functions, every element functions of contraints (multiplied by $\lambda_j$) and element functions resulting of the product of two element functions coming from the same constraint.
PartiallySeparableNLPModels must evaluate distinctly the value and derivatives of :
- original element functions;
- the element function of constraints;
- modified element functions from constraints;
- product of element functions from constraints;
to evaluate objective function and derivatives of Lagrangian problem.
Group partial separability
It there is some structure on the element functions from constraints, it can be used to simplify the computation of the derivatives (group partial separability).
Example:
$$
h(x_1,x_2,x_3) = c_{j,i}(x_1) . c_{j,i+1}(x_2,x_3)
$$
Suppose that $c_{j,i}(x_1) = 4x_1$ (linear) and $c_{j,i+1}(x_2,x_3)$ non-linear.
The partial derivatives of $h$ will be:
$$
\frac{\partial h}{\partial x_1} = 4 c_{j,i+1}(x_2,x_3),
$$
$$
\frac{\partial h}{\partial x_2} = c_{j,i}(x_1) . \frac{\partial c_{j,i+1}(x_2,x_3)}{\partial x_2} = 4 x_1 . \frac{\partial c_{j,i+1}(x_2,x_3)}{\partial x_2},
$$
$$
\frac{\partial h}{\partial x_3} = c_{j,i}(x_1). \frac{\partial c_{j,i+1}(x_2,x_3)}{\partial x_3} = 4 x_1. \frac{\partial c_{j,i+1}(x_2,x_3)}{\partial x_3}.
$$
Even without considering linear constraints, if the variables of $c_{j,i}$ and $c_{j,i+1}$ are not overlapping, then $\nabla h$ is mainly recombination of $\nabla c_{j,i}$ and $\nabla c_{j,i+1}$ with a lot of redundancies.
Later on, $\nabla h$ will be multiplied by $\mu$.
