# CS635 – Problem Set #8 solution

\$29.99

Original Work ?

## Description

Instructions for Handing In Homework
Formulate the following problems in GAMS and solve them. Submit this assignment electronically
using the instructions on the course web page. You should hand in a single zip file containing exactly
3 files with the following names: hw8-1.gms, hw8-2.gms, hw8-3.gms
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 Prof Michael Ferris 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