I am at a point in n-dimensional space $X^0$ and it costs me to move to $X_i$ with varying cost depending on direction $\Sigma_i c_i |X_i-X^0_i|$.

But, it's good for me to move closer to a target point $X^*$ because I'm penalized quadratically for being away from the target $d \Sigma_i |X_i-X^*_i|^2$.

I know the absolute values make this problematic but is there a way to globally minimize the total cost function for $X_i$? (algorithmically?)

$Cost =\Sigma_i c_i |X_i-X^0_i| + d \Sigma_i |X_i-X^*_i|^2$

  • 1
    $\begingroup$ It seems like you're asking an algorithms question - in which case you'd get better answers over at SO instead. $\endgroup$ – B. Mehta May 8 '18 at 1:14
  • $\begingroup$ Sure I'll give it a shot. $\endgroup$ – rhaskett May 8 '18 at 1:16
  • 1
    $\begingroup$ The cost function I see is plainly sum of functions each depending on a single (and unique) coordinate. If that is it, it may perfectly well be optimized coordinate-wise. And, by the way, why this is tagged 'non-convex optimization'? ;) $\endgroup$ – metamorphy May 8 '18 at 1:40
  • $\begingroup$ @rhaskett: You might also want to take a look at this. $\endgroup$ – VHarisop May 8 '18 at 1:52
  • 1
    $\begingroup$ Minimizing absolute value is expressible as a linear problem: $x\geq |y|$ is the same as $x\geq y \geq -x$. The square can be handled with a second-order cone. $\endgroup$ – Michal Adamaszek May 8 '18 at 6:54

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.