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
    If you relax the first constraint to $a_1^2 + a_2^2 + a_3^2 \leq 1$, then your optimization problem becomes convex. There are lots of packages to solve such problems. If you solve this problem and the original equality constraint is satisfied, then you know the convex-programming solution solves the original problem as well.2011-09-15
  • 0
    @cardinal, so should I search for "convex programming" in this case? Or is there any other more relevant keywords?2011-09-15
  • 0
    You can also search for **QCQP** and **quadratically constrained quadratic program**, which is what the relaxed version in my comment amounts to. Lots of software packages can be used to solve such problems, and being convex means that quite a lot can be said about a feasible solution.2011-09-15
  • 1
    In retrospect, there is a rather obvious issue with my relaxation suggestion for this particular problem: $a_1 = a_2 = a_3 = a_4 = 0$ is a feasible point, and so the optimal value of the objective function is zero.2011-09-15
  • 0
    @cardinal, as you remark yourself there is a trivial solution. So I guess that the **CQCP** isn't a good way to solve the problem?2011-09-17
  • 0
    Not as currently formulated, no. There are some constraints you can add to keep the problem as a QCQP and give nontrivial answers, but they may not be optimal for your problem. Do you know anything further about the $p_i$? Are they, e.g., all positive?2011-09-17
  • 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
    Can you explain either (a) what you mean by "quadratic programming" or (b) how to recast this as a quadratically constrained quadratic program? You have a quadratic *equality* constraint here, which does not fit into the (standard) formulation of a quadratic program.2011-09-15
  • 1
    @cardinal This is a QP with quadratic equality constraints. There is a standard way of handling linear equality constraints but not this (AFAIK). Hence this is a more difficult problem. I don't know what `alglib` does so I just formulated a constrained QP (actually a nonlinear program) without a Lagrange multiplier. Now there are nonstandard tools which can be used in the search for a local minimum but I don't know more about that.2011-09-15
  • 0
    Yes, that was sort of what I was getting at. I think it might be misleading to call this a "quadratic program" as doing so (i) suggests that it is one and (ii) hints that there might be standard software to solve it. :) If we relax the equality constraint to an inequality, then standard software *can* be used to solve it since it's a (convex) [QCQP](http://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program).2011-09-15
  • 0
    On the other hand, if we relax it as I suggested, we get a trivial and unhelpful solution. See my comment to the OP above.2011-09-15
  • 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