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