Chapter 4
: Constrained
gradient-based optimization
4 11 . Intro + Problem
formulation
~s
optim problems
. are
rarely unconstrained
Build
further the methods from Chapter 3 ?
↳
on n
first introduce
optimality conditions for constrained
opt problem
then
~
focus on 3 main methods
2
{
w
Penalty methods
=
sequential quads progr .
.
(SQP)
·
interior-point methods
in
general : minf(x
t X /Mx dim ) variable vector
2 . .
g(x)20 -
-
ps vecter constraints
ha = eg h : --R
: /R -
" inequality
vector
0 ~
D
equality constraints
↳ both
of (f) .
+ contraints
(g ,
h)
_
↳ con be non-lineair f
ㅇ
↳ should be
2
continuous
constraints ?
-to solve a contrained
problem - Also
requir gradients of all
값 값
1
…
Yn Similar
Ig (Mg
=
: :
-- .
,
재행 ? :
↓ xnx)
(MnXMx) ↳
for inequality constraint
.
G 2) conditions
.
Optimality
↳ Not as
straight forward as those
for unconstrained
start for
~
equality contr .
*
Equality Constraints
~
again start fum order Tayler series
expansion of objective function .
f(x p) f(x)
+ = +
ffxxp
~ Since ** 0 min =>
OfSX 1Tp *
3 0 ④
If unconstrained
only
the
inequality would be If (x *
problem
-
to
satisfy
were 1 =
,
way
-
If problem is constrained ,
function increase & still applies ,
but
p
must be also a
feasible direction
direction 12 order
to
find feasible write
Taylor expansion
~ can
,
we a
constraint
for each
equality
一
,hj(x hj(x) ohjkx)
+
+
p) = +
pj 1
,..., order
mn
first
=
here
dso A feasibility
~
assume
higher order
neglected because
of small step size
T
jThe ne
Assuming is
feasible point-phj(x) 0
for all
=
X a
#‰
→
here Mx =
Mn = 2
↳
feasible space reduced
to
single point
this has to
r means
any feasible di. => no
optim .
freedom !
lis in
nulspace of Jacobian
of the constraints In?
_
Assume rank /i µ
In has full de Constraint
grad linearly indep. (
>
-
.
e . .
Or
>
-
feasible space is sulspace of dimension Mx -
Mp .
for opt . To be
possible nx > un Why ?
~
for one contraint ,
we have thip = o
↳
feasible space corresponds to
tangent plane
- >
for 2 or moe contraints ,
feorible space
reduces to intersection of all tangent hyperplanes ?
~
in 3D -- a line
~
for constrained
optimality > need to
satisfy both If 1 p3 *
, 0 and
Ip(x)p =
-for equality constrained ,
if p
is
feasible ,
-p
must dro be
feasible
=>
ratify
My way to OfIp 70 is
if IfTp =
~ in sum ,
for
*
to be a contrained
optimum ,
we
requir Of *
p
= 0
for all
p such
that
Yu ( t ip
* = o
, other words, vanish
projection of dy function's gradient
~ must
in .
into
feasible space
If(x upon (th(x
Chasx Ohnn' ** )
* *
or
*
) = ) , ) , . . . ,
hers this is illustrated
for case
2 constraints
in 3D
>
-
constrained optimum If * p = o
require If to be I to nullspace of In
motic contains all vectors I to it's nullspace
~ row
space of a
because ofTp
>
-
rowe are
gradients of the constraints
-
objective funct gradient must be a linear comb
of gradients of constraints
Ef ( +
*
) =
λ jchjs + * 1
associated with each constraints
Lagrange multipliers
↳ ,
one
=
first-order optimality condition
for equality contraint are
「
ef ( x *
1 -
yn /x ) λ
h(x) 0
=
Def In constrained optio ,
the
lagrangian function being
a scalar is
defined a
2(x, x) =
f(x) + h5xX
↳
hagrang
Considered to
;an multiplien ora
be
independant
Theorem
gradient of h wrt
king both andit
h EfA reYn *
*
e. =
* *
) λ = 0
第h = hir *
) = 0
with x linear
satisfying independence constraint
qualification
With
lagrangian ,
we
transformed a contrained problem I
design var
, M eg. Contraints
into unconstrained
Adding
by
variable x / MM I
>
new
-
problem
.
desivation
of first-order optimally assumes
gradients of constraints
linearly independent In full rew
>
rank
一
: Constrained
gradient-based optimization
4 11 . Intro + Problem
formulation
~s
optim problems
. are
rarely unconstrained
Build
further the methods from Chapter 3 ?
↳
on n
first introduce
optimality conditions for constrained
opt problem
then
~
focus on 3 main methods
2
{
w
Penalty methods
=
sequential quads progr .
.
(SQP)
·
interior-point methods
in
general : minf(x
t X /Mx dim ) variable vector
2 . .
g(x)20 -
-
ps vecter constraints
ha = eg h : --R
: /R -
" inequality
vector
0 ~
D
equality constraints
↳ both
of (f) .
+ contraints
(g ,
h)
_
↳ con be non-lineair f
ㅇ
↳ should be
2
continuous
constraints ?
-to solve a contrained
problem - Also
requir gradients of all
값 값
1
…
Yn Similar
Ig (Mg
=
: :
-- .
,
재행 ? :
↓ xnx)
(MnXMx) ↳
for inequality constraint
.
G 2) conditions
.
Optimality
↳ Not as
straight forward as those
for unconstrained
start for
~
equality contr .
*
Equality Constraints
~
again start fum order Tayler series
expansion of objective function .
f(x p) f(x)
+ = +
ffxxp
~ Since ** 0 min =>
OfSX 1Tp *
3 0 ④
If unconstrained
only
the
inequality would be If (x *
problem
-
to
satisfy
were 1 =
,
way
-
If problem is constrained ,
function increase & still applies ,
but
p
must be also a
feasible direction
direction 12 order
to
find feasible write
Taylor expansion
~ can
,
we a
constraint
for each
equality
一
,hj(x hj(x) ohjkx)
+
+
p) = +
pj 1
,..., order
mn
first
=
here
dso A feasibility
~
assume
higher order
neglected because
of small step size
T
jThe ne
Assuming is
feasible point-phj(x) 0
for all
=
X a
#‰
→
here Mx =
Mn = 2
↳
feasible space reduced
to
single point
this has to
r means
any feasible di. => no
optim .
freedom !
lis in
nulspace of Jacobian
of the constraints In?
_
Assume rank /i µ
In has full de Constraint
grad linearly indep. (
>
-
.
e . .
Or
>
-
feasible space is sulspace of dimension Mx -
Mp .
for opt . To be
possible nx > un Why ?
~
for one contraint ,
we have thip = o
↳
feasible space corresponds to
tangent plane
- >
for 2 or moe contraints ,
feorible space
reduces to intersection of all tangent hyperplanes ?
~
in 3D -- a line
~
for constrained
optimality > need to
satisfy both If 1 p3 *
, 0 and
Ip(x)p =
-for equality constrained ,
if p
is
feasible ,
-p
must dro be
feasible
=>
ratify
My way to OfIp 70 is
if IfTp =
~ in sum ,
for
*
to be a contrained
optimum ,
we
requir Of *
p
= 0
for all
p such
that
Yu ( t ip
* = o
, other words, vanish
projection of dy function's gradient
~ must
in .
into
feasible space
If(x upon (th(x
Chasx Ohnn' ** )
* *
or
*
) = ) , ) , . . . ,
hers this is illustrated
for case
2 constraints
in 3D
>
-
constrained optimum If * p = o
require If to be I to nullspace of In
motic contains all vectors I to it's nullspace
~ row
space of a
because ofTp
>
-
rowe are
gradients of the constraints
-
objective funct gradient must be a linear comb
of gradients of constraints
Ef ( +
*
) =
λ jchjs + * 1
associated with each constraints
Lagrange multipliers
↳ ,
one
=
first-order optimality condition
for equality contraint are
「
ef ( x *
1 -
yn /x ) λ
h(x) 0
=
Def In constrained optio ,
the
lagrangian function being
a scalar is
defined a
2(x, x) =
f(x) + h5xX
↳
hagrang
Considered to
;an multiplien ora
be
independant
Theorem
gradient of h wrt
king both andit
h EfA reYn *
*
e. =
* *
) λ = 0
第h = hir *
) = 0
with x linear
satisfying independence constraint
qualification
With
lagrangian ,
we
transformed a contrained problem I
design var
, M eg. Contraints
into unconstrained
Adding
by
variable x / MM I
>
new
-
problem
.
desivation
of first-order optimally assumes
gradients of constraints
linearly independent In full rew
>
rank
一
