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?

| cite | improve this question | | | | |
  • 1
    $\begingroup$ $\forall x\in\mathcal R.\exists y\in\mathcal R.f(y)\leq f(x)$ is simply true tautologically. $\endgroup$ – Derek Elkins left SE Jul 17 '18 at 19:27
  • $\begingroup$ I am looking for reasonable analogous interpretation. $\endgroup$ – 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.

| cite | improve this answer | | | | |
  • $\begingroup$ Can you provide a concrete example? $\endgroup$ – T.... Jul 18 '18 at 1:59
  • $\begingroup$ Is it fair to tell optimization problems are in $\Sigma_2$? $\endgroup$ – T.... Jul 18 '18 at 4:37

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.