3
$\begingroup$

I need to solve the following optimization problem. \begin{aligned} \min_{\lambda_0,\lambda_1} & \sum_{t=1}^T\sum_{n\in\{4,8,12,16\}} \left(\frac{1}{n}A_n + \frac{1}{n}B_n^\top X_t + y_t^{(n)}\right)^2 \\ \text{s.t. }\\ & A_{n+1} = A_n + B_n^\top(\mu - \Sigma\lambda_0) + \frac{1}{2}B_n^\top\Sigma\Sigma^\top B_n, & n=1,\dots,16 \\ & B_{n+1} = (\Phi - \Sigma\lambda_1)^\top B_n - \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, & n=1,\dots,16 \\ & A_1 = 0, \qquad B_1 = -\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}\\ \end{aligned} where $B_n$ is $3\times 1$, $A_n$ is a scalar and $\Phi,\mu, \Sigma,y_t^{(n)}, X_t, \;t=1,\dots,T$ are given. $\Phi,\Sigma$ are $3\times3$ and $\mu, X_t$ are $3\times1$.

Unknown variables are $\lambda_0$ which is $3\times1$ and $\lambda_1$ which is $3\times 3$.

I'm familiar with Matlab, Matematica, R. Which software can I use? Which functions? How do I program it, a Lagrangian with a many constraints? Is there other method of solving such problems?

$\endgroup$
  • $\begingroup$ Ah, sorry, I missed that. At a first glance I thought the constraints were affine. Will delete comment momentarily. $\endgroup$ – copper.hat Mar 4 '13 at 19:59
  • $\begingroup$ Is the evolution of some dynamical system? (I mean, something straightforward.) $\endgroup$ – copper.hat Mar 4 '13 at 20:00
  • $\begingroup$ It is a dynamic system (affine term structure model from finance). The idea is to select two parameters $\lambda_0,\lambda_1$, so that the model fits data the best. $\endgroup$ – Affine Mar 4 '13 at 20:06
  • $\begingroup$ Sometimes such problems can be formulated as an optimal control problem which may have simpler optimality characterizations... $\endgroup$ – copper.hat Mar 4 '13 at 20:25
  • $\begingroup$ Just to double check: are $\lambda$ the only variables? $\endgroup$ – Dominique Mar 4 '13 at 21:36
0
$\begingroup$

If you already use MATLAB and the problem is indeed convex (haven't checked in detail) you could try CVX.

$\endgroup$
0
$\begingroup$

Your problem is an "EQP" (an Equality-Constrained Quadratic Program). It has a convex quadratic objective and linear equality constraints, i.e., it has the general form $$ \min_x \ c^T x + \tfrac{1}{2} x^T H x \quad \text{subject to} \ Ax=b, $$ where $H$ is a symmetric and positive semi-definite matrix. It turns out that solving EQPs is just a matter of linear algebra since any solution is a global minimizer and also solves the linear system $$ \begin{bmatrix} H & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} -c \\ b \end{bmatrix}, $$ where $y$ is the vector of Lagrange multipliers associated to the equality constraints. The matrix of this system is symmetric and indefinite so in Matlab you can use ldl() to factorize it. If it's very large and/or very dense, you can also use minres() to solve the system. But judging from your post, a simple "backslash" might do.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.