1
$\begingroup$

I have a math problem and I would like to solve it, but I'm not sure what area to look under.

Basically given $x \in \mathbb{R}^k$ (for my purposes, $x \in \mathbb{Q}^k$ since I am using a computer) and $L \geq 0 $, we want to find $n \in \mathbb{N}^k$ such that $n^Tx \geq L$ and $n$ is "minimal". Here minimal means that if $m^Tx \geq L$, then $|n| \leq |m|$ where $|n| = \sum_{i=1}^kn_i$. (this is not "minimal" in the traditional sense since there is no partial order due to a lack of anti-symmetry, but I couldn't think of another word to use)

So would this fall under integer programming where we want to minimize $\sum_{i=1}^kn_i$ under the constraint $\sum_{i=1}^k x_i n_i \geq L$, or would this not count as integer programming since $x \in \mathbb{R}^k$?

Anyways, does this sound familiar to anyone? I just need a direction to google.

$\endgroup$
  • 2
    $\begingroup$ I think you need to come up with exactly what “minimal” means before you can proceed further $\endgroup$ – David M. Mar 20 at 0:11
  • $\begingroup$ If $k=2$ and $x=(1,1)$ and $L=7$, then which of the possibilities $(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)$ is the minimal $n$? $\endgroup$ – Gerry Myerson Mar 20 at 0:13
  • 1
    $\begingroup$ I guess this would be integer programming with: minimize $\sum_{i=1}^k n_i$ with the constraint $\sum_{i=1}^k x_i n_i \geq L$ $\endgroup$ – Ceeerson Mar 20 at 3:36
  • $\begingroup$ See: ntrl.ntis.gov/NTRL/dashboard/searchResults/titleDetail/… for a variety of algorithms that may be helpful. $\endgroup$ – O. S. Dawg Mar 23 at 17:31
1
$\begingroup$

Solutions to the equation $y^Tx\geq L$ for $y\in \mathbb{R}^k$ is a half space $H$ with the vector $Lx/(x^Tx)$ lying on the boundary, with the interior of the half space in the normal direction $x$ from there. A difficulty in this situation is how the boundary of the half space sits with respect to the integer lattice... since you are allowing $x$ to have real coefficients, it may potentially avoid all integer points!

One approach would be to approximate $x$ by a vector of $\mathbb{Q}^k$, giving an actual integer linear program once one clears out the denominators. Either you can do this for a sequence of better approximations and stop once the minimal solution seems good enough, or it might be possible to calculate how good of a solution one would need to guarantee the approximated half space contains exactly the same points of $\mathbb{N}^k$. I have not read it, but this thesis appears to have quite a lot about these sorts of approximations: Vaughan Clarkson, "Approximation of Linear Forms by Lattice Points". One keyword appears to be "simultaneous Diophantine approximation."

There is a chance that your $x$ is already in $\mathbb{Q}^k$, for instance if you are on a computer with a floating-point representation of the vector, in which case approximation might not be necessary.


I'm going to leave here my own attempt at a solution. First of all, the $L=0$ case has the minimal solution $n=0$, so we may assume $L>0$ and then divide $x$ through by $L$ to simplify the problem to $y^Tx\geq 1$. Let $f(n)=\sum_{i=1}^kn_i$ be your objective function, which of course is $f(n)=\mathbf{1}^Tn$ with $\mathbf{1}$ the all-ones vector.

The next observation is that we can assume $x_i>0$ for each $i$. If not, then by taking any solution to $n^Tx\geq 1$ we can get another solution by setting $n_i$ to $0$, possibly decreasing $f(n)$ in the process, and then removing dimension $i$ from the problem.

Suppose $e\in \mathbb{R}^k_{\geq 0}$ is a vector of non-negative entries. The inequality $n^T(x+e)\geq 1$ has all the solutions to $n^Tx\geq 1$ plus possibly some more. Given an integer $N\geq 1$, we can form the rational approximation $x^N\in\mathbb{Q}^k_{>0}$ given by $x^N_i=\lceil Nx_i\rceil/N\geq x_i$, hence $n^Tx^N\geq 1$ has all the solutions to $n^Tx\geq 1$.

Let $i$ be such that $x_i$ is largest, and let $M=\lceil 1/x_i\rceil$. We can see there is an $f$-minimal solution within the set $\{0,1,2,\dots,M\}^k$, since $n$ given by $n_i=M$ and $n_j=0$ for $j\neq i$ is a solution with $f(n)=M$. So, there are at most $(M+1)^k$ solutions to consider. Finiteness implies that there is some large enough $N$ such that $n^Tx^N\geq 1$ has the same solutions as $n^Tx\geq 1$, when restricted to $n\in \{0,1,2,\dots,M\}^k$. In particular, the sets $S_N\subseteq \{0,1,2,\dots,M\}^k$ of solutions to $n^Tx^N\geq 1$ satisfy $S_1\supseteq S_2\supseteq S_3\supseteq\cdots$, so it must eventually stabilize.

Since $x^N_i-x_i<\frac{1}{N}$, we have for a minimal solution $n$ that \begin{align} n^Tx^N &= \sum_{i=1}^k n_i x_i^N\\ &< \sum_{i=1}^k n_i (x_i+\frac{1}{N}) \\ &= \sum_{i=1}^k n_i x_i + \frac{1}{N}\sum_{i=1}^k n_i \\ &= n^Tx + \frac{1}{N} f(n)\\ &\leq n^Tx + \frac{M}{N}. \end{align} So $n^Tx^N\geq 1$ implies $n^Tx\geq 1-\frac{M}{N}$. This new inequality defines a half space $H_N\supset H$; letting $S'_N=H_N\cap\{0,1,2,\dots,M\}^k$, we have $\require{AMScd}$ \begin{CD} S_1 @>\supseteq>> S_2 @>\supseteq>>\cdots \\ @VV\subseteq V @VV\subseteq V \\ S_1' @>\supseteq>> S_2' @>\supseteq>>\cdots \end{CD} If we can estimate some $N$ such that $S'_N = H\cap \{0,1,2,\dots,M\}^k$, which is a point from which the bottom sequence stabilizes, then the top sequence has stabilized as well. (Geometrically, inside of $\mathbb{R}^k_{\geq 0}$, we have that the boundary of rational approximation half space lies between the boundaries of $H$ and $H_N$.)

This is where I got stuck: we need to know some $\epsilon>0$ distance we can translate $H$ in the $-x$ direction without its boundary colliding with the integer lattice within $\mathbb{R}^k_{\geq 0}$. Once we have such an $\epsilon$, we can calculate a sufficient $N$ and then do integer programming with the corresponding rational approximation of the inequality.

There is still an algorithm here, however. Choose an $N$, do the corresponding integer program to get a preliminary solution $n'$. If $n'$ does not satisfy $(n')^Tx\geq 1$, then increase $N$ to a value where $n'$ does not satisfy $(n')^Tx^N\geq 1$ and repeat. Eventually $n'$ will be a solution to the unapproximated problem. Since $n'$ is $f$-minimal for $n^Tx^N\geq 1$, it is $f$-minimal for $n^Tx\geq 1$ as well. Without the $\epsilon$ estimate, though, the algorithm is merely guaranteed to terminate.

By the way, it is conceivable that there is a method that could use less-good approximations of the inequality with a smaller $N$ by somehow taking more advantage of the particular objective function.

$\endgroup$
  • $\begingroup$ Hey thanks for going above and beyond here. I feel bad because for my purposes $x \in \mathbb{Q}^k$ because I am using a computer :( So sorry if I wasted too much of your time, I'll fix this in my question and hopefully never forget the difference that this makes. Anyways, clearing denominators is a good idea, I will do that to get an integer linear program. Thanks so much! $\endgroup$ – Ceeerson Mar 20 at 17:18
  • $\begingroup$ @Ceeerson Depending on your application, it seems rational approximations of your rational $x$ could potentially give a faster running time, if that matters. In any case, it's an interesting problem to think about so don't feel bad! $\endgroup$ – Kyle Miller Mar 20 at 17:24
0
$\begingroup$

It was pointed out to me that there is a much better solution than anything outlined in my other answer, though perhaps not a solution you intended.

Consider a solution $n^Tx\geq L$, and suppose that $i$ is such that $x_i\geq x_j$ for all $j$; by rearranging let us assume $i=1$. As it was pointed out, we can assume $x_1>0$. Then, there is a corresponding solution $n'=(\sum_i n_i,0,0,\dots,0)$ with the same value of the objective function. Since $(\lceil L/x_1\rceil,0,0,\dots,0)$ is also a solution, we can conclude that $\lceil L/x_1\rceil$ is the minimum value for the objective function, and furthermore that $(\lceil L/x_1\rceil, 0,0,\dots,0)$ is a minimizing solution.

I'm leaving the other answer up because it might help in the case of multiple inequalities or different (linear) objective functions.

$\endgroup$
  • $\begingroup$ Ooooh I was worried that the lack of constraints, compared to a usual linear program, might lead to no minimal vector or a trivial one. Now that it's written out in front of me it makes sense that you would put all necessary eggs into the best basket, so to speak. In truth My problem stems from a probability model that I have, which I will later take into account the desire to minimize variance, so I'll see where that takes me, but thanks for the response, this all has been helpful. $\endgroup$ – Ceeerson Mar 20 at 18:38

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.