代写introduction to operation research and optimization代做Statistics统计

Question 1 (Unpledged, 15 Points)

Consider a quadratic programming problem of the form.

where k ∈ R is a constant.

(a) Show that the objective function is convex, and the feasible region is always nonempty and convex.

(b) Using the KKT conditions, solve this quadratic programming problem in which k= 4.

(c) For certain values of k, the optimal solution of the problem lies on the boundary of the feasible region. What are those values, and what are the corresponding optimal solutions, Lagrange multipliers, and optimal objective function values?

(d) What is the optimal solution for an arbitrary instance of this problem (i.e., for arbitrary k) for which the optimal solution does not lie on the boundary of the feasible region?

Question 2 (Pledged, 10 Points)

Consider the following NLP.

(2)

Using the KKT conditions, show that (4, 2) is NOT an optimal solution to (2).

Question 3 (Pledged, 10 Points)

Solve the problem

(3)

using Newton's method. Run the algorithm starting from both = (0,0) and from z = (0, 100) until ||Vfll2 < 10-5. Recall the algorithm is as follows:

You may find it helpful to write functions that evaluate the Hessian and gradient. Most programming languages have a built-in function for taking the inverse of a matrix and the 2-norm of a vector.

Question 4 (Unpledged, 10 Points)

Consider an undirected graph G=(V, E), where every edge e has a weight ce 20. Formulate the minimum spanning tree problem over G as an integer program.

Question 5 (Unpledged, 10 Points)

LinkedIn has an undirected social network G=(V,E), where V is the set of users and an edge (i,) exists if and only if users i and j are connections. You may use the matrix B, where by1 if users and j are connections, and 0 otherwise. The set of connections for user j is △y.

A marketing firm, which can observe G, has the budget to advertise to K users.

1. If user u sees the advertisement (i.e., the marketer chooses to show her the ad), the firm receives Sc, > 0.

2. If user v does not see the advertisement, but at least one of her contacts does, the firm receives Sd,, where Sc, > Sd, > 0. This is true even if more than one contact sees the ad.

3. If user u does not see the advertisement, none of her contacts do, but at least one contact of a contact (second-degree contact, if you will) does see the advertisement, the firm receives Sfo, where Sc, > Sd, > Sf, > 0.

Formulate the most appropriate optimization model to determine which users should see the advertisement.

Question 6 (Unpledged, 10 Points)

Four workers are available to perform. tasks A, B, C, and D. However, worker 1 cannot do tasks B, C, or D. Also, worker 2 cannot do tasks C or D, and worker 3 cannot do tasks A, C, or D.

(a) Draw the network for the maximum flow problem that can be used to determine whether all tasks can be assigned to a suitable worker.

(b) Formulate this problem as a linear program. Clearly define all variables and explicitly write out all flow constraints. Take the dual of the linear program. Do not solve.

Question 7 (Pledged, 20 Points)

I've started playing a new variant of the card game war with Mike. We started with 26 cards each, and each turn we turn over a card. The higher card wins, but in this variant, there are no ties, as whenever the numbers match, spades beat hearts, which beat diamonds, which beat clubs. So the 8 of clubs is better than the 6 of hearts, but worse than the 8 of hearts. The winner takes his own card as well as that of his opponent. Assume that Mike and I perform. a perfect shuffle after every turn. Let the state s be the number of cards Mike has in his deck before turn t; s = 26.

1. Argue that the stochastic process of the number of Mike's cards is a Markov chain. In particular, what flavor of Markov chain?

2. Determine the probability transition matrix for this Markov chain. (You don't need to write out all the states but establish the pattern.)

3. Suppose you left us for Thanksgiving break, and Mike had 32 cards. How would find the probability that I have 8 or fewer cards when you came back, 12,345,678 turns later?

4. If Mike and I played forever, what do you think the long-run probability distribution would be across the states? In other words, if we played till the end of time, what is the probability that we will be in each of the 53 states?