  Studies of the most luminous quasars at high redshift directly probe the
evolution of the most massive black holes in the early Universe and their
connection to massive galaxy formation. However, extremely luminous quasars at
high redshift are very rare objects. Only wide area surveys have a chance to
constrain their population. The Sloan Digital Sky Survey (SDSS) has so far
provided the most widely adopted measurements of the quasar luminosity function
(QLF) at $z>3$. However, a careful re-examination of the SDSS quasar sample
revealed that the SDSS quasar selection is in fact missing a significant
fraction of $z\gtrsim3$ quasars at the brightest end. We have identified the
purely optical color selection of SDSS, where quasars at these redshifts are
strongly contaminated by late-type dwarfs, and the spectroscopic incompleteness
of the SDSS footprint as the main reasons. Therefore we have designed the
Extremely Luminous Quasar Survey (ELQS), based on a novel near-infrared JKW2
color cut using WISE AllWISE and 2MASS all-sky photometry, to yield high
completeness for very bright ($m_{\rm{i}} < 18.0$) quasars in the redshift
range of $3.0\leq z\leq5.0$. It effectively uses random forest machine-learning
algorithms on SDSS and WISE photometry for quasar-star classification and
photometric redshift estimation. The ELQS will spectroscopically follow-up
$\sim 230$ new quasar candidates in an area of $\sim12000\,\rm{deg}^2$ in the
SDSS footprint, to obtain a well-defined and complete quasars sample for an
accurate measurement of the bright-end quasar luminosity function at $3.0\leq
z\leq5.0$. In this paper we present the quasar selection algorithm and the
quasar candidate catalog.
