It is always lovely when you can form a convex polyhedron with a discrete optimization problem.  It gives you properties you can exploit, some that you have pointed out.  The application I'd like to point out is Scheduling.  Scheduling is pretty notorious for exploiting properties of convex polyhedra if the problem as an optimization problem can be formulated as a relaxed LP (of its IP counterpart).  Of course this usually means solving a linear program then rounding can be used (or in some realms is avoided, but instead primal-dual approaches are found at times).  

Here is an example of how (the rounding theorem in this paper is the crux of how):  https://www.researchgate.net/publication/4355176_Approximation_algorithms_for_scheduling_unrelated_parallel_machines

The above link is to a very important 2-approximation algorithm that showed how you can tackle heterogeneous computer scheduling (unrelated parallel machines) with linear programming, and still matches the best approximation factor to this date (some others have been proposed with the same approximation factor).  New results still draw from this paper to this date (see the cited in, there are a lot).

The notion of convexity can be applied to optimization problems and give us a better understanding of how well or just how we can approximate intractable problems.

Hope this helps :)!

Conference Paper Approximation Algorithms for Scheduling Unrelated Paralle Machines

It is always lovely when you can form a convex polyhedron with a discrete optimization problem.  It gives you properties you can exploit, some that you have pointed out.  The application I'd like to point out is Scheduling.  Scheduling is pretty notorious for exploiting properties of convex polyhedra if the problem as an optimization problem can be formulated as a relaxed LP (of its IP counterpart).  Of course this usually means solving a linear program then rounding can be used (or in some realms is avoided, but instead primal-dual approaches are found at times).  

Here is an example of how (the rounding theorem in this paper is the crux of how):  https://www.researchgate.net/publication/4355176_Approximation_algorithms_for_scheduling_unrelated_parallel_machines

The above link is to a very important 2-approximation algorithm that showed how you can tackle heterogeneous computer scheduling (unrelated parallel machines) with linear programming, and still matches the best approximation factor to this date (some others have been proposed with the same approximation factor).  New results still draw from this paper to this date (see the cited in, there are a lot).

The notion of convexity can be applied to optimization problems and give us a better understanding of how well or just how we can approximate intractable problems.

Hope this helps :)!

Conference Paper Approximation Algorithms for Scheduling Unrelated Paralle Machines

Dear Vyacheslav,

Many thanks for your observations.    If possible, please post links to optimal placement and image processing, especially in segmentation.    One obvious way to segment an image using the idea of convexity is to do the following:

superimpose a Voronoi diagram on a image.   The Voronoi diagram consists of convex polygons that cover an image.     The sample Voronoi diagrams were produced using Mathematica  (see, e.g., the 2D colour diagram, where convex polygon is filled with a single colour).   In segmenting an image using this idea, it will be necessary to decide what part of an image each convex polygon would cover.    Do you have any suggestions?

Dear Daniel,

Many thanks for your observations.   Do you have any examples of intractable problems that have been approximated using the notion of convexity?    One thing comes to mind about how one might solve the approximation problem.   Try J.M. Lien's approach, where we relax the convex set requirement and allow shapes to be partially convex.    There are many examples showing partial convexity in

http://cs.gmu.edu/~jmlien/research/app-cd/lien-dissertation.pdf

I remember two recent notions pertained to "convexity" in mathematical physics:

1) convexity theorem of Atiyah in symplectic manifold. 2) recent amplituhedron as convex polytopes in twistor-momentum space that simplifies the calculation of scattering amplitudes in particle and high energy physics.

Dear Vyacheslav,

As a followup to what you observed, I found the following report:

Y.G. Stoyan, N.I. Gil', A. Pankratov, G. Scheithauer, Packing non-convex polytopes into a parallelepiped, Technische Universitat Dresden, 2004:

http://www.math.tu-dresden.de/~scheith/ABSTRACTS/PREPRINTS/04-non-conv.pdf

Here the trick is to consider convex sub-regions in looking for local minima.

Dear Manouchehr,

I found the following paper:

W. Schmaltz, The Atiyah-Guillemin-Sternberg convexity theorem, 2010:

http://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Schmaltz.pdf

The Atiyah-Guillemin-Sternberg convexity theorem is given (with a proof) in Section 8, p. 12.   Is this the theorem you mentioned?

Yes exactly, and a few similar articles where the relation between volume (measure) of convex polytopes toral varieties, angular momentum and algebraic geometry has been explored, the reason of my interest is the possible relation between probability amplitudes explained in the context of amplituhedron and the Koushnirenko theorem mentioned in an article by Atiah :ANGULAR MOMENTUM,CONVEX POLYHEDRA

AND ALGEBRAIC GEOMETRY. These diverse concepts may originate from a hidden  common background.

Dear Jim,

Your question forms one the kernels of mathematics! It may cove a very large part of mathematics. As for applications I can think of:

Economics: Optimisation

Algebraic Topology: 

[Günter_Ewald]_Combinatorial_Convexity_and_Algebraic_Geometry

[John_R_Stallings]_Lectures_on_polyhedral_topology

Jakob Jonsson, Simplicial Complexes of Graphs, Springer.

Various applications:

Convex Sets and Their Applications (Dover Books on Mathematics) Paperback – June 5, 2007  by Steven R. Lay

Dear @James, seems the application of convex sets is present in so many areas. I will mention the application of convex sets in the are of system science, dynamical systems and control. I have attached 3 papers bellow!  The formulation of convex optimization problems as Linear Matrix inequalities in Systems and Control is known for a long time and it is solved by MATLAB.It seems that the possibility of convex sets application is inexhaustible!

http://www-verimag.imag.fr/~maler/Papers/reach-infinity.pdf

http://www.sciencedirect.com/science/article/pii/0022247X87900953

http://infoscience.epfl.ch/record/111904/files/KKL-ECC07.pdf

Dear Costas,

Many thanks for your observations and pointers towards applications of convexity.

Dear Ljubomir,

Yes, convex sets are omni-present and very useful in quite a few applications such as those mentioned by @Costas and by you.   

Dear James,

Aside from the convex sets in Euclidean spaces either abstract or geometric used in applications (optimization, control theory, etc) and for the sake of abstract studies that are closed  by segment connectivity, to see that notion of being convex outside of mathematics, any matter that constantly moves, rotates and have frictions with an outside physical matter tends to become convex - as the edges or corners that pointed inward, reasons of concavity,  forced to disappear over time.

The universe is a convex set in which no dent will exist as it rotates and moves outward constantly.  We also see that things in nature that tend to be stable are either convex or star-shaped as the existence of dents make them loose stability and eventually disappear from existence or from their original position.

Dear James,

I am teaching the course of engineering optimization. One section is devoted to definition of convexity and convex sets. If the objective function and constraints are all convex , we will have a convex programming problem. These problems have the property that any local minimum must be a global minimum.

Real word convex optimizations problems are not very common in civil engineering and most of problems are non-convex. I have attached a Ph.D. thesis in topology optimization in which convex modeling is used:

Zhao, X. (2013). Convex modeling based topology optimization under load uncertainty (Doctoral dissertation, RUTGERS THE STATE UNIVERSITY OF NEW JERSEY-NEW BRUNSWICK).

Dear Behrouz,

Your engineering optimisation course covers some noteworthy topics and the report by A. Ben-Tal, Convex optimization in engineering: modeling, analysis, algorithms is interesting.

2011 was a bumper year for doctoral dissertations on convexity and convex optimisation.    Perhaps you will find the following thesis helpful for your course:

Martin Jaggi, Sparse Convex Optimization Methods for Machine Learning, Ph.D. thesis, 2011:

http://m8j.net/math/thesis.pdf

This thesis presents some interesting aspects of convex functions.    See, e.g., Section 2.3, starting on page 20, convex optimisation.

A good introduction to convexity and optimisation is given in

C. Vinzant, Real Algebraic Geometry in Convex Optimization, Ph.D thesis, 2011:

http://www-personal.umich.edu/~vinzant/thesisVinzant.pdf

Convexity in sets [ http://en.wikipedia.org/wiki/Convex_set ] silently implies the notion of closure: The set is closed for every specific linear combination of its elements with coefficients added to unity, ie

k1 x1+k2 x2 + ... + kn xn  belongs to  S,  for all xi,i=1,2,...,n of S, with k1+k2+...+kn=1

Thus we have a special case of closure, which is fundamental in Mathematics. I remind that both Algebra & Topology are based on closure.

The problem is that, like Taylor series expansion and linearization processes, there also exists a false attitude that all problems can be 'convexitable', ie we can find a convex approximation of them. This practice has led to big fallacies, especially in optimization algorithms.

I may add some references on convexity:

Jan van Tiel Convex Analysis An Introductory Text

Constantin Niculescu, LarsErik Persson Convex Functions and Their Applications

Ralph Tyrell Rockafellar Convex analysis

The first is an introductory text and the last two advanced.

Dear Costas,

The added references are very helpful.   I just now found an online copy of

C.P. Niculescu, Convex Functions and Their Applications.   A Contemporary Approach.  SPIN Springer, 2004, x + 250pp:

http://carma.newcastle.edu.au/jon/Preprints/Books/CUP/CUPold/np-convex.pdf

This book has 255 references, 10 pages, 236-246,

extensive keyword index, 247-250,

indexed major theorems, p. 250

helpful list of symbols, 1-3

5 details appendices, including Appendix A Background on Convex Sets, 197-206

The book itself is well-written.

@Demetris Christopoulos: ...there also exists a false attitude that all problems can be 'convexitable', ie we can find a convex approximation of them. This practice has led to big fallacies, especially in optimization algorithms.

If possible, please give examples of falacies found in optimization algorithms.   It would be interesting to see where attempts at convex approximation have failed.

Dear James, besides applications, convex sets are an object of unbelievable deep theoretical study. Convex compact sets in Rn build a Baire space, so it makes sense to speak about their topological majority (where a minority is a subset of first Baire category, and the majority is ist complement). An intersection of finitely many topological majorities is again a topological majority, so one can speak about the typical convex body. Following Victor Klee, most convex bodies are strictly convex, C1 and not C2. Many other typical properties followed, some of them discovered by Tudor Zamfirescu. The portrait of the typical convex body looks really weird, and is, to sum up, a strong existence theorem. It is really hard to imagine how the typical convex body is, when we try to put all typical properties together...

Many models, that are used every day as valid, have been built upon a hidden convexity issue.Take for example the Markowitz portfolio theory:

http://stephenkinsella.net/WordPress/wp-content/uploads/2008/02/mark91.pdf

And all utility theory (even Economics as a feild) have as requirement convexity.

A smal  example: in Greece we have three oil refiners. Can you define convexity constraints with such a small number? Maybe no, but all theory is based on convexity.

Dear @George and @Demetris,

Yes, many thanks for the suggestions about mathematical finance and econometrics.    See, for example,

E. Hazan, Efficient Algorithms for Online Convex Optimization and Their Applications, Ph.D. thesis, Princeton University, 2006:

http://ie.technion.ac.il/~ehazan/papers/thesis.pdf

See Chapter 3, starting on page 39, experiments with portfolio management.