Geometry optimization has become an essential part of quantum-chemical computations, largely because of the availability of analytic first derivatives. Quasi-Newton algorithms use the gradient to update the second derivative matrix (Hessian) and frequently employ corrections to the quadratic approximation such as rational function optimization (RFO) or the trust radius model (TRM). These corrections are typically carried out via diagonalization of the Hessian, which requires O(N-3) operations for N variables. Thus, they can be substantial bottlenecks in the optimization of large molecules with semiempirical, mixed quantum mechanical/molecular mechanical (QM/MM) or linearly scaling electronic structure methods. Our O(N-2) approach for solving the equations for coordinate transformations in optimizations has been extended to evaluate the RFO and TRM steps efficiently in redundant internal coordinates. The regular RFO model has also been modified so that it has the correct size dependence as the molecular systems become larger. Finally, an improved Hessian update for minimizations has been constructed by combining the Broyden-Fletcher-Goldfarb-Shanno (BFGS) and (symmetric rank one) SR1 updates. Together these modifications and new methods form an optimization algorithm for large molecules that scales as O(N-2) and performs similar to or better than the traditional optimization strategies used in quantum chemistry.