5

As a research project, we're investigating various algorithms developed for non-differentiable, convex (or concave, if you're into economics) optimization. I'd like to find some good examples of real problem formulations that arise in different fields, especially economics.

Any example is welcome, as long as it is non-smooth in some sense, either in the objective function or the feasible set. Ideally I'd like examples of both strictly concave and not strictly concave functions. Both problems that are separably concave and problems that aren't are of interest.

Benjamin Lindqvist
  • 159
  • 2

4 Answers4

3

Here are four I could think of:

  1. Leontief and Lexicographic functions, used in preferences or production functions are non-differentiable.
  2. Labor models often employ a discrete labor supply (work or don't work, sometimes alongside the decision of how much or how hard to work).
  3. Housing models often employ a non-convex adjustment cost to ensure that there is a discontinuity in the cost function for the choice of housing.
  4. Kinked objective functions, where at one or more points the left-hand and right-hand limits differ, are also common in economics (e.g. optimal option exercise at maturity)
BKay
  • 16,292
  • 2
  • 35
  • 80
  • Thanks for your suggestions, however integrality constraints and non-convexity is not related to this particular problem set-up - we're dealing with convex, non-smooth problems exclusively right now. This seems to exclude 2-4 – Benjamin Lindqvist Jun 04 '15 at 10:37
2

"Indivisibillity of goods" is a standard example of a non-differentiable feasible set. Still, while it has produced a number of theoretical results in microeconomics mainly regarding individual behavior, when examining real-world markets and economies, the smoothing effects of aggregation allows to treat it as though it was smooth and differentiable, with the approximation error being negligible (and indeed it is).

An interesting case that might qualify for what you are asking, is dynamic problems where investment becomes a step-function (see this post also).

A classic example is Telecommunications market. Companies invest in building an initial network that has a capacity "to last certain periods". As (or if) they grow commercially, it comes a time that capacity is indeed reached (typically 80% of theoretical capacity, validating once more the Pareto principle/rule-of-thumb), and then they have to invest, not a little something to smoothly increase capacity say by 1%, but again a sizeable amount to increase capacity to "last for some periods". Etc.
This sometimes is inherent in the nature of things and the technology involved, and/or takes into account economies of scale from volume-purchases and project-management costs.

What this does is to impose an additional dynamic constraint on the decision variable "investment": "if network saturation is below XX, Investment is "zero", if it has reached XX, invest, and not less than YY". So in the first subset of periods, the feasible set for investment is just a single point (zero), while in the rest, it has a non-trivial lower bound. In turn the "network saturation" will depend on other decision variables of the firm (like marketing efforts etc) as well as on past investments that have determined the current maximum capacity.

Again, at the macroeconomic level, one could invoke the smoothing effects of aggregation, but not when doing micro-economic work on how to solve the problem of a particular firm. Obviously, this has specific applied uses.

Community
  • 1
Alecos Papadopoulos
  • 33,814
  • 1
  • 48
  • 116
  • Correct me if I'm wrong, but aren't you describing a discontinuous problem, rather than a non-differentiable one? If so, it's actually not even concave. – Benjamin Lindqvist Jun 04 '15 at 11:19
2

I think there are some problems like this cooperative game theory. The one that jumps to mind is the Gale-Shapley algorithm.

Giskard
  • 29,387
  • 11
  • 45
  • 76
  • The stable marriage problem does indeed seem non-differentiable and convex. It seems as though it can be formulated and solved as a linear program though, so it probably won't garner much interest... Game theory does seem like a good field though, all the interesting examples we've found so far has been from mechanism design. – Benjamin Lindqvist Jun 04 '15 at 11:27
2

Let me just add two research areas which where not mentioned so far:

Chris Shannon has a nice reading list of the "classics" and there is an article by Truman Bewley on Knightian decision theory which is pretty good. But there are many other problems in which it is applied.

As this is not really my research area, I can't really give you an example but you should be able to find some in the articles mentioned, as these fields mostly deal with problems of the kind you are looking for.

The Almighty Bob
  • 1,682
  • 1
  • 12
  • 26
  • Thanks a lot. I'll leave the question open a little while longer in case some one wants to add a suggestion. Otherwise, I'll accept this one. – Benjamin Lindqvist Jun 05 '15 at 15:42