> I think we need more explicit information about what f() looks like and about the problem size (dimension of the space, number of vertices, etc...).
Sounds good. I'm working with an economic model of supply and demand. The convex set C is the "supply" side. The supply comes from a set of "fields" which split their resources between various crops. For instance, a field might devote all its energy to corn and produce 10 corn. Or it might devote itself solely to wheat and produce 20 wheat. Or it could produce 0.4*10 corn and (1 - 0.4)*20 wheat.
Each good has a price. Fields always produce crops which gets them the most money. In the above example, if p_corn = $3 and p_wheat = $1, the field produces all corn. If p_corn changes to $1, it produces all wheat. If p_corn changes to $2, it can produce both corn and wheat in any legal proportion.
So, C, the set of possible supplies, can be thought of as the set of optimal production possibilities (given a price). It is the boundary of a (non-strict) convex set.
f is the "demand" side. Different agents own the fields and collect their revenue (i.e. price*quantity produced). They spend this revenue on the same goods that are being produced. f tells me how much total demand there is, given the quantities produced and prices.
The goal is to find a point on C where the supply (q) is equal to the demand (a function of q and the tangent plane, i.e. the price, p).
The number of fields is high (~10^6), the number of goods is smaller (~10^3).