Create a strictly increasing sequence following criterias

Question

Problem

Let y be a sequence of real numbers (of length $n$) bounded in the range [0,1]. I am trying to calculate the sequence x that respects the following criteria:

• x must be of length $n$ too
• x must also be bounded in the range [0,1]
• No two values of x must be closer to each other than $\epsilon$. That is $ \epsilon \le x_i - x_j \space \forall i \neq j$

So far, there are an infinite number of possible solutions. There is therefore a statistic to optimize

• The sum of square differences between x and y must be minimized. That is $\sum_{i=1}^n (x_i - y_i)^2$ must be minimized.

---

Case specific solution 1

$y = [0,\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{3}{4}]$

$x = [0,\frac{1}{2}-\epsilon,\frac{1}{2},\frac{1}{2}+\epsilon,\frac{3}{4}]$

Case specific solution 2

$y = [0,0,0]$

$x = [0,\epsilon,2\cdot \epsilon]$

Of course, there are cases where no solution exist. Typically, in the second example if $2\cdot \epsilon > 1$, then there are no solution.

Answer 1

Partial answer: So the problem maybe formulated as $$ \begin{align} \text{minimize}& & f(\mathbf{x}) &= \sum_{i=1}^n (x_i - y_i)^2 \\ \text{subject to}& & x_{j+1} - x_j &\geq \varepsilon, j = 1, 2, \ldots, n-1 \\ & & x_1 &\geq 0 \\ & & x_n & \leq 1 \\ \end{align}$$

As you have mentioned, for the feasibility of the problem, obviously one has to restrict that $$ \varepsilon \leq \frac {1} {n - 1}$$

Following https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

Note the following problem share the same optimal solution $\mathbf{x}^*$: $$ \begin{align} \text{maximize}& & -f(\mathbf{x}) &= -\sum_{i=1}^n (x_i - y_i)^2 \\ \text{subject to}& & \varepsilon - x_{j+1} + x_j &\leq 0, j = 1, 2, \ldots, n-1 \\ & & -x_1 &\leq 0 \\ & & x_n - 1 &\leq 0 \\ \end{align}$$

So now we have $n+1$ inequality constraints. Consider the necessary conditions in Karush–Kuhn–Tucker conditions: $$ \begin{align} \frac {\partial f} {\partial x_i} = 2(x_i - y_i) &= \begin{cases} -\mu_{i-1}+\mu_i, i = 2, 3, \ldots, n-1 \\ \mu_1 - \mu_n, i = 1 \\ -\mu_{n-1} +\mu_{n+1}, i = n \end{cases} \\ \mu_j &\geq 0, j = 1, 2, \ldots, n+1 \\ \mu_j(\varepsilon - x_{j+1} + x_j) &= 0, j = 1, 2, \ldots, n-1 \\ -\mu_n x_1 &= 0 \\ \mu_{n+1}(x_n - 1) & = 0 \end{align} $$

Sorry it is just the formulation. To solve this you need to check whether the inequalities constraints are active, and proceed to solve the system. See if I / someone have time to do this later.