MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Caveat up-front: I'm not a mathematician, so please excuse any stupidity/ignorance that follows. First, let me explain what I'm trying to do: I want to choose a function that maximizes the following definite integral:

$\max_{b(q)} \int_0^1 1 - e^{-q b(q)} dq$

subject to

$b(q) \ge 0, \forall q$

$\int_0^1 b(q) = B$

My intuition is that an optimal solution for $b(q)$ will be an allocation so that the derivative of $1-e^{-q b(q)}$ with respect to $b$ will be the same (say $\lambda$) everywhere that b(q) > 0. This condition gives $b(q) = - \frac{1}{q} \log \frac{\lambda}{q}$. The second constraint gives the expression lets us solve for $\lambda$. Below is a plot showing $b(q)$ for various values of $\lambda$. My (guess?) is that I could find this curve explicitly using the calculus of variations.

alt text

Now, for the complicated part and my real question. As you can see from some values of $\lambda$, it is not the case that $b'(q) \ge 0$. In fact, the curve as a peak at $e \lambda$. I want to maximize the same definite integral as before, but with the added constraint that $b'(q) \ge 0, \forall q$.

My intuition is that this optimal curve now has three parts: (1) a region where b(q) = 0, as in the unconstrained case (2) a region where the curve has the same shape as the previous, unconstrained portion [the upward sloping region] and (3) a flat, slope = 0 portion that is tangent to the maximum. These restrictions fully define a curve for a given value of B---see below for examples:

alt text

I have some sketched ideas for a "proof," but my ideas do not seem that convincing to me. My question is what would be an approach for proving my constructed curve is in fact optimal? Is there some "textbook" way of approaching this kind of problem that I should read up on? Thanks for any advice or pointers.

share|cite|improve this question
up vote 2 down vote accepted

Your constant-derivative intuition is correct. In general, if we are optimizing $x$ with respect to a bound on $y$, we might as well be optimizing $x-Cy$ for some constant $C$, which would require $dx/dv-Cdy/dv=0$ for any variable $v$ we have control over.

If we write $b(q)=\int_0^q a(t)dt$, then the derivative of the quantity being optimized, with respect to $a(t)$, is $\int_t^1 qe^{-q b(q)}dq$. Since the cost is $1-t$, this should be a constant multiple of $1-t$ except where $a=0$, where it should be lower.

Thus, where the $b'(q)$ is positive, we have $\int_t^{1} qe^{-q b(q)}dq=C(1-t)$ so $qe^{-qb(q)}=C$. Thus, where the curve is upward-sloping, it must equal one of your original curves, and the same for each upward-sloping region. The only way to do this is to have a flat section, and then part of your original curve's upward-sloping region, and then another flat section, as you guessed.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.