Scribd
Upload
37 views7 pages

Convex Problems: September 15, 2008

This document summarizes techniques for converting convex optimization problems with inequalities and equalities into equivalent problems that preserve convexity. It introduces using slack variables to convert linear inequalities into equalities, eliminating equality constraints by introducing new variables, and using epigraph form to convert problems into equivalent forms that can be solved as linear programs. The techniques allow for problems with mixed inequality and equality constraints to be solved while maintaining convexity.

Uploaded by

Samuel Alfonzo Gil Barco
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
37 views7 pages

Convex Problems: September 15, 2008

This document summarizes techniques for converting convex optimization problems with inequalities and equalities into equivalent problems that preserve convexity. It introduces using slack variables to convert linear inequalities into equalities, eliminating equality constraints by introducing new variables, and using epigraph form to convert problems into equivalent forms that can be solved as linear programs. The techniques allow for problems with mixed inequality and equality constraints to be solved while maintaining convexity.

Uploaded by

Samuel Alfonzo Gil Barco
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Lecture 6

Convex Problems

September 15, 2008

• Chapters 4.1-4.2 (except for 4.2.5) of Boyd and Vandenberghe’s book


Lecture 6

Introducing Slack Variables for Linear Inequalities

minimize f (x)
subject to Ax  b

with A ∈ Rm×n and b ∈ Rm, is equivalent to

minimize f (x)
subject to Ax + s = b
s0

• The minimization is over x ∈ Rn and s ∈ Rm

• Convexity preserved

Convex Optimization 1
Lecture 6

Convex Problem with Inequalities and Equalities


minimize f (x)
subject to g(x) ≤ 0, Ax = b

• Eliminating equality constraints:


For a particular solution x0 of Ax = b, and a matrix D whose range is
NA, we have
Ax = b ⇐⇒ x = Dz + x0 for some z
• The problem is equivalent to

minimize f (Dz + x0)


subject to g(Dz + x0) ≤ 0

• The minimization is over z


• Convexity preserved

Convex Optimization 2
Lecture 6

Introducing Equality Constraints


minimize f (A0x + b0)
subject to gj (Aj x + bj ) ≤ 0, j = 1, . . . , m

is equivalent to

minimize f (y0)
subject to gj (yj ) ≤ 0, j = 1, . . . , m
yj = Aj x + bj , j = 0, 1, . . . , m

• The minimization is over x and yj , j = 0, 1, . . . , m

• Convexity preserved

Convex Optimization 3
Lecture 6

Epigraph Form
minimize f (x)
subject to g(x) ≤ 0, Ax = b
is equivalent to

minimize w
subject to f (x) ≤ w
g(x) ≤ 0, Ax = b

• The minimization is over x ∈ Rn and w ∈ R

• Is convexity preserved?

Convex Optimization 4
Lecture 6

Polyhedral Objective Example

minimize max{aT1 x + b1, . . . , aTmx + bm}


subject to B T x ≤ d

• Using the epigraph form of f , the problem is equivalent to an LP

minimize w
subject to aTj x + bj ≤ w, j = 1, . . . , m
BT x ≤ d

Convex Optimization 5
Lecture 6

Minimizing over some Variables


minimize f (x1, x2)
subject to gj (x1) ≤ 0, j = 1, . . . , m̃
gj (x2) ≤ 0, j = m̃ + 1, . . . , m

is equivalent to

minimize F (x2)
subject to gj (x2) ≤ 0, j = m̃ + 1, . . . , m

where
F (x2) = inf f (x1, x2)
x1 : g1 (x1 )≤0,...,gm̃ (x1 )≤0

Convex Optimization 6

You might also like