ISYE524 Homework 5 solution

Problem 1 — Nonconvex Quadratics

Suppose you have the constraint:

2x2+y2+z2+3xy−xz+2yz≤02𝑥2+𝑦2+𝑧2+3𝑥𝑦−𝑥𝑧+2𝑦𝑧≤0 (1)

(a) Write constraint (1) in the standard form vTQv≤0𝑣𝑇𝑄𝑣≤0 where Q𝑄 is a symmetric matrix. What is Q𝑄 and what is v𝑣?

v = ⎛⎝⎜xyz⎞⎠⎟(𝑥𝑦𝑧), Q = ⎛⎝⎜21.5−0.51.511−0.511⎞⎠⎟(21.5−0.51.511−0.511)

(b) This constraint is not convex (i.e., the set of points satisfying the constraint is not an ellipsoid). Explain why this is the case. Hint: You can perform an orthogonal decomposition of a symmetric matrix Q𝑄 in Julia like this:

As seen above, the constraint is not positive semidefinite by orthogonal decomposition, as some eigenvalues are nonpositive.

(c) We can write constraint (1) in norm format as follows:

∥Av∥22−∥Bv∥22≤0‖𝐴𝑣‖22−‖𝐵𝑣‖22≤0 (2)

Find matrices A𝐴 and B𝐵 that make this constraint equivalent to (1).

∥Av∥22−∥Bv∥22≤0‖𝐴𝑣‖22−‖𝐵𝑣‖22≤0

∥Av∥22=(2x)2+y2+z2‖𝐴𝑣‖22=(2𝑥)2+𝑦2+𝑧2

∥Bv∥22=(3xy−xz+2yz)2‖𝐵𝑣‖22=(3𝑥𝑦−𝑥𝑧+2𝑦𝑧)2

A = ⎛⎝⎜411110101⎞⎠⎟(411110101) B = ⎛⎝⎜0−6−4−606−460⎞⎠⎟(0−6−4−606−460)

(d) Explain how to find (x,y,z)(𝑥,𝑦,𝑧) that satisfy the above constraint but make 2x2+y2+z22𝑥2+𝑦2+𝑧2 arbitrarily large.

To find (x,y,z) such that the above constraint is satisfied and 2x2+y2+z22𝑥2+𝑦2+𝑧2 is arbitrarily large,

vTQv=λ1w21+...+λnw2n𝑣𝑇𝑄𝑣=𝜆1𝑤12+…+𝜆𝑛𝑤𝑛2

must be proven, where w=UTv𝑤=𝑈𝑇𝑣 (or v=Uw𝑣=𝑈𝑤) and v is the same v defined in (a).

To do so, let wi=0𝑤𝑖=0 if λi>=0𝜆𝑖>=0 and wi=t𝑤𝑖=𝑡 for some positive t𝑡 if λi<0𝜆𝑖<0

Thus, it stands to reason that t𝑡 should be arbitrarily large, as w is a vector of either 0 or t𝑡, and therefore, v=Uw𝑣=𝑈𝑤 is arbitrarily large therefore 2x2+y2+z22𝑥2+𝑦2+𝑧2 is arbitrarily large

Problem 2 — Geometric Programming

Fizzy Water, Inc. is designing a pipe that disinfects their water before it is packaged. The pipe is designed to heat the water to T𝑇 (degrees above ambient temperature). The pipe has a fixed length and circular cross section with radius r𝑟. The pipe is wrapped in a layer of material with thickenss w𝑤 (much smaller than r𝑟) for insulation to minimize heat loss. The design variables for the pipe are T,r,𝑇,𝑟, and w𝑤.

Heat loss can be converted to energy cost and is roughly equal to (α1Tr)/w(𝛼1𝑇𝑟)/𝑤 for some constant α1𝛼1. The cost of the pipe is approximately proportional to the total material used: α2r𝛼2𝑟 for a constant α2𝛼2. The insulation cost, similarly,is porportional to the total insulation material used, or roughly α3rw𝛼3𝑟𝑤 for a constant α3𝛼3. The total cost of constructing and using the pipe is the sum of these three costs.

Fizzy Water wants to maximize the total heat flow through the pipe, which is proportional to the velocity of the water through the pipe. This value can be approximated by α4Tr2𝛼4𝑇𝑟2 for a constant α4𝛼4. All α𝛼 constants and all variables T,r,w𝑇,𝑟,𝑤 are strictly positive.

The problem Fizzy Water wants you to help them solve is to maximize the total heat flow through the pipe, subject to their budget Cmax𝐶max which is an upper bound on total cost. They also have the following constraints:

• Tmin≤T≤Tmax𝑇min≤𝑇≤𝑇max
• rmin≤r≤rmax𝑟min≤𝑟≤𝑟max
• wmin≤w≤wmax𝑤min≤𝑤≤𝑤max
• w≤0.1r𝑤≤0.1𝑟

(a) Express this problem as a geometric program, and convert it into a convex optimization problem.

Geometric form:

Convex form:

(b) Consider a simple instance of this problem where Cmax=100𝐶max=100 and all αi𝛼𝑖 values equal 1. Assume for simplicity that every variable (T,r,w𝑇,𝑟,𝑤) has a lower bound of 1 and no upper bound. Solve this problem using JuMP. Use the Ipopt solver (or any other solver that can solve convex optimization problems) and the “@NLconstraint(…)” command to specify any nonlinear constraints. What are the optimal T,r𝑇,𝑟, and w𝑤?