Optimization problems with good characterization, but no polynomial-time algorithm Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the maximum value of $f(x)$ over $n$-bit strings $x$?

Let us say that such a problem has a minimax characterization, if there is another polynomial-time computable function $g$, such that 
$$\max_x f(x) = \min_y g(y)$$ holds. Here $x$ runs over all $n$-bit strings, and $y$ runs over all $m$-bit strings; $n$ and $m$ may be different, but they are polynomially related. 

Numerous natural and important optimization problems have such minimax characterization. A few examples (the theorems on which the characterizations are based shown in parenthesis): 


   Linear Programming  (LP Duality Thm),   Maximum Flow   (Max Flow Min Cut Thm),   Max Bipartite Matching   (Konig-Hall Thm),   Max Non-Bipartite Matching   (Tutte's Thm, Tutte-Berge formula),   Max Disjoint Arborescences in directed graph   (Edmond's Disjoint Branching Thm),   Max Spanning Tree Packing in undirected graph    (Tutte's Tree Packing Thm),    Min Covering by Forests   (Nash-Williams Thm),   Max Directed Cut Packing   (Lucchesi-Younger Thm),   Max 2-Matroid Intersection   (Matroid Intersection Thm),   Max Disjoint Paths   (Menger's Thm),   Max Antichain in Partially Ordered Set   (Dilworth Thm), and many others.


In all these examples, a polynomial-time algorithm is also available to find the optimum. My question: 


  Is there any optimization problem with a minimax characterization, for which no polynomial-time algorithm has been found so far?


Note: Linear Programming was in this status for about 30 years!
In some technical sense you are asking whether $P = NP \cap coNP$.  Suppose that $L \in NP \cap coNP$, thus there exists poly-time $F$ and $G$ so that $x \in L$ iff $\exists y: F(x,y)$ and $x \not\in L$ iff $\exists y: G(x,y)$.  This can be recast as a minmax characterization by
$f_x(y) = 1$ if $F(x,y)$ and $f_x(y) = 0$ otherwise; $g_x(y) = 0$ if $G(x,y)$ and $g_x(y) = 1$
otherwise.  Now indeed we have $max_y f_x(y) = min_y g_x(y)$.

So in this sense, any problem known to be in $NP \cap coNP$ but not known to be in $P$ can be turned into an answer to your question.  E.g. Factoring (say, the decision version of whether the $i$'th bit of the largest factor is 1).