3
$\begingroup$

\begin{equation} \label{eqgen} \begin{aligned} & \underset{x}{\text{maximize}} & & F(x)\\ & \text{subject to} & & x \geq 0, \\ & & &x + f(x)\leq d, \end{aligned} \end{equation} where $F(x), f(x)$ are continuous functions from $\mathbb{R}^+ \to \mathbb{R}^+$.

Here is my approach. Intuitively, $x+f(x)\leq d, x\geq 0$ is equivalent to $x \in [a_1, b_1] \cup [a_2, b_2]\cup \cdots \cup [a_{n}, b_{n}]$, where $a_i\leq b_i$, $a_1$ is either 0 or solution of $x+f(x) = d$, $b_n$ is either d or solution of $x+f(x) = d$, and $a_i, b_i$ are solutions of $x+f(x) = d$ for other cases.

Hence, the optimization problem becomes \begin{equation} \begin{aligned} & \underset{x}{\text{maximize}} & & F(x)\\ & \text{subject to} & & x \in [a_1, b_1] \cup [a_2, b_2]\cup \cdots \cup [a_{n}, b_{n}]. \end{aligned} \end{equation}

max $F(x)$ on $[a_i, b_i]$ is attained at either $a_i, b_i$ or maximum of $F(x)$ on $[a_i, b_i]$. We can conclude that the optimal solution is either solutions of $x+f(x) = d, or x=0, x= d$ or local maximum of function $F(x)$. This is also what I want to prove.

How can I formally write down the solution of the above approach? I wrote this and my professor does not accept my solution. Thank you in advance!

enter image description here

$\endgroup$
3
  • $\begingroup$ Have you tried: en.wikipedia.org/wiki/… $\endgroup$
    – Juanito
    May 15 '17 at 17:14
  • $\begingroup$ Thanks for your hint. But it does not work $\endgroup$ May 23 '17 at 19:54
  • $\begingroup$ Can you tell me what you mean by it does not work? You would not find any closed form solutions in any case. Under differentiability, you would get first order conditions. $\endgroup$
    – Juanito
    May 24 '17 at 1:19
1
+50
$\begingroup$

There are a lot of intuitive tricks that one can use if one knows exactly the values of $f(x),\ d$, but given it is not given, I will lay out a general way of Kuhn-Tucker conditions.

Write: $L=F(x)+\lambda_1 x-\lambda_2 (x+f(x)-d) $ with $\lambda_1, \lambda_2 \geq0$

Think of the intuition behind the sign of the lambdas. If $x$ becomes negative that is bad for our purpose given the constraint, and that is getting reflected by our objective function getting a negative "shock" through the positive $\lambda_1$. You can reason through similarly for the other lambda.

Now, take derivative w.r.t $x$ to get:

$F'(x)-\lambda_1+\lambda_2(1+f'(x))=0$

Couple this equation with the constraints:

$\lambda_1 x=0$

$\lambda_2 (x+f(x)-d)=0$

And these conditions have complementary slackness.

Case 1: Suppose both constraints are binding, then $\lambda_1, \lambda_2>0$. And, $x=0$, and, $f(0)=d$. If, $f(0) \ne d$, we can immediately move on from this case to the second case.

Otherwise, plug in $x=0$ in the derivative condition, solve for lambdas and check if they are actually positive, otherwise, as before, we move on from this case. Check here:

$F'(0)-\lambda_1+\lambda_2(1+f'(0))=0$

Case 2: Constraint 1 binds and 2 does not. So, $\lambda_1>0$ and $\lambda_2=0$ and $x=0$.

Check back into the derivative condition and check if the values match up with it and with the condition

$ f(0)\leq d $

Case 3: Constraint 2 binds and 1 does not. So, $\lambda_1=0$ and $\lambda_2>0$ and $x=0$.

Solve for $x$ from $f(x)=d$, given we are not in case 1, $x$ should not be zero. Use that value of the solution to check back if $x\geq 0$ holds, and if the derivative condition is satisfied for positive $\lambda_2$.

Case 4: Both constraints bind So, $\lambda_1=0$ and $\lambda_2=0$

Solve it like an unconstrained problem, find $x$ and check back to confirm that the inequality conditions are satisfied.

Finally at any case when you find a solution, you check for the second derivative of the maximand (Lagrangian function L) to be negative at the optimal point ($x^*, \lambda^*$). Also, if you found multiple solutions from the different cases, choose among them by plugging them directly into the actual function $F$ to see which one gives the maximum value.

$\endgroup$
5
  • $\begingroup$ $d$ is given and plays the role of constant. $\endgroup$ May 24 '17 at 5:46
  • $\begingroup$ I mean, do you know how $f(0)$ and $d$ are exactly related? Also does the above answer help you? $\endgroup$
    – Juanito
    May 24 '17 at 5:58
  • $\begingroup$ Many thanks. I am checking. If it is correct I will mark it. $\endgroup$ May 24 '17 at 6:22
  • $\begingroup$ I think it's correct and make it as completed answer. But how can we deal with the case when $F, f$ are continuous but not differentiable. From my picture I think it still holds. $\endgroup$ May 24 '17 at 8:54
  • $\begingroup$ Without differentiability, your best hope would be to take the same four cases as above, and find the optimal in each case by plotting+eye inspection or by logical reasoning. $\endgroup$
    – Juanito
    May 24 '17 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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