MIT 6.7220/15.084 — Nonlinear Optimization (Spring ‘25) Tue, Feb 25th 2025
Lecture 6
Separation as a proof system
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
Beyond the ellipsoid method, separation also gives rise to deep results about certification
of infeasibility for optimization problems. To appreciate those, however, we need to make
a digression to appreciate the notion of complexity class for a problem.
L6.1 Decision problems and complexity
Within computer science, one of the main goals of complexity theory is that of classifying
problems into complexity classes.
L6.1.1 Decision problems
For the purposes of this lecture, we can focus our attention on decision problems, that is,
those problems for which we seek to construct an algorithm whose output is either true or
false. Examples of decision problems include the following:
• PRIME: given as input an integer 𝑛 (encoded in binary), return true if 𝑛 is a prime
number, and false otherwise.
• FACTOR: given as input two integers 𝑛 and 𝑚 (encoded in binary), return true if 𝑛 has
an integer divisor in the range [2, 𝑚], and false otherwise.
• LP: given a set 𝐴𝑥 ≤ 𝑏 of 𝑚 inequalities in 𝑛 variables with rational coefficients
(encoded as fractions of numbers encoded in binary), return true if the set {𝑥 ∈ ℝ𝑛 :
𝐴𝑥 ≤ 𝑏} is nonempty, and false otherwise.
Note that while these are decision problems, if we knew that a correct algorithm correctly
solves the problem in time polynomial in the input, we could use such an algorithm to solve
a search problem.
• For example, if FACTOR was known to be solvable in polynomial time, then we could
factorize an integer 𝑚 by binary searching the largest factor 𝑛, divide 𝑚 by 𝑛, and
repeat, taking a total of log2(𝑚) times the runtime of the algorithm.
• Similarly, when faced with a generic linear program
min
𝑥
s.t.
𝑐⊤𝑥
𝐴𝑥 ≤ 𝑏
𝑥 ∈ ℝ𝑛,
we could first establish a range [𝑎, 𝑏] such that, for sure, the optimal value would fall
within the range. Then, we could find the value 𝑐⊤𝑥 at optimality by performing a
binary search on the interval [𝑎, 𝑏]. At each iteration, we could check if at optimality
𝑐⊤𝑥 ≤ 𝛾 by using the algorithm for LP to check whether the system of inequalities
𝐴𝑥 ≤ 𝑏, 𝑐⊤𝑥 ≤ 𝛾
has a solution. If yes, then we would decrease 𝛾; if not, then we would have overshot
on our guess, and we would need to increase 𝛾.¹ Armed with the value of the optimum,
we could then perform another binary search for each coordinate of 𝑥.
L6.1.2 Complexity classes for decision problems
Let’s recall three fundamental complexity classes.
• A decision problem is in the complexity class P if there exists an algorithm that in
polynomial time (in the size of the input description) returns the correct answer.
• A decision problem is in the complexity class NP if for all true instances there exists
a polynomially-sized (in the size of the input description) certificate that can be given
as input to a polynomial-time verification algorithm. The verification algorithm takes
as input the problem instance and the certificate, and outputs true if and only if the
certificate proves that the decision true on the problem instance is indeed correct.
• A decision problem is in the complexity class co-NP if for all false instances there
exists a polynomially-sized (in the size of the input description) certificate that can be
given as input to a polynomial-time verification algorithm. The verification algorithm
takes as input the problem instance and the certificate, and outputs true if and only
if the certificate proves that the decision false on the problem instance is correct.
Remark L6.1. It is clear from definition that every problem in P is automatically in NP
and also in co-NP. So, P ⊆ NP ∩ co-NP. A major open question in complexity theory
is proving whether P = NP ∩ co-NP. The general consensus is that P ≠ NP ∩ co-NP.
In light of the remark, finding problems that are in NP ∩ co-NP and yet provably cannot be
solved in polynomial time is a major open question. Linear programming is one example of
problem famously in NP ∩ co-NP (we will see how such a result rests firmly on separation).
• For a long time, people conjectured that linear programming (LP) was not in P. See
for example this excerpt from the introduction of a paper by Dobkin, D. P., & Reiss,
S. P. [DR80]:
They were proven wrong by the ellipsoid method. This should give a bit more context
as to why the ellipsoid method was such a surprising development to warrant the front
page of the New York Times (see Lecture 5).
• PRIME is another important problem that is known to be in NP ∩ co-NP (this is not
obvious, but with a bit of number theory it can be shown using only elementary
results on cyclic groups²). PRIME was shown to also be in P in a breakthrough result
by Agrawal, M., Kayal, N., & Saxena, N. [AKS04].
• Finally, also FACTOR is in NP ∩ co-NP. This problem is not currently known to be in P.
L6.2 Linear programming belongs to NP ∩ co-NP
It is pretty straightforward that LP is in NP. This is because if a system of inequalities
𝐴𝑥 ≤ 𝑏 has a solution, then the solution itself is the certificate, and one can verify that
the certificate is correct by carrying out the matrix-vector product 𝐴𝑥 and checking that
indeed 𝐴𝑥 ≤ 𝑏.³
It is significantly less obvious that LP is in co-NP, that is, that whenever 𝐴𝑥 ≤ 𝑏 does
not have a solution, we can still certify that in polynomial time with a polynomially-sized
certificate.
How would you certify that 𝐴𝑥 ≤ 𝑏 has no solution? Here is a case in which a polynomially-
sized certificate can be given. Suppose that there exist nonnegative multipliers 𝑦1, ..., 𝑦𝑚 for
the 𝑚 inequalities defined by 𝐴𝑥 ≤ 𝑏 with the following property:
• Multiply each inequality 𝑎⊤
𝑗 𝑥 ≤ 𝑏𝑗 by 𝑦𝑗;
• Then, sum all inequalities, obtaining a new inequality in which the left-hand side is
identically 0, and the right-hand side is (strictly) negative.
Then, the original system of inequalities was clearly unsatisfiable. In this case, the vector
𝑦 = (𝑦1, ..., 𝑦𝑚) is a valid certificate of infeasibility. One (perhaps unexpected?) consequence
of separation is that the above certificate must always exist when 𝐴𝑥 ≤ 𝑏 is infeasible. This
result typically goes under the name of Farkas lemma.
Theorem L6.1 (Farkas lemma). Let 𝐴𝑥 ≤ 𝑏 be a system of inequalities where 𝐴 ∈ ℝ𝑚×𝑛.
Then, exactly one of the following options is true:
• either 𝐴𝑥 ≤ 𝑏 has a solution; or
• there exists a vector 𝑦 ≥ 0 such that 𝐴⊤𝑦 = 0 and 𝑏⊤𝑦 < 0.
Proof. As mentioned, the proof of this result relies on separation. In particular, consider
the set
Ω ≔ {𝐴𝑥 + 𝑠 : 𝑥 ∈ ℝ𝑛, 𝑠 ∈ ℝ𝑚
≥0} ⊆ ℝ𝑚,
The set Ω is a convex cone. Furthermore, if 𝑏 ∈ Ω, then this means that 𝑏 = 𝐴𝑥⋆ + 𝑠⋆ for
some 𝑥⋆ ∈ ℝ𝑛 and 𝑠⋆ ≥ 0; so, 𝐴𝑥⋆ = 𝑏 − 𝑠⋆ ≤ 𝑏, which shows that 𝐴𝑥 ≤ 𝑏 has a solution.
On the other hand, if 𝑏 ∉ Ω, then we can use separation!
In particular, if 𝑏 ∉ Ω, we know that there must exist 𝑢 ∈ ℝ𝑚 such that
⟨𝑢, 𝑏⟩ < 0 and ⟨𝑢, 𝐴𝑥 + 𝑠⟩ ≥ 0 ∀𝑥 ∈ ℝ𝑛, 𝑠 ∈ ℝ𝑚
≥0.
Setting 𝑠 = 0 but letting 𝑥 be arbitrary in ℝ𝑛, we have
⟨𝑢, 𝐴𝑥⟩ ≥ 0 ∀𝑥 ∈ ℝ𝑛 ⟺ ⟨𝐴⊤𝑢, 𝑥⟩ ≥ 0 ∀𝑥 ∈ ℝ𝑛.
Since 𝑥 is arbitrary, the only vector 𝐴⊤𝑢 that can possibly satisfy such a condition is
𝐴⊤𝑢 = 0. Hence, the vector 𝑢 ∈ ℝ𝑛 that arises from separation serves as a valid certificate
𝑦.
Finally, setting 𝑥 = 0 and 𝑠 = 𝑒𝑖 ≥ 0, where 𝑒𝑖 is the 𝑖-th indicator vector,4 we find that
⟨𝑢, 𝑒𝑖⟩ ≥ 0.
Since 𝑖 was arbitrary, this shows that 𝑢 ≥ 0, completing the proof of existence of the
certificate of infeasibility.
This shows that either the first bullet or the second bullet holds. To complete the proof,
we need to show that it is not possible that they both hold. This is trivial: if 𝐴⊤𝑦 = 0
and 𝑏⊤𝑦 < 0, then no solution to 𝐴𝑥 ≤ 𝑏 can possibly exist, as that would imply that
0 = (𝑦⊤𝐴)𝑥 = 𝑦⊤(𝐴𝑥) ≤ 𝑦⊤𝑏 < 0, a contradiction. □
Bibliography for this lecture
[DR80] Dobkin, D. P., & Reiss, S. P. (1980). The complexity of linear programming. The
oret. Comput. Sci., 11(1), 1–18. https://doi.org/10.1016/0304-3975(80)90031-6
[Pra75] Pratt, V. R. (1975). Every Prime Has a Succinct Certificate. SIAM Journal on
Computing, 4(3), 214–220. https://doi.org/10.1137/0204018
[AKS04] Agrawal, M., Kayal, N., & Saxena, N. (2004). PRIMES is in P. Ann. Of Math.,
160(2), 781–793. https://doi.org/10.4007/annals.2004.160.781
Changelog
• Feb 25, 2025: Simplified proof of Farkas lemma using conic separation.
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful
for any reports of typos.
¹Several details are missing from this description, but the main idea of using the binary search was the
really important insight; the rest can be fixed. Can you think of how you could deal with an infeasible or
unbounded linear program? How could one compute the interval [𝑎, 𝑏] in polynomial time in the input?
²The existence of polynomially-sized certificates of primality was shown by Pratt, V. R. [Pra75].
³Here, we are ignoring subtleties related to the encoding of numbers on machines. This is not a problem
in our case: if 𝐴𝑥 ≤ 𝑏 has a solution, then it must have a rational solution encodable using polynomially
many bits [▷ Try to prove this].
4That is, the vector containing all zeros except in position 𝑖, where it has a one.
Lecture 6
Separation as a proof system
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
Beyond the ellipsoid method, separation also gives rise to deep results about certification
of infeasibility for optimization problems. To appreciate those, however, we need to make
a digression to appreciate the notion of complexity class for a problem.
L6.1 Decision problems and complexity
Within computer science, one of the main goals of complexity theory is that of classifying
problems into complexity classes.
L6.1.1 Decision problems
For the purposes of this lecture, we can focus our attention on decision problems, that is,
those problems for which we seek to construct an algorithm whose output is either true or
false. Examples of decision problems include the following:
• PRIME: given as input an integer 𝑛 (encoded in binary), return true if 𝑛 is a prime
number, and false otherwise.
• FACTOR: given as input two integers 𝑛 and 𝑚 (encoded in binary), return true if 𝑛 has
an integer divisor in the range [2, 𝑚], and false otherwise.
• LP: given a set 𝐴𝑥 ≤ 𝑏 of 𝑚 inequalities in 𝑛 variables with rational coefficients
(encoded as fractions of numbers encoded in binary), return true if the set {𝑥 ∈ ℝ𝑛 :
𝐴𝑥 ≤ 𝑏} is nonempty, and false otherwise.
Note that while these are decision problems, if we knew that a correct algorithm correctly
solves the problem in time polynomial in the input, we could use such an algorithm to solve
a search problem.
• For example, if FACTOR was known to be solvable in polynomial time, then we could
factorize an integer 𝑚 by binary searching the largest factor 𝑛, divide 𝑚 by 𝑛, and
repeat, taking a total of log2(𝑚) times the runtime of the algorithm.
• Similarly, when faced with a generic linear program
min
𝑥
s.t.
𝑐⊤𝑥
𝐴𝑥 ≤ 𝑏
𝑥 ∈ ℝ𝑛,
we could first establish a range [𝑎, 𝑏] such that, for sure, the optimal value would fall
within the range. Then, we could find the value 𝑐⊤𝑥 at optimality by performing a
binary search on the interval [𝑎, 𝑏]. At each iteration, we could check if at optimality
𝑐⊤𝑥 ≤ 𝛾 by using the algorithm for LP to check whether the system of inequalities
𝐴𝑥 ≤ 𝑏, 𝑐⊤𝑥 ≤ 𝛾
has a solution. If yes, then we would decrease 𝛾; if not, then we would have overshot
on our guess, and we would need to increase 𝛾.¹ Armed with the value of the optimum,
we could then perform another binary search for each coordinate of 𝑥.
L6.1.2 Complexity classes for decision problems
Let’s recall three fundamental complexity classes.
• A decision problem is in the complexity class P if there exists an algorithm that in
polynomial time (in the size of the input description) returns the correct answer.
• A decision problem is in the complexity class NP if for all true instances there exists
a polynomially-sized (in the size of the input description) certificate that can be given
as input to a polynomial-time verification algorithm. The verification algorithm takes
as input the problem instance and the certificate, and outputs true if and only if the
certificate proves that the decision true on the problem instance is indeed correct.
• A decision problem is in the complexity class co-NP if for all false instances there
exists a polynomially-sized (in the size of the input description) certificate that can be
given as input to a polynomial-time verification algorithm. The verification algorithm
takes as input the problem instance and the certificate, and outputs true if and only
if the certificate proves that the decision false on the problem instance is correct.
Remark L6.1. It is clear from definition that every problem in P is automatically in NP
and also in co-NP. So, P ⊆ NP ∩ co-NP. A major open question in complexity theory
is proving whether P = NP ∩ co-NP. The general consensus is that P ≠ NP ∩ co-NP.
In light of the remark, finding problems that are in NP ∩ co-NP and yet provably cannot be
solved in polynomial time is a major open question. Linear programming is one example of
problem famously in NP ∩ co-NP (we will see how such a result rests firmly on separation).
• For a long time, people conjectured that linear programming (LP) was not in P. See
for example this excerpt from the introduction of a paper by Dobkin, D. P., & Reiss,
S. P. [DR80]:
They were proven wrong by the ellipsoid method. This should give a bit more context
as to why the ellipsoid method was such a surprising development to warrant the front
page of the New York Times (see Lecture 5).
• PRIME is another important problem that is known to be in NP ∩ co-NP (this is not
obvious, but with a bit of number theory it can be shown using only elementary
results on cyclic groups²). PRIME was shown to also be in P in a breakthrough result
by Agrawal, M., Kayal, N., & Saxena, N. [AKS04].
• Finally, also FACTOR is in NP ∩ co-NP. This problem is not currently known to be in P.
L6.2 Linear programming belongs to NP ∩ co-NP
It is pretty straightforward that LP is in NP. This is because if a system of inequalities
𝐴𝑥 ≤ 𝑏 has a solution, then the solution itself is the certificate, and one can verify that
the certificate is correct by carrying out the matrix-vector product 𝐴𝑥 and checking that
indeed 𝐴𝑥 ≤ 𝑏.³
It is significantly less obvious that LP is in co-NP, that is, that whenever 𝐴𝑥 ≤ 𝑏 does
not have a solution, we can still certify that in polynomial time with a polynomially-sized
certificate.
How would you certify that 𝐴𝑥 ≤ 𝑏 has no solution? Here is a case in which a polynomially-
sized certificate can be given. Suppose that there exist nonnegative multipliers 𝑦1, ..., 𝑦𝑚 for
the 𝑚 inequalities defined by 𝐴𝑥 ≤ 𝑏 with the following property:
• Multiply each inequality 𝑎⊤
𝑗 𝑥 ≤ 𝑏𝑗 by 𝑦𝑗;
• Then, sum all inequalities, obtaining a new inequality in which the left-hand side is
identically 0, and the right-hand side is (strictly) negative.
Then, the original system of inequalities was clearly unsatisfiable. In this case, the vector
𝑦 = (𝑦1, ..., 𝑦𝑚) is a valid certificate of infeasibility. One (perhaps unexpected?) consequence
of separation is that the above certificate must always exist when 𝐴𝑥 ≤ 𝑏 is infeasible. This
result typically goes under the name of Farkas lemma.
Theorem L6.1 (Farkas lemma). Let 𝐴𝑥 ≤ 𝑏 be a system of inequalities where 𝐴 ∈ ℝ𝑚×𝑛.
Then, exactly one of the following options is true:
• either 𝐴𝑥 ≤ 𝑏 has a solution; or
• there exists a vector 𝑦 ≥ 0 such that 𝐴⊤𝑦 = 0 and 𝑏⊤𝑦 < 0.
Proof. As mentioned, the proof of this result relies on separation. In particular, consider
the set
Ω ≔ {𝐴𝑥 + 𝑠 : 𝑥 ∈ ℝ𝑛, 𝑠 ∈ ℝ𝑚
≥0} ⊆ ℝ𝑚,
The set Ω is a convex cone. Furthermore, if 𝑏 ∈ Ω, then this means that 𝑏 = 𝐴𝑥⋆ + 𝑠⋆ for
some 𝑥⋆ ∈ ℝ𝑛 and 𝑠⋆ ≥ 0; so, 𝐴𝑥⋆ = 𝑏 − 𝑠⋆ ≤ 𝑏, which shows that 𝐴𝑥 ≤ 𝑏 has a solution.
On the other hand, if 𝑏 ∉ Ω, then we can use separation!
In particular, if 𝑏 ∉ Ω, we know that there must exist 𝑢 ∈ ℝ𝑚 such that
⟨𝑢, 𝑏⟩ < 0 and ⟨𝑢, 𝐴𝑥 + 𝑠⟩ ≥ 0 ∀𝑥 ∈ ℝ𝑛, 𝑠 ∈ ℝ𝑚
≥0.
Setting 𝑠 = 0 but letting 𝑥 be arbitrary in ℝ𝑛, we have
⟨𝑢, 𝐴𝑥⟩ ≥ 0 ∀𝑥 ∈ ℝ𝑛 ⟺ ⟨𝐴⊤𝑢, 𝑥⟩ ≥ 0 ∀𝑥 ∈ ℝ𝑛.
Since 𝑥 is arbitrary, the only vector 𝐴⊤𝑢 that can possibly satisfy such a condition is
𝐴⊤𝑢 = 0. Hence, the vector 𝑢 ∈ ℝ𝑛 that arises from separation serves as a valid certificate
𝑦.
Finally, setting 𝑥 = 0 and 𝑠 = 𝑒𝑖 ≥ 0, where 𝑒𝑖 is the 𝑖-th indicator vector,4 we find that
⟨𝑢, 𝑒𝑖⟩ ≥ 0.
Since 𝑖 was arbitrary, this shows that 𝑢 ≥ 0, completing the proof of existence of the
certificate of infeasibility.
This shows that either the first bullet or the second bullet holds. To complete the proof,
we need to show that it is not possible that they both hold. This is trivial: if 𝐴⊤𝑦 = 0
and 𝑏⊤𝑦 < 0, then no solution to 𝐴𝑥 ≤ 𝑏 can possibly exist, as that would imply that
0 = (𝑦⊤𝐴)𝑥 = 𝑦⊤(𝐴𝑥) ≤ 𝑦⊤𝑏 < 0, a contradiction. □
Bibliography for this lecture
[DR80] Dobkin, D. P., & Reiss, S. P. (1980). The complexity of linear programming. The
oret. Comput. Sci., 11(1), 1–18. https://doi.org/10.1016/0304-3975(80)90031-6
[Pra75] Pratt, V. R. (1975). Every Prime Has a Succinct Certificate. SIAM Journal on
Computing, 4(3), 214–220. https://doi.org/10.1137/0204018
[AKS04] Agrawal, M., Kayal, N., & Saxena, N. (2004). PRIMES is in P. Ann. Of Math.,
160(2), 781–793. https://doi.org/10.4007/annals.2004.160.781
Changelog
• Feb 25, 2025: Simplified proof of Farkas lemma using conic separation.
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful
for any reports of typos.
¹Several details are missing from this description, but the main idea of using the binary search was the
really important insight; the rest can be fixed. Can you think of how you could deal with an infeasible or
unbounded linear program? How could one compute the interval [𝑎, 𝑏] in polynomial time in the input?
²The existence of polynomially-sized certificates of primality was shown by Pratt, V. R. [Pra75].
³Here, we are ignoring subtleties related to the encoding of numbers on machines. This is not a problem
in our case: if 𝐴𝑥 ≤ 𝑏 has a solution, then it must have a rational solution encodable using polynomially
many bits [▷ Try to prove this].
4That is, the vector containing all zeros except in position 𝑖, where it has a one.