EE364 Review Session 4

EE364 Review
EE364 Review Session 4
Outline:
• convex optimization examples
• solving quasiconvex problems by bisection
• exercise 4.47
1
Convex optimization problems
we have seen
• linear programming (LP)
• quadratic programming (QP)
• quadratically constrained QP (QCQP)
• second-order cone programming (SOCP)
• geometric programming (GP)
• semidefinite programming (SDP)
EE364 Review Session 4
2
Force/moment generation with thrusters
• rigid body with center of mass at origin p = 0 ∈ R2
• n forces with magnitude ui, acting at pi = (pix, piy ), in direction θi
ui
θi
(pix, piy )
PSfrag replacements
EE364 Review Session 4
3
• resulting horizontal force: Fx =
• resulting vertical force: Fy =
• resulting torque: T =
Pn
i=1 ui cos θi
Pn
i=1 ui sin θi
Pn
i=1 (piy ui cos θi
− pixui sin θi)
• force limits: 0 ≤ ui ≤ 1 (thrusters)
• fuel usage: u1 + · · · + un
problem: find thruster forces ui that yield given desired forces and torques
Fxdes, Fydes, T des, and minimize fuel usage (if feasible)
EE364 Review Session 4
4
can be expressed as LP:
minimize
1T u
subject to F u = f des
0 ≤ ui ≤ 1, i = 1, . . . , n
where

···
cos θ1
sin θ1
···
F =
p1y cos θ1 − p1x sin θ1 · · ·
f des = (Fxdes, Fydes, T des),
EE364 Review Session 4

cos θn
,
sin θn
pny cos θn − pnx sin θn
1 = ( 1, 1, · · · 1 )
5
clear all; close all;
% input data
% ---------% thrusters x-coordinates
px = [-3 -2 -1 1.5 2 ];
% thrusters y-coordinates
py = [ 0 1 -2 1
-2.5];
% angles
thetas = [-85 30 -150 0 85]*pi/180;
F = [ cos(thetas);
sin(thetas);
py.*cos(thetas) - px.*sin(thetas)];
% different problem specified by each column of f_des
f_des = [ 0 0 1 -.5 0 0; ...
.5 -1 0
0 0 0; ...
0 0 0
0 2 -2];
EE364 Review Session 4
6
% problem solution
thrus = [];
for i=1:6
cvx_begin
variable u(5)
minimize ( sum ( u ) )
F*u == f_des(:,i)
u >= 0
u <= 1
cvx_end
thrus = [thrus u];
end
EE364 Review Session 4
7
for Fxdes = 0, Fydes = 0.5, T des = 0:
4
3
2
1
0
−1
−2
−3
−4
−4
EE364 Review Session 4
−3
−2
−1
0
1
2
3
4
8
for Fxdes = 0, Fydes = −1, T des = 0:
4
3
2
1
0
−1
−2
−3
−4
−4
EE364 Review Session 4
−3
−2
−1
0
1
2
3
4
9
for Fxdes = 1, Fydes = 0, T des = 0:
4
3
2
1
0
−1
−2
−3
−4
−4
EE364 Review Session 4
−3
−2
−1
0
1
2
3
4
10
for Fxdes = −0.5, Fydes = 0, T des = 0:
4
3
2
1
0
−1
−2
−3
−4
−4
EE364 Review Session 4
−3
−2
−1
0
1
2
3
4
11
for Fxdes = 0, Fydes = 0, T des = 2:
4
3
2
1
0
−1
−2
−3
−4
−4
EE364 Review Session 4
−3
−2
−1
0
1
2
3
4
12
for Fxdes = 0, Fydes = 0, T des = −2:
4
3
2
1
0
−1
−2
−3
−4
−4
EE364 Review Session 4
−3
−2
−1
0
1
2
3
4
13
Extensions of thruster problem
• opposing thruster pairs:
Pn
minimize kuk1 = i=1 |ui|
subject to F u = f des
|ui| ≤ 1, i = 1, . . . , n
can express as LP
• more accurate fuel use model:
Pn
minimize
i=1 φi(ui)
subject to F u = f des
0 ≤ ui ≤ 1, i = 1, . . . , n
φi are piecewise linear increasing convex functions
can express as LP
EE364 Review Session 4
14
• minimize maximum force/moment error:
minimize kF u − f desk∞
subject to 0 ≤ ui ≤ 1, i = 1, . . . , n
can express as LP
• minimize number of thrusters used:
minimize # thrusters on
subject to F u = f des
0 ≤ ui ≤ 1, i = 1, . . . , n
can’t express as LP
(but we could check feasibility of each of the 2n subsets of thrusters)
EE364 Review Session 4
15
Optimizing structural dynamics
linear elastic structure
PSfrag replacements
f1
f2
f3
f4
dynamics (ignoring damping): M d¨ + Kd = 0
• d(t) ∈ Rk : vector of displacements
• M = M T 0 is mass matrix; K = K T 0 is stiffness matrix
EE364 Review Session 4
16
Fundamental frequency
• solutions have form
di(t) =
k
X
αij cos(ωj t − φj )
j=1
where 0 ≤ ω1 ≤ ω2 ≤ · · · ≤ ωk are the modal frequencies, i.e., positive
solutions of det(ω 2M − K) = 0
• fundamental frequency:
1/2
1/2
ω1 = λmin (K, M ) = λmin(M −1/2KM −1/2 )
– structure behaves like mass at frequencies below ω1
– gives stiffness measure (the larger ω1, the stiffer the structure)
• ω1 ≥ Ω ⇐⇒ Ω2M − K 0 so ω1 is quasiconcave function of M , K
EE364 Review Session 4
17
• design variables: xi, cross-sectional area of structural member i
(geometry of structure fixed)
• M (x) = M0 +
P
i xi M i ,
K(x) = K0 +
• structure weight w = w0 +
P
P
i xi K i
i xi w i
• problem: minimize weight s.t. ω1 ≥ Ω, limits on cross-sectional areas
as SDP:
EE364 Review Session 4
P
minimize w0 + i xiwi
subject to Ω2M (x) − K(x) 0
li ≤ x i ≤ u i
18
Solving quasiconvex problems via bisection
minimize f0(x)
subject to fi(x) ≤ 0, i = 1, . . . , m
Ax = b
fi convex, f0 quasiconvex
idea: express sublevel set f0(x) ≤ t as sublevel set of convex function:
f0(x) ≤ t ⇔ φt(x) ≤ 0
where φt : Rn → R is convex in x for each t
now solve quasiconvex problem by bisection on t, solving convex feasibility
problem
φt(x) ≤ 0, fi(x) ≤ 0, i = 1, . . . , m, Ax = b
(with variable x) at each iteration
EE364 Review Session 4
19
bisection method for quasiconvex problem:
given l < p∗; feasible x; > 0
u := f0(x)
repeat
t := (u + l)/2
solve convex feasibility problem
φt(x) ≤ 0, fi(x) ≤ 0, Ax = b
if feasible,
u := t
x := any solution of feas. problem
else l := t
until u − l ≤ • reduces quasiconvex problem to sequence of convex feasibility problems
EE364 Review Session 4
20
4.47 Maximum determinant positive semidefinite matrix completion.
We consider a matrix A ∈ Sn, with some entries specified, and the others
not specified. Say


3.0 0.5
0.25
 0.5 2.0 0.75


.
A=

0.75 1.0
0.25
5.0
The positive semidefinite matrix completion problem is to determine values
of the unspecified entries of the matrix so that A 0 (or to determine
that such a completion does not exist).
EE364 Review Session 4
21
(a) Why can we assume (w.l.o.g) that Aii are specified?
(b) Formulate this problem as an SDP feasibility problem?
EE364 Review Session 4
22
(c) Assume that A has at least one completion that is positive definite, and
the diagonal entries of A are specified (i.e., fixed). The positive definite
completion with largest determinant is called the maximum determinant
completion. Show that the maximum determinant completion is unique.
Show that if A? is the maximum determinant completion, then (A?)−1
has zeros in all the entries of the original matrix that were not specified.
(d) Suppose A is specified on its tridiagonal part, i.e., we are given
A11, . . . , Ann and A12, . . . , An−1,n . Show that if there exists a positive
definite completion of A, then there is a positive definite completion
whose inverse is tridiagonal.
EE364 Review Session 4
23
Matlab code:
n = 4;
% create and solve the problem
cvx_begin sdp
% A is a PSD symmetric matrix (n-by-n)
variable A(n,n) symmetric;
maximize( det_rootn( A ) )
A >= 0;
% constrained matrix entries.
A(1,1) == 3;
A(2,2) == 2;
A(3,3) == 1;
A(4,4) == 5;
A(1,2) == .5;
A(1,4) == .25;
A(2,3) == .75;
cvx_end
EE364 Review Session 4
24
Matrix A with maximum determinant (20.578) is:
A =
3.0000
0.5000
0.1874
0.2500
0.5000
2.0000
0.7500
0.0417
0.1874
0.7500
1.0000
0.0156
0.2500
0.0417
0.0156
5.0000
Its eigenvalues are:
eigs =
0.5964
2.0908
3.2773
5.0355
The inverse of matrix A is:
0.3492
-0.0870
0.0000
-0.0167
-0.0870
0.7174
-0.5217
-0.0000
EE364 Review Session 4
0.0000
-0.5217
1.3913
0.0000
-0.0167
-0.0000
0.0000
0.2008
25

Download Report