COPtimzation-Problem Set 3 Convex Optimization Solved

Problem 1. A Boolean linear program is an optimization problem of the form,

Minimize cTx

Subject to Ax = b

xi ∈ {0,1}

In general, such problems are very difficult to solve, even though the feasible set is finite.

(a)     In a general method called relaxation, the constraint that xi be zero or one is replaced with the linear inequalities 0 ≤ xi ≤ 1:

Minimize cTx

Subject to Ax = b

0 ≤ xi ≤ 1

We refer to this problem as the LP relaxation of the Boolean LP. The LP relaxation is far easier to solve than the original Boolean LP. Show that the optimal value of the LP relaxation is a lower bound on the optimal value of the Boolean LP. What can you say about the Boolean LP if the LP relaxation is infeasible?

(b)     The Boolean LP can also be reformulated as the problem

Minimize cTx

Subject to Ax = b

xi(1 − xi) = 0

Find the Lagrange dual of this problem. The optimal value of the dual problem (which is convex) gives a lower bound on the optimal value of the Boolean LP. This method of finding a lower bound on the optimal value is called Lagrangian relaxation

(c)      Show that the lower bound obtained via Lagrangian relaxation in part (b), and via the LP relaxation in part (a), are the same. Hint. Derive the dual of the LP relaxation.

(d)     Can you describe an application for Boolean linear program?

Problem 2. Consider a quadratic programming (QP) described by,

Minimize  

Subject to Ax ≤ b

Assume that the matrix P is subject to errors, and the other parameters (q,r,A,b) are exactly known. The optimization problem with unknown matrix P is defined as,

                                                                                 Minimize sup                                                     (1)

Subject to Ax ≤ b

where E is the set of possible matrices P.

(a)     Let E be a finite set of matrices: E = {P1, P2, ...Pk} with . Express the optimization problem (1) as an standard QCQP.

(b)     Let E be described by with      0. Express the optimization problem

(1) as an standard QP.

Problem 3. The relative entropy between two vectors  is defined as

 

This is a convex function, jointly in x and y. In the following problem we calculate the vector x that minimizes the relative entropy with a given vector y, subject to equality constraints on x:

Minimize  

 Subject to

.

The parameters   and b ∈ Rm are given. Derive the Lagrange dual of this problem and simplify it to get,

                                                                                      Maximize ,                                                          (2)

where ak is the kth column of A.

Problem 4. Source localization from range measurements: A signal emitted by a source at an unknown position x ∈ Rn (n = 2 or n = 3) is received by m sensors at known positions y1,...ym ∈ Rn. From the strength of the received signals, we can obtain noisy estimates dk of the distances kx − ykk2. We are interested in estimating the source position x based on the measured distances dk. In the following problem the error between the squares of the actual and observed distances is minimized:

                                                                                       Minimize    

Introducing a new variable t = xTx, we can express this as

                                                                                  Minimize                                                      (3)

Subject to t = xTx.

Although this problem is not convex, it can be shown that strong duality holds. The objective of this problem is to solve (3) for an example with m = 5,

 ,

and

2

(a) To solve the problem, you can note that x? is easily obtained from the KKT conditions for (3) if the optimal multiplier ν? for the equality constraint is known. Derive the dual problem, express it as an SDP, and solve it using CVX (CVX can be downloaded from www.cvxr.com). (b) Reduce the KKT conditions to a nonlinear equation in ν, and pick the correct solution (c) Compare the results in part (a) and (b).

Matlab Assignment
Problem 5.

(a)     Generate random instances of the problem 1 in part (a) and solve it using CVX for different values of n. Comment on the computational time varying n.

(b)     Generate random instances of the problem 1 in part (b) and solve it using CVX for different values of n. Comment on the computational time varying n.

3