#math784##tex2html_wrap_inline8474# is on the boundary of the
feasible region satisfying #tex2html_wrap_inline8476#, while the
unconstrained extremum is outside the feasible region.
<#19867#>Figure<#19867#> 2.20:
<#19868#>Inequality Constrained Optimization<#19868#>
| [width=120mm]<#3852#>figures/KKT0a.eps<#3852#> |
We consider the following two possible cases.
- First, if the unconstrained extremum is inside the
feasible region, i.e., the inequality constraint is
inactive, then the solution #tex2html_wrap_inline8478# is the same as
that of an unconstrained problem, not on the boundary of
the feasible region, i.e.,
#math785# #tex2html_wrap_indisplay19872#
(166)
Similar to the case of an inactive equality constraint,
here the multiplier for an inactive inequality constraint
is zero, i.e., #tex2html_wrap_inline8480#, and we get
#math786# #tex2html_wrap_indisplay19875#
(167)
the same as in Eq. (#inactiveEqualityConstraint#3873>).
- Second, if the unconstrained extremum at which
#math787##tex2html_wrap_inline8482# is outside the
feasible region, i.e., the inequality constraint is active,
then the constrained solution #tex2html_wrap_inline8484# must be on the
boundary of the feasible region, and it is different from
the unconstrained solution:
#math788# #tex2html_wrap_indisplay19879#
(168)
In this case, the problem becomes the same as an equality
constrained problem considered before, i.e., the objective
function #tex2html_wrap_inline8486# and the constraint function #tex2html_wrap_inline8488#
have the same tangent at #tex2html_wrap_inline8490# with parallel gradients:
#math789# #tex2html_wrap_indisplay19884#
(169)
<#19885#>Figure<#19885#> 2.21:
<#19886#>Determination of Signs of Lagrange Multipliers<#19886#>
| [width=110mm]<#3900#>figures/KKT1a.eps<#3900#> |
266
However, different from before, now we also need to consider
whether the two gradients have the same or opposite directions,
corresponding to #tex2html_wrap_inline8492# or #tex2html_wrap_inline8494#, respectively. Specifically,
there exist four possible cases in terms of the sign of #tex2html_wrap_inline8496#,
depending on whether #tex2html_wrap_inline8498# is to be maximized or minimized,
and whether the constraint is #math790##tex2html_wrap_inline8500# or #math791##tex2html_wrap_inline8502#,
as the four points #tex2html_wrap_inline8504# through #tex2html_wrap_inline8506# illustrated in the 1-D examples
in Fig. #KKT1a#3907> and also summarized in the tables below:
#math792# #tex2html_wrap_indisplay19897#
(170)
#math793# #tex2html_wrap_indisplay19899#
(171)
We can also consider the product of #tex2html_wrap_inline8508# and #tex2html_wrap_inline8510#
for either maximization or minimization:
#math794# #tex2html_wrap_indisplay19903#
(172)
Summarizing the two cases above, we see that #math795##tex2html_wrap_inline8512#
but #tex2html_wrap_inline8514# in the first case of an inactive constraint, and
#math796##tex2html_wrap_inline8516# but #tex2html_wrap_inline8518# in the second case of an active
constraint, i.e., the following holds in both cases:
#math797# #tex2html_wrap_indisplay19909#
(173)
The discussion above can be generalized from 2-D to #tex2html_wrap_inline8520# dimensional
space, in which the optimal solution #tex2html_wrap_inline8522# is to be found
to extremize the objective #tex2html_wrap_inline8524# subject to #tex2html_wrap_inline8526# inequality
constraints #math798##tex2html_wrap_inline8528#. To solve this inequality
constrained optimization problem, we first construct the Lagrangian:
#math799# #tex2html_wrap_indisplay19916#
(174)
where #math800##tex2html_wrap_inline8530# is a vector for #tex2html_wrap_inline8532#
Lagrange multipliers.
(We note that in some literature, a plus sign is used in front of the
summation of the second term. This is equivalent to our discussion
here so long as the sign of #tex2html_wrap_inline8534# indicated in Table #PolarityTable#3969>
is negated.) Now Eq. (#mugeqz#3970>) can be written as
#math801# #tex2html_wrap_indisplay19921#
(175)
We then set the gradient of the Lagrangian to zero:
#math802# #tex2html_wrap_indisplay19923#
(176)
and get two equation systems of #tex2html_wrap_inline8536# and #tex2html_wrap_inline8538# equations,
respectively:
#math803# #tex2html_wrap_indisplay19927#
(177)
and
#math804# #tex2html_wrap_indisplay19929#
(178)
The result above for the inequality constrained problems based on
Eq. (#LagrangianInequality#4007>) looks the same as that for the
equality constrained problems based on Eq. (#LagrangianEquality#4008>),
but with an additional requirement regarding the sign of the
Lagrange multipliers. For an equality constrained problem, the
direction of the gradient #math805##tex2html_wrap_inline8540# is of no
concern, i.e., the sign of #tex2html_wrap_inline8542# is unrestricted; but here for
an inequality constrained problem, the sign of #tex2html_wrap_inline8544# needs to be
consistent with those shown in Table #PolarityTable#4010>, unless
when the constraint is inactive and #tex2html_wrap_inline8546#.
We now consider the general optimization of an N-D objective
function #tex2html_wrap_inline8548# subject to multiple constraints of equalities
and inequalities:
#math806# #tex2html_wrap_indisplay19936#
(179)
For notational convenience, we denote the #tex2html_wrap_inline8550# equality and
inequality constraints in vector form as:
#math807# #tex2html_wrap_indisplay19939#
(180)
where #math808##tex2html_wrap_inline8552# and
#math809##tex2html_wrap_inline8554#.
To solve this optimization problem, we first construct the Lagrangian
#math810# #tex2html_wrap_indisplay19943#
(181)
where the Lagrange multipliers in
#math811##tex2html_wrap_inline8556# and
#math812##tex2html_wrap_inline8558# are for the #tex2html_wrap_inline8560#
equality and #tex2html_wrap_inline8562# non-negative constraints, respectively.
We then set to zero the gradient of
#math813##tex2html_wrap_inline8564# with
respect to both #math814##tex2html_wrap_inline8566# and #math815##tex2html_wrap_inline8568#
as well as #tex2html_wrap_inline8570#.
#math816# #tex2html_wrap_indisplay19953#
(182)
Solving these equation systems we get the solution #tex2html_wrap_inline8572#.
While #tex2html_wrap_inline8574# can be either positive or negative, the sign
of #tex2html_wrap_inline8576# needs to be consistent with those specified in Table
#PolarityTable#4102>. Otherwise the inequality constraints is
inactive.
<#4103#>Example:<#4103#>
Find the extremum of #math817##tex2html_wrap_inline8578# subject to each of
the three different constraints: #tex2html_wrap_inline8580#, #tex2html_wrap_inline8582#, and
#tex2html_wrap_inline8584#.
<#19961#>Figure<#19961#> 2.22:
<#19962#>Constrained Optimization Example 1<#19962#>
| [width=70mm]<#4105#>figures/optConstrainedEx.eps<#4105#> |
#math818# #tex2html_wrap_indisplay19965#
The Lagrangian is:
#math819# #tex2html_wrap_indisplay19967#
Solving the following equations
#math820# #tex2html_wrap_indisplay19969#
we get #math821##tex2html_wrap_inline8586#, i.e., the function
is minimized at #math822##tex2html_wrap_inline8588#. We note that #tex2html_wrap_inline8590#
and #tex2html_wrap_inline8592# have the same gradients at #math823##tex2html_wrap_inline8594#:
#math824# #tex2html_wrap_indisplay19976#
- Consider these two problems:
#math825# #tex2html_wrap_indisplay19978#
These problems are the two middle cases (2 and 3) in Table
#PolarityTable#4141>. They have the same Lagrangian as above
with the same results #math826##tex2html_wrap_inline8596# and #tex2html_wrap_inline8598#.
According to Table #PolarityTable#4142>, #tex2html_wrap_inline8600# is
the solution for the minimization problem subject to
#math827##tex2html_wrap_inline8602# (left), or the maximization problem
subject to #math828##tex2html_wrap_inline8604#.
- Consider these two problems:
#math829# #tex2html_wrap_indisplay19985#
These problems are cases 1 and 4 in Table #PolarityTable#4158>.
Again they have the same Lagrangian as in the previous cases
and the same results #math830##tex2html_wrap_inline8606#, and #tex2html_wrap_inline8608#.
According to Table #PolarityTable#4159>, #tex2html_wrap_inline8610# is <#4161#>not<#4161#>
the solution of either of the two problems, i.e., the constraint
is inactive. We therefore need to assume #tex2html_wrap_inline8612# and solve the
following equations for an unconstrained problem:
#math831# #tex2html_wrap_indisplay19991#
Now we get #tex2html_wrap_inline8614# and #math832##tex2html_wrap_inline8616#, with
minimum #math833##tex2html_wrap_inline8618#. This is the solution for the
minimization problem (right), at which #math834##tex2html_wrap_inline8620#,
i.e., the constraint is inactive. However this is not
the solution for the maximization problem as the function
is unbounded from above.