Description
1 Support Vector Machines
Support vector machines are a popular method for classification within the machine learning community. Essentially, a linear classifier f is generated as f(x) = w
0x + γ such that if f(x) > 0 then x is
in class P+ whereas if f(x) < 0 then x ∈ P−.
To generate this classifier a quadratic optimization model is solved:
minw,γ,ψ
1
2w
0w + C
P
i ψi
s.t. yi
[w
0xi + γ] ≥ 1 − ψi
, i = 1, . . . , m
ψi ≥ 0
Here m runs over a set of training examples, and yi is 1 if i ∈ P+ and −1 if i ∈ P−. xi are the values
of the predictor variables.
The dual problem of this quadratic program is:
maxα
P
i αi −
1
2
P
i,j αiαjyiyjx
0
ixj
s.t. P
i
yiαi = 0
C ≥ αi ≥ 0
1.1 Problem
You should formulate both these problems in GAMS. Note that for the dual problem, you may want
to introduce some intermediate variables
vk =
X
i
αiyixik
and express the objective function as
X
i
αi −
1
2
X
k
v
2
k
where k runs over the predictor features. Solve (the easiest one) using the qcp solver of your choice,
and the use the multiplier information from this first solve to set the starting values for the second
solve. Try to make the second solve take as little time as possible. You should use the data that is
provided in the abalone.gdx file and choose an appropriate value of C. What you should attempt to
predict is whether the “number of rings” is greater than 10 or not. You should allow the value of C to
be changed at the command line as shown in class. For your information the data fields are:
Problem 1 Page 1
CS635 Problem Set #8 Prof Michael Ferris
Name Data Type Meas. Description
---- --------- ----- -----------
Sex nominal M, F, and I (infant)
Length continuous mm Longest shell measurement
Diameter continuous mm perpendicular to length
Height continuous mm with meat in shell
Whole weight continuous grams whole abalone
Shucked weight continuous grams weight of meat
Viscera weight continuous grams gut weight (after bleeding)
Shell weight continuous grams after being dried
Rings integer +1.5 gives the age in years
Note that the first nominal value has been converted to 3 binary values and can be treated as separate
data for this assignment. Use the first 4000 data points for training your classifier, and report the
number of errors that you make with your classifier to a file ’error.txt’ on the remaining 177 samples.
2 Points in Polyhedra
In this problem, you are given a “random” polyhedron
P(ξ) = {x ∈ R
n
| Ax ∼ b},
where ∼ is one of ≤, ≥, and b ∈ R
m. We will create each P(ξ) by choosing its parameters uniformly
and randomly in the intervals:
• bi ∈ [−10, 10]∀i = 1, . . . , m
• aij ∈ [−2, 2]∀i = 1, . . . , m, j = 1, . . . , n.
To ensure that P 6= ∅, we will ensure that 0 ∈ P by letting the inequalities defining P be
Xn
j=1
aijxj ≤ bi
if bi ≥ 0 and
Xn
j=1
aijxj ≥ bi
if bi < 0.
You are also given a (random) point xˆ(ω) ∈ R
n, where each component of xˆ is chosen randomly
and uniformly in the interval xˆj ∈ [−20, 20].
2.1 Problem
Let n = 400, m = 100. Use multiple solves in GAMS to estimate the probability that xˆ(ω) ∈ P(ξ).
• If xˆ 6∈ P, then estimate the following quantities:
1. z2
def = minx∈P kx − xˆk2
2. z1
def = minx∈P kx − xˆk1
3. z∞
def = minx∈P kx − xˆk∞
Problem 2 Page 2
CS635 Problem Set #8 Prof Michael Ferris
Recall that
kxk2 =
vuut
Xn
j=1
x
2
j
kxk1 =
Xn
j=1
|xj |
kxk∞ = max
j=1,...,n
{xj}
Note that the first problem can be solved with QCP, and the second and third minimum distance
problems can be solved with LP.
3 Double pendulum
Consider the double inverted pendulum system shown in Figure 1. The objective of the system is
Figure 1: Double pendulum
to maintain the pendulum in the upright position using the minimum amount of energy. This is
achieved by applying an appropriate control force to the car to damp out any displacements θ1(t) and
θ2(t).
3.1 Problem
Formulate the problem as an optimal control problem within GAMS and solve for the given data.
Detail: The dynamics of the system are nonlinear but can be approximated by
x˙(t) = Ax(t) + Bu(t)
where
x(t) =
θ1(t)
˙θ1(t)
θ2(t)
˙θ2(t)
, A =
0 1 0 0
α 0 −β 0
0 0 0 1
−α 0 α 0
, B =
0
−1
0
0
Problem 3 Page 3
CS635 Problem Set #8
with α > 0, β > 0 and α 6= β. The “dot” notation represents first derivatives with respect to time and
the parameters α and β depend on the length and weight of each pendulum and the mass of the car,
etc. Suppose at t = 0 small nonzero displacements of θ1(t) and θ2(t) occur. What control u(t) is needed
to steer the system back into the equilibrium state x(t) = 0 at t = T0?
Discretize over time to generate:
x(k + 1) = φx(k) + gu(k)
where T0 = K∆t. The energy consumed by these control actions is
J =
K
X−1
k=0
u
2
(k)
which needs to be minimized. You should assume that |u(k)| ≤ U.
Use the above facts and the model lqr.gms given in class to generate the model. Data is: K = 100,
α = 10, β = 12, U = 10, θ1(0) = 0.4, θ2(0) = 0.2, T0 = 1. Comment on the solution.
Problem 3 Page 4