2

I have an optimisation problem where I wish to find the fitted values $(\hat{y}_1, \hat{y}_2, \dots, \hat{y}_n)$ that minimise a pairwise 'distance' to observed values $(y_1, y_2, \dots, y_n)$. I would like to penalise negative distances more than positive distances, that is $\hat{y}_i - y = d$ for some $d > 0$, should be penalised less than if $\hat{y}_i - y = -d$. Ideally I would like positive distances to be penalised like an $\ell^2$ norm. Something like $\exp(-|\hat{y}_i - y|) + |\hat{y}_i - y|^2$ gives a crude example of what I am after, except this is not minimised at $d = 0$.

Can you please suggest some good objective functions? (In this context, good means having as many of the following properties as possible: 1) easily differentiable, 2) computationally easy, 3) convex, 4) continuous.)

EDIT: improving on my crude example, consider the function

$$g(x) = \lambda \exp(-x) + x^2$$

This has a minimum at $x = r$ such that:

$$g'(r) = -\lambda\exp(-r) + 2r = 0.$$

The minimum at $x = r$ is easily found by any root solver. Then, the objective function $$f(x) = \lambda\exp(-(x+r)) + (x+r)^2 - g(r)$$ satisfies all the desired properties with the caveat about the imprecision of calculating $r$.

Are there any other functions like the above?

Alex
  • 293

2 Answers2

2

Any function $f(\max(0,x)) + g(\max(0,-x))$ where $g(x) > f(x)$ would work.

Since you want quadratic, $\max(0,x)^2 + 2\max(0,-x)^2$ for example. The quadratic programming formulation of this would be $s^2 + 2t^2$ with constraints $s\geq 0, s\geq x, t\geq 0, t\geq -x$ where $s$ and $t$ are new decision variables.

Johan Löfberg
  • 9,497
  • 1
  • 15
  • 15
  • I am bit worried that this leaves a discontinuity at the origin. – Alex Sep 27 '17 at 23:07
  • You remove the non-smoothness of the objective by reformulating it to a problem with linear inequalities to obtain a simple quadratic program. This is very standard. – Johan Löfberg Sep 28 '17 at 07:01
  • 1
    ...note though, the objective is not discontinuous, it is even once differentiable. As I said though, this is a non-issue once you model it through the epigraph reformulation leading to a QP – Johan Löfberg Sep 28 '17 at 07:03
  • and if you for some reason absolutely don't want to have a QP (which you do want, as it basically is one of the easiest and most researched problem to solve) but want to arrive at a unconstrained (smooth) nonlinear program, you can always use the approximation $\max(x,y) \approx \log(\exp(rx) + \exp(ry))/r$ for large $r$. People spend a lot of effort to derive LPs and QPs though so this would be weird in my opinion though – Johan Löfberg Sep 28 '17 at 07:07
1

First and foremost, there are potentially many solutions, each of which has its own advantages and disadvantages.

One possibility is to use the penalty method (https://en.wikipedia.org/wiki/Penalty_method).

For example, you can first formulate the problem into a constrained optimization problem: $$ \min \sum_i |ŷ_i−y_i|^2 $$

$$ \text{such that:} \quad y_i - ŷ_i \leq 0. $$

Then, use a penalty function such that $$ p_i(y_i,ŷ_i) = \max (0,y_i - ŷ_i)^2. $$

The below objective function is one answer:

$$ f(y_1,...,y_n) = \sum_i |ŷ_i−y_i|^2 + \sum_i \lambda_i \, p_i(y_i,ŷ_i) $$

where $\lambda_i$ are positive constants chosen by you to control the penalty terms, the bigger they are the more the unwanted cases are penalized. One can use a log barrier function too (https://en.wikipedia.org/wiki/Barrier_function) but I would go for the penalty approach.

MMM
  • 537