Presume f_fitted(x) is your fitted function. You will have to choose a parameterization. But per your example, piecewise linear is a possibility. You could use fixed break points or have them chosen in the fitting procedure. You could use cross validation to choose the optimal number of break points.
The key to achieving your stated aim of fitting a function which is monotonically increasing is to impose such a condition as part of the fitting optimization problem. So you want derivative of f_fitted(x) >= 0 at all points at which is is defined. It may not be defined at break points if you use linear functions between the break points. So, say you have fitted lines between each break point, you need to impose the constraint that slope >= 0 for each segment. Also impose for all i the continuity constraint that the fitted function between x_i and x_i+1 is equal at x_i+1 to the fitted function between x_i+1 and x_i+2. Together, these constraints will ensure a monotonically increasing continuous function.
You can use the same kind of ideas with functions (basis) other than piecewise linear. In fact, this is roughly the kind of thing that's done in spline regression, except that derivative continuity rather than monotonicity might be imposed
So think of training as fitting, and think of fitting as an optimization problem. Impose the constraints you want as part of the optimization problem. Reading chapter 5 of Hastie, Tibshirani, Friedman 'The Elements of Statistical Learning' may give you ideas on choosing basis functions and how to go about the fitting in general, since perhaps piecewise linear functions may not be a great choice.