## Description

1. CHALLENGE 1: The goal is for you to understand the idea of Support Vector Machines (SVMs) and the power of linear optimization for classification of data. In this project, we will use linear

programming for breast cancer diagnosis. The project will use the Wisconsin Diagnosis Breast

Cancer Database (WDBC). The idea is to come up with a discriminant function (a separating plane

in this case) to determine if an unknown sample is benign or malignant. In order to do this, you

will use part of the data in the above database as a “training set” to generate your separating

plane and the remaining part as a testing set to test your separating plane. Attributes 3 to 32

form a 30-dimensional vector representing each case as a point in 30-dimensional real space R30

.

To generate the separating plane, a training set, consisting of two disjoint point sets B and M in

R30 representing confirmed benign and malignant cases. The separating plane, to be determined by

solving a single linear program in MATLAB or SCIP is based on the formulation proposed in class.

(a) Formulate the problem as a linear program. Solve the problem using the M and B as a training

set from the first 500 cases of the wdbc.data file available from

https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Diagnostic)

The last 69 points should be used as a testing set. Solve the linear program and print out the

separating hyperplane, and the minimum value of the LP.

(b) Test the separating plane on the 69 cases of the testing set. Report the number of misclassified

points on the testing set. It is probably a good idea if you create an MATLAB file to do this.

(c) We saw in class that there is a a quadratic programming formulation of the separation problem

(to maximize margin distance). Formulate the quadratic program in SCIP and try to solve it

that way. Is the separating hyperplane better?

2. PROJECT 2: Finding out the top features that determine what is an “spam email”

You will write an algorithm in SCIP for deciding what are the most important features that distinguish spam email from regular truthful email. You can download the data files from http:

//archive.ics.uci.edu/ml/machine-learning-databases/spambase/

In there you can find the data file spambase.data that contains information on 4601 emails (1813

are Spam!!) Each row contains 58 attributes: 58 (57 continuous, 1 nominal class label). The last

attribute in the very last column of ’spambase.data’ denotes whether the e-mail was considered

spam (1) or not (0).

Most of the attributes indicate whether a particular word or character was frequently occurring in

the e-mail. The run-length attributes (55-57) measure the length of sequences of consecutive capital

letters. For more information see the documentation.

GOAL use the LASSO method to figure out what are the most significant of the characteristics

that define the spam emails (e.g., maybe number of consecutive capital letters is overly excessive?).

Can you run LASSO directly? You can rewrite the LASSO convex model as a linear program by

adding some extra variables!

3. CHALLENGE 3: You need to write a SCIP model to solve the following geometric problem:

Your problem is packing m of spheres in a box of minimal area. The spheres have a given radius

ri

, and the problem is to determine the precise location of the centers xi

. The constraints in this

problem are that the spheres should not overlap, and should be contained in a square of center 0

and half-size R. The objective is to minimize the area of the containing box.

• Show that two spheres of radius r1, r2 and centers x1, x2 respectively do not intersect if and

only if ||x1 − x2||2 exceeds a certain number, which you will determine.

• Formulate the sphere packing problem as an optimization model. Is the formulation you have

found convex optimization?

• Using your model write SCIP code to solve the packing problem of five and six circular disks

of the same radius inside a square of half-size R. What is the optimal size if the disks have

radius 1? Do some drawings using MATLAB of the packings you discovered. Is the solution

unique?

4. THEORY PROBLEMS: CONVEXITY vs NON-CONVEXITY As we saw in class, in Data Science

and Machine Learning, convex sets and functions play an important modeling role. Here are some

problems to help you think more carefully about the properties of convex sets functions:

• Let C be a nonempty subset of Rn

, and let λ1 and λ2 be positive scalars. Show that if C is a

convex set, then (λ1 + λ2)C = λ1C + λ2C. Show by example that this need not be true when

C is not convex.

• Show that for x, y positive scalar real numbers yex/y = maxa>0 a(x+y)−y·a·ln(a). Use this to

prove that the function yex/y is convex inside the positive orthant. Let f(x) = ln(e

x1 +. . . exn ).

Is this convex?

• In this problem you need to test whether the following functions are convex or not:

– The function sk : Rn → R which is defined as sk(x) = Pk

i=1 x[i] where x[i]

is the i-th largest

component of the vector x. HINT: Explore what happens with examples n = 3, k = 2.

– For n = 2k − 1 odd Consider the function φ : RnR with

φ(x) = 1

n

Xn

i=1

|xi − med(x)|

where med(x) is the median of the components of x. HINT: Use sk.

• Let F be a closed compact convex set in Rn

, show that for all u there is a unique point in F

which is closest to u.

• Consider the optimization problem

min 2×1 arctan(x1) − ln(x

2

1 + 1) + x

4

2 + (x3 − 1)2

subject to: x

2

1 + x

2

2 + x

2

3 − 4 ≤ 0, x1 ≥ 0

.

Prove that this problem is a convex optimization problem. Use the Karush -Kuhn-Tucker

theorem to find an optimal solution.

• Consider the optimization problem

min x3

subject to: (x1 − 1)2 + x

2

2 + x

2

3 − 1 ≥ 0,

(x1 + 1)2 + x

2

2 + x

2

3 − 1 ≥ 0,

x

2

1 + x

2

2 + x

2

3 − 4 ≤ 0

.

– Is the feasible region convex?

– What is the convex hull of the feasible region?

– Solve the above optimization problem over the convex hull.

• Find the maximum value of the function f(x, y) = x

2 + y

4 + xy inside the convex hull of the

points (−1, 1), (−1, 2), (−2, 2), (−3, 1). Is the maximum unique? What about the minimum

value of f(x, y)? Does this function have a unique global minimum in R2

.

• Let y be an arbitrary point in R

n and let us define the function “distance to y” by:

dy(x) = kx − yk

2

2

, x ∈ R

n

Show that the function dy is strictly convex. A function f defined over R

n

is strictly convex if

and only if for any pair of points x, y ∈ R

n with x 6= y and any λ ∈ (0, 1):

f(λx + (1 − λ)y) < λf(x) + (1 − λ)f(y)
• Let us consider the polyhedron P = {x ∈ R
n
| Ax ≤ b} for some A ∈ R
m×n and b ∈ R
m. In
this problem, we are interested in the following linear program (LP)
max
x∈P
c
|x (1)
We define the recession cone P
o associated with P by:
P
o def = {d ∈ R
n
| ∀x ∈ P, ∀λ ≥ 0, x + λd ∈ P}
a. Show that P
o = {d ∈ R
n
| Ad ≤ 0}.
b. Show that P
o
is a convex set.
c. Show that the linear program (1) above is unbounded if and only if there exists d ∈ P
o
such that c
|d > 0.