# Optimization problems and quantifiers

A simple optimization problem is of form $\max_{x\in\mathcal R}f(x)$.

We can quantify as $\exists x\in\mathcal R\forall y\in\mathcal R f(y)\leq f(x)$.

The quantification here is $\exists\forall$.

1. Is there a meaning to $\forall\exists$ from optimization?

2. What is a good natural meaning to $\forall\exists$ quantification?

• $\forall x\in\mathcal R.\exists y\in\mathcal R.f(y)\leq f(x)$ is simply true tautologically. – Derek Elkins left SE Jul 17 '18 at 19:27
• I am looking for reasonable analogous interpretation. – T.... Jul 17 '18 at 19:35

The $\exists x \forall y$ form of quantification is used to indicate that there is some single object that has a particular relationship to all others, for instance an input that achieves the globally largest objective value in your example.
In $\forall y \exists x$ quantification, there can be a different $x$ for each $y$, but as pointed out in a comment, this is only interesting if the formula being quantified contains more than just a single inequality that allows setting $x=y$. The existence of locally optimal values (that fail to achieve a globally maximal objective value, but are perhaps only a short distance away and still achieve an absolute target value for the objective function) would be expressed in this way.
• Is it fair to tell optimization problems are in $\Sigma_2$? – T.... Jul 18 '18 at 4:37