Abstract: Solving constrained approximation problems is important in the research of complex data fitting, and it directly affects the model’s capability to characterize complex data and its approximation accuracy. The constrained least-squares progressive and iterative approximation (CLSPIA) method can effectively solve the constrained approximation problem of interpolating some data points while approximating the remaining ones. Unfortunately, it suffers from a slow convergence speed. To overcome this shortcoming, we proposed a conjugate-gradient-based CLSPIA method by integrating the conjugate-gradient method into CLSPIA. Firstly, the inner-layer iteration of the Uzawa algorithm is solved using the CG-LSPIA method to solve the corresponding unconstrained optimization problem. Then, the outer-layer iteration is completed according to the iteration scheme of the Lagrange multiplier to handle the constraint conditions. The convergence of this algorithm is also theoretically proven. Finally, taking cubic B-spline curves and surfaces as examples, experimental results show that under the same error precision, the proposed algorithm reduces the total iteration number by an average of 83.07% and the CPU execution time by an average of 55.45% compared to the CLSPIA algorithm.