1
$\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$
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$
  • $\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$ – Geoff Oxberry Apr 25 '14 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$ – thus spake a.k. Apr 26 '14 at 7:52
1
$\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$

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.