Useful links:

1. https://sites.math.washington.edu/~rothvoss/lecturenotes/lasserresurvey.pdf
2. https://web.stanford.edu/class/cs369h/
3. Laurent’s survey [1]
4. https://rameesh-paul.github.io/sos.pdf
5. https://www.ams.jhu.edu/~abasu9/papers/main-Lasserre.pdf
6. Chapter 3 of Ali Kemal Sinop’s PhD thesis

When I started writing this post, I hadn’t found so many “useful links” yet. The content below and link 1.2. only focus on using the Lasserre hierarchy on LPs, while 3.4.5.6. mention more general cases.

1 $K\subset [0,1{]}^n\to K\cap {\left\{0,1\right\}}^n$

We want to solve a 0-1 integer program. Since this task is NP-hard in general, we usually consider its linear relaxation. Different LP formulations have different integrality gaps. For example, consider the following linear relaxation of the max matching IP in non-bipartite graph.

$$\begin{array}{c}\begin{array}{rlrl}\sum _{e\in \delta (v)}x(e)& \le 1& & \forall v\in V\\ x(e)& \in [0,1]& & \forall e\in E\end{array}\end{array}$$ :(, this polytope is not integral. Edmonds proved that the following formulation is integral.

$$\begin{array}{c}\begin{array}{rlrl}\sum _{e\in \delta (v)}x(e)& \le 1& & \forall v\in V\\ x(e)& \in [0,1]& & \forall e\in E\\ \sum _{e\in E[U]}x(e)& \le (|U|-1)/2& & \forall U\subset V,|U|\text{ odd}\end{array}\end{array}$$

Schrijver [2] showed that those odd constraints can be obtained by adding cutting planes to the previous polytope. Fortunately for matching polytope we have a polynomial time separation oracle. However, for harder problems adding cutting planes may make the program NP-hard to solve. Lasserre hierarchy is a method to strengthen the polytope to approaching the integer hull while providing provable good properties and keeping the program polynomial time solvable (if applied constant number of times).

2 Probability Perspective

There is a good interpretation of the linear relaxation of 0-1 integer programs. Let $K=\left\{x\in {\mathbb{R}}^n|Ax\ge b\right\}\subset [0,1{]}^n$ be the polytope of the linear relaxation. The goal of solving the integer program is to describe all possible discrete distribution over $K\cap {\left\{0,1\right\}}^n$. Note that for a fixed distribution the expected position $({\sum }_p\mathrm{Pr}[X_p(1)=1]x_p(1),...,{\sum }_p\mathrm{Pr}[X_p(n)=1]x_p(n){)}^T$ is in $\mathrm{conv}(K\cup {\left\{0,1\right\}}^n)$ and iterating over all possible distribution gives us the integer-hull. Hence we can find the integral optimal solution if having access to all distribution over integer points.

For any $x\in K$, $x_i$ can be seen as the probability of $x_i=1$. We only care about the discrete distribution on feasible integral points. However, each $x\in K$ only describes some marginal probabilities and this this marginal probability may not be even feasible. Consider the following 2D example. Any point in $\text{green area}\setminus \text{orange area}$ is not a marginal distribution of any possible joint distribution over $(0,0),(1,0)$ and $(1,1)$. The idea is to iteratively prune this area.

Now we need to think about how to represent all possible joint distribution. One natural way is to use a vector $y\in {\mathbb{R}}^{2^n}$ for the distribution law of every possible integer point in ${\left\{0,1\right\}}^n$. However, this method does not work well with our existing marginal probabilities. Let $y\in {\mathbb{R}}^{2^n}$ be a random vector such that $y_I=\mathrm{Pr}[{\bigwedge }_{i\in I}(x_i=1)]$ and $y_{\varnothing }=1$. Computing all feasible $y$ is the same as finding all possible bivariate discrete distribution on the integer points. To make $y$ a feasible probability from some joint distribution and to make $(y_{\left\{1\right\}},...,y_{\left\{n\right\}}{)}^T\in K$ we have to add more constraints.

2.1 Feasible Probability

For now let’s forget about $K$ and consider $y\in [0,1{]}^{2^{[n]}}$ and a discrete distribution $D$ on ${\left\{0,1\right\}}^n$. We want to make $y_I={\mathrm{Pr}}_D[{\bigwedge }_{i\in I}(X_i=1)]$. In fact, there is a one to one correspondence between $y$ and $D$. If $D$ is given, computing $y_I$ is easy for any $I\subseteq [n]$. If $y$ is given, recovering the distribution $D$ is the same as solving a system of $2^n$ linear equations with $2^n$ variables ($2^n-1$ of the the equations come form $y_I$, and the remaining one is ${\sum }_{p}D(p)=1$.) Thus, with a slight abuse of notation, we will refer to $y$ as a distribution.

We work with the 2D example first. Let $x=(x_1,x_2{)}^T\in K$ be a marginal distribution. One can see that $y=(1,x_1,x_2,\mathrm{Pr}[X_1=X_2=1]{)}^T$ and the last number is not arbitrary. In fact, $\mathrm{Pr}[X_1=X_2=1]$ must in range $[\max (0,x_1+x_2-1),\min (x_1,x_2)]$.

To make sure $y$ is indeed a probability distribution the moment matrix is considered. The moment matrix $M(y)$ is of size $2^n\times 2^n$ and $M(y)[I,J]$ is defined as the expectation $E[{\prod }_{i\in I\cup J}{X}_i]=y_{I\cup J}$ (the only non-zero term is $1\cdot \mathrm{Pr}[{\bigwedge }_{i\in I\cup j}(X_i=1)]=y_{I\cup J}$). The expectation is taken over the distribution defined by $y$.

Note that in the proof something like sum of squares appears. Lasserre hierarchy has deep connections with SOS optimization and is also known as sum-of-squares hierarchy.

It is psd since $M(y)$ is psd. The determinant is $y_I(1-y_I)\ge 0$.

Let ${\mathrm{Pr}}_D[p]$ be the probability of selecting $p\in {\left\{0,1\right\}}^n$ in $D$. It remains to prove the following system of linear equations has a solution such that ${\mathrm{Pr}}_D[p]\in [0,1]$ for all $p$.

$$\begin{array}{c}\begin{array}{rl}{y}_{[n]}& ={\mathrm{Pr}}_D[1]\\ y_{[n]\setminus \left\{n\right\}}& =\sum _{p:\underset{i\in [n-1]}{\bigwedge }(p_i=1)}{\mathrm{Pr}}_D[p]\\ y_{[n]\setminus \left\{n-1\right\}}& =\sum _{p:\underset{i\in [n]\setminus \left\{n-1\right\}}{\bigwedge }(p_i=1)}{\mathrm{Pr}}_D[p]\\ & ⋮\\ y_{\left\{1\right\}}& =\sum _{p:p_1=1}{\mathrm{Pr}}_D[p]\\ y_{\varnothing }& =\sum _p{\mathrm{Pr}}_D[p]\end{array}\end{array}$$ I believe this can be proven with the idea of Lemma 2 here.

2.2 Projection in $K$

Let the projection of $y$ be $(y_{\left\{1\right\}},\dots ,y_{\left\{n\right\}}{)}^T$. For any $y$ the projection should always lie in $K$. One may want to define moment matrices for constraints $Ax\ge b$. This is called the moment matrix of slacks. For simplicity we only consider one linear constraint $a^{T}x-b\ge 0$. The moment matrix for this constraint is $M(y)={\left({\sum }_{i=1}^n{a}_i{y}_{I\cup J\cup \left\{i\right\}}-b{y}_{I\cup J}\right)}_{I,J\subseteq [n]}$. Then we can do similar arguments.

$$\begin{array}{c}\begin{array}{rl}{z}^{T}M(y)z& =\sum _I\sum _J{z}_I{z}_J(\sum _{i=1}^n{a}_i{y}_{I\cup J\cup \left\{i\right\}}-b{y}_{I\cup J})\\ & =\sum _I\sum _J{z}_I{z}_J(\sum _i{a}_{i}E[\prod _{k\in I\cup J\cup \left\{i\right\}}{X}_k]-bE[\prod _{k\in I\cup J}{X}_k])\\ & =E\left[\sum _I\sum _J{z}_I{z}_J(\sum _i{a}_i{X}_i-b)\prod _{k\in I\cup J}{X}_k\right]\\ & =E\left[(\sum _i{a}_i{X}_i-b){\left(\sum _I{z}_I\prod _{i\in I}{X}_i\right)}^2\right]\end{array}\end{array}$$

Note that we can combine the expectations since they are taken over the same probability distribution. Now assume that we have $a^{T}X-b\ge 0$.

$$\begin{array}{c}\begin{array}{rl}E& \left[(\sum _i{a}_i{X}_i-b){\left(\sum _I{z}_I\prod _{i\in I}{X}_i\right)}^2\right]\\ & =\sum \mathrm{Pr}[\cdots ](a^{T}X-b){\left(\sum _I{z}_I\prod _{i\in I}{X}_i\right)}^2\ge 0\end{array}\end{array}$$

If $a^{T}X\ge b$ is satisfied, then the corresponding slack moment matrix is psd.

Finally, this is a more formal definiton.

Note that the $t$-th level of Lasserre hierarchy only involve entries $y_I$ with $|I|\le 2t+1$. ($+1$ comes from the moment matrix of slacks) The matrices have dimension $\left(\genfrac{}{}{0ex}{}{n}{2t+1}\right)=n^{O(t)}$ and there are only $m+1$ matrices. Thus to optimize some objective over the $t$-th level of Lasserre hierarchy takes $m{n}^{O(t)}$ time which is still polynomial in the input size. (The separation oracle computes eigenvalues and eigenvectors. If there is a negative eigenvalue we find the corresponding eigenvector $v$ and the separating hyperplane is ${\sum }_{I,J}{v}_I{v}_J{x}_{I,J}=0$. See Example 43.)

3 Properties

Almost everything in this part can be found here.

Suppose that we have the $t$-th level of Lasserre hierarchy ${\mathrm{Las}}_t(K)$. Denote by ${\mathrm{Las}}_t^{proj}(K)$ the projection of the $t$-th level.

0. ${\mathrm{Las}}_t(K)$ is convex
1. $y_I\in [0,1]$ for all $y\in {\mathrm{Las}}_t(K)$
2. $0\le y_I\le y_J\le 1$ for all $J\subset I$ with $|I|,|J|\le t$
3. $y_{I\cup J}\le \sqrt{y_I\cdot y_J}$
4. $K\cap {\left\{0,1\right\}}^n\subset {\mathrm{Las}}_t^{proj}(K)$ for all $t\in [n]$
5. ${\mathrm{Las}}_t^{proj}(K)\subset K$
6. ${\mathrm{Las}}_n(K)\subset {\mathrm{Las}}_{n-1}(K)\subset \cdots \subset {\mathrm{Las}}_0(K)$

1.2.3. show that $y$ behaves similarly to a real probability distribution.

4.5.6. show that $K\cap {\left\{0,1\right\}}^n\subset {\mathrm{Las}}_n^{proj}(K)\subset {\mathrm{Las}}_{n-1}^{proj}(K)\subset \cdots \subset {\mathrm{Las}}_0^{proj}(K)=K$.

The goal of this section is to show that $K\cap {\left\{0,1\right\}}^n={\mathrm{Las}}_n^{proj}(K)$. When working on the Lasserre hierarchy, instead of considering the projection $x_i$ solely, we usually perform the analysis on $y$.

3.1 Convex Hull and Conditional Probability

For any $y\in {\mathrm{Las}}_n(K)$ and $S=[n]$, the previous lemma implies the projection of $y$ is convex combination of integral vectors in $K\cap {\left\{0,1\right\}}^n$. Then it follows that ${\mathrm{Las}}_n^{proj}(K)=K\cap {\left\{0,1\right\}}^n$. This also provides proofs for the facts that if $M_n(y)⪰0$ and $M_n^{\ell }(y)⪰0$ then $y$ is indeed a probability distribution and the projection is in $K$.

$y\in {\mathrm{Las}}_t(K)$ is a probability distribution if we consider only $|I|\le t$, $y_I=\mathrm{Pr}[{\bigwedge }_{i\in I}{X}_i=1]$. The vectors $z^{(1)},z^{(2)}$ we constructed in the previous proof can be understood as conditional probabilities. $$\begin{array}{c}\begin{array}{rl}& z_I^{(1)}=\frac{y_{I\cup \left\{i\right\}}}{y_i}=\frac{\mathrm{Pr}[{\bigwedge }_{k\in I\cup \left\{i\right\}}{X}_k=1]}{\mathrm{Pr}[X_i=1]}=\mathrm{Pr}[\underset{k\in I}{\bigwedge }{X}_k=1|X_i=1]\\ & z_I^{(2)}=\frac{y_I-y_{I\cup \left\{i\right\}}}{1-y_i}=\frac{\mathrm{Pr}[{\bigwedge }_{k\in I}(X_k=1)\wedge X_i=0]}{\mathrm{Pr}[X_i=0]}=\mathrm{Pr}[\underset{k\in I}{\bigwedge }{X}_k=1|X_i=0]\end{array}\end{array}$$

The proof is basically showing that

$$\begin{array}{c}\begin{array}{rl}{y}_I& =\mathrm{Pr}[X_i=1]\mathrm{Pr}[\underset{k\in I}{\bigwedge }{X}_k=1|X_i=1]+\mathrm{Pr}[X_i=0]\mathrm{Pr}[\underset{k\in I}{\bigwedge }{X}_k=1|X_i=0]\\ & =\mathrm{Pr}[\underset{i\in I}{\bigwedge }{X}_i=1]\end{array}\end{array}$$

For any partially feasible probability distribution $y\in {\mathrm{Las}}_t(K)$, $y_i\in (0,1)$ implies that both $X_i=0$ and $X_i=1$ happen with non-zero probability, which in turn impies $z^{(1)},z^{(2)}\in {\mathrm{Las}}_{t-1}(K)$. One can also explicitly express $y$ as convex combination and see the relation with Möbius inversion, see p9 in this notes.

In Lemma 4, each vector in the convex combination (those with integer value on $S$, such as $z^{(1)},z^{(2)}$) can be understood as a partial probability distribution under condition $[{\bigwedge }_{i\in I}(X_i=1){\bigwedge }_{j\in J}(X_j=0)]$ where $I\bigsqcup J=S$, and the probability assigned to it is exactly the chance its condition happens. More formally, Lemma 4 implies the following,

Moreover, this distribution is “locally consistent” since the prabability assigned to each vector only depends on its condition.

Since the constraints in ${\mathrm{Las}}_t$ only concern the psdness of certain matrices, one may naturally think about its decomposition. This leads to a vector representation of $y_I$ for all $|I|\le t$ and may be helpful in rounding algorithms. For $J\subset I$, $v_I$ lies on the sphere of radius $\Vert v_J\Vert /2=\sqrt{y_J}/2$ and center $v_J/2$.

3.2 Decomposition Theorem

We have seen that ${\mathrm{Las}}_n^{proj}(K)$ is the integer hull. Can we get better upperbounds based on properties of $K$? Another easy upperbound is ${\max }_{x\in K}|\mathrm{ones}(x)|+1$, where $\mathrm{ones}(x)=\left\{i|x_i=1\right\}$. This is because $y\in {\mathrm{Las}}_t(K)$ is a partial distribution for $|I|\le t$ that can be realized as the marginal distribution of some distribution on $K\cap {\left\{0,1\right\}}^n$; if $k\cap {\left\{0,1\right\}}^n$ does not contain a point with at least $t$ ones, we certainly have $\mathrm{Pr}[{\bigwedge }_{i\in I}(X_i=1)]=0$ for $|I|\ge t$.

This fact implies that for most hard problems we should not expect ${\mathrm{Las}}_k$ to give us a integral solution for constant $k$.

Karlin, Mathieu and Nguyen [3] proved a more general form of Lemma 4 using similar arguments.

4 Moment Relaxation

In this section we briefly show the non-probabilistic view of Lasserre hierarchy and how this idea is used in polynomial optimization problems.

Everything in this section can be found in useful_link[6].

Consider the following polynomial optimiation problem $$\begin{array}{c}\begin{array}{rlrlrl}\min & & a(x)& & & \\ s.t.& & b(x)& \ge 0& & \forall b\in B\\ & & x& \in {\left\{0,1\right\}}^n& & \end{array}\end{array}$$ where $a,b,c$ are polynomials. We want to formulate this problem with SDP.

We can consider polynomials $a,b$ as multilinear polynomials. Since $x_i\in \left\{0,1\right\}$, we have $x_i^2=x_i$. Now we can consider enumerating $x_S={\prod }_{i\in S}{x}_i$ and write these polynomials as linear functions. For example, we can rewrite $a(x)={\sum }_{S\subset [n]}{\sum }_{{\alpha }_S:S\to \mathbb{Z}}{a}_S{\prod }_{i\in S}{x}_i^{{\alpha }_S(i)}$ as ${\sum }_{S\subset [n]}{a}_S{x}_S$ which is linear in the moment sequence $(x_{\varnothing },x_{\left\{1\right\}},\dots ,x_{[n]})$.

Recall that our goal is to find a SDP formulation. A common technique is replace each variable with a vector. We consider the moment vectors $[v_S\in {\mathbb{R}}^{\gamma }{]}_{S\in 2^{[n]}}$. Similar to the LP case, we want $⟨v_A,v_B⟩=x_{A\cup B}$. This is exactly the Gram decomposition of the moment matrix. There exist such moment vectors iff the moment matrix is psd. For $b(x)\ge 0$, we consider the slack moment matrix $M^b(x)={\left({\sum }_S{b}_S{x}_{I\cup J\cup S}\right)}_{I,J}$

Then the program becomes the following SDP

$$\begin{array}{c}\begin{array}{rlrlrl}\min & & \sum _{S\subseteq [n]}{a}_S{x}_S& & & \\ s.t.& & M^b(x)& ⪰0& & \forall b\in B\\ & & M(x)& ⪰0& & \\ & & x_{\varnothing }& =1& & \end{array}\end{array}$$

Note that if the max degree of polynomials $a,b$ is at most $d$, then the following program is a relaxation of the original polynomial optimiation problem (cf. Corollary 3.2.2.).

$$\begin{array}{c}\begin{array}{rlrlrl}\min & & \sum _{S\subseteq [n]}{a}_S{x}_S& & & \\ s.t.& & M_F^b(x)& ⪰0& & \forall b\in B\\ & & M_{F\uplus V_{\le d}}(x)& ⪰0& & \\ & & x_{\varnothing }& =1& & \end{array}\end{array}$$ where $F\subset 2^{[n]}$, $\uplus (A,B)=\left\{a\cup b|\forall a\in A,b\in B\right\}$ is element-wise union and $M_F$ is the submatrix of $M(F)$ on entries $F\times F$. Taking $F=\left(\genfrac{}{}{0ex}{}{[n]}{\le t}\right)$ gives us ${\mathrm{Las}}_t$.

5 Applications

5.1 Sparsest Cut

There are lots of applications in the useful links, but none of them discusses sparsest cut [4].

In [4] Guruswami and Sinop describe Lasserre hierarchy in a slightly different way. (Note that useful_link[6] is Sinop’s thesis) We have seen that $y\in [0,1{]}^{2^{[n]}}$ is sufficient for describing the joint distribution. However, the total number of events is $3^n$, since for each variable $X_i$ in an event there are 3 possible states, $X_i=0,X_i=1$ and $X_i$ is absent.

Instead of using $y\in [0,1{]}^{2^{[n]}}$, they enumerate each of the $3^n$ events and consider the vectors in the Gram decomposition. For each set $S\subset V$ of size $\le r+1$, and for each 0-1 labeling $f$ on elements of $S$, they define a vector $x_S(f)$. Note that $S(f)$ enumerates all events and one should understand $x_S(f)$ as the vector corresponding to $y_{S,f}\in [0,1{]}^{3^{[n]}}$ in the Gram decomposition and $⟨x_S(f),x_T(g)⟩=y_{f(S)\wedge g(T)}$. Then $x_S(f)$ should have the following properties:

1. if $f(S)$ and $g(T)$ are inconsistant, i.e. there is an element $e\in S\cap T$ and $f(e)\ne g(e)$, then one should have $⟨x_S(f),x_T(g)⟩=y_{f(S)\wedge g(T)}=0$.
2. if $f(S)\wedge g(T)$ and $f^{\prime }(A)\wedge g^{\prime }(B)$ are the same event, i.e. $A\cup B=S\cup T$ and the labels are the same, then $⟨x_S(f),x_T(g)⟩=⟨x_A(f^{\prime }),x_B(g^{\prime })⟩$
3. $\Vert x_{\varnothing }{\Vert }^2=1$ here $\varnothing$ is the union of all events.
4. for all $u\in V$, $\Vert x_u(0){\Vert }^2+\Vert x_u(1){\Vert }^2=\Vert x_{\varnothing }{\Vert }^2=1$.
5. for $S\subset V,u\in S$ and $f\in {\left\{0,1\right\}}^{S\setminus \left\{u\right\}}$, $x_S(f\wedge (u=1))+x_S(f\wedge (u=0))=x_{S\setminus \left\{u\right\}}(f)$. (Note that two lhs vectors are orthogonal)

Then write $x_u=x_{\left\{u\right\}}(1)$. The follwing “SDP” is a relaxation of sparsest cut.

$$\begin{array}{c}\begin{array}{rlrl}\min & & \frac{{\sum }_{u<v}{c}_{u,v}\Vert x_u-x_v{\Vert }^2}{{\sum }_{u<v}{D}_{u,v}\Vert x_u-x_v{\Vert }^2}& \\ s.t.& & \sum _{u<v}{D}_{u,v}\Vert x_u-x_v{\Vert }^2& \ge 0\\ & & x\in {\mathrm{Las}}_r(V)& \end{array}\end{array}$$

Scaling every $x_S(f)$ by a factor of the square root of the objective’s denominator gives us a real SDP.

$$\begin{array}{c}\begin{array}{rlrl}\min & & \sum _{u<v}{c}_{u,v}\Vert x_u-x_v{\Vert }^2& \\ s.t.& & \sum _{u<v}{D}_{u,v}\Vert x_u-x_v{\Vert }^2& =1\\ & & x\in {\mathrm{Las}}_r(V),\Vert x_{\varnothing }{\Vert }^2& >0\end{array}\end{array}$$

The rounding method is too complicated, so it won’t be covered here.

5.2 Matching

This application can be found in section 3.3 of useful_link[1]. We consider the maximum matching IP in non-bipartite graphs. Let $K=\left\{x\in {\mathbb{R}}_{\ge 0}^n|{\sum }_{e\in \delta (v)}{x}_e\ge 1\forall v\in V\right\}$ be the polytope and consider ${\mathrm{Las}}_t(K)$. In the notes Rothvoss shows the following lemma.

However, one can see that Lemma 9 is not tight. ${\mathrm{Las}}_0^{proj}(K)$ should be contained in $(1+\frac{1}{2})\cdot \mathrm{conv}(K\cap {\left\{0,1\right\}}^n)$ and ${\mathrm{Las}}_n^{proj}(K)$ should be exactly the integer hull. Can we prove a slightly better gap that matches observations at ${\mathrm{Las}}_0$ and ${\mathrm{Las}}_n$? The later part of the proof in fact shows that $y\in {\mathrm{Las}}_t(K)$ satisfies all odd constraints with $|U|\le 2t+1$. Consider an odd cycle with $2t+3$ vertices. $(1/2,\dots ,1/2{)}^T\in {\mathbb{R}}^{2t+3}$ is a feasible solution in ${\mathrm{Las}}_t(K)$ and proves a tight lowerbound of $k+1/2$.

6 Questions

6.1 Replace $M_t^{\ell }(y)⪰0$ with ${\mathrm{Las}}_t^{proj}(y)\in K$

I don’t see any proof relying on the psdness of slack moment matrices…

It turns out that problems occur in the proof of Lemma 4. If ${\mathrm{Las}}_t(K)$ is defined as $\left\{y|M_t(y)⪰0,y^{proj}\in K\right\}$, then we cannot guarantee $z^{(1)},z^{(2)}\in K$. Without Lemma 4, ${\mathrm{Las}}_n^{proj}(K)$ may not be exactly $K\cap {\left\{0,1\right\}}^n$ and the hierarchy seems less interesting? But an alternative formulation (see Sparsest cut, which entirely ignore the slack moment matrices) still allows good rounding even without Lemma 4. Generally speaking, if the psdness of slack moment matrices is neglected, then we won’t have Law of total probability(Lemma 4); However, we still have “finite additivity property of probability measures”(Lemma 8 (3)).

6.2 Separation Oracle for Implicit $K$

Sometimes $K$ is given in a compact form. For example, consider finding matroid cogirth.

$$\begin{array}{c}\begin{array}{rlrlrl}\min & & \sum _{e\in E}{x}_e& & & \\ s.t.& & \sum _{e\in B}{x}_e& \ge 1& & \forall \text{ base B}\\ & & x_e& \ge 0& & \forall e\in E\end{array}\end{array}$$

If $K$ is only accessable through a separation oracle, is it possible to optimize over ${\mathrm{Las}}_t(K)$ in polynomial time for constant $t$?

References