1
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ For numerical algorithm, I think interior points is a good numerical algorithm. $\endgroup$
    – Kroki
    Commented Aug 1, 2017 at 18:49
  • $\begingroup$ small typo: $\{y_i\} = \{y_1, y_2,...,y_{n-1}\}$ $\endgroup$ Commented Aug 1, 2017 at 18:49
  • $\begingroup$ $y_n$ is not used. $\endgroup$ Commented Aug 1, 2017 at 19:16

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Note that $\rm A$ is the oriented incidence matrix of a linear graph on $n$ nodes. $\endgroup$ Commented Aug 2, 2017 at 12:58
0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .