I recently encountered a quadratic programming equation and would appreciate assistance in understanding and obtaining the explicit solution. The equation is given by:
$$ u^* = \text{argmin}_{u \in \mathbb{R}^m} \lVert u - u_d \rVert $$
subject to the constraint: $$ Au \geq -b $$ where A is of shape (1,3), u is a column vector of shape (3,1), and b is a scalar.
The explicit solution is presented as: $$ u^* = u_d + u_s $$ where $$ u_s = \begin{cases} -\frac{A^T}{AA^T} \Psi & \text{if } \Psi < 0, \\ 0 & \text{otherwise} \end{cases} $$ $$ \Psi = Au + b $$
I am particularly interested in understanding how the explicit solution $-\frac{-A^T}{AA^T} \Psi$ is derived. Could someone provide a step-by-step explanation or point me to relevant resources that explain the process?
Note: I admit this is lengthy, and there's probably shorter way, but at least this works.
The optimization problem is, $$ \text{min}_{u \in \mathbb{R}^m} \lVert u - u_d \rVert \tag{1}\label{1}\\ \text{s.t.} \quad Au \geq -b $$
Suppose we change variables from $u$ to $u'$ by $u = u_d + u'$. Now the problem becomes, $$ \text{min}_{u' \in \mathbb{R}^m} \lVert u' \rVert \tag{2}\label{2}\\ \text{s.t.} \quad Au' \geq - Au_d -b $$
What is the benefit of this? Well now the objective function is simpler. Importantly, we know $\lVert u' \rVert \geq 0 \; \forall \, u'$ and $\lVert u' \rVert = 0$ only when $u' = 0$. Thus, if $u'=0$ satisfies the constraints, then $u'=0$ is the minimum. When does this happen? When $Au_d + b \geq 0 $.
For convenience, let's define $\Psi \equiv Au_d + b$. So now we have two cases: when $\Psi \geq 0$, we know the minimum. So let's tackle the other case of $\Psi < 0$. Looking at the problem now, it becomes $$ \text{min}_{u' \in \mathbb{R}^m} \lVert u' \rVert \tag{3}\label{3}\\ \text{s.t.} \quad Au' \geq - \Psi > 0 $$
If we think of $A^T$ and $u'$ as two geometric vectors of shape (3,1), then $$Au' = A^T \cdot u' = \lVert A^T \rVert \lVert u' \rVert \cos(A^T, u')$$
Now a vector $p$ can be divided into it's magnitude $\lVert p \rVert$ and unit direction $\hat{p} \;$ by $p = \lVert p \rVert \hat{p} $. Let's do this for $u'$, defining $x \equiv \lVert u' \rVert$ and $y \equiv \hat{u'}$ for visual clarity. Then, noting that $\cos(A^T, u') = \cos(A^T, \hat{u'})$, the optimization problem becomes, $$ \text{min}_{x \in \mathbb{R}_{\geq 0}, y \in \mathbb{R}^m} \; x \tag{4}\label{4}\\ \text{s.t.} \quad \lVert A^T \rVert x \cos(A^T, y) \geq - \Psi > 0 $$
Since we are considering the $\Psi < 0$, $\cos(A^T, y)$ must be strictly positive. Hence we can rearrange to get, $$ \text{min}_{x \in \mathbb{R}_{\geq 0}, y \in \mathbb{R}^m} \; x \tag{5}\label{5}\\ \text{s.t.} \quad x \geq - \frac{\Psi}{\lVert A^T \rVert \cos(A^T, y)} $$
Since $x$ and $y$ are independent variables, the solution to the above is $x^* = - \frac{\Psi}{\lVert A^T \rVert}$ with $\cos(A^T, y^*) = 1$. The latter means $y^* = \hat{A^T} = \frac{A^T}{\lVert A^T \rVert}$. Now going back to Eq. \eqref{3}, we can say the solution is $$u^{'*} = x^* y^* = -\frac{A^T \Psi}{\lVert A^T \rVert^2} = -\frac{A^T \Psi}{A^T \cdot A^T} = -\frac{A^T \Psi}{A A^T}$$
Thus we we have solved for the $\Psi < 0$ case. Combining the two cases, we get the solution to Eq. \eqref{2} as, $$ u^{'*} = \begin{cases} -\frac{A^T}{AA^T} \Psi & \text{if } \Psi < 0, \\ 0 & \text{otherwise} \end{cases} $$
Now using the variable transformation, $$ u^* = \text{argmin}_{u \in \mathbb{R}^m} \lVert u - u_d \rVert = u_d + \text{argmin}_{u' \in \mathbb{R}^m} \lVert u' \rVert = u_d + u^{'*}$$
Thus we can say the solution to our original problem Eq. \eqref{1} is, $$ u^* = u_d + u_s \\ u_s = \begin{cases} -\frac{A^T}{AA^T} \Psi & \text{if } \Psi < 0, \\ 0 & \text{otherwise} \end{cases} $$