5
$\begingroup$

I have a function to minimize:

$f(a_1,a_2,a_3,a_4)=\sum_{i=1}^n\left(\sum_{k=1}^3 a_k\ p_i^k -a_4\right)^2$

subjected to this constraint:

$a_1^2+a_2^2+a_3^2=1$

and

$a_4\geq0$

I am trying to cast it in least square principles and Lagrange multiplier and solve it, but I am not quite sure how to do it.

The reason I want to do it this way is because I want to leverage existing library like alglib to solve it, it contains the least square principle toolbox, but it doesn't contain least square principles with Lagrange multiplier.

Any idea how to cast this problem in a appropriate format that can be attacked by standard numerical libraries?

  • 0
    @cardinal, nope, $p_i$ can be anything.2011-09-18

2 Answers 2

5

I don't know if quadratic programming is OK with you because I don't know what alglib does. It takes only to rewrite your function in terms of matrices as follows:

Define a vector $P_i := \begin{pmatrix}p^1_i\\p^2_i\\p_i^3 \\-1\end{pmatrix}, a =\begin{pmatrix}a_1\\a_2\\a_3 \\a_4\end{pmatrix} $ Then, your function to be minimized can be expressed as $f(a) = a^T\left( \sum_k P_kP_k^T\right)a$ such that $a^T\begin{pmatrix} I_3 &0\\0&0_1\end{pmatrix}a = 1$ and $\begin{pmatrix}1&a^T \end{pmatrix}\begin{pmatrix} 0 &0 &0 &0 &1\\0 &0 &0 &0 &0\\0 &0 &0 &0 &0\\0 &0 &0 &0 &0\\1 &0 &0 &0 &0\end{pmatrix}\begin{pmatrix}1\\a \end{pmatrix} \geq 0$

  • 1
    Actually there are non-smooth non-convex algorithms available but I don't know if they handle also QCQPs. Most of the times it boils down to Clarke differentials and other esoteric stuff. But they do handle SDP in general so it is not that hopeless of a situation. At least it is better formulated in this form for my taste. But you are right maybe i should have used a disclaimer.2011-09-15
1

The standard approach for a minimization problem with constraints is to consider extremising the Lagrangian

$L(a_1,a_2,a_3,a_4,\lambda) = \sum_{i=1}^n \left( \sum_{k=1}^3 a_k p_i^k - a_4 \right) ^2 - \lambda \left( \sum_{k=1}^3 a_k^2 - 1 \right)$

over the variables $a_1,a_2,a_3,a_4,\lambda$. Differentiating with respect to these variables and setting the resulting quantities to zero will result in one equation which enforces your constraint, and four other equations that are linear in the $a_k$ and $\lambda$.

I do not know what form the 'standard numerical libraries' expect the problem to be in, but this is the classical approach to constrained optimisation.

  • 0
    I figure out on the first part as well. But I am stuck on the second part.2011-09-15