Numerical optimization question

Question

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?

Answer 1

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

Answer 2

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.