2
$\begingroup$

Are there optimizers where it is possible to specify ordinal ranking of parameters?

Assume that I have a function of three parameters $f(\theta_1, \theta_2, \theta_3)$. Are there optimizers such that I can specify $$ {\arg\min}_{\theta_1 > \theta_2 >\theta_3}f(\theta_1, \theta_2, \theta_3) $$

Assume that $f$ is smooth ($n$-th order differentiable in each of the parameters).

$\endgroup$

2 Answers 2

2
$\begingroup$

If you relax the strictness criterion, then yes, you could pose your question as a constrained optimization problem:

\begin{align} & \min_{\theta_{1}, \theta_{2}, \theta_{3}} f(\theta_{1}, \theta_{2}, \theta_{3}) \\ \textrm{s.t.} & \theta_{1} \geq \theta_{2} \geq \theta_{3}. \end{align}

To approximate $\theta_{1} > \theta_{2} > \theta_{3}$, you could add a parameter $\varepsilon > 0$ such that:

\begin{align} & \min_{\theta_{1}, \theta_{2}, \theta_{3}} f(\theta_{1}, \theta_{2}, \theta_{3}) \\ \textrm{s.t.} & \theta_{1} \geq \theta_{2} + \varepsilon \\ & \theta_{2} \geq \theta_{3} + \varepsilon \end{align}

These variants of your constraints are linear, so provided that your function $f$ is well-behaved (smooth, easy to calculate, easy to compute derivatives, derivatives are well-conditioned, etc.), any constrained optimization solver should be able to solve your problem without issue.

$\endgroup$
1
$\begingroup$

An approach I often use when applying unconstrained optimisation algorithms to constrained problems is to transform the parameter space such that the constraints cannot be violated.

For your problem I would define

$$ g(x_1, x_2, x_3) = f(x_1, x_1-x_2^2, x_1-x_2^2-x_3^2) $$

then solve

$$ \arg \min g(x_1, x_2, x_3) $$

and finally recover the solution to the original problem with

$$ \begin{align*} \theta^*_1 &= x^*_1\\ \theta^*_2 &= x^*_1 - x^{*2}_2\\ \theta^*_3 &= x^*_1 - x^{*2}_2 - x^{*2}_3 \end{align*} $$

Of course this results in $\theta^*_1\geq\theta^*_2\geq\theta^*_3$ which isn't quite what you asked for. To get a strict ranking you'll need to bump $x_1-x^2_2$ and $x_1-x^2_2-x^2_3$ down at the last digit of precision.

$\endgroup$
2
  • $\begingroup$ In general, I would not advise this approach. If $f$ is linear, your transformation results in a nonlinear program; constrained LPs are generally regarded as easier to solve. The resulting transformation also may affect convexity and may affect conditioning of the Hessian. Constrained algorithms generally handle linear constraints well (they're also fairly easy to project out anyway). $\endgroup$ Commented Apr 25, 2014 at 21:51
  • $\begingroup$ @GeoffOxberry: I was assuming that $f$ was non-linear. This is the approach that I use with algorithms like Nelder-Mead or simulated annealing. $\endgroup$ Commented Apr 26, 2014 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.