how to define the lagrange problem on the boundaries

52 Views Asked by At

Im reading a paper where they solve a problem of the form: minimize

$$f(a,b,c) = \sum_{i=1}^n(a+by_i+cy_i^2-u_i)^2$$

Where $y_i,n$ and $u_i$ are given over the compact domain $K$

$$ K=\begin{cases} 0\le a\le t_1 \\ |b|\le c \text{ and }|b|\le t_2- c\\ 0\le c\le t_2 \end{cases}$$

for known constants $t_1,t_2$. Since the function is quadratic we have $\nabla f= \frac{1}{2}Ax-b$ for a matrix $A$, vector $b$ and $x=(a,b,c)$. This can be solved easily numerically. However, it is not guaranteed that the solution lies within the above defined compact set $K$. If not we need to check the boundaries, i.e. flat sides, edges and vertices. Lets for example focus on the side where we fix $a=t_1$. The authors says this can be done (per side) by applying a lagrange multipliers which turns into a $3\times3$ linear system.

We find that $$\frac{\partial f}{\partial a} = 2\sum_{i=1}^n(a+by_i+cy_i^2-u_i)$$ $$\frac{\partial f}{\partial b} = 2\sum_{i=1}^ny_i(a+by_i+cy_i^2-u_i)$$ $$\frac{\partial f}{\partial b} = 2\sum_{i=1}^ny_i^2(a+by_i+cy_i^2-u_i)$$

therefore we have

$$A = \begin{pmatrix} n & \sum_{i=1}^n y_i & \sum_{i=1}^n y_i^2 \\ \sum_{i=1}^n y_i & \sum_{i=1}^n y_i^2 & \sum_{i=1}^n y_i^3 \\ \sum_{i=1}^ny_i^2 & \sum_{i=1}^n y_i^3 & \sum_{i=1}^n y_i^4 \end{pmatrix}$$ and $$b = \begin{pmatrix} \sum_{i=1}^n u_i^2 \\ \sum_{i=1}^n y_iu_i \\ \sum_{i=1}^ny_i^2u_i \end{pmatrix}$$

I'm struggeling with the concrete form of this linear $3\times 3$ equation system. What is the form of this linear system? Im not interested in the actual numbers, more how I can derive it by myself.