MIT 6.7220/15.084 — Nonlinear Optimization Thu, Feb 22nd 2024
Lecture 4B
Feasibility, optimization, and separation
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful for any
reports of typos.
Beyond the ellipsoid method, separation also gives rise to deep results about certification of infea-
sibility for optimization problems. To appreciate those, however, we need to make a digression to
appreciate the notion of complexity class for a problem.
1 Decision problems and complexity
Within computer science, one of the main goals of complexity theory is that of classifying problems
into complexity classes.
Decision problems. For the purposes of this lecture, we can focus our attention on decision prob-
lems, 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 𝑥 until an optimal point is isolated.
¹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? Can you think of how one could compute the interval [𝑎, 𝑏] in polynomial time in the input representation?
Complexity classes for decision problems. For the purposes of today, I want to recall three funda-
mental 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 poly-
nomially-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 indeed correct.
Remark 1.1. It is clear from the 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 likely 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 above).
• 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.
²The existence of polynomially-sized certificates of primality was shown by Pratt, V. R. [Pra75].
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 𝑚 in-
equalities 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 2.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 convex. 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
⟨𝑢, 𝑏⟩ < 𝑣 and ⟨𝑢, 𝐴𝑥 + 𝑠⟩ ≥ 𝑣 ∀𝑥 ∈ ℝ𝑛, 𝑠 ∈ ℝ𝑚
≥0.
Setting 𝑠 = 𝑥 = 0, we find that ⟨𝑢, 0⟩ ≥ 𝑣, from which it follows that 𝑣 ≤ 0 and therefore ⟨𝑢, 𝑏⟩ <
0.
Setting 𝑠 = 0 but letting 𝑥 be arbitrary in ℝ𝑛, we have
⟨𝑢, 𝐴𝑥⟩ ≥ 𝑣 ∀𝑥 ∈ ℝ𝑛 ⟺ ⟨𝐴⊤𝑢, 𝑥⟩ ≥ 𝑣 ∀𝑥 ∈ ℝ𝑛.
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 𝑘 ≥ 0 and 𝑒𝑖 is the 𝑖-th indicator vector,³ we find
that
⟨𝑢, 𝑘𝑒𝑖⟩ ≥ 𝑣 ⟹ ⟨𝑢, 𝑒𝑖⟩ ≥
𝑣
𝑘 .
Since 𝑘 ≥ 0 is arbitrary and 𝑣 ≤ 0, then ⟨𝑢, 𝑒𝑖⟩ ≥ 0, that is, the 𝑖-th coordinate of 𝑢 is nonnegative.
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. □
³That is, the vector containing all zeros except in position 𝑖, where it has a one.
Bibliography
[DR80] D. P. Dobkin and S. P. Reiss, “The complexity of linear programming,” Theoret. Comput.
Sci., vol. 11, no. 1, pp. 1–18, May 1980, doi: 10.1016/0304-3975(80)90031-6.
[AKS04] M. Agrawal, N. Kayal, and N. Saxena, “PRIMES is in P,” Ann. Of Math., vol. 160, no. 2,
pp. 781–793, 2004, doi: 10.4007/annals.2004.160.781.
[Pra75] V. R. Pratt, “Every Prime Has a Succinct Certificate,” SIAM Journal on Computing, vol.
4, no. 3, pp. 214–220, 1975, doi: 10.1137/0204018.
Lecture 4B
Feasibility, optimization, and separation
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful for any
reports of typos.
Beyond the ellipsoid method, separation also gives rise to deep results about certification of infea-
sibility for optimization problems. To appreciate those, however, we need to make a digression to
appreciate the notion of complexity class for a problem.
1 Decision problems and complexity
Within computer science, one of the main goals of complexity theory is that of classifying problems
into complexity classes.
Decision problems. For the purposes of this lecture, we can focus our attention on decision prob-
lems, 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 𝑥 until an optimal point is isolated.
¹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? Can you think of how one could compute the interval [𝑎, 𝑏] in polynomial time in the input representation?
Complexity classes for decision problems. For the purposes of today, I want to recall three funda-
mental 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 poly-
nomially-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 indeed correct.
Remark 1.1. It is clear from the 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 likely 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 above).
• 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.
²The existence of polynomially-sized certificates of primality was shown by Pratt, V. R. [Pra75].
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 𝑚 in-
equalities 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 2.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 convex. 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
⟨𝑢, 𝑏⟩ < 𝑣 and ⟨𝑢, 𝐴𝑥 + 𝑠⟩ ≥ 𝑣 ∀𝑥 ∈ ℝ𝑛, 𝑠 ∈ ℝ𝑚
≥0.
Setting 𝑠 = 𝑥 = 0, we find that ⟨𝑢, 0⟩ ≥ 𝑣, from which it follows that 𝑣 ≤ 0 and therefore ⟨𝑢, 𝑏⟩ <
0.
Setting 𝑠 = 0 but letting 𝑥 be arbitrary in ℝ𝑛, we have
⟨𝑢, 𝐴𝑥⟩ ≥ 𝑣 ∀𝑥 ∈ ℝ𝑛 ⟺ ⟨𝐴⊤𝑢, 𝑥⟩ ≥ 𝑣 ∀𝑥 ∈ ℝ𝑛.
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 𝑘 ≥ 0 and 𝑒𝑖 is the 𝑖-th indicator vector,³ we find
that
⟨𝑢, 𝑘𝑒𝑖⟩ ≥ 𝑣 ⟹ ⟨𝑢, 𝑒𝑖⟩ ≥
𝑣
𝑘 .
Since 𝑘 ≥ 0 is arbitrary and 𝑣 ≤ 0, then ⟨𝑢, 𝑒𝑖⟩ ≥ 0, that is, the 𝑖-th coordinate of 𝑢 is nonnegative.
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. □
³That is, the vector containing all zeros except in position 𝑖, where it has a one.
Bibliography
[DR80] D. P. Dobkin and S. P. Reiss, “The complexity of linear programming,” Theoret. Comput.
Sci., vol. 11, no. 1, pp. 1–18, May 1980, doi: 10.1016/0304-3975(80)90031-6.
[AKS04] M. Agrawal, N. Kayal, and N. Saxena, “PRIMES is in P,” Ann. Of Math., vol. 160, no. 2,
pp. 781–793, 2004, doi: 10.4007/annals.2004.160.781.
[Pra75] V. R. Pratt, “Every Prime Has a Succinct Certificate,” SIAM Journal on Computing, vol.
4, no. 3, pp. 214–220, 1975, doi: 10.1137/0204018.