3
$\begingroup$

I have a optimization problem as follows,

$$ \begin{array}{cll} [\hat{x_1},\hat{x_2},\hat{x_3}] = & \text{argmin}_{x_1,x_2,x_3} \sum_{i = 1}^N \sum_{t = 1}^T \left[ \ln(f_{i,t}(x_1,x_2,x_3)) + \frac{a_{i,t}}{f_{i,t}(x_1,x_2,x_3)}\right] & (1)\\ & \text{s. t.} & \\ & f_{i,t}(x_1,x_2,x_3) = x_1 + x_2 a_{i,t-1} + x_3 f_{i,t-1}(x_1,x_2,x_3) & (i)\\ & x_1,x_2,x_3 \ge 0 & (ii)\\ & x_2 + x_3 < 1 & (iii)\\ \end{array}$$ where $T, N$ are known positive constants, $a_{i,t}$ are known constants $\forall t \in \{1,...,T\}, \forall i \in \{1,...,N\}$ and the initial value for the filter $(i)$ over the given time horizon, that is to say $f_{i,1}$, is known $\forall i \in \{1,...,N\}$.

I have found one source that solves this with Augmented Lagrangian Relaxation combined with SQP.

I would like to propose the following alternative, instead change variables as follows: $$ \begin{array}{c} x_1 = \lambda_1^2\\ x_2 = \frac{\lambda_2^2}{1+\lambda_2^2+\lambda_3^2}\\ x_3 = \frac{\lambda_3^2}{1+\lambda_2^2+\lambda_3^2}\\ \end{array} $$

The above transformation should effectively remove the conditions $(ii)$, $(iii)$, and we get a new problem

\begin{array}{cll} [\hat{\lambda_1},\hat{\lambda_2},\hat{\lambda_3}] = & \text{argmin}_{\lambda_1,\lambda_2,\lambda_3} \sum_{i = 1}^N \sum_{t = 1}^T \left[ \ln(f_{i,t}(\lambda_1,\lambda_2,\lambda_3)) + \frac{a_{i,t}}{f_{i,t}(\lambda_1,\lambda_2,\lambda_3)}\right] & (2)\\ & \text{s. t.} & \\ & f_{i,t}(\lambda_1,\lambda_2,\lambda_3) = \lambda_1^2 + \frac{\lambda_2^2}{1+\lambda_2^2+\lambda_3^2} a_{i,t-1} + \frac{\lambda_3^2}{1+\lambda_2^2+\lambda_3^2} f_{i,t-1}(\lambda_1,\lambda_2,\lambda_3) & (i)\\ \end{array} where we simply substitute in $(i)$ into equation $(2)$ and have an unbounded non-linear optimization problem. As far as implementations go, my idea is to use BFGS with a relatively high error margin, and once I find an optimum in the transformed problem, transform it back and run it again in the original problem (without constraints $(ii)$,$(iii)$) starting at the newly found optimum, and it should be sufficiently close to the optimum to give a reliable result.

Now to the question, I've found several examples of substitution in nonlinear optimization but they often tend to specify that the transformation is a 1:1 one, which is not the case here ($\lambda_1 = \pm 1 \rightarrow x_1 = 1$). I haven't found any mention of this approach in literature on constrained nonlinear optimization. Is there any reason why my above solution would not work, take more time or provide an numerically unreliable or incorrect result? If so, why and what are the recommended methods for solving $(1)$?

$\endgroup$
  • 1
    $\begingroup$ In case anyone stumbles upon this and wonders, I tested it in R and it worked pretty darn well! Good enough for my application any way! A word of advise, be careful when you calculate the gradient! Using Automatic Differentiation on this will slow down the process tremendously! $\endgroup$ – Abonimation May 30 '16 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.