Optimization Procedures, Lecture

Topics/Exam Questions, Spring 2024

  1. What is the fundamental task of optimization? What do we mean by linear programming (LP)? Provide an example of an optimization problem that can be formulated as an LP (non-trivially).
  2. What is the fundamental task of optimization? What do we mean by quadratic programming (QP)? When do we say a QP problem is convex? Provide an example of an optimization problem that can be formulated as QP (non-trivially). Is its example convex?
  3. What is the fundamental task of optimization? What do we mean by integer programming (IP)? Provide an example of an optimization problem that can be formulated as IP (non-trivially).
  4. Describe how to obtain the Lagrange dual of a primal problem. What do we denote by p* and d*? State the weak duality theorem. What are the normal forms of an LP problem? Minimize a linear function over Rn. Dualize one of the LP normal forms.
  5. Write down how we can obtain the Lagrange dual of a primal problem. What are denoted by p* and d*? State the weak duality theorem. Minimize a homogeneous quadratic function on Rn. Dualize a problem that can be brought into a QP form.
  6. Write down how we can obtain the Lagrange dual of a primal problem. What norms do you know? Define the concept of dual norm. Dualize the problem of minimizing a norm under linear constraints.
  7. Write down how we can obtain the Lagrange dual of a primal problem. Define the concept of convex conjugate of a real-valued function. Dualize a problem of minimizing an objective function under linear constraints.
  8. Write down the conditions of the Slater's theorem. Define sets E and F and state their fundamental properties. State the separation theorem for convex sets. Write down its consequence in the proof of the Slater's theorem. In what cases are we "almost done" and why?
  9. If there exist optimal solutions for both primal and dual, then prove the weak duality theorem as a single sequence of inequalities. Analyze the case of equality (of course, under certain conditions if necessary). Write down the KKT conditions and state the Karush-Kuhn-Tucker theorem. Prove the theorem.
  10. Describe the solution sets of systems of equations: Ax=0, Ax=b, Ax≤=0, Ax≤=b. Define the necessary basic concepts: linear subspace, affine subspace, polyhedral cone, polyhedron. Describe the segment AB, the line AB using vectors. Define the concepts of linear combination, affine combination, cone combination, convex combination. Alternative description of polyhedral cones and polyhedra: stating the Minkowski-Weyl theorem.
  11. The boundary point, supporting hyperplane, and supporting hyperplane of a convex set. Faces of polyhedra. Concept of vertices. Characterization of vertices. Regular polyhedra. Refined form of the Minkowski-Weyl theorem.
  12. LP problem on regular polyhedra: Relationship between vertices and optimal points (theorem and proof). LP problem with integer coefficients: stating and proving the theorem.
  13. Define the basic IP problem. What do we mean by LP relaxation of an IP problem? What is the relationship between the optimal values of the original and the relaxed problems? When do we call a regular polyhedron integral? State the Edmonds-Giles theorem. Prove the Edmonds-Giles theorem.
  14. Define the basic IP problem. What do we mean by LP relaxation of an IP problem? What is the relationship between the optimal values of the original and the relaxed problems? When do we call a regular polyhedron integral? Define the TU property of matrices. Write down an example matrix set that has the TU property. Prove it. If the matrix of an inequality system describing a polyhedron has the TU property and its constants are integers, then the polyhedron is integral. Prove this. Provide an application of this theorem.
  15. Define the basic IP problem. What do we mean by LP relaxation of an IP problem? What is the relationship between the optimal values of the original and the relaxed problems? When do we call a regular polyhedron integral? Define the TDI property of inequality systems. State the previous Edmonds-Giles theorem and derive from it that a TDI system describes an integral polyhedron.
  16. Define the basic IP problem. What do we mean by LP relaxation of an IP problem? What is the relationship between the optimal values of the original and the relaxed problems? When do we call a regular polyhedron integral? Define the TDI property of inequality systems. Define the matching polytope. State Edmonds' theorem on this polytope. If you consider this theorem as two inclusions, which one is simpler and why? State the Cunningham-Marsh theorem.
  17. Describe the matching polytope of a graph. What do we mean by the testing problem of this polytope? What is the naive start of the testing algorithm? Why can we assume that the vector to be tested satisfies the vertex constraints with equality?
  18. Describe the matching polytope of a graph. What do we mean by the testing problem of this polytope? If the vector to be tested satisfies the vertex constraints with equality, what kind of cut problem needs to be solved? Define the Gomory-Hu tree. How can it be used to extract answers to cut problems? Prove the submodular lemma. [See handout pdf file from the "Cuts" slide to the "Further Information in a Gomory–Hu Tree" slide and the "Introductory Lemma"+"Proof" slide.]
  19. Describe the PP polytope of independent sets in a graph. Provide an "upper bound" for this polytope. Define the clique constraints. Give examples where your upper bounds are exact, and ones where they are not. [See handout pdf file from the beginning to the "Another Example" slide.]
  20. Define perfect and nice graphs. Give examples of perfect and non-perfect graphs. State the strong and weak perfect graph conjectures/theorems. State the Chvátal-Fulkerson theorem. Write down the two statements from the lecture that imply both of the above theorems. [See handout pdf file from the "Colorings, Cliques" slide to the "Two Sides of the Fulkerson—Chvátal Theorem" slide.]
  21. Descriptions of positive semidefinite matrices. Inner product in the realm of symmetric matrices. Define the basic problem of semidefinite programming. Normal forms.
  22. Lagrange dualization procedure for SDP. Characterization of positive semidefinite matrices using inner products.
  23. Eigenvalues and SDP. Parameters alpha(G) and khi (G) OR estimation of alpha(G) with eigenvalues (Hoffman theorem). (Your choice!) Squeezing the estimates.
  24. Graph Shannon capacity, elementary estimates. Orthogonal representation of graphs. C5 and the umbrella construction. Lovász theta function.
  25. Combinatorial optimization problems and vector relaxation, approximation algorithms using SDP techniques: Goemans-Williamson algorithm OR Coloring of 3-colorable graphs. (Your choice!)