23
$\begingroup$

Up till now I have just learned that the concept of convexity in functions of one variable is used to complete the graphs of functions, meaning to locate points of inflexion and see if the graph is concave or convex in given intervals. Spivak's book mention that altough this is what we typically learn at calculus, the importance of this concept doesn't lie precisely on ploting graphs and it is really worth to assimilate the information. I'd like to know the main aplications of this concept and it's importance in general.

$\endgroup$
  • 3
    $\begingroup$ If you look at a graduate textbook in Microeconomics, convexity is one of the first concepts introduced as applied to individual utility functions. In plain english, it is a way to mathematically demonstrate that consumers prefer variety over just one product. Though I cannot think of any other specific examples currently, it is commonly used in models involving optimization. $\endgroup$ – GovEcon Aug 8 '13 at 17:07
  • 1
    $\begingroup$ Here's one in finance/bonds: investopedia.com/university/advancedbond/advancedbond6.asp $\endgroup$ – PhD Aug 8 '13 at 18:31
  • 2
    $\begingroup$ In addition to convex optimization and applied math, I'd like to hear more about the role/uses of convex functions in pure math. $\endgroup$ – littleO Aug 9 '13 at 6:52
20
$\begingroup$

Convex functions are particularly easy to minimise (for example, any minimum of a convex function is a global minimum). For this reason, there is a very rich theory for solving convex optimisation problems that has many practical applications (for example, circuit design, controller design, modelling, etc.), see here and here.

I can't remember who's quote this is, or exactly what the quote was, but it basically stated that (EDIT: thanks to Rahul Narain for providing the correct quote now included below):

"In fact the great watershed in optimization isn’t between linearity and nonlinearity, but convexity and nonconvexity." R.T. Rockafellar, "Lagrange Multipliers and Optimality", SIAM Review, 1993.

Aside: I first heard the above paraphrased in a lecture where the speaker (I can't remember who) also mentioned that researchers in the soviet union caught onto the above much sooner than western researchers (I can't vouch personally whether this is true or not).

$\endgroup$
  • 2
    $\begingroup$ If you saw the above mentioned online, the lecturer might have been Stanford's Stephen Boyd. $\endgroup$ – jubobs Aug 8 '13 at 22:37
  • $\begingroup$ @Jubobs you might be right -- I followed his courses online a couple of years ago, they're great. $\endgroup$ – jkn Aug 8 '13 at 22:42
  • 1
    $\begingroup$ Another good application of convex optimization is support vector machines in machine learning. Also, image recovery problems (arising in MRI and medical imaging, for example) use convex optimization. $\endgroup$ – littleO Aug 9 '13 at 6:49
9
$\begingroup$

Convex functions has a lot of applications. It is used for proving some inequalities in easy manner. Also it has lot of applications in operation research, Quadratic and Geometric programming problems etc.

$\endgroup$
9
$\begingroup$

Besides optimization problems (which have already been mentioned in other answers), one common way to make use of convexity is via Jensen's inequality, which has the following nice and concise statement:

"If $f$ is a convex function applied to a bunch of values $x_i$ and their mean $\bar x$, then the mean of the $f$s is greater than or equal to $f$ of the mean. Also, if $f$ is strictly convex, the inequality is strict unless all the $x_i$'s are equal."

The reason this is so useful is that it turns out that, in probability theory, one quite often ends up comparing the averages of some set of values before and after applying a function, and the function quite often turns out, or can be arranged, to be (at least locally) convex.

For example, since the standard deviation of a distribution is the square root of its variance (which in turn is the mean of the squared distances from the mean), and since the square root function is concave, it follows from Jensen's inequality that the sample variance, being an unbiased estimator of the true variance, yields an underestimate of the standard deviation.

For another example, the arithmetic–geometric mean inequality follows directly from Jensen's inequality and the observation that the exponential function is convex (or, equivalently, that the logarithm is concave).

In fact, Jensen's inequality continues to hold even if the mean is replaced by any weighted mean (or, in other words, by any convex combination) of the values, provided that the values are weighted the same way before and after applying $f$.

This fact also has a nice geometric interpretation: if a set of points $(x_i,\,y_i)$ lie on the graph $y=f(x)$ of a convex function $f$, then their convex hull lies entirely above the graph and (assuming $f$ is strictly convex) intersects it only at the points $(x_i,\,y_i)$ themselves:

Graphical illustration of Jensen's inequality

I at least find this connection between geometry and probability theory very elegant, not to mention often handy.

$\endgroup$
5
$\begingroup$

If we speak more generally about convex functions at convex domains in $\mathbb{R^n}$ ($n\geqslant 1$), then this kind of functions has some very nice properties concerning the optimization tasks. At least, it can be proven that every local extremum is also a global extremum and there exists only one such extremum.

$\endgroup$
3
$\begingroup$

Convex analysis has proven that in a certain sense, convexity is the next best thing to linearity. Basically, as soon as you allow inequalities in linear setting, you are immediately in the territory of convex analysis. So convexity arises naturally in the study of dual spaces and weak topologies. In fact, there is a tendency to give the name "convexity" to anything that is nicely compatible with variational minimization problems. On another note, convexity and monotonicity are two sides of the same coin. Importance of monotonicity is something that does not need too much convincing. This link has been exploited e.g. in nonlinear PDEs, such as the Monge-Ampere equations.

$\endgroup$
  • $\begingroup$ That's very interesting. Can you elaborate on this viewpoint or give any references that make this viewpoint clear? In particular the idea that "convexity is the next best thing to linearity". I haven't often seen that point emphasized in convex optimization or convex analysis literature. (Although the book Fundamentals of Convex Analysis by Hirriart-Urruty and Lemarechal does make this point, for example stating that a convex cone [closed under convex combinations] is like the "one-sided" version of a subspace [closed under linear combinations].) $\endgroup$ – littleO Sep 6 '13 at 2:50
  • $\begingroup$ (I meant to say a convex cone is closed under conic combinations.) $\endgroup$ – littleO Sep 7 '13 at 19:53
  • $\begingroup$ I'm also curious to hear more about why the importance of monotonicity is something that does not need too much convincing. $\endgroup$ – littleO Oct 12 '13 at 9:32
  • $\begingroup$ @littleO, a convex hull is the join of affine and cone hulls, and linear span is the meet. In higher dimensions cones can be more than one-sided, eg positive orthant in R^3 is a cone. Similarly, a triangle has 3 sides, intersections of that cone and an affine plane. $\endgroup$ – alancalvitti Nov 23 '14 at 18:19
2
$\begingroup$

Here is a cool example of convexification of a function having an important application: Behcet Acikmese, a current professor at UT Austin, worked at JPL (NASA subset) and developed GNC algorithms. His research developed a fundamental result, known as "lossless convexification", that provides the solution of a general class of nonconvex optimal control problems via computationally tractable convex optimization methods. The algorithm calculated a fuel-optimal trajectory from a current state to a given position, and does so by taking what was once a nonconvex problem and "convexifying" the solution space. Under certain constraints, this will always yield a solution that is inside the original feasible set. I don't know the gory details, but I had a chance to talk with Behcet about his work and the main point he stressed is that solving a convex problem on a computer is orders of magnitude faster than a nonconvex one, so being able to "convexify" the problem and still get an optimal, feasible answer is the holy grail of engineering problems.

$\endgroup$

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.