What is the best way to solve this QP?

Question

I have been studying the following optimization problem in $x_0, \dots, x_{n-1}$

$$\begin{array}{ll} \text{minimize} & \frac{1}{2} \displaystyle\sum_{i=1}^{n-1} \left( x_{i-1} - x_i - y_i \right)^2\\ \text{subject to} & x_j \in [-\alpha_j, \alpha_j]\end{array}$$

where $y_1, \dots, y_n$ and $\alpha_0, \dots, \alpha_{n-1} \geq 0$ are constants.

What is the best way to solve this QP? Best in terms of computation effort (speed and memory requirements).

Thanks!

Answer 1

Alternating direction method of multipliers (ADMM) should solve this problem with linear convergence rate (for a given accuracy).

Define $z_i=x_i+\alpha_i$, $z_{i+n}=-x_i+\alpha_i$, where $z_i\geq0$ and a matrix $A\in\mathbb{R}^{2n\times n}$ such that $z=Ax$. So your problem has the following form:

\begin{equation} min_{x\in\mathbb{R}^n \\ z\in\mathbb{R}^{2n} \\ z=Ax}\sum_i(x_{i-1}-x_{i}-y_i)^2+\delta_{\mathbb{R}_+^{2n}}(z) \end{equation}

and apply ADMM (you can find here https://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf more details).

Answer 2

This is a constrained least-squares problem that can be written in the form

$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} & -\mathrm c \leq \mathrm x \leq \mathrm c\end{array}$$

where $\mathrm c > 0_n$ and $\rm A$ is the following $(n-1) \times n$ matrix

$$\mathrm A = \begin{bmatrix} 1 & -1 & & & \\ & 1 & -1 & & \\ & & \ddots & \ddots & \\ & & & 1 & -1\end{bmatrix}$$

Since this is a fat matrix, the linear system $\mathrm A \mathrm x = \mathrm b$ is underdetermined. Since $\rm A$ has full row rank, $\mathrm A \mathrm A^\top$ is invertible and, thus, the least-norm solution is

$$\mathrm x_{\text{LN}} := \mathrm A^\top \left( \mathrm A \mathrm A^\top \right)^{-1} \mathrm b$$

Since $\rm A 1_n = 0_{n-1}$, the $1$-dimensional null space is spanned by $1_n$. Thus, the solution set is the line

$$\left\{ \color{blue}{\mathrm x_{\text{LN}} + t 1_n} \mid t \in \mathbb R \right\}$$

Does this line intersect the feasible region? If $-\mathrm c \leq \mathrm x_{\text{LN}} \leq \mathrm c$, we can immediately conclude that the line does indeed intersect the feasible region. If not, we then have $n$ inequalities in parameter $t$

$$-\mathrm c \leq \mathrm x_{\text{LN}} + t 1_n \leq \mathrm c$$

If the line does intersect the feasible region, then the minimum of the original quadratic program is zero. If the line does not intersect the feasible region, then the minimum is positive. In this case, we can use, say, MATLAB's lsqlin to solve the quadratic program numerically.