Inequality-constrained least-squares

Question

Consider

$$\begin{array}{ll} \text{minimize} & \frac{1}{2}\displaystyle\sum_{i=1}^{n} (x_i- \bar{x_i})^2\\ \text{subject to} & x_1 \geq x_2 \geq \cdots \geq x_n\end{array}$$

where $\bar{x_i}$ are given constants. Find and explicit form of for the dual problem for all $n$.

Answer 1

I made an attempt. Let us try and solve for $n=4$ and extend it to all $n$. $$L(x,\lambda)= \frac{1}{2}\big[(x_1- \bar{x_1})^2+(x_2- \bar{x_2})^2+(x_3- +\bar{x_3})^2+(x_4- \bar{x_4})^2\big]- \lambda_1(x_1-x_2)- \lambda_2(x_2-x_3)- \lambda_3(x_3-x_4)$$

First order necessary conditions are,

$\begin{array}{ll} \frac{\partial L}{\partial x_1}=x_1-\bar{x_1}-\lambda_1=0 \\ \frac{\partial L}{\partial x_2}=x_2-\bar{x_2}+\lambda_1- \lambda_2=0 \\ \frac{\partial L}{\partial x_3}=x_3-\bar{x_3}-\lambda_2 - \lambda_3=0 \\ \frac{\partial L}{\partial x_4}=x_4-\bar{x_4}-\lambda_3=0 \end{array}$

We then substitute the values for $x_i$ in terms of $\bar{x_i} \text{and} \lambda_j$ in the lagrangian.

Note the dual function is $$\max_{\lambda \geq 0} L(x,\lambda)$$

On doing some simplification,(lot of the terms cancel out) I arrive at the dual function to be $$\Theta(\lambda)= \lambda_1(\bar{x_2}-\bar{x_1})+\lambda_2(\bar{x_3}-\bar{x_2})+\lambda_3(\bar{x_4}-\bar{x_3})$$

Extending this to the case for all n, we have the dual problem to be, $$\max_{\lambda_i \geq 0}\Theta(\lambda)= \sum_{i=1}^{n-1}\lambda_i(\bar{x}_{i+1}-\bar{x_{i}})$$