Information Technology Reference
In-Depth Information
Quadratic Programming (QP) A quadratic programming is a convex optimiza-
tion problem with a convex quadratic function as its objective function and with
affine constraint functions.
1
2 x T Qx
p T x
min
x
+
+
r,
n
R
s.t.
g i (x)
h i ,i
=
1 ,...,m,
a i
x
=
b i ,i
=
1 ,...,l,
where Q is a symmetric and positive semidefinite matrix.
Semidefinite Programming (SDP) A semidefinite programming is a convex opti-
mization problem with a linear objective function optimized over the intersection
of the cone of a group of positive semidefinite matrices with an affine space.
n α T x,
min
x
R
s.t.
x 1 K 1 +···+
x n K n +
G
0 ,
a i
x
=
b i ,i
=
1 ,...,l
where G and K i ,i
=
1 ,...,n are the cone of positive semidefinite matrices.
21.3.4 Lagrangian Duality
An optimization problem can be converted to its dual form, called the dual problem
of the original optimization problem. Sometimes, it is much easier to solve the dual
problem.
Suppose the original optimization problem is written as
min
x
f(x),
s.t.
g i (x)
0 ,i
=
1 ,...,m,
h i (x)
=
0 ,i
=
1 ,...,l.
The main idea of Lagrangian Duality is to take the constraints in the above op-
timization problem into account by revising the objective function with a weighted
sum of the constraint functions. The Lagrangian associated with the above optimiza-
tion problem is defined as
m
l
L(x, θ, φ) = f(x) +
θ i g i (x) +
φ i h i (x),
i
=
1
i
=
1
Search WWH ::




Custom Search