Open Problems in Convex Analysis and Convex Optimization

Since Convex Analysis is not as old as many other branches of Analysis, I think there are still a lot of unsolved questions in this area, that many of us are not aware of them. Therefore, I decided in this post gather several open problems in convex analysis, and convex optimization (finite or infinite dimensional spaces). This would be helpful for those who are seeking good problems in this areas of research!

The aim of this post is not only focusing on few well-known open problems! If you yourself have conjectured something interesting you may write your problem here (but please point out this is your conjecture).

It would be greatly appreciated if you write problems with citing to some references!

Looking forward to seeing your problems!

Solution 1:

As per Ashkan's request, I'll put up some details about the Chebyshev conjecture, and link to a stronger formulation that I ask here:

Is it possible to partition a real Banach space into closed half-lines?

Given a metric space $(X, d)$ and subset $S \subseteq M$, we can define the distance from a point $x \in X$ and $S$ by $d_S(x) = d(x, S) = \inf_{y\in S} d(x, y)$. The points in $Y$, if any, that achieve this infimum form the set of metric projections of $x$ onto $S$, often denoted $P_S(x)$. This makes $P_S$ a set-valued map with a closed graph.

A set $S$ for which $P_S$ is everywhere single-valued is known as a Chebyshev set. One notable family of Chebyshev sets are closed convex sets in reflexive Banach spaces (the property that all closed convex sets are Chebyshev actually characterises reflexivity, by James' Theorem).

The Chebyshev conjecture is most commonly posed as follows:

"If $C$ is a Chebyshev subset of a Hilbert space $X$, then $C$ is convex."

There's also a stronger version, where the condition of "Hilbert space" is replaced with "smooth, reflexive space".

One particularly famous paper on the (weaker) conjecture was published by Asplund in 1969 called Cebysev Sets in Hilbert Spaces. Asplund presents the following:

• Given a set $S \subseteq X$ (not necessarily convex or Chebyshev), a continuous convex function whose subgradient at each point $x$ contains $P_S(x)$. Specifically, this function is $\phi(x) = \frac{1}{2}\|x\|^2 - \frac{1}{2}d_S(x)^2$.
• If a Chebyshev set has a continuous metric projection, then it is convex (for which he provides two proofs).
• Given any non-convex Chebyshev set $C$, there exists a closed half-space $H$ and point $x$ such that $x$ has no projection onto $C \cap H$. Specifically, this gives us an equivalent formulation: "The intersection of any two Chebyshev subsets of a Hilbert space is also Chebyshev".
• He shows that the Chebyshev conjecture is equivalent to the following:
  • "If $S \subseteq X$ is a set with the property that every point has a unique furthest point, then $S$ is a singleton."
  • "There does not exist a Klee Cavern in $X$: a Chebyshev set that is the complement of an open, non-empty, bounded, convex set."

For more results, there have been a couple of survey papers on the problem:

• V. S. Balaganskii, L. P.Vlasov, The problem of convexity of Chebyshev sets, 1996
• James Fletcher, Warren B. Moors, Chebyshev Sets, 2014

The former is basically comprehensive, although rendered practically unreadable to me by some odd choices in notation. The latter is a far more friendly and geometrically intuitive introduction to the problem.

One other interesting result, covered in both of the above papers, is the construction of a non-convex set in an incomplete inner product space, which I refer to in my question.

It's also worth mentioning a paper by the late great Jon Borwein in 2006, called Proximality and Chebyshev Sets, in which he addresses five conceptually-related open problems:

• The Chebyshev conjecture
• The equivalent formulation involving furthest points
• The stronger Chebyshev conjecture
• "Does every closed set in a reflexive Banach space admit a nearest point? What about rotund smooth renormings of Hilbert space?"
• "Does every closed set in a reflexive Banach space admit proximal normals at a dense set of boundary points?"