Using convexity in optimization
Using graphical analysis
Here we look at the solution of Example 6.4 from the mt3042 Optimization Guide by M. Baltovic:
subject to , .
are assumed to be positive. This could be about maximizing revenue from selling two goods, and those familiar with graphical analysis in Economics can immediately say that the maximum is achieved where is tangent to The first two constraints are not binding. The proof of the Kuhn-Tucker theorem shows that then we can use the Lagrangian that doesn't involve the nonbinding constraints. The implicit function existence condition necessary for application of the Lagrange theorem is and it is satisfied everywhere except at the origin. The FOC's are
I leave to the reader to find the solution:
Graphical analysis in a more educated way
A set is called convex if, together with any two points belonging to it, it contains the whole segment connecting those two points. A square and a disk are convex. A heart is not convex (all sets are considered with their interiors and boundaries).
For a function , the set of points lying on and above the graph is called an epigraph. is called convex if its epigraph is convex. Examples of convex functions: a linear function , a paraboloid , an exponential function . Examples of functions that are not convex: , a parabola with .
Maximum principle. A convex function on a compact convex domain attains its maximum only on the boundary.
Geometric interpretation of the gradient: let be differentiable. Then the gradient , at any given point shows the direction in which the growth of the function is the fastest.
In our case both the function and the domain are convex, so by the maximum principle the maximum is attained on the boundary. Since the gradient is , the values of the function cannot be maximized at the coordinate axes. Thus, only the third constraint can be binding. The rest of the solution employs the Lagrangian as above.
Compare the above solutions with the three-page solution from Baltovic (pp.93-96).
Main lessons: (1) Don't pedantically look through all possible combinations of constraints. This can be good only in a multidimensional problem where you have no geometric guidance. (2) Use geometry, convexity or any other means to figure out which constraints are binding. Then the proof of the Kuhn-Tucker theorem tells you that you can work with the Lagrangian with only binding constraints included. Check the constraint qualification (which I call the implicit function existence condition) only for binding constraints.
Leave a Reply
You must be logged in to post a comment.