I have the following nonlinear optimization problem.
$$
\underset {b_1, b_2} \max\, f(b_1, b_2) = N_1(V_1 – b_1)F(b_1;\mu_1,\sigma_1) + N_2(V_2-b_2)F(b_2;\mu_2,\sigma_2)
$$
subject to:
$$
g_1(b_1, b_2) = N_1 F(b_1;\mu_1,\sigma_1) + N_2 F(b_2;\mu_2,\sigma_2) \le I_1 \\
g_2(b_1, b_2) = N_1 F(b_1;\mu_1,\sigma_1) + N_2 F(b_2;\mu_2,\sigma_2) \ge I_2 \\
b_1, b_2 \ge 0
$$
where F(.) is the CDF (cumulative distribution function) of the log-normal distribution. We need to find the optimal value of $b_1, b_2$ and everything except $b_1, b_2$ is known. The constraints are not convex.
I am new to nonlinear programming. What would be the best way to solve this? If I apply KKT conditions, it would be difficult to solve the equalities analytically. Also, in the actual problem, there are lots of variables similar to $b_1, b_2$, so using KKT conditions would mean checking a lot of possibilities.
I was thinking, if we assume $F(b_1;\mu_1,\sigma_1) = x_1$ and $F(b_2;\mu_2,\sigma_2)=x_2$, then we will have linear constraints and a nonlinear objective function like this:-
$$
\underset {x_1, x_2} \max\, f(x_1, x_2) = N_1(V_1 – f_1(x_1))x_1 + N_2(V_2-f_2(x_2))x_2
$$
s.t.
$$
N_1 x_1 + N_2 x_2 \le I_1 \\
N_1 x_1 + N_2 x_2 \ge I_2 \\
0\le x_1, x_2 \le 1$$
where $b_1 = f_1(x_1)= F^{-1}(x_1;\mu_1,\sigma_1), b_2 =f_2(x_2)=F^{-1}(x_2;\mu_2,\sigma_2)$
Is this formulation any better?
EDIT: 1. Added constraints as per Prubin's answer.
- Responding to TickaJules' comment: To give a sense of how the problem came about –
Let's say there are 2 types of items to be sold in auctions – item 1 and item 2. There are $N_1$ no. of item 1 and $N_2$ no. of item 2. There are lots of bidders including me, fighting to buy each of the items. No bidder knows prices that others bid, they only know the prices they themselves bid.
As is the case with auctions, whoever submits the highest bid-price, wins the item. The winning price (the minimum required price to win the auction) for item 1 and 2 ($\hat b_1, \hat b_2$ respectively) follow a lognormal distribution with parameters $\mu_1,\sigma_1$ and $\mu_2,\sigma_2$ respectively. So, if I submit a bid price of $b_1$ for the first item, the probability that I'd win the auction is $Pr(\hat b_1<b_1) = F(b_1;\mu_1,\sigma_1)$. If I do win an item 1 product I can sell it to somebody else at price $V_1$. So my profit from one product of item 1 would be $(V_1-b_1)$. As there are $N_1$ products in item 1, the expected profit from item 1 is $N_1 (V_1-b_1)F(b_1;\mu_1,\sigma_1)$. Similarly the the expected profit from item 2 is $N_2(V_2-b_2) F(b_2;\mu_2,\sigma_2)$.
So I want to maximize my overall profit $N_1(V_1-b_1) F(b_1;\mu_1,\sigma_1) + N_2(V_2-b_2) F(b_2;\mu_2,\sigma_2)$. The constraints just say that I want to keep the total items I buy within the limits $I_1$ and $I_2$.
Best Answer
Your variable transformation has potential. You should add the domain constraints $0 \le x_1, x_2 \le 1$. The objective is not concave, but one possibility would be to approximate it by a piecewise linear function (turning the problem into an integer linear program). Assuming that model solves reasonably easily, you could iteratively refine the PWL approximation near each solution and solve again to get a more accurate solution.
Another possible approach, using the original model, starts with finding strictly positive values of $b_1$ and $b_2$ for which both constraints are strict inequalities (i.e., have positive slack). You could then try using a barrier function to turn the problem into an unconstrained nonlinear program, and use a gradient based search method starting from your initial point. Given the nonconvexity/nonconcavity of your objective function, I don't think you can expect a guaranteed optimum, but rerunning it a few times with random (strictly feasible) starts might be good enough for your purposes.