Non-metric MDS gives nonsense results on the Digits dataset

### Describe the bug

I am running metric and nonmetric MDS on the Digits dataset, and obtain nonsense results with `metric=False`. At the same time, my understanding is that non-metric MDS is more flexible and should not yield worse results compared to metric MDS. Is my understanding wrong, or does it suggest some problems with the non-metric MDS implementation?

### Steps/Code to Reproduce

```Python
%matplotlib notebook

import pylab as plt
import numpy as np
from sklearn.datasets import load_digits
from sklearn.manifold import MDS

digits = load_digits()
X, y = digits.data, digits.target

Z1 = MDS(n_components=2, n_init=1, random_state=42).fit_transform(X)
Z2 = MDS(n_components=2, n_init=1, random_state=42, metric=False).fit_transform(X)

titles = ['Metric MDS', 'Non-metric MDS']

fig, axs = plt.subplots(nrows=1, ncols=2, figsize=(6, 3), layout='constrained')

for i,Z in enumerate([Z1, Z2]):
    ax = axs.ravel()[i]
    
    ax.set_aspect('equal', 'datalim')
    
    ind = np.random.permutation(X.shape[0])
    ax.scatter(*Z[ind].T, s=3, color=plt.cm.Dark2(y)[ind])

    ax.set_xticks([])
    ax.set_yticks([])
    for sp in ax.spines:
        ax.spines[sp].set_visible(False)
        
    ax.set_title(titles[i])
    
fig.savefig('digits-embed-mds-nonmetric.png', dpi=300)
```

### Expected Results

Non-metric MDS giving something sensible.

### Actual Results

![digits-embed-mds-nonmetric](https://github.com/scikit-learn/scikit-learn/assets/8970231/aa6af88a-75d0-4ef2-ab6e-6482c4df5ae8)


### Versions

```shell
System:
    python: 3.7.9 (default, Aug 31 2020, 12:42:55)  [GCC 7.3.0]
executable: /home/dmitry/anaconda3/bin/python
   machine: Linux-5.15.0-76-generic-x86_64-with-debian-bullseye-sid

Python dependencies:
          pip: 22.3.1
   setuptools: 65.6.3
      sklearn: 0.24.1
        numpy: 1.21.5
        scipy: 1.7.3
       Cython: 0.29.32
       pandas: 1.3.5
   matplotlib: 3.5.2
       joblib: 1.1.1
threadpoolctl: 2.2.0

Built with OpenMP: True
```

COMMENT:
> I really am not sure whether this is just an example of how constrained systems can outperform under-constrained systems, or if there is something operatively incorrect about the non-metric MDS implementation, but I lean towards the prior.

No, I'm actually pretty sure it's the latter.

First, metric MDS takes 756 iterations to converge. Default is max_iter=300, but I checked with 
```
Z1 = MDS(n_components=2, n_init=1, random_state=42, metric=True, verbose=2, max_iter=1000).fit_transform(X)
```
But non-metric MDS stops after two iterations
```
Z2 = MDS(n_components=2, n_init=1, random_state=42, metric=False, verbose=2).fit_transform(X)
```
Here is the full output:
```
it: 0, stress 88230.49297090062
it: 1, stress 73509.74850291299
it: 2, stress 73810.46739972188
breaking at iteration 2 with stress 73810.46739972188
```
This is very fishy. The loss goes up, so it stops the iterations.

Second, let's initialize non-metric optimiazation with the result of metric optimization:
```
Z3 = MDS(n_components=2, n_init=1, random_state=42, metric=False, verbose=2).fit_transform(X, init=Z1)
```
Now it also converges in two iterations, but achieves much lower loss:
```
it: 0, stress 3355940054.205797
it: 1, stress 33534.27419788723
it: 2, stress 33605.33211344484
breaking at iteration 2 with stress 33605.33211344484
```
This is also very fishy -- that's 2x lower loss than the default optimization run.
 
![digits-embed-mds-nonmetric-2](https://github.com/scikit-learn/scikit-learn/assets/8970231/4b35531d-7424-45b5-aa67-9b081f3ef531)

Labels: Bug, Needs Investigation