[Boyd]_cvxslides

Introducing new variables and equality constraints

minimize f0(Ax + b)

•dual function is constant: g = infx L(x) = infx f0(Ax + b) = p

•we have strong duality, but dual is quite useless

dual function follows from

norm approximation problem: minimize kAx − bk

can look up conjugate of k · k, or derive dual directly

Implicit constraints

LP with box constraints: primal and dual problem

= −bT ν − kAT ν + ck1 dual problem: maximize −bT ν − kAT ν + ck1

Problems with generalized inequalities

Ki is generalized inequality on Rki

definitions are parallel to scalar case:

•Lagrange multiplier for fi(x) Ki 0 is vector λi Rki

•Lagrangian L : Rn × Rk1 × · · · × Rkm × Rp → R, is defined as

• dual function g : Rk1 × · · · × Rkm × Rp → R, is defined as

g(λ1, . . . , λm, ν) = inf L(x, λ1, · · · , λm, ν)

xD

lower bound property: if λi Ki 0, then g(λ1, . . . , λm, ν) ≤ p proof: if x˜ is feasible and λ Ki 0, then

•weak duality: p ≥ d always

•strong duality: p = d for convex problem with constraint qualification (for example, Slater’s: primal problem is strictly feasible)

Semidefinite program

•Lagrange multiplier is matrix Z Sk

•Lagrangian L(x, Z) = cT x + tr (Z(x1F1 + · · · + xnFn − G))

•dual function

p = d if primal SDP is strictly feasible ( x with x1F1 + · · · + xnFn G)

Convex Optimization — Boyd & Vandenberghe

6.Approximation and fitting

•norm approximation

•least-norm problems

•regularized approximation

•robust approximation

6–1

Norm approximation

minimize kAx − bk

(A Rm×n with m ≥ n, k · k is a norm on Rm) interpretations of solution x = argminx kAx − bk:

•geometric: Ax is point in R(A) closest to b

•estimation: linear measurement model

y = Ax + v

y are measurements, x is unknown, v is measurement error given y = b, best guess of x is x

•optimal design: x are design variables (input), Ax is result (output) x is design that best approximates desired result b

examples

• least-squares approximation (k · k2): solution satisfies normal equations

AT Ax = AT b

(x = (AT A)−1AT b if rank A = n)

• Chebyshev approximation (k · k∞): can be solved as an LP

minimize t

subject to −t1 Ax − b t1

• sum of absolute residuals approximation (k · k1): can be solved as an LP

Penalty function approximation

(A Rm×n, φ : R → R is a convex penalty function)