Abstract: In the research of complex data fitting, solving constrained approximation problems is important, as it directly affects the model’s ability to represent complex data and its approximation accuracy. Although the constrained least-squares progressive and iterative approximation (CLSPIA) algorithm can effectively solve the constrained approximation problem of interpolating some data points while approximating the remaining ones, it suffers from a slow convergence rate. To overcome this shortcoming, we proposed a conjugate-gradient-based CLSPIA algorithm by integrating the conjugate-gradient algorithm into CLSPIA. First, the inner iteration of the Uzawa algorithm is solved using the CG-LSPIA algorithm to solve the corresponding unconstrained optimization problem. Then, the outer iteration of the Uzawa algorithm is performed according to the Lagrange multiplier iteration format to handle the constraints. Finally, the convergence of this algorithm is theoretically proven. Experimental results using cubic B-spline curves and surfaces as examples demonstrate that under the same error accuracy, 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.