Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  cardinal Sep 15 '11 at 11:35
    
@cardinal, so should I search for "convex programming" in this case? Or is there any other more relevant keywords? –  Graviton Sep 15 '11 at 12:40
    
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. –  cardinal Sep 15 '11 at 17:25
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. –  cardinal Sep 15 '11 at 18:03
    
@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? –  Graviton Sep 17 '11 at 9:19

2 Answers 2

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$$

share|improve this answer
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. –  cardinal Sep 15 '11 at 17:02
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. –  user13838 Sep 15 '11 at 17:17
    
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‌​. –  cardinal Sep 15 '11 at 17:23
    
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. –  cardinal Sep 15 '11 at 18:04
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. –  user13838 Sep 15 '11 at 19:29

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.

share|improve this answer
    
I figure out on the first part as well. But I am stuck on the second part. –  Graviton Sep 15 '11 at 9:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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