Quadratic Programming

Optimization problem with (Convex) Quadratic Objective. and linear inequality constraints.

Standard Form:

Minimize $f_0(x)=\frac{1}{2}{x}^{T}Hx+c^{T}x+d$ , which is a quadratic function.

subject to $Ax\le b$

d doesn’t change the opimization problem (only change value)

solver = quadprog(H, c, d, A, b)

Convexity $⟺$ H is PSD (not just symmetric).

---

Examples of QP

1. Least Square is a quadratic Programming

$$mi{n}_x\Vert Ax-b{\Vert }_2^2$$

expand the objective function.

$$f_0(x)=x^T(A^{T}A)Ax-2b^{T}Ax+\Vert b{\Vert }_2^2$$

Pattern match with standard form:

$$H=A^{T}A$$ $$c=-2A^{T}b$$

No constraints in regular Least Squares.

---

2. Linearly Constraint Least Square.

$$mi{n}_x\Vert Ax-b{\Vert }_2^2\text{such that}Cx=d$$ $$Cx=d⟺Cx\le d\text{and}-Cx\le -d$$

---

3. LASSO (l1 regularized least squares)

$$mi{n}_x\Vert Ax-b{\Vert }_2^2+\lambda \Vert x{\Vert }_1$$

Formulate this as quadratic program.

$$mi{n}_{x,t}\Vert Ax-b{\Vert }_2^2+\lambda \sum _i{t}_{i}s.t{x}_i\le t_i,-x_i\le t_i$$

Can convert this into standard form: check picture.

the $\lambda$ is lagrange mulitpliers. incoporitng constraints into objective functions.

---

l1 regularization encourages sparsity of the solution. Why?

$$mi{n}_x\Vert Ax-b{\Vert }_2^2\text{s.t}c{a}^{(x)\le k}$$

cardinality(x) = # of non-zero entries in x vector. (non-convex constraint and hard to deal with).

so l1 regularization is like solving l2 regularization with the sparsity constraint. (cardinality of x ⇐ k)

$\lambda$ is a Lagrange multiplier - meaning that problem 3 (LASSO) is equivalent to $mi{n}_x\Vert Ax-b{\Vert }_2^2+\lambda \text{card}(x)$ for suitable $\lambda$. (still hard to solve). → relaxation.

if lambda is big, cardinality will be small.

if lambda is small (0), don’t care cardinility.

lambda = penalizaing / costing for not obeying the constraints.

Holder’s inequality: $\Vert x{\Vert }_1\le \text{card}(x)\Vert x{\Vert }_{\infty }$

Relax Constrained problem.

submit homework 3

8.1

8.4 and 8.5 (features) Record your optimum prediction rate in your write-up and include your Kaggle

username. Don’t forget to use the “submissions” tab or link on Kaggle to select your best

submission!