Quantum optimization is a promising field for practical quantum computing, but limitations in current quantum devices, such as the limited number of qubits and noise, restrict the applicability of these algorithms, leading to efforts in developing quantum algorithms amenable for noisy intermediate-scale quantum (NISQ) devices, with QAOA emerging as a promising candidate for solving combinatorial optimization problems. Recently, several limitations of this algorithm have been identified. This work focuses on addressing these limitations and enhancing the performance of QAOA without increasing the circuit size and keeping the algorithm still NISQ-feasible. Drawing on the principles of Recursive-QAOA, we have formulated new methodologies to iteratively apply QAOA to simplify the problem of interest, and to combine it with classical optimization techniques. These methods are demonstrated using the Max-2-SAT problem as an example. Additionally, we have developed a new algorithm that utilizes QAOA to calculate correlations and inform a classical cluster algorithm. This so called QAOA-informed cluster algorithm is used to calculate the ground state of certain spin glass systems. The developed techniques in this thesis can be extended beyond QAOA and are believed to be useful in a broader context of developing quantum optimization algorithms for near-term devices.