A new strategy for the optimization of natural gas liquefaction processes is presented, in which flowsheets formulated using nondifferentiable process models are efficiently and robustly optimized using an interior-point algorithm. The constraints in the optimization formulation lead to solutions that ensure optimal usage of the area of multistream heat exchangers in the processes in order to minimize irreversibilities. The process optimization problems are solved reliably without the need for a complex initialization procedure even when highly accurate descriptions of the process stream cooling curves are required. In addition to the well-studied PRICO liquefaction process, two significantly more complex single mixed-refrigerant processes are successfully optimized and results are reported for each process subject to constraints imposed by several different operating scenarios.