3
$\begingroup$

I have a general question about the Karush-Kuhn-Tucker-Theorem. Let's assume that we want to maximize the following funtion: $$f(x)$$ subject to some constraints $$g_i(x ) \leq 0$$ Using the objective function $f(x)$ and the constraints I get the following Lagrangian Function $$Z(x)=f(x)+\sum_i \lambda_i g_i(x)$$

Let's assume further that the function $Z(x)$ can not be solved algebraically because it's a function of higher order. Instead I'm using a program (e. g. gradient method) to determine a value for $x^*$ that maximizes $f(x)$ under the constraints $g_i(x)$. Let's assume also that all Karush-Kuhn-Tucker-conditions are satisfied ($f(x)$ is concave; $g_i(x)$ is convex....)

Now my question: Is $x^*$ a value that gives a global maximum for $f(x)$ or is $x^*$ just the value that gives a local maximum in the possible range under the constraints $g_i(x)$? And if the Karush-Kuhn-Tucker-Conditions are satisfied is $x^*$ the only value which I have to consider? Maybe I have to add that my main concern has to do with the higher order of my function $f(x)$ and therefore more than one optimal value for $x^*$ (but not under the constraints).

Thank you for your answer.

$\endgroup$
1
  • $\begingroup$ This is how I explain it to myself. There are two mountains. Tips of both mountains are local maximas. Tip of taller mountain is global maxima. If the tip of the larger mountain is flat, there are multiple global maximas. Tips of all such mountains will satisfy KKT conditions. If function is concave, there can be only one mountain. If tip is flat, all points at the tip will satisfy KKT conditions and all points that satisfy KKT conditions are global optima. If tip is sharp, only one point will satisfy KKT conditions. Thus, KKT conditions become sufficient to determine the unique global maxima $\endgroup$
    – dineshdileep
    Jun 23, 2017 at 11:25

2 Answers 2

Reset to default
1
$\begingroup$

Since $f(x)$ is concave and $g(x)$ is convex, any local maximum of $f(x)$ in the region $\{ x : g_i(x) \leq 0 \}$ is automatically a global maximum of $f(x)$ subject to $g_i(x) \leq 0$.

Furthermore, if $f(x)$ is strictly concave, then the global maximum of $f(x)$ subject to $g_i(x) \leq 0$ is guaranteed to be unique (if it exists).

See this Wikipedia article.

$\endgroup$
7
  • $\begingroup$ Thank you for your answer. Somehow I have the feeling that I don't really understand the difference between a local and a global maximum. Isn't the global maximum always unique? And thank you for editing my post. I missed the sum notation. $\endgroup$
    – PAS
    Jun 23, 2017 at 9:08
  • $\begingroup$ Ah, good point: a global maximum is a point $\mathbb x^\star$ such that $f(\mathbb x^\star) \geq f(x)$ for all $x$. Now consider the concave function $f(x,y) = -x^2$. For any choice of $y$, the point $(0,y)$ is a global maximum! So there are infinitely many global maxima! Notice that $f(x,y) = -x^2$ is concave, but not strictly concave (i.e. it doesn't satisfy the concavity definition with strict inequalities). If we look instead at $f(x,y) = -x^2 - y^2$, which is strictly concave, then you find that it has a unique global maximum at $(0,0)$. Does that answer your question? $\endgroup$
    – Kenny Wong
    Jun 23, 2017 at 9:18
  • $\begingroup$ As I understand it: A global maximum is not always unique. But let's go back to my point above which is also stated in this link: lindo.com/doc/online_help/lingo15_0/… Let's assume I have the above function $f(x)$ with the constraints and I get a solution for $x^*$ which maximizes my function $f(x^*)$. All the Karush-Kuhn-Tucker conditions are satisfied one can say that $x^*$ gives a global maximum for $f(x^*)$ (e. g. Chiang & Wainwright, P. 424) and therefore $x^*$ is the optimal solution and no value for $x$ is better in the domain. Thanks again! $\endgroup$
    – PAS
    Jun 23, 2017 at 10:25
  • $\begingroup$ Sorry, what does your "point above" refer to? And what do you mean by the Karush-Kuhn-Tucker conditions: do you mean the equations $\nabla f = \lambda_i \nabla g_i$, $g_i \leq 0$, $\lambda_i \geq 0$, $g_i \lambda_i = 0$ etc, or do you mean the condition of $f$ being concave and $g$ being convex? Finally, I don't follow the logic of your comment - you seem to be saying "$x^\star$ is a global maximum $\implies$ KKT satisfied (whatever that means) $\implies$ $x^\star$ is a global maximum", which looks like a circular statement. So sorry! $\endgroup$
    – Kenny Wong
    Jun 23, 2017 at 10:36
  • $\begingroup$ By the way, could you please explain what you mean when you say that you don't "really" understand the difference between a local and a global maximum? $\endgroup$
    – Kenny Wong
    Jun 23, 2017 at 10:39
1
$\begingroup$

I'm very sorry if my answer was misleading and I think it is entirely my fault for not making my point clear enough. I think I need a little bit more space so I have to "answer my own question".

The point I was trying to make is the following: We have a maximization problem and the following conditions are satisfied:

(1) $f(x)$ is concave

(2) $g(x)$ is convex

(3) the point $x^*$ is a solution to the maximization problem and satisfies the Karush-Kuhn-Tucker conditions (the one you mentioned in your comment with $∇f=λi∇gi∇f=λi∇gi , gi≤0gi≤0, λi≥0λi≥0, giλi=0giλi=0 $)

then $x^*$ gives a global maximum for $f(x)$ and is therefore the optimal (and best) solution for the optimization problem. (This is exactly the statement made by Chiang and Wainwright, p. 424 in "Fundamental Methods of Mathematical Economics" (I was trying to find an online version of the book but couldn't find one)). They go on and say that "(1), (2) and (3) are sufficient to say that $x^*$ is an optimal solution"

The problem is that even when $f(x)$ is of higher order (and has maybe more than one solution) how do I know that the value $x^*$ is the optimal solution for my maximization problem and gives a global maximum?

About your last comment on "really" understanding global and local optima: A local maximum for $f(x^*)$ is the highest value for $f$ in the immediate neighborhood of $x^*$. But I can't be sure if there is a value for $x$ which is far away from $x^*$ that gives a higher value for $f$. On the other hand a global maximum is the highest value for $f$ in the entire range or domain of $x^*$ and there is no value for $x$ that gives e higher $f$. This does not necessarily mean that $x^*$ is unique.

$\endgroup$
3
  • $\begingroup$ I totally agree. And my point is this: (i) in general, it is possible to find local maxima that are not global maxima. But if $f$ is concave, then every local maximum is also a global maximum. (The graph of a concave function looks like a single hill. A function that looks like a little hill next to a big hill is not a concave function.) $\endgroup$
    – Kenny Wong
    Jun 23, 2017 at 11:59
  • $\begingroup$ (ii) in general, global maxima need not be unique. But if $f$ is strictly concave then the global maximum (if it exists) is unique. (A function that looks like a ridge is concave but not strictly concave; it has infinitely many global maxima. The "strict concavity" condition rules out ridge-shaped functions.) $\endgroup$
    – Kenny Wong
    Jun 23, 2017 at 12:01
  • $\begingroup$ Thank you again. I think I get the point. $\endgroup$
    – PAS
    Jun 23, 2017 at 12:47

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.