changes we have felt it necessary to make [parse of "necessary to make"]

Solution 1:

It starts out as an extremely awkward sentence:

• We have felt [[for us to make changes] to be necessary]

transformed by extraposition on the higher infinitive, moving the lower infinitive and inserting a dummy it:

• We have felt it to be necessary [for us to make changes]

and then by deletion of optional material, the following sentence is produced:

• We have felt it necessary [to make changes].

At this point we want to refer to those changes outside the clause, so we make changes into an antecedent NP with a relative clause

• changes [(that) we have felt it necessary to make].

As you can see, the noun phrase has been extensively revised from its original syntactic shape. Two subordinate clauses have been stretched, sliced, and diced along the length of a main clause, with several rules applying.

That's what transformations do to constituents -- they make them unrecognizable as one thing but still understandable as another. And there are a lot of them.

As for whether any particular stretch of this is an adjective phrase or an object complement, that isn't really important. Looking for labels to put on some possible string of words in some possible transformation of one sentence is not a particularly helpful strategy in understanding syntax.