Spring 2022/23 Paper (Short Questions))

Question 1

How could you encode each of the following as linear constraints? Assume that x and y are specified as binary decision variables, where the value 0 means “not selected” and 1 means “selected”.
(i) Exactly one of x and y is selected.
(ii) At most one of them is selected.
(iii) If x is selected, then y is also selected.
(iv) If x is selected, then y is not selected.

Answer 1

(i) x + y = 1
(ii) x + y ≤ 1
(iii) x ≤ y
(iv) x + y ≤ 1

Question 2

If x* is the optimal objective function value of P and y* is the optimal function value of P’, then x≥ y

Answer 2

True: Adding a constraint to maximization problem (from P to P’) either leaves the feasible region unchanged or reduces it. Thus, the maximum value in P’ cannot exceed the maximum value of P, hence x≥ y

Question 3

If y is a feasible solution of P’, y will also be feasible for P

Answer 3

True: Since P’ includes all the constraints of P plus at least one additional constraint, any solution that satisfies all the constraints of P’ must also satisfy the constraints of P

Question 4

If x is optimal solution of P and x is feasible for P’, then x will be optimal for P’

Answer 4

True: Since adding a constraint can only reduce the feasible region or keep it unchanged, x being feasible and optimal in P makes it optimal in P’ as well, provided it remains within the feasible region of P’

Question 5

Given a LP with five variables, it is known that (0,3,0,1,4) is a feasible solution. Lets suppose that we solve the associated dual problem. Which of the following cases are possible ….

(i) The dual problem has optimal bounded solution
(ii) The dual problem is infeasible
(iii) The dual problem is unbounded

Answer 5

(iii) The dual problem is unbounded.

If the primal problem is feasible but optimal, the dual problem could potentially be unbounded. This occurs if there is no upper bound on the objective function value in the dual problem that aligns with a primal feasible region allowing indefinite improvement

Question 6

If the right-hand side term of a constraint changes, but without leaving its sensitivity interval, which of the following will remain unchanged ?

(i) the composition of the basis
(ii) the value of the basic variables
(iii) the value of the objective function

Answer 6

(i) the composition of the basis.

When a right hand side of a constraint changes, without leaving its sensitivity interval, the composition of the basis does not change. While both the value for the basic variables and objective function change.

Question 7

Intersection of two convex sets is convex (True/False)

Answer 7

True: The intersection of two convex sets is always convex

Question 8

Union of two convex sets is convex (True/False)

Answer 8

False: The union of two convex sets is not necessarily convex.

Question 9

When minimizing a convex function over a convex set, a local minimum is necessarily a global minimum (True/False)

Answer 9

True: One fundamental property of convex functions is that any local minimum is also a global minimum when the function is defined over a convex set.

Question 10

Set of points contained in a high-dimensional rectangle is an example of a convex set (True/False)

Answer 10

True: A high-dimensional rectangle (hyperrectangle) is a product of intervals, and like lower-dimensional rectangles, it is a convex set.

Question 11

Is the LP given by ….

maximize x1 + x2
subject to.. x1 - x3 ≤ 4
x1 + x2 ≥ 2
x1 + x3 ≤ -1
x1, x2, x3 ≥ 0

(i) infeasible, or
(ii) unbounded, or
(iii) has an optimal solution?

Answer 11

(i) Infeasible

Given that constraint 3 “x1 + x3 ≤ -1” is inherently unsatisfiable under the non-negativity restrictions, the entire set of constraints cannot be satisfied simultaneously, thus the LP is infeasible

Question 12

Consider a maximisation integer-linear program and let w∗ be its optimal objective function value. Let the optimal objective function value of its linear programming relaxation be v∗ and let y∗ be the objective function value of a feasible solution of
the dual of its linear programming relaxation. Which of the following statements is true? Briefly explain your answer.

(i) w∗ ≤ v∗ ≤ y∗
(ii) w∗ ≤ v∗ ≥ y∗
(iii) w∗ ≥ v∗ ≤ y∗
(iv) w∗ ≥ v∗ ≥ y∗

Answer 12

(ii) w∗ ≤ v∗ ≥ y∗

w: the optimal objective function value of the maximization integer-linear program.
v: optimal objective function value of the linear programming relaxation of the ILP
y*: objective function value of the feasible solution of the dual LP relaxation.

Each derivative of the previous format of the ILP, cannot be bigger than what it was derived from.

Question 13

Consider a primal problem P and its dual problem D. If D is infeasible, what can we say about P ?

(i) It is possible that P is infeasible
(ii) It is possible that P is unbounded
(iii) It is possible that P has an optimal solution
(iv) P can be either infeasible, unbounded or optimal; infeasible D doesn’t limit P in any way

Answer 13

(i) It is possible that P is infeasible: TRUE
(ii) It is possible that P is unbounded: TRUE
(iii) It is possible that P has an optimal solution: FALSE
(iv) P can be either infeasible, unbounded or optimal; infeasible D doesn’t limit P in any way: FALSE

An unbounded primal implies its dual is infeasible under certain conditions, but an infeasible dual does not necessarily mean the primal is unbounded or feasible.

Question 14

When Newton’s Method is started from a point near the solution, it will converge very quickly (True/False)

Answer 14

TRUE: Newton’s Method is known for its rapid convergence properties, particularly when started close to the solution.

Question 15

In descent methods, the particular choice of search direction does not matter so much (True/False)

Answer 15

FALSE: The choice of search direction is crucial in descent methods. The direction, typically chosen to be in the negative of the gradient, is fundamental to ensure that each step moves towards a local minimum.

Question 16

Techniques such as gradient descent, ADAM optimization, and quasi-newton method are often used to optimize the cost function in machine learning techniques, even though cost functions are not necessarily convex. (True/False)

Answer 16

TRUE: These optimization techniques are commonly used in machine learning to handle cost functions, which are often non-convex.

Question 17

Secant Method approximates the second order derivative for univariate optimization problems.

Answer 17

FALSE: The Secant Method is used primarily to find the root of a function.

Question 18

If the optimal solution to the linear program relaxation is integer then it is also the optimal solution of the integer linear program (True/False)

Answer 18

TRUE: If the optimal solution of the LP relaxation is already integer-values, it means that this solution also satisfies the integer constraints of the ILP.

Question 19

If a linear programming relaxation has a feasible solution, then its integer linear program will also have a feasible solution (True/False)

Answer 19

FALSE: Just because the LP relaxation of an ILP has a feasible solution does not necessarily mean that the ILP itself will have a feasible solution.

Question 20

If an integer-linear program has a feasible solution, then its linear programming relaxation will also have a feasible solution.

Answer 20

TRUE: An LP relaxation being unbounded does not necessarily imply that there is a feasible integer solution.

Question 21

Explain what is meant by NP-Completeness. Is Linear Programming NP-Hard? Is Integer-Linear Programming NP-Hard?

Answer 21

NP-Completeness: A problem is considered NP-complete if it satisfies two constraints..
1) Is it in NP
2) Is it NP-Hard (it is at least as hard as the hardest problems in NP)

Is Linear Programming NP-Hard?
No: Linear Programming is not NP-Hard. LP can be solved in polynomial time by algorithms such as the interior-point method and simplex method.

Is Integer-Linear Programming NP-Hard?
Yes: This is because it includes, as special cases, several combinatorial problems that are known to be NP-complete, such as the knapsack problem, the travelling salesman problem, etc. The integer constraints make ILP significantly harder to solve compared to LP.

Question 22

What are some potential problems with using Gradient Descent for optimization problems ?

Answer 22

> Convergence to local minima
Depending on learning rate
Sensitive to initial conditions
Scaling issues
Plateaus and saddle points

Question 24

Are the following sets convex or non-convex…..

(i) Slab
(ii) Rectangle
(iii) Union of Rectangles

Answer 24

(i) Slab: Convex, A slab in R^n defined by linear inequalities is convex because it is the intersection of two half-spaces, both defined by linear inequalities.

(ii) Rectangle: Convex, A rectangle is the cartesian product of intervals. Cartesian product of a Convex Set, is Convex.

(iii) Union of Rectangles: Non-Convex, you can find points in each rectangle such that the line segment joining these points passes outside the two rectangles, illustrating non-convexity.