Prove zero slope point is global maximum for constrained function with binomials. Without restriction, objective function is non-concave

Question

How to prove the zero slope point is a global maximum in this non-concave program for a function with binomials?

I need to find the (global) maximum of the following constrained problem:

$$\max_{CAP} \pi[CAP] =(v-CAP) \sum_{j=1}^J j \cdot q^j (1-q)^{N-j} \binom{N}{j} \\ +J(v-(1- \delta)C) \sum_{j=J+1}^{N} q^j (1-q)^{N-j} \binom{N}{j} \notag \\ \text{respecting }\text{the constraint that for all } q \in (0,1) \subset \mathbb{R}: \notag \\ 0= ( CAP - C ) \sum_{j=1}^J j N \cdot q^{j-1} (1-q)^{N-1-j} \binom{N}{j} \\ - \delta C \sum_{j=J+1}^{N} j N \cdot q^{j-1} (1-q)^{-j+N-1} \binom{N}{j} \notag$$

Where:

endogenous variables:

• $ 0<q<1$ respects the constrained maximization
• $CAP>C$ maximizes the objective function w.r.t the constraint

exogenous variables:

• $v>0$
• $0<C<v$
• $0< \delta <1$

I have good reasons to suspect the global optimal is reached when $CAP=v$. For the proof I write down the Lagrangian:

$$\mathcal{L}[CAP,q,\lambda] = (v-CAP) \sum_{j=1}^J j \cdot q^j (1-q)^{N-j} \binom{N}{j} \label{lagrangian} \\ + (v- c + \delta C) \sum_{j=J+1}^{N} J \cdot q^j (1-q)^{N-j} \binom{N}{j} \notag + \lambda \Bigg\{(CAP-C) \sum_{j=1}^J q^{j-1} (1-q)^{N-1-j} \binom{N-1}{j-1} \notag \\ - \delta C \sum_{j=J+1}^{N} q^{j-1} (1-q)^{N-1-j} \binom{N-1}{j-1} \Bigg\} \notag $$

Now I managed to show (with a very tedious, torturous proof) that $\frac{d\mathcal{L}[CAP,q,\lambda]}{d CAP}=0$, but I need to show that it is also an (global) optimum. The problem is that the objective function $\pi[CAP]$ is not concave! See Figure 1 and 2 for 3d representations of the objective function.
Here is the Mathematica program I used to draw these Figures.

Fig.1:Objective Function Fig.2:Objective Function - different angle

The constraint, however, seems concave as Figure 3 shows. I suspect that the problem is strictly concave for all $q$ respecting the constraint, as Figure 4 indicates.

Fig.3: The constraint

Fig.4: Intersection Objective and Constraint - 3D

Mathematica has a bit a problem to show the intersection nicely in Fig.4, so I drew some 2D graphs using simulations. E.g., see Figure 5.

Fig.5: Intersection Objective and Constraint - 2D The vertical line indicates the maximum. In the graph $v=200$. The plot in Fig.5 clearly shows how the maximum is attained at $CAP=200=v$ and that this is a global optimum (for the specific parameter values used to draw Fig.5).

What can I do here? I understand that people have looked at this sort of problems. Heal (1984) addresses non-concave objective functions in his paper " Equivalence of Saddle-Points and Optima for Non-concave Programmes"}. He shows that for some of these problems you can transform the variables so that the transformed problem has a concave objective problem. That is a great idea, but I don't see what kind of transformation I could make.

Answer 1

I solved the problem by reformulating it using an economic argument. I find it astonishing how simple the problem becomes after the reformulation/reconceptualization. I believe there must be a form of mathematical mapping that projects the original problem onto the new problem and I am very curious what that could be. The argument I use is economic in nature and is probably quite "chatty" for a mathematician.

The Economic Problem

As it is key to my argument, I write the economic problem once again, adding some important details.

The buyer

One buyer wants to buy maximally $J$ units. For each unit he buys, he earns $v$. The number of units that is offered to him is $j$. Thus, for example, with $v=10$ and $j=3, 4, 5, 6, \text{and } 7$, the buyer earns $30, 40, 50, 50, \text{and } 50$. The price per unit depends on the supply, but has a maximum, $CAP$, set by the buyer.

The number of units that is offered, $j$, follows a random distribution. When the number of units $j \leq J$, the supply is less than demand, and the price per unit is as high as possible, $CAP$ When the number of units $j > J$, the price per unit is $- \delta C$, where $C$ is the fixed cost of a unit.

The sellers

There are $J$ identical sellers. Each sellers has a fixed cost of $C$. For a seller to become eligible to sell to the buyer, it has to enter the market and I assume that this involves making a sunk investment equal to a proportion of it's cost, $\delta C$. All sellers decides simultaneously to become eligible with probability $q$. The probability $q$ is determined so that the sellers make zero profits in expectation.

Variables

Then:

• $0<q<1$ is the probability of a a unit being offered
• $v>0$ is the value of a unit for the buyer \
• $C>0$ is the fixed cost of the unit for the seller and $C<<v$ \
• $0<- \delta C<C$ is the \textit{negative} price of a unit when $j>J$.\
• $CAP>C$ is the price of a unit when $j \leq $ and a parameter to set by the buyer.

The Original Formulation

The buyer wants to maximize its profit leads and thus originally I started out writing the Lagrangian:

\begin{align*} \mathcal{L}[CAP,q,\lambda] =& (v-CAP) \sum_{j=1}^J j \cdot q^j (1-q)^{N-j} \binom{N}{j} \\ & + (v- c + \delta C) \sum_{j=J+1}^{N} J \cdot q^j (1-q)^{N-j} \binom{N}{j} \notag \\ & + \lambda \Bigg\{(CAP-C) \sum_{j=1}^J q^{j-1} (1-q)^{N-1-j} \binom{N-1}{j-1} \notag \\ & - \delta C \sum_{j=J+1}^{N} q^{j-1} (1-q)^{N-1-j} \binom{N-1}{j-1} \Bigg\} \notag && \end{align*}

However, as detailed in my post above, this approach led to a non-concave objective function and the proof that the Lagrangian has slope zero when $CAP=v$ alone is torturous, Moreover, the proof does not establish it is a maximum, let alone a global maximum.

Alternative (but equivalent) Formulation

The problem can be reformulated after applying some economic intuition. The question I ask is in what precise cases the buyer's profit decreases. There are two such cases.

1. Over-entry

When $j>J$ sellers decide to enter, then $j-J$ of them will not be able to sell and have made the sunk cost, $\delta C$, in vain. I call this a case of "over-entry": Too many sellers entered the market. The expected loss due to over-entry is thus $( \delta C ) \sum_{j=J+1}^N (j-J) \cdot q^{j} (1-q)^{N-j} \binom{N}{j}$. As the sellers make zero profit by assumption, this loss is paid by the buyer and thus decreases the buyer's profit.

2. Under-entry

When $j<J$ sellers decide to enter, then the buyer loses out on the opportunity to buy $J-j$ items. I call this a case of "under-entry": Too few sellers entered the market. Each of those lost sales would have increased his profit by $(v-C)$, the value the buyer has for the item minus the cost of producing that item. The expected loss due to under-entry is thus $( v- C ) \sum_{j=0}^J (J-j) \cdot q^{j} (1-q)^{N-j} \binom{N}{j}$.

Thus the buyer basically would like to minimize these two factors that decrease his profits. Let's call this the loss function. Then:

\begin{align*} loss[q]=&( \delta C ) \sum_{j=J+1}^N (j-J) \cdot q^{j} (1-q)^{N-j} \binom{N}{j} \\ &+ ( v- C ) \sum_{j=0}^J (J-j) \cdot q^{j} (1-q)^{N-j} \binom{N}{j} \end{align*}

With, as in the original problem, the restriction:

\begin{align*} &(CAP-C) \sum_{j=1}^J q^{j-1} (1-q)^{N-1-j} \binom{N-1}{j-1} \notag = \delta C \sum_{j=J+1}^{N} q^{j-1} (1-q)^{N-1-j} \binom{N-1}{j-1} \end{align*}

The only free parameter for the buyer is to set $CAP$. Setting $CAP$ affects the probability of entry through the restriction $q$. I can thus solve the problem by finding the $q$ that minimizes $loss[q]$ and use the restriction then to determine the corresponding $CAP$.

Solving the Alternative Formulation

Let us thus differentiate $loss[q]$ and set it equal to zero. \begin{align*} 0=&\frac{d loss[q]}{d q} \\ =& \delta C \sum_{j=J+1}^N (j-J) \Big(j \cdot q^{j-1} (1-q)^{N-j} \\ &-(N-j) \cdot q^{j} (1-q)^{N-1-j} \Big) \cdot \binom{N}{j} \\ &+ ( v- C ) \sum_{j=0}^J (J-j) \Big(j \cdot q^{j-1} (1-q)^{N-j} -(N-j) \cdot q^{j} (1-q)^{N-1-j} \Big) \cdot \binom{N}{j} \\ =& \delta C \Bigg( \sum_{j=J+1}^N (j-J) j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \\ &- \sum_{j=J+1}^N (j-J) (N-j) \cdot q^{j} (1-q)^{N-1-j} \binom{N}{j} \Bigg) \\ &+ ( v- C ) \Bigg( \sum_{j=0}^J (J-j) j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \\ &- \sum_{j=0}^J (J-j) (N-j) \cdot q^{j} (1-q)^{N-1-j} \binom{N}{j} \Bigg) \\ =& \delta C \Bigg( \sum_{j=J+1}^N (j-J) j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \\ &- \sum_{j=J+2}^{N+1} (j-1-J) (N+1-j) \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j-1} \Bigg) \\ &+ ( v- C ) \Bigg( \sum_{j=0}^J (J-j) j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \\ &- \sum_{j=1}^{J+1} (J+1-j) (N+1-j) \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j-1} \Bigg) \\ =& \delta C \Bigg( \sum_{j=J+1}^N (j-J) j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \\ &- \sum_{j=J+1}^N (j-1-J) j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \Bigg) \\ &+ ( v- C ) \Bigg( \sum_{j=0}^J (J-j) j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \\ &- \sum_{j=0}^J (J+1-j) j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \Bigg) \\ =& \delta C \Bigg( \sum_{j=J+1}^N j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \Bigg) \\ &- ( v- C ) \Bigg( \sum_{j=0}^J j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} + J \cdot q^{J-1} (1-q)^{N-J} \binom{N}{J} \Bigg) \end{align*}

Using the restriction to substitute for the term $\delta C \Bigg( \sum_{j=J+1}^N j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \Bigg) $ gives: \begin{align*} 0=& (CAP-C) \Bigg( \sum_{j=0}^J j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \Bigg) - ( v- C ) \Bigg( \sum_{j=0}^J j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \Bigg) \\ =& (CAP-v) \Bigg( \sum_{j=0}^J j \cdot q^{j-1} (1-q)^{N-j} \binom{N}{j} \Bigg) \end{align*} We can thus conclude that $CAP \gtreqqless v \implies \frac{d loss[q]}{d q} \gtreqqless 0$ and $loss[q]$ is thus strictly convex and therefore has a global minimum at $CAP=v$. Of course, given the setup, this implies that the buyer's profit reaches a global maximum at $CAP=v$.