Optimization Procedures, Lecture

Topics/Exam Questions, Spring 2025

  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 your 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).
  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 polytope of a graph's matching. What do we understand by its testing problem? What is the naive start of the testing algorithm? Assume that the vector to be tested satisfies the vertex conditions by equality. In this case, reformulate the testing problem as a cutting problem. What cutting problems do you remember? What is their complexity? Define the Gomory-Hu tree. How can you read answers to cutting problems from this?
  18. Describe the polytope of a graph's matching. What do we understand by its testing problem? Define a graph's Gomory-Hu tree. State the main lemma and prove it. In its proof, prove the submodular property as well (for the appropriate function). Write down the segmentation procedure that outputs the Gomory-Hu tree.
  19. Write down the vertex packing polytope of a graph. Provide an "upper bound" for this polytope. Define the clique constrains. Give examples where its upper bounds are accurate and where they are not.
  20. Define nice and perfect graphs. Give examples of perfect and non-perfect graphs. State the strong and weak perfect graph conjecture/theorem. Give alternative definitions for the perfect graph property ((*), (*+) properties). Define the blow up operation of a perfect graph with cliques. Prove that this yields a perfect graph.
  21. State the weak perfect graph conjecture/theorem. State the Chvatal-Fulkerson theorem. Write down the two statements from the lecture from which both the above theorems follow. Choose one and prove it.
  22. Descriptions of positive semidefinite matrices. Inner product in the realm of symmetric matrices. Define the basic problem of semidefinite programming. Normal forms.
  23. Lagrange dualization procedure for SDP. Characterization of positive semidefinite matrices using inner products.
  24. Eigenvalues and SDP. Parameters alpha(G) and khi (G) OR estimation of alpha(G) with eigenvalues (Hoffman theorem). (Your choice!) Squeezing the estimates.
  25. Graph Shannon capacity, elementary estimates. Orthogonal representation of graphs. C5 and the umbrella construction. Lovász theta function.
  26. Combinatorial optimization problems and vector relaxation, approximation algorithms using SDP techniques: Goemans-Williamson algorithm OR Coloring of 3-colorable graphs. (Your choice!)