Lochte, Feigen och två andra medlemmar i det amerikanska simlaget sa att de hade blivit rånade under pistolhot i en taxi i Rio.
Men polisen säger att deras redogörelse om när de anlände till den olympiska byn inte fyrkantig med CCTV inspelningar.
Lokala medier rapporterar att Lochte lämnade Brasilien innan ordern utfärdades.
Hans Twitter-konto visar bilder på honom när han kom tillbaka till USA på måndag.
Lochte simmade i två evenemang på Rio Games, vinna guld i 4x200m freestyle reläet.
Feigen, som fortfarande tros vara i Brasilien, vann guld i 4x100m freestyle reläet.
Berättelser om vad som hände med simmarna har varit förvirrande från början.
Lochte berättade först US TV-nätverket NBC om det men International Olympic Committee talesman Mark Adams sade rapporter om rånet var "absolut inte sant".
Den amerikanska olympiska kommittén (USOC) bekräftade senare simmarnas räkenskaper.
Lochte själv berättade för polisen att han och lagkamraterna James Feigen, Gunnar Bentz och Jack Conger alla hade deltagit i en fest i det franska olympiska lagets gästvänlighet hus på lördag kväll.
Han sade att under hemresan till den olympiska byn stoppades taxin av män som utgav sig för att vara poliser.
En av männen höll en pistol mot hans huvud, sade Lochte, och rånade honom på hans pengar och personliga tillhörigheter.
Polisen har inte hittat några bevis för rånet.
De pekar också på "inkonsistenser" i simmarnas räkenskaper.
Lochte och Feigen berättade för polisen att de och deras simmare hade återvänt till den olympiska byn kl. 04:00 lokal tid (08:00 GMT).
Men CCTV-inspelningar verkar visa att simmarna återvänder till den olympiska byn klockan 07:00 lokal tid.
De kan ses sätta sina tillhörigheter genom en metalldetektor vid ingången till byn på vad som verkar vara ett lugnt sätt.
Polisen säger att de inte har kunnat spåra föraren som simmarna sa körde dem tillbaka till byn.
De sade också att Feigen och Lochte gav olika berättelser om hur många män som rånade dem.
Utredare har begärt en husrannsakan för de rum som simmarna bodde i för att undersöka Feigens mobiltelefon.
De sa att de ville spåra simmarna på lördag kväll och söndag morgon.
Den amerikanska olympiska kommittén (USOC) bekräftade att den brasilianska polisen hade sökt pass och ytterligare vittnesmål från Lochte och Feigen.
I ett uttalande sade kommittén: "Simlaget flyttade ut ur byn efter deras tävling, så vi kunde inte göra idrottarna tillgängliga."
I uttalandet sades att USOC "inte gör idrottare reseplaner offentliga och därför inte kan bekräfta idrottarnas nuvarande plats" men att de skulle samarbeta med de brasilianska myndigheterna.
En domare i Brasilien har utfärdat en order som hindrar amerikanska simmare Ryan Lochte och James Feigen från att lämna landet efter att polisen förhört deras bevis i ett rånfall.