My objective is linear

First, drop the restriction that $a$ and $b$ are positive and the inequality condition.

Now, all solutions satisfy:

$|a|$ and $|b|$ are consecutive Fibonacci numbers, such that $a$ is of odd index (1,2,5,13,34...) and $b$ is of even index (0,1,3,8,21,...). If $b>a$ , then $a$ and $b$ are of the same sign, and if $b<a$ , then $a$ and $b$ are of opposite sign.

To prove this, suppose it's not true, and take the solution with smallest $|a| + |b|$ - clearly neither of them can be zero, as the only such solution is (1,0) which is of the above form. It is also easy to check that $|a|$ and $|b|$ must both be greater than 3, by solving the quadratic in the cases that $|a|$ or $|b|$ are at most 3 and noting that all solutions are as above. Then, we can observe that in any solution with $|a|$ and $|b|$ greater than 3, $|a| < 2|b|$ and $|b| < 2|a|$ by supposing otherwise and noting that one side is too large, and that there is clearly no solution with $a = b$ .

(e.g. to prove $|a| < 2|b|$ , suppose otherwise. So $ab < 0$ , and then $a^2 \geq 2|ab| > 1 + b^2 + |ab|$ .)

Suppose that $|a| > |b|$ , and WLOG $b > 0$ since we can multiply both $a$ and $b$ by $-1$ at our leisure. Clearly, $ab$ must be less than 1 and so negative, so $a$ is negative. By Vieta's formula, there is another solution with the same value of $b$ , namely $(-(b+a),b)$ . Since $|a| < 2|b|$ , this is a smaller solution, so it must be of the above form by the induction hypothesis. However, that is impossible because that means that our original solution was also of the above form, contradicting our assumption. If $|a| < |b|$ , we run a similar argument, except we consider the equation as a quadratic in $a$ .

Therefore, all solutions are of the above form. Since $a$ and $b$ are positive, we have only the solutions in which $a = F_{2k-1}$ , $b = F_{2k}$ .

It is easy to prove by induction that $7b - 11a$ takes alternating values in the Lucas sequence, 1, 4, 11, 29, ..., and the largest value less than 1000 is 521.

Rearranging the second condition: $b^2 - a^2 = ab - 1$

We see that we must have $b>a$ , except for the trivial solution $1,0$ and $1,1$ .

Let $b = a+c$ . Substituting this in the above equation $\begin{aligned} (a+c)^2 - a^2 &= a(a+c)-1 \\ 2ac + c^2 &= a^2 + ac - 1 \\ a^2 - c^2 &= ac + 1 \end{aligned}$

Here we see, again that $a>c$ since $ac+1$ must be positive. So, subsituting $a = c+d$ in the last equation:

$\begin{aligned} (c+d)^2 - c^2 &= c(c+d) + 1 \\ 2cd + d^2 &= c^2 + cd + 1 \\ c^2 - d^2 &= cd - 1 \end{aligned}$

But this is actually the same equation that we started with. So we have shown that if a solution $(a,b)$ exists, then there is a smaller solution $(c,d)$ . In fact, if $(c,d)$ is a solution then the next-biggest solution is $(c+d, 2c+d)$ .

This means that we can work back from the smallest solution $c=1, d=1$ in order to generate all possible solutions. (The special case $(1,0)$ gives $(1,1)$ anyway so we don't have to worry about that).

This gives us $(1,1), (2,3), (5,8), (13, 21), ..$

i.e. $F_{2n-1}, F_{2n}$ .

To quickly find the solution from here we note that as $n$ gets large, the ratio between successive Fibonacci numbers approaches the golden ratio $\phi$ . So we would want $7 \phi a - 11a \lt 1000$ , i.e. $a(7 \phi - 11) < 1000$ , i.e. $a \lt 3066$ .

Checking a list of Fibonacci numbers shows that $a=1597, b=2584$ is the largest pair meeting this condition, and $7b - 11a$ here is $\boxed{521}$ .