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).


  • $\begingroup$ For numerical algorithm, I think interior points is a good numerical algorithm. $\endgroup$ – Youem Aug 1 '17 at 18:49
  • $\begingroup$ small typo: $\{y_i\} = \{y_1, y_2,...,y_{n-1}\}$ $\endgroup$ – CuriousGeorge Aug 1 '17 at 18:49
  • $\begingroup$ $y_n$ is not used. $\endgroup$ – Rodrigo de Azevedo Aug 1 '17 at 19:16

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).

  • $\begingroup$ From a numerical point of view, I think an interior point method would be much faster than ADMM. $\endgroup$ – CuriousGeorge Aug 2 '17 at 17:36

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.

  • $\begingroup$ Note that $\rm A$ is the oriented incidence matrix of a linear graph on $n$ nodes. $\endgroup$ – Rodrigo de Azevedo Aug 2 '17 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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