This paper presents new methods to find the optimal non-least-squares (NLS) estimator that minimizes the integrity risk in Receiver Autonomous Integrity Monitoring (RAIM). These methods aim at lowering the integrity risk in exchange for a slight increase in nominal positioning error. A first algorithm is formulated as a multi-dimensional minimization problem, which directly minimizes integrity risk, but can only be solved using a time-consuming iterative process involving the integration of a bivariate normal distribution. Then, parity space representations are exploited to develop a new computationally-efficient, near-optimal NLS-estimator design method, which uses a straightforward line-search process. Performance analyses for an example multi-constellation Advanced RAIM (ARAIM) application show that this new method enables significant integrity risk reduction, even in real-time implementations where computational resources are limited.