Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
This is a 24 hour take-home inal. Please turn it in on Gradescope within 24 hours of your respective start times. The exam is open textbook, open notes, and open homework, and you may cite equations from the book, notes, and homework. You may also refer to online documentation for CVX* and your programming language of choice. Any other outside or online resources are strictly prohibited.
There are six problems on this exam. All problems have equal weight, but we will only count the best ive out of six questions towards your inal exam grade. Some are (quite) straightforward. Others, not so much. Be sure you are using the most recent version of CVX, CVXPY, or Convex.jl.
You may not discuss the exam with anyone until May 7th, 9PM EST, after everyone has taken the exam. The only exception is that you can ask the teaching staf for clariication, via e-mail – please do not use Piazza so as to avoid accidentally sending a public post that was meant to be private. We have made the exam as unambiguous and clear as possible, so we are unlikely to say much.
Assemble your solutions in order (problem 1, problem 2, problem 3, . . . ), starting a new page for each problem. Put everything associated with each problem (e.g., text, code, plots) together; do not attach code or plots at the end of the inal.
We will deduct points from long, needlessly complex solutions, even if they are correct. Our solutions are not long, so if you ind that your solution to a problem goes on and on for many pages, you should try to igure out a simpler one. You do not have to LATEXyour solutions, but we do expect neat, legible exams from everyone.
When a problem involves computation you must give all of the following: a clear discussion and justii- cation of exactly what you did, the source code that produces the result, and the inal numerical results or plots. Remember, the more information and explanation that you give us regarding your thought process, the easier it is for us to give you partial marks!
For problems asking you to generate random data, please use the following random seeds:
. Matlab: randn(’state’,0); rand(’state’,0);
. Python: np.random.seed(0)
. Julia: Random.seed!(0);
Please respect Penn’s Academic Integrity Code: although we allow you to work on homework assignments in small groups, you cannot discuss the inal with anyone until everyone has taken it.
Check your email often during the exam, just in case we need to send out an important announcement.
Some of the data iles generate random data (with a ixed seed), which are not necessarily the same for Matlab, Python, and Julia.
By taking this exam you are agreeing to respect Penn’s Academic Integrity Code. Good luck!
1. An undirected graph with p vertices can be described by its adjacency matrix A 2 Sp given by
1 if there is an edge between nodes i and j
Aij = {
0 otherwise.
Two undirected graphs are isomorphic if the vertices of one graph can be permuted so that it is the same as the other, i.e., such that the same pairs of vertices are connected by edges. If we describe these graphs by their adjacency matrices A1 and A2 , then A1 is isomorphic to A2 if and only if there exists a permutation matrix P 2 Rp p such that PA1 P」 = A2 . Recall that a matrix P is a permutation matrix if each row and each column has exactly one entry equal to 1, and all other entries equal to 0. This problem comes up in several applications, such as determining if two molecular structures are the same, or whether a circuit’s physical layout and schematic diagram are consistent.
(a) Find a set of linear equalities and inequalities on P 2 Rp p , that together with a Boolean con- straint Pij 2 f0, 1g, are necessary and sufficient for P to be a permutation matrix satisfying PA1 P」 = A2 .
(b) Consider the relaxed version of the problem found in part (a), i.e., the LP that results when the constraints Pij 2 f0, 1g are replaced with Pij 2 [0, 1]. When this LP is infeasible, we know that two graphs are not isomorphic, and similarly, if a solution is found such that Pij 2 f0, 1g for all i,j, then the graphs are isomorphic because we have the original Boolean problem. However, this does not always happen even if the graphs are isomorphic.
A standard trick to encourage the entries of P to take on values in f0, 1g is to add a random linear objective to the relaxed feasibility LP, as this doesn’t change whether the problem is feasible or not. In other words, we minimize：i;j WijPij , where the Wij are chosen randomly, say from Ⅵ (0, 1). Carry out this scheme for the two isomorphic graphs with adjacency matrices A1 and A2 given in Prob1.* to ind a permutation matrix P that satisies PA1 P」 = A2 . Report the permutation vector given by the matrix-vector product Pv, where v = (1, 2, . . . , p). Verify that all the required conditions on P hold. To check that the entries of the solution of the LP are (close to) f0, 1g, report maxi;j Pij (1 - Pij ). And yes, you may have to attempt more than one instance of the randomized method described above before you inda permutation that establishes isomorphism of the two graphs: if that is the case, increase the random seed by one at each trial, i.e., trial 0 will have random seed‘0’, trial 1 will have random seed‘1’, etc.
2. A symmetric matrix is positive semideinite if and only if all of its principal minors are nonnegative. Here we consider approximations of the positive-semideinite cone by partially relaxing this condition.
Denote by K1;p the cone of matrices whose 1 × 1 principal minors (i.e., diagonal elements) are nonneg- ative, so that
K1;p = fM 2 Sp : Mii ≥ 0 for all ig.
Similarly, denote by K2;p the cone of matrices whose 1 × 1 and 2 × 2 principal minors are nonnegative:
K2;p = {M 2 Sp : lM(M)ij(ii) M(M)jj(ij)] > 0 for all i j } ,
i.e., the cone of symmetric matrices with positive semideinite 2 × 2 principal submatrices. These two cones are convex and proper and satisfy:
K1(*);p K2(*);p S K2;p K1;p ,
where K1(*);p and K2(*);p are the dual cones of K1;p and K2;p, respectively. The last two inclusions follow
immediately from the deinitions of the cones, and the irst two follow from the second bullet on page 53 of the textbook.
(a) Give an explicit characterization of K1(*);p. Argue that both K1;p and K1(*);p can be represented using
LPs.
(b) Give an explicit characterization of K2(*);p. Argue that both K2;p and K2(*);p can be represented using
SOCPs.
(c) Consider the problem
minimize trCX
subject to trAX = b
X 2 K
with variable X 2 Sp. The problem parameters are C 2 Sp , A 2 Sp , b 2 R, and the cone K Sp. Using the data in Prob2.* solve this problem ive times, each time replacing K with one of the
ive cones K1;p, K2;p , S, K2(*);p , K1(*);p.. Report the ive diferent optimal values you obtain.
Note: Python users who run into numerical issues might want to use the SCS solver by using prob.solve(solver=cvxpy.SCS).
Note: For parts (a) and (b), the shorter and clearer your description is, the more points you will receive. At the very least, it should be possible to implement your description in CVX*.
3. Flux balance analysis is based on a very simple model of the reactions going on in a cell, keeping track only of the gross rate of consumption and production of various chemical species within the cell. Based on the known stoichiometry of the reactions, and known upper bounds on some of the reaction rates, we can compute bounds on the other reaction rates, or cell growth, for example.
We focus on m metabolites in a cell, labeled M1 , . . . , Mm . There are n reactions going on, labeled, R1 , . . . , Rn , with nonnegative reaction rates v1 , . . . , vn. Each reaction has a (known) stoichiometry, which tells us the rate of consumption and production of the metabolites per unit of reaction rate. The stoichiometry is given by the stoichiometry matrix S 2 Rm ×n , deined as follows: Sij is the rate of production of Mi due to unit reaction rate vj = 1. Here we consider consumption of a metabolite as negative production; so Sij = 一2, for example, means that reaction Rj causes metabolite Mi to be consumed at a rate 2vj .
As an example, suppose reaction R1 has the form M1 ! M2 + 2M3. The consumption rate of M1 , due to this reaction, is v1 ; the production rate of M2 is v2 ; and the production rate of M3 is 2v1. Here, the reaction R1 has no efect on the metabolites M4 , . . . , Mm . This corresponds to a irst column of S of the form (一1, 1, 2, 0, . . . , 0).
Reactions are also due to model low of metabolites into and out of the cell. For example, suppose that reaction R2 corresponds to the low of metabolite M1 into the cell, with v2 giving the low rate. This corresponds to a second column of S of the form (1, 0, . . . , 0).
The last reaction, Rn , corresponds to biomass creation, or cell growth, so the reaction rate vn is the cell growth rate. The last column of S gives the amounts of metabolites used or created per unit of cell growth rate.
Since our reactions include metabolites entering or leaving the cell, as well as those converted to biomass within the cell, we have conservation of the metabolites, which can be expressed as Sv = 0. In addition, we are given upper limits on some of the reaction rates, which we express as v 京 vmax where we set vj(max) = 1 if no upper limit on reaction j is known.
- 经济Economics
- 金融Finance
- 会计Accounting
- 工商管理Business Management
- 计算机computer science
- 商业分析business analysis
- 法律Law
- 管理Management
- 市场营销Marketing
- 哲学Philosophy
- 心理学Psychology
- 物理Physical
- 统计学statistics
- 电气工程electric engineering
- 化学chemistry
- 生物biology
- 数学mathematics
- 语言学linguistics
- 土木工程civil engineering
- 工程力学engineering mechanics
- 艺术art
PROFESSIONAL HELP!
在线咨询
立即下单
Wechat：THEend8_ 
Email：