Critical infrastructures such as power grids, transportation networks, water systems, gas networks, and others have become increasingly reliant on each other for functional facilities in recent years. Consequently, coordinating these interdependent networks has become crucial for synergistic operation. Since these infrastructures are generally managed by different entities, this dissertation presents decentralized optimization algorithms and solution methods tailored to address various coordination challenges. First, this dissertation presents a decentralized framework for coordinating optimization models of power and transportation networks for the integration of electric vehicles with minimal information exchange. Since the transportation optimization model is in a mixed-integer program (MIP) form, a novel decentralized optimization algorithm that guarantees optimality and convergence for the decentralized coordination of MIPs is proposed. Moreover, the proposed decentralized optimization algorithm is further improved to tackle the unique challenges of intertwined power and water networks, where boundary variables (variables shared by two optimization models) are discontinuous. Therefore, the mixed-integer boundary-compatible decentralized optimization algorithm is proposed to coordinate MIPs with discontinuous boundary variables. Second, in addition to the coordination of infrastructure from the economic perspective, this dissertation also focuses on resilient and uncertainty-aware coordination of the power grid and other critical infrastructures. For power distribution system restoration after disasters, the coordination of emergency response resources such as mobile energy resources and repair crews is proposed. However, the computational requirement of the restoration model is high; therefore, a computationally efficient power distribution system restoration approach is investigated. Moreover, with the increasing penetration of variable renewable energy sources like solar energy, the necessity to consider uncertainties in the operation and planning of the power grid is heightened. Therefore, the efficacy of the proposed decentralized optimization algorithms in coordinating mixed-integer programs under uncertainty is validated by coordinating the chance-constrained optimization models of the power grid and other critical infrastructures.