03-Convex-Optimization-Problems

5 minute read

This is the third notebook of the series going through Convex Optimizaion. The topics here are following MOOC Convex Optimization course by Stephen Boyd at Stanford.

Convex Optimization in standard form

A convex optimization problem is one of the form:

where $f_0,\dots,f_m$ are convex functions and equality constraints are affine.

  • feasible set of a convex optimization problem is convex:

Local and global optima

For any convex optimization problem, any locally optimal point is also (globally) optimal.

Suppose:

for some $R$. Suppose $x$ is not globally optimal. Then there is a feasible $y$ such that $ f_0(y)<f_0(x) $ and . Now consider the point $z$: $z=(1-\theta)x+\theta y, \theta=\frac{R}{2\parallel y-x\parallel_2}$ and therefore $\parallel z-x\parallel_2=R/2<R$.

By convexity of $f_0$ we have: $f_0(z)\leq (1-\theta)f_0(x)+\theta f_0(y)<f_0(x)$ Which is a contradiction to earlier assumption and therefore there exist no feasible $y$ with $f_0(y)<f_0(x)$.

Optimality criterion for differentiable $f_0$

Suppose $f_0$ in a convex optimization problem is differentiable, so that for all $x,y \in \textbf{dom } f_0$,

$f_0(y)\geq f_0(x)+\nabla f_0(x)^T(y-x)$

Let $X$ denote the feasible set,

$X=\{x \vert f_i(x) \leq 0,i=1,\dots,m,h_i(x)=0,i=1,\dots,p\}$

Then $x$ is optimal iff $x\in X$ and:

$\nabla f_0(x)^T(y-x)\geq 0 \text{ for all } y\in X$.


Problems with equality constraints only

Based on the optimizality condition for $x$ we have:

Which can be shown that :

This derives the Lagrange Multiplier optimality.

Minimization over nonnegative orthant

Based on the optimizality condition for we have:

Which can be shown that holds when:

Because both and are nonnegative in every element therefore it must be the case that sparsity patterns of two vectors are complimentary.


Equivalent convex problems

Two problems are (informally) equivalent if the solution of one is readily obtained from the solution of the other, and vice versa.

Eliminating equality constraints.

All equality constrainst are of the form:

which can be eliminated by finding a particular $x_0$ of $Ax=b$, and a mtrix F whose range is the nullspace of A.

Introducing equality constraints

is equivalent to:

Introducing slack variables for linear inequalities

is equivalent to:

epigraph form

Any convex optimization problem can be converted to epigraph form:

therefore linear objective is universal for convex optimization

Minimizing over some variables

is equivalent

where

Quasiconvex optimization

For these problems $x$ is optimal if:

Notes:

  • The condition is only sufficient for optimality.
  • The condition requires be nonzero.

Linear Programming

In [1]:

1
2
3
4
import cvxpy as cvp
import cvxopt
import mpl_toolkits.mplot3d.axes3d as p3
import matplotlib.pyplot as plt

In [7]:

1
2
3
4
5
6
7
8
9
10
11
12
x=cvp.Variable(rows=3)
c=np.array([[7,8,9]])
b=np.array([10,8])
G=np.array([[2,1],[3,1],[2,2]])
print 'C:\n',c.T
print 'b:\n',b.T
print 'G:\n',G.T
constraints = [ x>=0,G.T*x <= b]
objective1 = cvp.Minimize(-1*c*x)
p1 = cvp.Problem(objective1, constraints)
p1.solve()
print 'optimal point:\n',x.value
C:
[[7]
 [8]
 [9]]
b:
[10  8]
G:
[[2 3 2]
 [1 1 2]]
optimal point:
[ 2.00e+00]
[ 5.40e-07]
[ 3.00e+00]

In [8]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
fig=plt.figure()
ax = fig.gca(projection='3d')
x = np.arange(0, 5, 0.1)
y = np.arange(0, 5, 0.1)

#Plot first constraints
xx, yy = np.meshgrid(x, y)
z=5-xx-1.5*yy
z[z<0]=np.nan
ax.plot_wireframe(xx,yy,z,  rstride=4, cstride=4, alpha=0.4)

#Plot second constraints
z=4-0.5*xx-0.5*yy
z[z<0]=np.nan
ax.plot_wireframe(xx,yy,z, rstride=2, cstride=2, alpha=0.4,color="red")

#Plot intersection line of two constraints.
yt=1-0.5*x
yt[yt<0]=np.nan
zt=5-x-1.5*yt
zt[zt<0]=np.nan
ax.plot(x,yt,zs=zt)

#Plot level surfaces of the objective function.
def draw_plt(b):
    z=b/9.0-7.0/9*xx-8.0/9*yy
    z[z<0]=np.nan
    if b==40:
        v=1
    else:
        v=2
    ax.plot_wireframe(xx,yy,z, rstride=v, cstride=v, alpha=0.4,color="grey")
map(draw_plt,np.arange(0,45,10))
plt.plot(2,0,zs=[3],marker='d')
ax.set_xlim(0,5)
ax.set_ylim(0,5)
ax.set_zlim(0,5)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.view_init(elev=30, azim=145)

png

Chebyshev center of polyhedron

Chebyshev center of

is center of largest inscribed ball:

$a_i^T x\leq b_i$ for all $x \in B$ iff: $\text{sup } {a_i^T(x_c+u) \vert \parallel u \parallel_2 \leq r }=a_i^Tx_c+r \parallel a_i \parallel_2 \leq b_i$ hence:

In [4]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from __future__ import division

# From CVXPy examples
# Taken from CVX website http://cvxr.com/cvx/examples/
# Example: Compute and display the Chebyshev center of a 2D polyhedron
# Ported from cvx matlab to cvxpy by Misrab Faizullah-Khan
# Original comments below

# Boyd & Vandenberghe, "Convex Optimization"
# Joelle Skaf - 08/16/05
# (a figure is generated)
#
# The goal is to find the largest Euclidean ball (i.e. its center and
# radius) that lies in a polyhedron described by linear inequalites in this
# fashion: P = { x : a_i'*x <= b_i, i=1,...,m } where x is in R^2

# Create the problem

# variables
radius = cvp.Variable(1)
center = cvp.Variable(2)

# constraints
a1 = cvxopt.matrix([2,1], (2,1))
a2 = cvxopt.matrix([2,-1], (2,1))
a3 = cvxopt.matrix([-1,2], (2,1))
a4 = cvxopt.matrix([-1,-2], (2,1))

b = cvxopt.matrix(1, (4,1))


constraints = [ a1.T*center + np.linalg.norm(a1, 2)*radius <= b[0],
                a2.T*center + np.linalg.norm(a2, 2)*radius <= b[1],
                a3.T*center + np.linalg.norm(a3, 2)*radius <= b[2],
                a4.T*center + np.linalg.norm(a4, 2)*radius <= b[3] ]


# objective
objective = cvp.Maximize(radius)

p = cvp.Problem(objective, constraints)
# The optimal objective is returned by p.solve().
result = p.solve()
# The optimal value
print radius.value
print center.value


# Now let's plot it
x = np.linspace(-2, 2, 256,endpoint=True)
theta = np.linspace(0,2*np.pi,100)

# plot the constraints
plt.plot( x, -x*a1[0]/a1[1] + b[0]/a1[1])
plt.plot( x, -x*a2[0]/a2[1] + b[0]/a2[1])
plt.plot( x, -x*a3[0]/a3[1] + b[0]/a3[1])
plt.plot( x, -x*a4[0]/a4[1] + b[0]/a4[1])


# plot the solution
plt.plot( center.value[0] + radius.value*cos(theta), center.value[1] + radius.value*sin(theta) )
plt.plot( center.value[0], center.value[1], 'x', markersize=10 )

# label
plt.title('Chebyshev Centering')
plt.xlabel('x1')
plt.ylabel('x2')

plt.axis([-1, 1, -1, 1])

plt.show()
0.447213535807
[-9.50e-08]
[-6.87e-18]

png

Quadratic Programming

$P \in S_{+}^n$ and therefore objective is convex.

  • Least square is an example of QP:

In [5]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
x=np.arange(0,5,0.05)
y=3*x+np.random.normal(scale=3,size=x.shape[0])+4
A=np.concatenate((np.ones((x.shape[0],1)),x.reshape((x.shape[0],1))),axis=1)
b=y.reshape((x.shape[0],1))
xx=cvp.Variable(rows=2)

objective1 = cvp.Minimize(cvp.quad_form(xx,np.dot(A.T,A))-xx.T*np.dot(A.T,b)-np.dot(b.T,A)*xx)
#
p1 = cvp.Problem(objective1)
p1.solve()
print 'Optimal Point:\n',xx.value

plt.scatter(x,y)
var=np.sqrt(np.var(y.reshape(x.shape[0],1)-np.dot(A,xx.value)))

plt.fill_between(x,np.dot(A,xx.value)[:,0]+var,y2=np.dot(A,xx.value)[:,0]-var
                 , facecolor='grey', alpha=0.2)
plt.plot(x,np.dot(A,xx.value))
plt.grid()
Optimal Point:
[ 4.92e+00]
[ 2.71e+00]

png