I have a large dataset consisting of an ordered categorical variable that is broken into exclusive binary vectors, one for each level of the category.

I would like to find a linear combination of these binary vectors to minimize a loss function. However, I would like the coefficients to be monotonically increasing.

Is there an optimization method that can take as constraints the values of the parameters it is trying to optimize? In my case each parameter value should be bounded between its neighboring parameters. The only literature I can find describes absolute bounds on the parameters, not relative ones.

I have looked at various implementations of the Hooke & Jeeves algorithm, but none of them support this feature.


If I'm understanding what you want correctly, you can phrase this as a set of linear constraints: you have that $$ x_1 \le \dots \le x_i \le \dots \le x_n $$ if and only if \begin{gather} x_1 - x_2 \le 0 \\ x_2 - x_3 \le 0 \\ \vdots \\ x_{n-1} - x_n \le 0 ,\end{gather} or in matrix notation $$ \underbrace{\begin{bmatrix} 1 &-1 & 0 & \dots & 0 & 0\\ 0 & 1 &-1 & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 &-1 \end{bmatrix}}_{(n-1) \times n} \underbrace{\begin{bmatrix}x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix}}_{n \times 1} \le \underbrace{\begin{bmatrix}0 \\ 0 \\ \vdots \\ 0\end{bmatrix}}_{(n-1) \times 1} .$$

Many optimization algorithms allow for these kinds of constraints.

  • 1
    $\begingroup$ This was the nudge I needed. I didn't realize these constraints could be expressed in such a format. $\endgroup$
    – Zelazny7
    Jul 20 '17 at 17:10

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.