3
$\begingroup$

How does one minimize the following function?

$$f(x,y) = |kx + ly + c|$$

where $x,y \in \mathbb N$.

$\endgroup$

closed as off-topic by TravisJ, choco_addicted, Leucippus, colormegone, John B Jun 4 '16 at 21:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – TravisJ, choco_addicted, Leucippus, colormegone, John B
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ obivously this function is minimal if $f(x,y) = 0$. So the question reduces to finding all $(x,y)$ such that $kx + ly + c = 0$. $\endgroup$ – user159517 Jun 4 '16 at 17:06
  • 2
    $\begingroup$ If x and y have to be integers, then f(x,y) will not always be minimized to 0. Example : k = 2, l= -2, c = -1. $\endgroup$ – Priyansh Goel Jun 4 '16 at 17:08
  • $\begingroup$ Why is the question downvoted? $\endgroup$ – Priyansh Goel Jun 4 '16 at 17:29
  • $\begingroup$ Have you considered adding constraints to make and equivalent constrained linear integer program? Otherwise, you have convex relaxations, so a simple branch and bound would work. Are you looking for/hoping for a closed form solution? $\endgroup$ – David Jun 4 '16 at 19:39
1
$\begingroup$

What is going on?

Let us first look at the real case:

2D view 3D view

We see that $f(x,y) = \lvert (k, l) (x,y)^\top + c \rvert$ results in a $V$ shaped surface. The reason is the "case distinction" of the absolute value function.

The valley line (the red line at $z=0$) is $$ \frac{1}{\sqrt{k^2 + l^2}} (k, l) (x,y)^\top = \frac{-c}{\sqrt{k^2 + l^2}} = d $$ where $(1/\sqrt{k^2 + l^2}) (k,l)^\top$ is a unit normal vector to the valley line (see the vector on the unit circle in the left graph) and $\lvert d \rvert$ is the distance to the origin (see the radius of the green circle and green sphere).

Discrete case:

For the discrete case we need to determine the intersections of $f$ with the grid $\mathbb{Z}^3$.

It should run down into coming up with the two planes that the $V$ is part of, stating the linear Diophantine equation there, and going for the smallest positive solution each, finally picking the smallest $z$-value of both cases.

Determining the planes:

The two linear Diophantine equations in three variables are $$ k x + l y - z = -c \\ k x + l y + z = -c $$ where the part intersecting with $f$ is characterized by $z \ge 0$.

Examples on how to solve such equations are given here and here.

$\endgroup$
  • $\begingroup$ So, what does it mean? $\endgroup$ – Priyansh Goel Jun 4 '16 at 17:37
  • $\begingroup$ I want to get an idea, what the parameters $k$, $l$, $c$ do influence. $\endgroup$ – mvw Jun 4 '16 at 17:38
  • $\begingroup$ Ohh okay. Suppose k,l,c are integers as large as 10^14 and greater than 0. $\endgroup$ – Priyansh Goel Jun 4 '16 at 17:40
  • $\begingroup$ What about this : kx+ly + c = P, and then kx+ly = P-c, and then see what is the minimum P-c which is divided by gcd(k,l)... Will this work? $\endgroup$ – Priyansh Goel Jun 4 '16 at 17:52
  • 1
    $\begingroup$ Your are faster asking than me trying to get a grip onto this problem :-) $\endgroup$ – mvw Jun 4 '16 at 17:53

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