[Boyd]_cvxslides

Multicriterion optimization

vector optimization problem with K = Rq+

f0(x) = (F1(x), . . . , Fq(x))

•q di erent objectives Fi; roughly speaking we want all Fi’s to be small

•feasible x is optimal if

y feasible = f0(x ) f0(y)

if there exists an optimal point, the objectives are noncompeting

• feasible xpo is Pareto optimal if

y feasible, f0(y) f0(xpo) = f0(xpo) = f0(y)

if there are multiple Pareto optimal values, there is a trade-o between the objectives

Regularized least-squares

minimize (w.r.t. R2+) (kAx − bk22, kxk22)

example for A R100×10; heavy line is formed by Pareto optimal points

Risk return trade-o in portfolio optimization

•x Rn is investment portfolio; xi is fraction invested in asset i

•p Rn is vector of relative asset price changes; modeled as a random variable with mean p¯, covariance Σ

•p¯T x = E r is expected return; xT Σx = var r is return variance

Scalarization

for convex vector optimization problems, can find (almost) all Pareto optimal points by varying λ K 0

Scalarization for multicriterion problems

to find Pareto optimal points, minimize positive weighted sum

λT f0(x) = λ1F1(x) + · · · + λqFq(x)

examples

• regularized least-squares problem of page 4–43

• risk-return trade-o of page 4–44

for fixed γ > 0, a quadratic program

Convex Optimization — Boyd & Vandenberghe

5. Duality

•Lagrange dual problem

•weak and strong duality

•geometric interpretation

•optimality conditions

•perturbation and sensitivity analysis

•examples

•generalized inequalities

5–1

Lagrangian

standard form problem (not necessarily convex)

variable x Rn, domain D, optimal value p

Lagrangian: L : Rn × Rm × Rp → R, with dom L = D × Rm × Rp,

•weighted sum of objective and constraint functions

•λi is Lagrange multiplier associated with fi(x) ≤ 0

•νi is Lagrange multiplier associated with hi(x) = 0

Lagrange dual function

g is concave, can be −∞ for some λ, ν

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

f0(˜x) ≥ L(˜x, λ, ν) ≥ inf L(x, λ, ν) = g(λ, ν)

xD

minimizing over all feasible x˜ gives p ≥ g(λ, ν)

Least-norm solution of linear equations

dual function

•Lagrangian is L(x, ν) = xT x + νT (Ax − b)

•to minimize L over x, set gradient equal to zero:

xL(x, ν) = 2x + AT ν = 0 = x = −(1/2)AT ν

• plug in in L to obtain g:

g(ν) = L((−1/2)AT ν, ν) = −14νT AAT ν − bT ν a concave function of ν

lower bound property: p ≥ −(1/4)νT AAT ν − bT ν for all ν