Convex optimization

(1)

Optimization problems Convex optimizations Quadratic optimization problems Second-order cone programming Geometric programming Generalized inequality constraints Semidefinite programs

Convex Optimization

A supplementary note to Chapter 4 ofConvex Optimizationby S. Boyd and L. Vandenberghe

Optimization Lab.

IE department Seoul National University

19th August 2009

(2)

Basic terminology

Expressing problems in standard form Equivalent problems

Optimization problem:

min f 0 (x)

s.t. f i (x) ≤ 0, i = 1, · · · , m h j (x) = 0, j = 1, · · · , p .

Decision variables: x ∈ R

ⁿ

Objective function: f

0

(x )

Constraints (inequality and equality): f

i

(x ) ≤ 0 and h

j

(x ) = 0.

Domain of problem: D =

m

\

i=0

domf

i

∩

p

\

j=1

domh

j

x ∈ D is feasible if it satisfies all constraints; infeasible, otherwise.

(3)

Basic terminology

Optimal value: p

^∗

= inf{f

0

(x )|f

i

(x) ≤ 0, ∀i, h

j

(x) = 0, ∀j }.

Optimal point: x

^∗

is optimal point if x

^∗

is feasible and f

0

(x

^∗

) = p

^∗

. Denote by X

opt

the set of optimal points.

A feasible x is an -suboptimal point if f

₀

(x) ≤ p

^∗

+ . A feasible x is locally optimal if ∃R > 0 s.t.

f

₀

(x) = inf{f

₀

(z)|f

_i

(x) ≤ 0, ∀i, h

_j

(x) = 0, ∀j , ||z − x||

₂

≤ R}

Feasibility problem: “Find x satisfying all the constraints.”

(4)

Basic terminology

Expressing problems in standard form

Standard form: Min-version min f

0

(x)

s.t. f

i

(x ) ≤ 0, i = 1, · · · , m h

j

(x ) = 0, j = 1, · · · , p.

Standard form: Max-version max f

0

(x)

s.t. f

i

(x ) ≥ 0, i = 1, · · · , m

h

j

(x ) = 0, j = 1, · · · , p.

(5)

Basic terminology

Equivalent problems

We say two problems are equivalent if, given a solution of one, we can efficiently find a solution of the other, and vice versa.

Example

Two problems are equivalent if α

i

> 0, ∀i, β

j

6= 0, ∀j:

min f

0

(x ) min α

0

f

0

(x)

s.t. f

i

(x) ≤ 0, ∀i s.t. α

i

f

i

(x) ≤ 0, ∀i

h

j

(x) = 0, ∀j β

j

h

j

(x) = 0, ∀j

(6)

Basic terminology

Change of variables

Suppose φ : R

ⁿ

→ R

ⁿ

is one-to-one mapping. Define ˜ f

i

(x) = f

i

(φ(x)) and ˜ h

j

(x ) = h

j

(φ(x)) Then the following two problems are equivalent:

min f

₀

(x)

s.t . f

_i

(x) ≤ 0, i = 1, . . . , m h

_i

(x ) = 0, i = 1, . . . , p min ˜ f

0

(x )

s.t. ˜ f

i

(x ) ≤ 0, i = 1, . . . , m

˜ h

_i

(x) = 0, i = 1, . . . , p.

(7)

Basic terminology

Transformation of obj. and const. functions

Suppose that ψ

0

: R → R is monotone increasing, ψ

1

, . . . , ψ

m

: R → R satisfy ψ

i

(u) ≤ 0 if and only if u ≤ 0, and ψ

m+1

, . . . , ψ

m+p

: R → R satisfy ψ

i

(u) = 0 if and only if u = 0. Define

˜ f

i

(x ) = ψ

i

(f

i

(x)), i = 0, . . . , m, and

˜ h

i

(x ) = ψ

m+i

(h

i

(x )), i = 1, . . . , p.

Then following two are equivalent:

min f

0

(x)

s.t. f

i

(x ) ≤ 0, i = 1, . . . , m h

i

(x) = 0, i = 1, . . . , p, min f ˜

0

(x)

s.t. f ˜

i

(x ) ≤ 0, i = 1, . . . , m

h ˜

i

(x) = 0, i = 1, . . . , p.

(8)

Basic terminology

Least-norm and least-norm-squared

min kAx − bk

2

versus min kAx − bk

²₂

.

(9)

Basic terminology

Slack variables

f

i

(x) ≤ 0 if and only if ∃ s

i

≥ 0 such that f

i

(x ) + s

i

= 0 s

i

is called a slack variable.

Then following two are equivalent:

min f

0

(x )

s.t. f

i

(x) ≤ 0, i = 1, . . . , m h

i

(x) = 0, i = 1, . . . , p min f

0

(x )

s.t. f

i

(x) + s

i

= 0, i = 1, . . . , m

h

i

(x) = 0, i = 1, . . . , p

s

i

≥ 0, i = 1, . . . , m.

(10)

Basic terminology

Introducing equality constraints

The following two problems are equivalent:

min f

0

(A

0

x + b

0

) min f

0

(y

0

)

s.t. f

i

(A

i

x + b

i

) ≤ 0, ∀i s.t. f

i

(y

i

) ≤ 0, ∀i

h

j

(x ) = 0, ∀j y

i

= Ax

i

+ b

i

∀i

h

j

(x) = 0 ∀j

(11)

Basic terminology

Optimizing over some variables

Since inf

x,y

f (x , y ) = inf

x

˜ f (x), where ˜ f (x ) = inf

y

f (x , y ), following two are equivalent:

min f

0

(x

1

, x

2

) ⇔ min ˜ f

0

(x

1

)

s.t. f

i

(x

1

) ≤ 0, i = 1, · · · , m

1

s.t. f

i

(x

1

) ≤ 0, i = 1, · · · , m

1

g

j

(x

2

) ≤ 0, j = 1, · · · , m

2

where ˜ f

0

(x

1

) = inf{f

0

(x

1

, z)|g

j

(z) ≤ 0, j = 1, · · · , m

2

}.

Example

Consider a strictly convex quadratic program constrained on some variables: min x

₁^T

P

11

x

1

+ 2x

₁^T

P

12

x

2

+ x

₂^T

P

22

x

2

s.t. f

i

(x

1

) ≤ 0, i = 1, . . . , m.

Since, inf

x₂

x

1^T

P

11

x

1

+ 2x

1^T

P

12

x

2

+ x

2^T

P

22

x

2

= x

1^T

(P

11

− P

12

P

₂₂⁻¹

P

12^T

)x

1

, we can obtain equivalent problem:

min x

₁^T

(P

11

− P

12

P

₂₂⁻¹

P

₁₂^T

)x

1

, s.t. f

i

(x

1

) ≤ 0, i = 1, . . . , m.

(12)

Basic terminology

Epigraph problem form

The following two problems are equivalent:

min f

0

(x ) min t

s.t. f

i

(x) ≤ 0, i = 1, · · · , m s.t. f

0

(x ) − t ≤ 0, i = 1, · · · , m

1

h

j

(x) = 0, j = 1, · · · , p f

i

(x) ≤ 0, i = 1, · · · , m

h

j

(x ) = 0, j = 1, · · · , p

(13)

Convex optimization problems in standard form Local and global optima

Optimality criteria for differentiable objective Quasiconvex optimization

Convex optimization problems in standard form

Convex minimization

min f

0

(x) f

0

is convex.

s.t. f

i

(x) ≤ 0, i = 1, . . . , m, f

i

are convex.

a

^T_j

x = b

j

, j = 1, . . . , p.

If f

0

is quasiconvex instead of convex, then problem is a quasiconvex minimization problem.

Concave maximization

max f

0

(x) f

0

is concave.

s.t. f

i

(x) ≥ 0, i = 1, . . . , m, f

i

are concave.

a

^T_j

x = b

_j

, j = 1, . . . , p.

(14)

Local and global optima

Theorem

Any local optimum of convex optimization problems is also a global optimum.

Proof Let x be a local optimum: ∃ R > 0 s.t. f

0

(x) = inf{f

0

(z)| z, feasible, kz − xk

2

≤ R}. Suppose, on the contrary, ∃ z ∈ D such that f (z) < f (x).

Then, ∃y such that ky − x k

2

< R and y = λx + (1 − λ)z for some 0 < λ < 1.

Since f (y ) ≥ f (x ) > f (z), f (y ) > λf (x ) + (1 − λ)f (z). A contradiction to convexity of f

0

.

Remark

Not necess. true for quasiconvex minimization.

(15)

Theorem

For convex minimization with differentiable f

0

, feasible x is optimal iff

∇f

0

(x )

^T

(y − x) ≥ 0 for any feasible y .

Proof “If” part. For any feasible y we have f

0

(y ) ≥ f

0

(x) + ∇f

0

(x )

^T

(y − x ) ≥ f

0

(x).

“Only if” part. Suppose not: ∃y ∈ X such that ∇f

0

(x )

^T

(y − x) < 0.

For λ ∈ [0, 1], let g (λ) = f

0

(λy + (1 − λ)x). Then, d

dλ g (λ)

λ=0

= ∇f

0

(x)

^T

(y − x ) < 0,

which implies that for small enough λ > 0, we have g(λ) < g (0). A

contradiction to optimality of x .

(16)

Corollary

For unconstrained convex minimization, x is optimal iff x is feasible and

∇f

0

(x ) = 0.

Corollary

For convex minimization with equality constraints only, x is optimal iff ∃λ s.t.

A

^T

λ = ∇f

0

(x ), where λ ∈ R

^p

. Proof

x optimal ⇐⇒ ∀y s.t. Ay = b, ∇f

0

(x)

^T

(y − x ) ≥ 0

⇐⇒ ∇f

0

(x)

^T

z ≥ 0, ∀z ∈ N (A) ⇐⇒ ∇f

0

(x )

^T

z = 0, ∀z ∈ N (A)

⇐⇒ ∇f

0

(x) ⊥ N (A) ⇐⇒ ∇f

0

(x) ∈ R(A

^T

)

⇐⇒ ∃λ s.t. A

^T

λ = ∇f

0

(x), λ ∈ R

^p

.

(17)

Example

Consider the problem

min f

0

(x ) s.t. x ≥ 0

Optimality condition : x ≥ 0, ∇f

0

(x)

^T

(y − x ) ≥ 0 for all y ≥ 0.

∇f

0

(x)

^T

y is unbounded below on y ≥ 0 unless ∇f

0

(x) ≥ 0, which implies −∇f

0

(x)

^T

x ≥ 0.

But, as x ≥ 0 and ∇f

0

(x) ≥ 0, we get ∇f

0

(x )

^T

x = 0.

Thus, optimality condition becomes

x ≥ 0, ∇f

0

(x) ≥ 0, x

i

(∇f

0

(x ))

i

= 0, complementary condition.

(18)

min f

0

(x) f

0

is quasiconvex,

s.t. f

i

(x) ≤ 0, i = 1, . . . , m, f

i

’s are convex, Ax = b.

1

It can have local optima that are not global optima.

2

A sufficient optimality condition: If x is feasible and

∇f

0

(x )

^T

(y − x) > 0, ∀ feasible y , then x is globally optimal.

3

Solvable via a sequence of convex feasibility problems.

(19)

Let φ

t

: R

ⁿ

→ R , t ∈ R such that

f

0

(x) ≤ t ⇐⇒ φ

t

(x ) ≤ 0 and φ

s

(x ) ≤ φ

t

(x ) for s ≥ t.

Then, optimal value p

^∗

can be computed as follows:

find x If the problem is feasible, then p

^∗

≤ t = UB.

s.t. φ

t

(x ) ≤ 0 Otherwise, p

^∗

≥ t = LB.

f

i

(x ) ≤ 0, ∀i t ← (UB + LB)/2

Ax = b Repeat until UB − LB ≤ .

Note that it requires dlog

₂

((UB − LB)/)e iterations for an -suboptimal

solution.

(20)

Examples

Quadratic program (QP) minimizes convex quadratic over polyhedron.

min

¹₂

x

^T

Px + q

^T

x + r s.t. Gx ≤ h

Ax = b, where P ∈ S

ⁿ+

, G ∈ R

^m×n

, A ∈ R

^p×n

.

Quadratically constrained quadratic program (QCQP) minimizes convex quadratic over intersection of ellipsoids.

min

¹₂

x

^T

P

0

x + q

₀^T

x + r

0

s.t.

¹₂

x

^T

P

i

x + q

_i^T

x + r

0

≤ 0, i = 1, · · · , m Ax = b,

where P

i

∈ S

ⁿ+

, i = 0, 1, · · · , m.

QCQP ⊇ QP ⊇ LP.

(21)

Examples

Minimizing Euclidean norm of affine functions

Least-squares and regression

kAx − bk

²₂

= x

^T

A

^T

Ax − 2b

^T

Ax + b

^T

b.

Analytical solution is x = A

^†

b. But, if linear inequality constraints are added, e.g.

min kAx − bk

²₂

s.t. l

i

≤ x

i

≤ u

i

, i = 1,· · · , n, problem does not have analytical solution and solvable via QP.

Distance between polyhedra For P

1

= {x|A

1

x ≤ b

1

},P

2

= {x|A

2

x ≤ b

2

}, dist(P

₁

, P

₂

) = inf{kx

₁

− x

2

k

₂

|x

₁

∈ P

₁

, x

2

∈ P

₂

},

can be computed via following QP:

min kx

₁

− x

2

k

²₂

s.t. A

1

x ≤ b

1

(x

1

∈ P

1

)

A

2

x ≤ b

2

(x

2

∈ P

2

).

(22)

Examples

Linear program with random cost

Suppose that c ∈ R

ⁿ

is random with mean ¯ c and covariance Σ. Then, E(c

^T

x ) = ¯ c

^T

x , Var(c

^T

x) = E(c

^T

x − ¯ c

^T

x)

²

= x

^T

Σx A possible problem is to minimize a weighted sum of expected cost and uncertainty cost. To do so, we can consider γ, risk-sensitive cost so that the problem is formulated as follows:

min c ¯

^T

x + γx

^T

Σx s.t. Gx ≤ h

Ax = b.

(23)

Examples

Markowitz portfolio optimization

Let x

_i

be amount of asset or stock i = 1, . . ., n; x

_i

> 0 ↔ long position in asset i, x

_i

< 0 ↔ short position in asset i.

Let p

i

be increase of price of i during a period; we assume p has mean vector ¯ p and covariance matrix Σ.

Classical model minimizes risk guaranteeing a return with no shorting:

min x

^T

Σx s.t. p ¯

^T

x ≥ r

min

,

1

^T

x = 1, x ≥ 0.

Various extensions are possible.

(24)

Examples

For x ∈ R

ⁿ

, A

i

∈ R

ⁿⁱ^×n

, SOCP has the form min f

^T

x

s.t. kA

i

x + b

_i

k

2

≤ c

_i^T

x + d

_i

, i = 1, · · · , m Fx = g .

The first constraints require affine transforms (A

i

x + b

i

, c

_i^T

x + d

i

) to be in second-order cones in R

ⁿⁱ⁺¹

.

Note that SOCP ⊇ QCQP ( by squaring soc-constraints) and SOCP

⊇ LP (when A

i

= 0, ∀i).

(25)

Examples

Robust linear programming

Let a

i

’s be uncertain and lie in given ellipsoids E

i

= {¯ a

i

+ P

i

u|kuk

2

≤ 1}.

min c

^T

x robust version −−−−−−−−−→ min c

^T

x

s.t. a

^Ti

x ≤ b

i

, i = 1, · · · , m s.t. a

^Ti

x ≤ b

i

, ∀a

i

∈ E

i

, ∀i a

^T_i

x ≤ b

i

, ∀a

i

∈ E

i

⇔ sup{a

_i^T

x |a

i

∈ E

i

} ≤ b

i

, and

sup{a

^T_i

x|a

i

∈ E

i

} = ¯ a

^T_i

x + sup{u

^T

P

_i^T

x |kuk ≤ 1} = ¯ a

^T_i

x + kP

_i^T

xk

2

≤ b

i

Thus, we have the following SOCP:

min c

^T

x

s.t. ¯ a

^Ti

x + kP

i^T

x k

2

≤ b

i

, ∀i .

(26)

Examples

Linear programming with random constraints

Suppose that a

i

’s are indep. Gaussian random vectors with mean ¯ a

i

and covariance Σ

i

. Also suppose P(a

^T_i

x ≤ b

i

) ≥ η ≥ 1/2. Let u = a

^T_i

x and σ

²

be its variance. Normalizing we have

P u − u ¯

σ ≤ b

i

− ¯ u σ

≥ η ⇐⇒ b

i

− ¯ u

σ ≥ Φ

⁻¹

(η) ⇐⇒ ¯ u + Φ

⁻¹

(η)σ ≤ b

i

. From σ = (x

^T

Σ

i

x )

^1/2

, we have ¯ a

^T_i

x + Φ

⁻¹

(η)kΣ

^1/2_i

x k

2

≤ b

i

. Hence

min c

^T

x ⇔ min c

^T

x

s.t. P(a

^T_i

x ≤ b

i

) ≥ η, ∀i s.t. ¯ a

^T_i

x + Φ

⁻¹

(η)kΣ

^1/2_i

xk

2

≤ b

i

, ∀i

Since η ≥ 1/2, Φ

⁻¹

(η) ≥ 0, and problem is thus an SOCP.

(27)

Monomials and posynomials Geometric program in convex form Examples

Monomials

f (x ) = cx

₁^a¹

x

₂^a²

· · · x

n^aⁿ

, c > 0, a

i

∈ R , domf = R

ⁿ++

Closed under multiplication and division.

Posi(tively weighted sum of mo)nomials

f (x ) =

K

X

k=1

c

k

x

₁^a^1k

x

₂^a^2k

· · · x

_n^a^nk

, c

k

> 0

Closed under addition, multiplication, and nonnegative scaling.

(28)

Definition

Geometric programming

min f

0

(x ) f

0

posynomial

s.t. f

i

(x) ≤ 1 i = 1, · · · , m f

i

posynomials h

j

(x ) = 1 j = 1, · · · , p h

j

monomials x > 0. implicit constraints Extensions of geometric programming

max x/y ⇒ min x

⁻¹

y

s.t. 2 ≤ x ≤ 3 s.t. 2x

⁻¹

≤ 1, (1/3)x ≤ 1 x

²

+ 3y/z ≤ √

y x

²

y

^−1/2

+ 3y

^1/2

z

⁻¹

≤ 1

x/y = z

²

xy

⁻¹

z

⁻²

= 1

(29)

Monomials and posynomials can be converted into convex form:

f

mono

(x) = cx

₁^a¹

· · · x

n^aⁿ

= c(e

^y¹

)

^a¹

· · · (e

^yⁿ

)

^aⁿ

= e

^a^T^y^+b

f

posy

(x) =

K

X

k=1

c

k

x

₁^a^1k

· · · x

_n^a^nk

=

K

X

k=1

c

k

(e

^y¹

)

^a^1k

· · · (e

^yⁿ

)

^a^nk

=

K

X

k=1

e

^a^T^k^y+b^k

,

where y

i

= log x

i

, b = log c, b

k

= log c

k

.

Using above conversion, we can transform GP into a convex optimization:

min

K₀

X

k=1

e

^a^T^0k^y+b^0k

⇒ min ˜ f

0

(y ) = log

^K0

X

k=1

e

^a^T^0k^y+b^0k

s.t.

K_i

X

k=1

e

â^Tîk^y+bîk

≤ 1 s.t. ˜ f

i

(y) = log

^Ki

X

k=1

e

â^Tîk^y^+bîk

≤ 0 e

^g^j^T^y+h^j

= 1 ˜ h

j

(y) = g

_j^T

y + h

j

= 0.

Since ˜ f

i

’s are convex and ˜ h

j

’s are affine, this is convex optimization.

(30)

Frobenius diagonal scaling y = Mu

scaling coordinates

−−−−−−−−−−−→

˜ y = DMD

⁻¹

u ˜ with ˜ u = Du, ˜ y = Dy.

kDMD

⁻¹

k

²_F

= tr (DMD

⁻¹

)

^T

(DMD

⁻¹

)

=

n

X

i,j=1

(DMD

⁻¹

)

²_ij

=

n

X

i,j=1

M

_ij²

d

_i²

/d

_j²

Thus, minimizing Frobenius norm is an unconstrained GP.

(31)

Design of cantilever beam

Minimize total volume of beam, w

₁

h

₁

+ · · · + w

_n

h

_n

subject to some

constraints.

(32)

Design of cantilever beam(cont’d)

1

Upper and lower bounds on w

i

, h

i

w

min

≤ w

i

≤ w

max

, h

min

≤ h

i

≤ h

max

, i = 1, · · · , N.

2

Upper and lower bounds on aspect ratios h

i

/w

i

S

_min

≤ h

_i

/w

_i

≤ S

max

,i = 1,· · · , N.

3

Upper bound on stress in each segment 6iF

w

i

h

²_i

≤ σ

max

, i = 1,· · · , N.

4

Upper bound on vertical deflection at end of beam, y

1

≤ y

max

From deflection and slope of beam segments, y

1

can be obtained:

F F

(33)

Definition Conic form problems Second-order cone programs

Convex optimization problem with generalized inequality constraints min f

0

(x )

s.t. f

i

(x)

K_i

0, i = 1, · · · , m Ax = b

where f

0

: R

ⁿ

→ R , K

i

⊆ R

^kⁱ

, and f

i

: R

ⁿ

→ R

^kⁱ

are K

i

−convex.

Many properties of ordinary convex optimization are extended to this problem

1

Feasible set, any sublevel set, and optimal set are convex.

2

Any local optimum is global optimum.

3

Feasible x is globally optimal iff ∇f

0

(x )

^T

(y − x ) ≥ 0 ∀ feasible y .

(34)

Conic form problems (conic programs, or cone-LPs). When K is nonnegative orthant, reduces to LP.

1. 2. 3.

min c

^T

x min c

^T

x min c

^T

x

s.t. Fx + g

K

0 s.t. x

K

0 s.t. Fx + g

K

0

Ax = b Ax = b

1

General form.

2

Standard form.

3

Inequality form.

(35)

min f

^T

x ⇒ min f

^T

x

s.t. kA

i

x + b

_i

k

2

≤ c

_i^T

x + d

_i

, ∀i s.t. −(A

i

x + b

_i

, c

_i^T

x + d

_i

)

Ki

0, ∀i

Fx = g Fx = g

where K

i

= {(y, t) ∈ R

^kⁱ⁺¹

|kyk

2

≤ t}

(36)

Definition

Standard and inequality form Examples

Here, K = S

^k+

. Then conic form is min c

^T

x

s.t. x

₁

F

₁

+ · · · x

_n

F

_n

+ G 0 (LMI ) Ax = b,

where G , F

1

, . . . , F

n

∈ S

^k

, A ∈ R

^p×n

.

Note that if G , F

₁

, · · · , F

_n

are all diagonal, then SDP reduces to LP.

(37)

Definition

1. 2.

min tr(CX ) min c

^T

x

s.t. tr(A

i

X ) = b

i

, i = 1, · · · , p s.t. x

1

A

1

+ · · · + x

n

A

n

B X 0.

1

Standard form: C, A

1

, · · · , A

n

∈ S

ⁿ

.

2

Inequality form: B, A

1

, · · · , A

n

∈ S

^k

, c ∈ R

ⁿ

.

(38)

Definition

Matrix norm (or maximum eigenvalue) minimization

Let A(x ) = A

0

+ x

1

A

1

+ · · · + x

n

A

n

, where A

i

∈ R

^p×q

. How to minimize maximum eigenvalue kA(x)k

2

or λ

max

(A(x ))? Observe that

λ

max(B)

≤ µ ⇐⇒ B = UλU

^T

, λI − Λ 0

⇐⇒ U(µI − Λ)U

^T

0 ⇐⇒ µI − UΛU

^T

0

⇐⇒ µI − B 0.

Therefore, we have

λ

max

(A(x)

^T

A(x)) ≤ s

²

⇐⇒ s

²

I −A

^T

(x )A(x ) 0 ⇐⇒

sI A(x ) A(x )

^T

xI

0, an LMI!

In sum, min kA(x )k

2

is equivalent to min t

sI A(x )