2
$\begingroup$

First of all, thanks for the help in previous post. The problem I'm facing is some legacy codes used Lagrange multipliers to solve a weighted regression problem. New requirements changed and I'm trying to understand how the old one worked.

More specifically, the problem is

\begin{align}\min_f&\quad\| W(Xf-r)\|^2\\\text{s.t.}&\quad A^\top f=0.\end{align}

I'm trying to reproduce the derivation using Lagrange multiplier but I'm far off. The numerical results from legacy calculation are reasonable. So, I guess there must be something I derived wrong.

My derivation is shown below. Part of the derivation was kindly corrected by Joni in my previous post here Translate standard weighted least square regression to quadratic programming enter image description here

However, the legacy technical notes has the Lagrange as

enter image description here

Unfortunately like all technical notes, only results are given.

I am not sure where my derivation is wrong.

$\endgroup$
2
  • 1
    $\begingroup$ Please try to avoid using images to showcase your work (instead, use MathJax) as it helps improve readability and searchability. Good post though. $\endgroup$
    – TheSimpliFire
    Jan 28, 2022 at 20:40
  • $\begingroup$ Sorry, didn't know that. Will do it next time. Thanks for the encouragement. $\endgroup$
    – inf
    Jan 28, 2022 at 20:52

1 Answer 1

3
$\begingroup$

The issue is in the objective function and is caused by two conventions. First, the weights need to be for the squared error. Second. typically an optional $1/2$ is added to avoid the resulting $2$'s in the gradient. So, you are dealing with the following problem:

\begin{align*} \min_f \quad& \frac{1}{2} {(Xf - r)}^T W (Xf - r) \\ \text{s.t.} \quad& A^T f = 0. \end{align*}

[Note: I would rather define the constraint as $Af = b$ but followed your original problem.]

The Lagrangian and its gradient w.r.t $f$ are

\begin{align*} L(f,\lambda) &= \frac{1}{2} {(Xf - r)}^T W (Xf - r) + \lambda^T A^T f, \\ \nabla_f L(f,\lambda) &= X^T W (X f - r) + A \lambda \\ &= X^T W X f + A \lambda - X^T W r . \end{align*}

where $\lambda$ is the dual variable for the constraint. Resulting stationarity and primal feasibility conditions you derive are found as

$$ \begin{bmatrix} X^T W X & A \\ A^T & 0 \end{bmatrix} \begin{bmatrix} f \\ \lambda \end{bmatrix} = \begin{bmatrix} X^T W r \\ 0 \end{bmatrix}. $$

While the scalar $1/2$ is optional and only affects the dual variable, the other convention comes from how the weighted least squares is defined. The standard linear model assumes that the errors have constant variance. In weighted least squares the underlying model has errors with nonconstant variance. Indeed, the weight of an observation is proportional to the reciprocal of the error variance for that observation, $w_i = 1/\sigma_i^2$, thereby cancelling out the nonconstant variance. Therefore, $W$ is defined as $$ W = \begin{bmatrix} w_1 & 0 & \ldots & 0 \\ 0 & w_2 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & w_n \end{bmatrix} $$

Finally, it is equivalent to transforming the particular linear model by multiplying it with $W^{1/2}$. So if you defined $\mathcal{W}=W^{1/2}$ you'd be fine, too.

$\endgroup$
3
  • $\begingroup$ Thank you very much for the detailed awesome explanation. The notes started with $min_{f} ||W(XF-r)||^2$ and got the results shown above. Sigh... Hope you don't mind one follow-up question. For the Lagrange, why did you have $+\lambda^T$ instead of $-\lambda^T$? Thanks a lot again! $\endgroup$
    – inf
    Jan 29, 2022 at 14:38
  • 1
    $\begingroup$ You are welcome :) I am, again, just following the convention. It can be written with a minus sign as well. As this is an equality constraint, the dual variable is unrestricted in sign. It it were a "$\leq$" constraint, you would most likely write it with a plus sign to keep your dual variables nonnegative (by convention). More so than the signs, one should focus what a positive or negative value for the constraint implies regarding the value of the associated dual variable. $\endgroup$ Jan 29, 2022 at 18:08
  • $\begingroup$ Thank you very much again! This solved my last puzzle. Nice. $\endgroup$
    – inf
    Jan 30, 2022 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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