[Math] Minimize the Squared $ {L}_{2} $ Norm of a Vector With Linear Equality and Inequality Constraints

convex optimizationlinear algebranonlinear optimizationoptimizationquadratic programming

Given the following Convex Optimization Problem:

The Problem

\begin{align*}
\text{minimize} & \quad & \left\| x \right\|_{2}^{2} \\
\text{subject to} & \quad & x – a \leq 0 \\
\text{} & \quad & \boldsymbol{1}^{T} x = b
\end{align*}

Below I solved it using 2 methods:

  1. The KKT Method.
  2. The Dual Problem Method.

The full code is in my Mathematics Q2375676 GitHub Repository.
The code is validated using CVX.

Best Answer

Dual Problem Solution

The Lagrangian is given by:

$$ L \left( x, \lambda, \nu \right) = {x}^{T} x + {\lambda}^{T} \left( x - a \right) + \nu \left( \boldsymbol{1}^{T} x - b \right) = {x}^{T} x + \left( \lambda + \nu \boldsymbol{1} \right)^{T} x -{\lambda}^{T} a - \nu b $$

The Dual Function is given by:

$$ g \left( \lambda, \nu \right) = \inf_{x} L \left( x, \lambda, \nu \right) $$

Looking at the term related to $ x $:

$$ \inf_{x} {x}^{T} x + \left( \lambda + \nu \boldsymbol{1} \right)^{T} x $$

Which is a quadratic form of $ x $ with its minimizer given by: $$ {x}^{\ast} = -\frac{1}{2} \left( \lambda + \nu \boldsymbol{1} \right) $$

Its minimum given by $$ {{x}^{\ast}}^{T} {x}^{\ast} + \left( \lambda + \nu \boldsymbol{1} \right)^{T} {x}^{\ast} = -\frac{1}{4} \left( \lambda + \nu \boldsymbol{1} \right)^{T} \left( \lambda + \nu \boldsymbol{1} \right) $$

Hence the Dual Problem is given by:

\begin{align*} \text{maximize} & \quad & -\frac{1}{4} \left( \lambda + \nu \boldsymbol{1} \right)^{T} \left( \lambda + \nu \boldsymbol{1} \right) - {\lambda}^{T} a - \nu b \\ \text{subject to} & \quad & \lambda \succeq 0 \end{align*}

The problem is Concave in $ \left( \lambda, \nu \right) $ hence it is a convex problem.
It can be solved by a Quadratic Programming as:

$$ \left( \lambda + \nu \boldsymbol{1} \right)^{T} \left( \lambda + \nu \boldsymbol{1} \right) = {\left\| E v \right\|}_{2}^{2} = {v}^{T} {E}^{T} E v = {v}^{T} H v $$

Where $ v = {\left[ \lambda, \nu \right]}^{T}, \; E = \left[ I, \boldsymbol{1} \right], \; H = {E}^{T} E $. Then the problem becomes:

$$ \begin{align*} \text{minimize} & \quad & \frac{1}{4} {v}^{T} H v + {v}^{T} f \\ \text{subject to} & \quad & A v \preceq 0 \end{align*} $$

Where $ A = - \left[ I, \boldsymbol{0} \right], \; f = {\left[ a, b \right]}^{T} $.

The above can directly solved by MATLAB's quadprog(). Then $ {x}^{\ast} = -0.5 E v $.