11 3 Convex and concave functions A function f(Xu X,,.X,)is a convex function on a convex set s if for any x'es and xn∈S fICX'(l-c)xn]s cf(x+( l-cf(x n holds for0<C≤1 on a convex set s if for any X e s and xn sc on ■ A function f(X1X2…,xXn) is a concave functi f[cx+(1-c)×]≥cf(x^)+(1-c)f(x) holds for0<C≤1
11 11.3 Convex and Concave Functions ◼ A function f(x1 , x2 ,…,xn) is a convex function on a convex set S if for any x’ s and x n s f [cx’+(1- c)xn] ≤ cf(x’)+(1-c)f(xn) holds for 0 ≤ c ≤ 1. ◼ A function f(x1 , x2 ,…,xn) is a concave function on a convex set S if for any x’ s and x n s f [cx’+(1- c)x n] ≥ cf(x’)+(1-c)f(x n) holds for 0 ≤ c ≤ 1
Theorems -Consider a general NLP a Suppose the feasible region S for nlp is a convex set. If f(x)is concave on S, then any local maximum (minimum) for the nlp is an optimal solution to the NLP a Suppose fn(x)exists for all x in a convex set s. then f(x) is a convex(concave)function of s if and only if P(x)≥0[P(x)≤0] for allx in s 日 Suppose f(X1,X2灬…,Xn) has continuous second- order partial derivatives for each point x=(Xl X2/n/es Then f(x1 X2. Xn is a convex function on S if and only if for each X e S, all principal minors of H are non-negative. 12
12 ◼ Theorems - Consider a general NLP. Suppose the feasible region S for NLP is a convex set. If f(x) is concave on S, then any local maximum (minimum) for the NLP is an optimal solution to the NLP. Suppose f n(x) exists for all x in a convex set S. Then f(x) is a convex (concave) function of S if and only if f n(x) ≥ 0[f n(x) ≤ 0] for all x in S. Suppose f(x1 , x2 ,…, xn) has continuous second-order partial derivatives for each point x=(x1 , x2 ,…, xn) S. Then f(x1 , x2 ,…, xn) is a convex function on S if and only if for each x S, all principal minors of H are non-negative
a Suppose f(Xi x2r Xn has continuous second-order partial derivatives for each point x= Xi, X2.DES. Then f(X1×2…Xn) is a concave function on s if and only if for eachⅹ∈ s and k=1 2.n all nonzero principal minors have the same sign as(-1 k the Hessian of f(Xu X is the n matrix whose ijth entry is 0f Oxax An ith principal minor of an n x n matrix is the determinant of any i x i matrix obtained by deleting n-i rows and the corresponding n columns of the matrix
13 Suppose f(x1 , x2 ,…, xn) has continuous second-order partial derivatives for each point x=(x1 , x2 ,…, xn) S. Then f(x1 , x2 ,…, xn) is a concave function on S if and only if for each x S and k=1, 2,…n, all nonzero principal minors have the same sign as (-1)k . ◼ The Hessian of f(x1 , x2 ,…, xn) is the n x n matrix whose ijth entry is ◼ An ith principal minor of an n x n matrix is the determinant of any i x i matrix obtained by deleting n – i rows and the corresponding n – i columns of the matrix. i j x x f 2
The kth leading principal minor of an nx n matrix is the determinant of thekx k matrix obtained by deleting the last n-k rose and columns of the matrix 14
14 ◼ The kth leading principal minor of an n x n matrix is the determinant of the k x k matrix obtained by deleting the last n-k rose and columns of the matrix