# ISYE524 Homework 5 solution

\$30.00

Original Work ?

5/5 - (1 vote)

## 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:

using LinearAlgebra
Q = [2 1.5 -0.5;1.5 1 1; -0.5 1 1]
(L,U) = (eigvals(Q),eigvecs(Q)) # L is the vector of eigenvalues and U is orthogonal
U * Diagonal(L) * U' # this is equal to Q (as long as Q was symmetric to begin with)
(L,U)
([-0.7717848741953769, 1.671965737371683, 3.099819136823694], [0.4755037916822413 -0.396463343135491 0.7853107420923526; -0.701884978187095 0.3671776439352714 0.6103589560164115; 0.5303335002534842 0.8414258109566005 0.10367730303646348])

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:

minT,r,w>0aβ14βTβ1β(r2)β1s.t.a1Tr/wCmax+a2r/Cmax+a3rw/CmaxTmin/TT/Tmaxrmin/rr/rmaxwmin/ww/wmaxw/0.1rβ€1β€1β€1β€1β€1β€1β€1β€1minπ,π,π€>0π4β1βπβ1β(π2)β1s.t.π1ππ/π€πΆπππ₯+π2π/πΆπππ₯+π3ππ€/πΆπππ₯β€1ππππ/πβ€1π/ππππ₯β€1ππππ/πβ€1π/ππππ₯β€1π€πππ/π€β€1π€/π€πππ₯β€1π€/0.1πβ€1

Convex form:

minx,y,zβxβ2ys.t.log(elog(a1/Cmax)+x+yβz+log(elog(a2/Cmax)+y+log(elog(a3/Cmax)+y+zlog(Tmin)log(rmin)log(wmin)zβyβ€0β€βxβ€log(Tmax)β€βyβ€log(rmax)β€βzβ€log(wmax)β€1minπ₯,π¦,π§βπ₯β2π¦s.t.πππ(ππππ(π1/πΆπππ₯)+π₯+π¦βπ§+πππ(ππππ(π2/πΆπππ₯)+π¦+πππ(ππππ(π3/πΆπππ₯)+π¦+π§β€0πππ(ππππ)β€βπ₯β€πππ(ππππ₯)πππ(ππππ)β€βπ¦β€πππ(ππππ₯)πππ(π€πππ)β€βπ§β€πππ(π€πππ₯)π§βπ¦β€1

(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π€?

cmax = 100
a1 = 1
a2 = 1
a3 = 1
a4 = 1

### MODEL ###

using JuMP, Ipopt

m = Model(Ipopt.Optimizer)

@variable(m, x)
@variable(m, y)
@variable(m, z)

@objective(m, Min, -x - 2y)

@NLconstraint(m,log(exp(log(a1/cmax)+ x + y - z))+log(exp(log(a2/cmax) + y)) + log(exp(log(a3/cmax) + y + z)) <= 0)
@constraint(m, -x >= 1)
@constraint(m, -y >= 1)
@constraint(m, -z >= 1)
@constraint(m, z-y <= 1)

optimize!(m)

println()
T = exp(value(x))
r = exp(value(y))
w = exp(value(z))
println("Temperature: ", T)
println("Thickness: ", w)
println("Maximum heat flow: ", T*r^2)
This is Ipopt version 3.14.13, running with linear solver MUMPS 5.6.0.

Number of nonzeros in equality constraint Jacobian...:        0
Number of nonzeros in inequality constraint Jacobian.:        8
Number of nonzeros in Lagrangian Hessian.............:        6

Total number of variables............................:        3
variables with only lower bounds:        0
variables with lower and upper bounds:        0
variables with only upper bounds:        0
Total number of equality constraints.................:        0
Total number of inequality constraints...............:        5
inequality constraints with only lower bounds:        3
inequality constraints with lower and upper bounds:        0
inequality constraints with only upper bounds:        2

iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
0  0.0000000e+00 1.00e+00 6.92e-01  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
1  3.2571425e+00 0.00e+00 4.82e-01  -1.0 4.34e+00    -  7.58e-01 1.00e+00h  1
2  3.0846593e+00 0.00e+00 4.31e-02  -1.7 2.28e-01    -  9.19e-01 1.00e+00f  1
3  3.0065655e+00 0.00e+00 2.22e-03  -2.5 1.13e-01    -  9.42e-01 1.00e+00f  1
4  3.0003081e+00 0.00e+00 4.60e-04  -3.8 3.11e-01    -  8.42e-01 1.00e+00f  1
5  3.0000037e+00 0.00e+00 1.15e-06  -5.7 7.17e-03    -  9.97e-01 1.00e+00f  1
6  3.0000000e+00 0.00e+00 4.10e-09  -8.6 7.94e-03    -  9.96e-01 1.00e+00f  1
7  3.0000000e+00 0.00e+00 5.62e-10  -9.0 3.07e-01    -  8.79e-01 1.00e+00h  1

Number of Iterations....: 7

(scaled)                 (unscaled)
Objective...............:   2.9999999718181813e+00    2.9999999718181813e+00
Dual infeasibility......:   5.6204110977765058e-10    5.6204110977765058e-10
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Variable bound violation:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   3.1301266299467510e-09    3.1301266299467510e-09
Overall NLP error.......:   3.1301266299467510e-09    3.1301266299467510e-09

Number of objective function evaluations             = 8
Number of objective gradient evaluations             = 8
Number of equality constraint evaluations            = 0
Number of inequality constraint evaluations          = 8
Number of equality constraint Jacobian evaluations   = 0
Number of inequality constraint Jacobian evaluations = 8
Number of Lagrangian Hessian evaluations             = 7
Total seconds in IPOPT                               = 0.005

EXIT: Optimal Solution Found.

Temperature: 0.3678794445158009
Maximum heat flow: 0.04978706977095408