3
$\begingroup$

Suppose we are trying to solve the following optimization problem: $$ \text{maximize } ~~ c\cdot y \\ \text{subject to } ~~ y\in S $$ where the region $S$ is described by an exponential number of constraints. We assume that $S$ is non-empty and convex, and that the problem has an optimal solution.

Suppose a separation oracle for $S$ was available, i.e., an oracle that given a vector $y$ does one of the following:

  1. says that $y$ is feasible ($y \in S$).
  2. says that $y$ is infeasible ($y \notin S$). In this case, it returns a violated constraint.

Then, we could have solved our problem with the following variant of the Ellipsoid method (called the sliding objective function technique): based on the oracle answer, a cut through $y$ is made to reduce the size of the current ellipsoid. If the oracle said that $y$ is infeasible, a feasibility cut is made with the returned violated constraint; otherwise, if the oracle said that $y$ is feasible, an optimality cut is made with respect to the objective function. Eventually, the returned solution is the vector with the highest objective value among all vectors deemed feasible by the oracle.

Now suppose that we only have access to a limited randomized version of the separation oracle. Given a vector $y$, it still returns one of the two options described above. When it says that $y$ is infeasible (option 2), it is always correct; but, when it says that $y$ is feasible (option 1), it may be incorrect, but we assume that it is right with high probability. In particular, assume that we know that the probability of success is $(1-\epsilon)$ for some small $\epsilon$.

What will happen if we use this randomized separation oracle inside this variant of the Ellipsoid method? Notice that an incorrect answer can only be returned when an optimality cut needs to be applied (only when the oracle says that $y$ is feasible), can we conclude that it only affects the optimiality?

Let $T$ be an upper bound on the number of iterations in any execution of the deterministic Ellipsoid method variant (the first one described) on our LP. If we used this randomized separation oracle once in each iteration, would it be reasonable to claim that the returned solution is an optimal solution with probability at least $(1-\epsilon)^T$?

[ intuitively, since each operation of the oracle is independent, the value $(1-\epsilon)^T$ gives a lower bound on the probability that we received a correct answer in all the iterations. ]

If so, can we increase the success probability of this Ellipsoid method variant to the same level as the success probability of the oracle (i.e., at least $(1-\epsilon)$) by operating it more than once at each iteration? Is there a way to relate the number of times we need to run the oracle in each iteration to $T$?

$\endgroup$
8
  • $\begingroup$ @NealYoung Thank you for your response! I edited the question, hope it's a bit more clear now. Your second comment may provide a solution to my problem. In practice, there is a randomized alg that I want to use as-is as a part of my separation oracle implementation, but I wasn't sure what the consequences would be. Furthermore, I tried to understand how the success probability of the oracle would affect the success probability of the ellipsoid method. Can you explain why $O(\log T(S))$ times should be enough? can we give a lower bound on the probability that an optimal solution will be found? $\endgroup$ Jan 6, 2023 at 22:49
  • $\begingroup$ @NealYoung The separation oracle may say that the vector $y$ is infeasible. Suppose we use the Central-Cut Ellipsoid Method ["Geometric Algorithms and Combinatorial Optimization" by Grötschel et al.], then in each iteration, the oracle is given the center of the current ellipsoid (desceibed by the vector $y$) and it needs to determine whether it is feasible. Accordingly, a cut is made and a smaller ellipsoid is considered. The ellipsoid variant I used for optimization is the 'sliding objective function technique' in which if a feasible vector was found then an optimality cut is made. $\endgroup$ Jan 7, 2023 at 10:13
  • $\begingroup$ @NealYoung I edited the question again and added more details about the specific variant of the ellipsoid method that I used. Your questions and observations have been very helpful to me. Thank you. $\endgroup$ Jan 7, 2023 at 16:41
  • 1
    $\begingroup$ If the oracle says that $y$ is feasible, and it is not, then the optimality cut might yield an ellipsoid that has an empty intersection with $S$, so all following solutions will be infeasible. In this case, your algorithm might return a solution that is infeasible, and better than all feasible solutions. $\endgroup$ Jan 7, 2023 at 19:48
  • $\begingroup$ @NealYoung (1) the answer is option (b) $k$ is an upper bound (I'll try to clarify this in the question). (2) I'm not sure what you mean by cost queries. The oracle only answers the quation "does $y$ belong to $S$?" if the answer is NO then we can be sure that indeed $y \notin S$, but if the answer is YES we can only be sure that $y \in S$ with high probability. $\endgroup$ Jan 7, 2023 at 21:01

1 Answer 1

2
$\begingroup$

Yes, given your conditions the probability of a correct result is at least $(1-\epsilon)^T$.

This seems to follow from standard calculations, so maybe I am missing something. Here are the calculations so you can check.

Fix an instance of your problem. Consider the random experiment of running ellipsoid with the randomized oracle that you describe. Let r.v. $N$ be the number of queries to the oracle made by ellipsoid. For $t\ge 0$, let $X_t$ be the event that the oracle returns a correct answer in each of the first $\min(t, N)$ iterations.

  1. First observe that, $(\forall t\ge 1)~\Pr[X_t | X_{t-1}] \ge 1-\epsilon]$.
    (Indeed, by assumption, in any single iteration, the oracle returns a correct answer with probability at least $1-\epsilon$. So, for all $t\ge 1$, $$\Pr[X_t ~|~ N \ge t \wedge X_{t-1}] \ge 1-\epsilon.$$ By definition of $X_t$, $$\Pr[X_t ~|~ N < t \wedge X_{t-1})] = 1.$$ So $$ \begin{aligned} \Pr[X_t ~|~ X_{t-1}] & {} = \Pr[N \ge t] \Pr[X_t ~|~ N \ge t \wedge X_{t-1}] \\ & ~~+ \Pr[N < t]\Pr[X_t ~|~ N < t \wedge X_{t-1}] \\ & {} \ge \Pr[N \ge t] (1-\epsilon) + \Pr[N < t] \\ & {} \ge 1-\epsilon, \end{aligned} $$ as claimed.)

  2. It follows that $(\forall t\ge 0)~\Pr[X_t] \ge (1-\epsilon)^t$.
    (Indeed, by definition $\Pr[X_0] = 1$, so for $t\ge 1$ $$ \begin{aligned} \Pr[X_t] & {} \ge \Pr[X_t | X_{t-1}] \Pr[X_{t-1}]\\ & {} \ge (1-\epsilon) \Pr[X_{t-1}] && \text{(by Step 1 above)}\\ & {} \ge (1-\epsilon) (1-\epsilon)^{t-1} && \text{(inductively)}\\ & {} = (1-\epsilon)^t, \end{aligned} $$ as claimed.)

  3. So $\Pr[X_T] \ge (1-\epsilon)^T$. Now suppose $X_T$ occurs. That is, the oracle doesn't fail within the first $\min(N, T)$ iterations. Then those first $\min(N, T)$ iterations are the same as they would be with a correct deterministic oracle. So (by definition of $T$) in this case the process returns a correct result. So $\Pr[\text{a correct result}] \ge \Pr[X_T] \ge (1-\epsilon)^T$. $~~~\Box$

$\endgroup$
5
  • $\begingroup$ My real goal was to understand how to relate the success probability of the oracle to the success probability of the ellipsoid method in order to (as you wrote in one of your earlier comments) increase the success-probability of this randomized ellipsoid method by calling the oracle more times in each iteration. I hope it's okay to ask if you could elaborate on why you wrote $O(\log(T))$ times? Is there a calculation that explains why it should work? All I managed to prove was that $\log_{\epsilon}[1-(1-\epsilon)^{\frac{1}{T}}]$ times would be sufficient, but not to directly relate it $T$. $\endgroup$ Jan 8, 2023 at 8:51
  • 1
    $\begingroup$ Consider replacing the oracle, say $A(y)$, by an oracle $A_d(y)$ that does the following: it calls $A(y)$ repeatedly, returning the violated constraint if/when $A(y)$ returns one, or if that doesn't happen within $d$ calls to $A(y)$, returns "feasible". Then the probability that $A_d(y)$ incorrectly says "feasible" in a given call is at most $1-\epsilon^d$. So, using $A_d$ instead of $A$, overall failure probability is at most $1-(1-\epsilon^d)^T \le 1 - (1-T\epsilon^d) = T\epsilon^d$, which is small if $d \gg \log(T)/\log(1/\epsilon)$. $\endgroup$
    – Neal Young
    Jan 8, 2023 at 12:31
  • 1
    $\begingroup$ Furthermore, in an iteration when $y\not\in S$, the expected number of calls that $A_d(y)$ makes to $A(y)$ is at most $1/(1-\epsilon) = 1+O(\epsilon)$. Note that each iteration of the other kind (where $y\in S$ and $A_d(y)$ makes $d$ calls to $A(y)$) is one in which ellipsoid adjusts the cost estimate, so presumably there are not so many of those iterations (and if for some reason there were, you could modify ellipsoid to use binary search for the cost instead, and then there wouldn't be). So perhaps using $A_d$ won't slow ellipsoid down much. $\endgroup$
    – Neal Young
    Jan 8, 2023 at 12:35
  • 1
    $\begingroup$ BTW if you are interested in actually solving LP's like this in practice, there are probably more practical (faster) algorithms (e.g. using column generation or lagrangian-relaxation, depending on the type of your LP). $\endgroup$
    – Neal Young
    Jan 8, 2023 at 12:42
  • 1
    $\begingroup$ Thank you, your answers (and questions) have been really helpful. I'll look into the practical algorithm as well. $\endgroup$ Jan 8, 2023 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.