[Boyd]_cvxslides

Force field interpretation

centering problem (for problem with no equality constraints)

minimize tf0(x) − Pm log(−fi(x))

i=1

force field interpretation

•tf0(x) is potential of force field F0(x) = −t f0(x)

•− log(−fi(x)) is potential of force field Fi(x) = (1/fi(x)) fi(x)

the forces balance at x (t):

Xm

F0(x (t)) + Fi(x (t)) = 0

i=1

example

•objective force field is constant: F0(x) = −tc

•constraint force field decays as inverse distance to constraint hyperplane:

where Hi = {x | aTi x = bi}

−3c

Barrier method

given strictly feasible x, t := t(0) > 0, µ > 1, tolerance ǫ > 0. repeat

1.Centering step. Compute x (t) by minimizing tf0 + φ, subject to Ax = b.

2.Update. x := x (t).

3.Stopping criterion. quit if m/t < ǫ.

4.Increase t. t := µt.

•terminates with f0(x) − p ≤ ǫ (stopping criterion follows from f0(x (t)) − p ≤ m/t)

•centering usually done using Newton’s method, starting at current x

•choice of µ involves a trade-o : large µ means fewer outer iterations, more inner (Newton) iterations; typical values: µ = 10–20

•several heuristics for choice of t(0)

Convergence analysis

number of outer (centering) iterations: exactly

log(m/(ǫt(0))) log µ

plus the initial centering step (to compute x (t(0))) centering problem

minimize tf0(x) + φ(x)

see convergence analysis of Newton’s method

•tf0 + φ must have closed sublevel sets for t ≥ t(0)

•classical analysis requires strong convexity, Lipschitz condition

•analysis via self-concordance requires self-concordance of tf0 + φ

Examples

inequality form LP (m = 100 inequalities, n = 50 variables)

•starts with x on central path (t(0) = 1, duality gap 100)

•terminates when t = 108 (gap 10−6)

•centering uses Newton’s method with backtracking

•total number of Newton iterations not very sensitive for µ ≥ 10

geometric program (m = 100 inequalities and n = 50 variables)

family of standard LPs (A Rm×2m)

m = 10, . . . , 1000; for each m, solve 100 randomly generated instances

number of iterations grows very slowly as m ranges over a 100 : 1 ratio

Feasibility and phase I methods

feasibility problem: find x such that

phase I: computes strictly feasible starting point for barrier method

•if x, s feasible, with s < 0, then x is strictly feasible for (2)

•if optimal value p¯ of (3) is positive, then problem (2) is infeasible

•if p¯ = 0 and attained, then problem (2) is feasible (but not strictly); if p¯ = 0 and not attained, then problem (2) is infeasible

sum of infeasibilities phase I method

for infeasible problems, produces a solution that satisfies many more inequalities than basic phase I method

example (infeasible set of 100 linear inequalities in 50 variables)

left: basic phase I solution; satisfies 39 inequalities

right: sum of infeasibilities phase I solution; satisfies 79 inequalities

example: family of linear inequalities Ax b + γ b

•data chosen to be strictly feasible for γ > 0, infeasible for γ ≤ 0

•use basic phase I, terminate when s < 0 or dual objective is positive

number of iterations roughly proportional to log(1/|γ|)