We develop new computational methods and new theoretical analysis for important classes of large-scale simulation and soptimization problems arising in a variety of areas in engineering, science, data science, and applied mathematics. Towards this goal, we will develop and analyze new classes of principled first-order methods (FOMs) that are adapted to deal with the lack of smoothness of the objective function and/or the feasible domain. FOMs are appealing in several ways, as they need only work with gradients, they enjoy reasonably fast convergence, and they scale well in problem dimensions. These features make them suitable for truly large-scale applications, where the objective function is a sum (or average) of a huge number of component functions and the dimension of the optimization variable is huge. However, many existing state-of-the-art FOMs suffer from much slower convergence for a wide range of non-smooth problems. Indeed, without the smoothness condition, traditional FOMs and their accelerated versions do not converge either theoretically or empirically. The development of FOMs with improved and guaranteed convergence rates for solving non-smooth problems will not only advance theory but also broaden the scope of applicability of FOMs to important applications. The proposed research aims to discover new curvature or other mathematical structure conditions (beyond the smoothness condition traditionally required by FOMs) and accordingly, develop new first-order methods (or frameworks) for these conditions. We aim to establish rigorous convergence results to theoretically analyze the methods we will develop for non-smooth optimization problems. Finally, we apply our developed algorithms to solve very large-scale optimization problems in application areas both traditional and new. We will demonstrate the usefulness of our optimization algorithms on novel large-scale applications in the synergistic domains of medical imaging, quantum computing, molecular dynamics, and deep learning. This project is funded by AFOSR.