CS计算机代考程序代写 chain Constrained NL Optimization (NLP)

Constrained NL Optimization (NLP)
Goals:
• Optimality conditions for linear constraints
• Lagrange multipliers and Lagrangian
• Optimality conditions for nonlinear constraints • Duality
3/21/2020 @2020 New York University Tandon 204 School of Engineering

3/21/2020
@2020 New York University Tandon 205 School of Engineering
General Statement
A minimization problem with constraints is often written as:
min f (x)
subjectto gi(x)0, iE
gj(x)0, jI where f and g are C2.

Essential Difference Between LP and NLP
For solvable LP problems, optimal solution occurs at an extreme point.
For NLP problems, the optimal solution may not be at an extreme point or even on the boundary of the feasible set.
3/21/2020 @2020 New York University Tandon 206 School of Engineering

Example 1: max P  KL,
subject to 4K  L  8,
Example 2:
max f(x)sinx,
K, L  0 3/21/2020
subject to 0  x  .
Examples
@2020 New York University Tandon 207 School of Engineering

Case 1: Linear Equality Constraints Consider the optimization problem:
min f (x)
subjectto Axb, Amn
with rank(A)  m  n.
Idea: transform the constrained problem into an unconstrained optimization problem.
3/21/2020 @2020 New York University Tandon 208 School of Engineering

3/21/2020
@2020 New York University Tandon 209 School of Engineering
A Motivating Example
Solve the optimization problem with a linear equality constraint:
min f(x)x2 2x x2 x2 4x 11233
subjectto x x 2x 2. 123

3/21/2020
@2020 New York University Tandon 210 School of Engineering
A Motivating Example (cont’d)
The optimization problem can be made “unconstrained” as follows:
min f(x)2×2 3×2 4x x 2x 23232
using x 2x 2x. 123

Answer
A strict local minimizer to the unconstrained problem
is:
x2  1.5, x3  1. Thus, for the original problem,
3/21/2020
@2020 New York University Tandon 211 School of Engineering
x (2.5, 1.5, 1), *
f x 1.5. *

3/21/2020
@2020 New York University Tandon 212 School of Engineering
An Exercise
Solve the following optimization problem:
max f (x)  x x x 123
subject to 123
x  x  x 1 aaa
123 withai 0,xi 0,i1,2,3.

Observation
Indeed, any optimization problem with linear equality constraints Ax=b
can be transformed into an unconstrained problem!
3/21/2020 @2020 New York University Tandon 213 School of Engineering

Some Terms from Matrix Theory
To generalize, let’s recall the following notions.
The null space of a matrix Amn , with m  n, is: NApn: Ap0.
 
T
The range space of A is defined as:
RAT qn:qAT,forsomem .  
NARA. nT
3/21/2020 @2020 New York University Tandon 214 School of Engineering

Null‐space Matrix Z: AZ=0
A matrix Z nr is a null-space matrix of A if any vector in N ( A) can be expressed as
a linear combination of the columns of Z.
If r  nm, then Z is called a basis matrix for
the null space of A (as the columns of Z are linearly
independent!).
3/21/2020 @2020 New York University Tandon 215 School of Engineering

Representation of the Null Space
Since the null space can be represented as
N(A) p: pZvforsomev ,  r
it follows that
N(A)  R(Z).
3/21/2020 @2020 New York University Tandon 216 School of Engineering

Comment
If Amn is a matrix of full (row) rank m,
then without loss of any generality, we can assume
AB N, Bmm fullrank,Nm(nm). As it can be directly checked,
Z B1Nn(nm). I
 nm
3/21/2020 @2020 New York University Tandon 217 School of Engineering

As a consequence, we have:
If x is any point satisfying Ax  b, then all other points can be written as
x  xZv, forsomevectorv Particular non-homogeneous solution
because x  x  N ( A).
3/21/2020 @2020 New York University Tandon 218 School of Engineering
General homogenous solutions

Optimization with Linear Equality Constraints
min f (x) subjectto Axb

m i nr  ( v )  f ( x  Z v ) . v
The function  is called the reduced function.
3/21/2020 @2020 New York University Tandon 219 School of Engineering

Comment
If Z is a basis matrix for the null space of A, then

is a function of n‐ m variables, i.e., r = n ‐ m. In other words, the transformed unconstrained
problem involves less variables.
3/21/2020 @2020 New York University Tandon 220 School of Engineering

Motivating Example revisited
min f(x)x2 2x x2 x2 4x 11233
subjectto x x 2x 2. 123
1 2 B1N
TakeZ1 0,forAB N 
and x200.
 1112 0 1  I 
   22  T
3/21/2020 @2020 New York University Tandon 221 School of Engineering

3/21/2020
@2020 New York University Tandon 222 School of Engineering
Motivating Example revisited
2 1 2v  xxZv01 01.
as before.
 v2 0 0 1
 
min(v)2v2 3v2 4vv 2v 12121

Optimality Conditions
minf(x) min(v)  f(xZv) subjectto Axb vr

Using the chain rule,
(v)  ZT f (x  Zv)  ZT f (x) 2(v)ZT2 f(xZv)ZZT2 f(x)Z
3/21/2020 @2020 New York University Tandon 223 School of Engineering

Necessary Conditions
Ifx isalocalminimizeroff over x:Axb
*
and Z is a null-space matrix for A, then
 ZTf(x)0. (x:”stationarypoint”) *
 ZT2 f (x )Z is positive semi-definite. *
That is, the reduced gradient is zero and the reduced Hessian matrix is positive semidefinite.
3/21/2020 @2020 New York University Tandon 224 School of Engineering


Comments
•
A point at which the reduced gradient is zero is
•
called a stationary point.
The second‐order condition implies:
3/21/2020
@2020 New York University Tandon 225 School of Engineering
pT2f(x)p0, pN(A). *
However, this condition does not require that 2 f (x ) be positive semidefinite!
*

 Ax b, *
Sufficient Conditions
If x satisfies: *
 ZTf(x)0,and *
 ZT2f(x)Zispositivedefinite, *
where Z n(nm) is a basis matrix for N(A), then, x is a strict local minimizer of
*
fover x:Axb.

3/21/2020 @2020 New York University Tandon 226 School of Engineering

3/21/2020
@2020 New York University Tandon 227 School of Engineering
Motivating Example revisited
min f(x)x2 2x x2 x2 4x 11233
subjectto x x 2x 2. 123
1 2 B1N TakeZ1 0 ,
I 0 1
 
forA B N  1 1 2 . 
N

3/21/2020
@2020 New York University Tandon 228 School of Engineering
T Sincef(x)2x 2, 2x , 2x 4 ,
123
ZTf(x)(0, 0)T atthefeasiblepoint *
x 2.5, 1.5, 1. *
In addition,
ZT2f(x)Z 0 2 01 0
1 1 02 0 01 2 * 201  
 4 4 positivedefinite 4 6
 0 0 20 1   

However, 2 f (x ) is not positive definite!!
*

Lagrange Multipliers
Fact : At a local minimizer x , *
f (x )  AT  **
where*m iscalled”Lagrangemultipliers”.
3/21/2020 @2020 New York University Tandon 229 School of Engineering

Proof
3/21/2020
@2020 New York University Tandon 230 School of Engineering
Let Z be any n  r null-space matrix for A. Then,vr,m s.t.
 Zv 0. *
**
f(x)Zv AT ***
 ZTZv 0, usingZT AT (AZ)T 0 *

3/21/2020
@2020 New York University Tandon 231 School of Engineering
A Geometric Demonstration
aT x  b
x*
f (x ) *
a
f (x)
x
isovalue contours

3/21/2020
@2020 New York University Tandon 232 School of Engineering
Motivating Example revisited
min f(x)x2 2x x2 x2 4x 11233
subjectto x x 2x 2. 123
2x 2  1  1 
2×2 1 usingthe1st-ordern.c. 2x 4 2 
3
and x  x  2x  2 the equality constraint
123
  3, x  2.5, 1.5, 1 .
**

T

Lagrangian Function
For the problem: min f (x), subject to Ax  b, Amn with rank(A)  m,
we can define the Lagrangian function:
L(x,λ)f(x)m aTxbf(x)T(Axb)
note :
aiT stands for the ith row of A.
iii i1
3/21/2020 @2020 New York University Tandon 233 School of Engineering

3/21/2020
@2020 New York University Tandon 234 School of Engineering
First‐Order Optimality Conditions
Lx ,  0, **
because
 L(x, )f(x)A ,
T L(x, )bAx.
x

3/21/2020
@2020 New York University Tandon 235 School of Engineering
A Perturbed Problem
Assumethatf(x )min f(x), subjecttoAxb. *
Then, for the perturbed problem:
f ( x )  min f ( x), subject to Ax  b  .
Indeed, for small ,
f (x)  f x x  x  f (x )
***
T f(x)xx A
***
 f(x )T **
T
T

Exercise
Consider min f(x)x2 x2x2 2x x x4 8x 113 122 2
subjectto: 2x 5x x 3. 123
(a) Which of the following points are stationary: TT
T
(b) local minimizer? local maximizer? saddle point?
(0,0,2) ; 0,0,3 ; 1,0,1 .
3/21/2020 @2020 New York University Tandon 236 School of Engineering

Case 2: Linear Inequality Constraints
Consider the optimization problem:
min f (x)
subjectto Axb, Amn.
3/21/2020 @2020 New York University Tandon 237 School of Engineering

3/21/2020
@2020 New York University Tandon 238 School of Engineering
An Example
min f (x)  1 x2  1 x2 21 22
subjectto x 2x 2 12
x  x  1 12
x 3. 1

x2
x
*
The optimal solution x* reduces to a solution of the equality constrained problem
with the active constraints.
3/21/2020 @2020 New York University Tandon 239 School of Engineering
x1

More specifically,
The minimizer x* for the original problem is the same as the simplified problem:
min1x2 1×2 21 22
24 2
 x* 5, 5,* 50.
subjectto  x2x2.

For this example, x  2x  2 is an active constraint
12 
Note :
at x* , while the other two are inactive.
12
3/21/2020 @2020 New York University Tandon 240 School of Engineering

 m i n f ( x )
subjectto Axb, Amn 
Observations
 m i n f ( x )
subjectto Axb, alltheactiveconstraints
ˆˆ
For the inactive constraints, we associate with zero Lagrange multipliers:
aTxb0, i1,,m. ii*i
3/21/2020 @2020 New York University Tandon 241 School of Engineering

Remark
It may happen that none of the constraints in NL programming are active, i.e., constrained NL programming may be the same as unconstrained. A sharp difference with linear programming!
3/21/2020
@2020 New York University Tandon 242 School of Engineering
22 minf(x)x1 x2
subject to
4x x 0,

12 2x x 0,
12
x  0, x  0.
12
12

3/21/2020
@2020 New York University Tandon 243 School of Engineering
Necessary Conditions
At a local minimizer x , then  s.t. **
 f(x)AT,(or,ZTf(x)0), ***
 * 0,
 T Ax b0, and
**
 ZT 2 f (x )Z is positive semi-definite, *
where Z is a null-space matrix for the matrix
ˆ
A of active constraints at x .
*

Comment 1
ˆ f(x)AT AT()
* * * active
because*i 0foranyinactiveithconstraint.
3/21/2020 @2020 New York University Tandon 244 School of Engineering

Comment 2 (On the sign of Lagrange multipliers for the inequality constraints)
3/21/2020
to guarantee non-existence of such a s. @2020 New York University Tandon
245
By contradiction, find a stepsize s to decrease f at x : *
0 f(x s) f(x )f(x )T s. ***
On the other hand, for the active constraints
ˆˆ
atx , i.e., Ax b0, wewant
**
ˆˆˆˆˆ 0A x s bAx b  As
Equivalently,
**

0
T
{f(x) s0andAs0 f(x)A, 0,
ˆˆ **
School of Engineering

Aˆ s
Clearly, the shaded area is empty only when these two vectors are in the same direction!
3/21/2020 @2020 New York University Tandon 246 School of Engineering
f x  *

3/21/2020
@2020 New York University Tandon 247 School of Engineering
An Example
Check the necessary conditions at x  (1, 0)T *
of the constrained minimization problem: 24
subject to
minx1 1.5 x2 0.5 x
1x x 0, 12
1x x 0, 12
1x x 0, 12
1x x 0. 12