1
$\begingroup$

Problem

Let y be an array of float numbers (of length $n$) bounded in the range [0,1]. I am trying to compute the array 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 though.

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

In short

I want to find x given y such 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 \\ & & min(x) &\geq 0 \\ & & max(x) & \leq 1 \\ \end{align}$$


Expected Output 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}]$

Expected Output 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. In such case, the program should throw an error.

Can you give me advice on how to go about solving this problem?

$\endgroup$
  • 1
    $\begingroup$ Not clear what you are asking for. "Strictly increasing" seems an important technical term; however, it only appears in the title. $\endgroup$ – hengxin Jun 4 '16 at 8:11
  • $\begingroup$ 1. Are the y's strictly increasing? Are the x's required to be strictly increasing? As it stands it is not clear what the task is, so the question does not seem answerable in its current form. Please edit the question to clarify what you are asking. 2. What approaches have you considered? What have you tried? Have you tried taking partial derivatives? Have you tried dynamic programming? $\endgroup$ – D.W. Jun 4 '16 at 10:25
  • $\begingroup$ Sorry about that. I rephrased the question while writing and forgot about the title. After sorting, "x" is strictly increasing. It is a logical consequence of the third criteria. I removed this term from the title as it only bring confusion. Is the question easier to understand nwo? $\endgroup$ – Remi.b Jun 4 '16 at 15:19
  • $\begingroup$ @D.W. Please see the post again and especially the short version of the problem. I think it should make sense. I removed the term strictly increasing from the title as it was just an extra term that could bring confusion. $\endgroup$ – Remi.b Jun 4 '16 at 15:33
  • 1
    $\begingroup$ That looks like how a mathematician would write down a non-linear optimization problem. I'd pick up a textbook on that topic. $\endgroup$ – Raphael Jun 4 '16 at 15:39

Your Answer

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

Browse other questions tagged or ask your own question.