So welcome to the lecture series on nonlinear programming, so what nonlinear programmings are

and why they are important this we will see in this course. You see that whenever they solve

any engineering or science problem we frequently encounter various optimization problems which

may be nonlinear in nature. So in this course we will see that what basically nonlinear problems

are and how to solve such problems okay. So the first lecture is on convex sets and

functions, now first what is OR, nonlinear programming is a part of operation research,

so what is the work first we will see this. OR or operation research is a scientific method

of providing executive department with a quantitative basis for decisions regarding

the operations under their control or by Wikipedia it is a discipline that deals

with the application of advance analytical methods to help make better decisions. So

OR is the basically part of the mathematics due by which we can take better decisions.

Now what is an optimization problem you see that in optimization problem they have two components

an objective function, a function which we have to maximize or minimize subject to some

constrains which we saw which say constrain set. So like here we have a problem P which

is minimization type minimization of f(x) subject to conditions are X belongs to C.

Where f the function from Rn to R and C is the subset of Rn, now this problem we are calling

this problem as an optimization problem because here we have to minimize a function f okay,

subject to conditions that, x belongs to some set C. So this function f here which we have to

minimize is called objective function and the set C is called set of constrains or constrain

set. Now this problem is also called basic mathematical programming problem okay.

The function f is called objective function and a set C is called the constrain set or the feasible

set. Now nay point x bar which belongs to C, C means that constrains set which belongs to

C we are calling that point as feasible point or feasible solution okay. And that collection of all

the feasible solution we are calling a feasible set or C. if C = phi, phi means C is empty though

then the problem is called infeasible, infeasible means no solution problem has no solution okay.

Now if C = Rn suppose C is the entire n dimension Euclidian space C = Rn then the problem P is

called unconstrained optimization problem there is no constrain that is we have to minimize this

function or whole Rn okay, otherwise we call it constraint optimization problem if C is a

proper subset of Rn then we call this problem as constrained optimization problem. Now let us

consider this problem. What this problem is this problem is minimize f(x) subject to gjx less than

equal to 0 and j = 1,2, ....m okay. Now here in this problem this function f is to minimize,

so this function we are calling as objective function and what are the constrains gj less

than equal to 0 are the constrains. How many constrains, m number of constrain so here we

have to minimize this function f subject to m number of constrains which is gj less than equal

to 0 okay. Now this optimization problem can be broadly classified in to two categories.

First is linear programming problems and second is nonlinear programming problems what are linear

programming problems if objective function the function which we have to minimize or maximize

is linear okay and all constrains are linear so such problem are called linear programming

problems. And otherwise we call it non linear programming problem so this is in this slide

if objective function and all the constrain gj are linear then the problem MP is called linear

programming problem which mathematically can be express in this form and if MP is not linear then

we call as non linear programming problems. Like example of LLP is something suppose we have

to minimize this function minimize z = say 2x1 + 3x2 - x3 subject to suppose it is 3x1 + 2x2 + x3

less than equal to 4 and x1 - x2 + 4x3 greater than equal to 2 and x1, x2, x3 non negative

so this is the LPP, this is basically a linear programming problem okay. Now in this LPP this can

be rewritten as 2 3 -1 and this can be written as x1 x2 x3 this constrains can be written as 3 2 1,

this can be written is 1 -1 4 and it is x1 x2 x3 it is one is less than, other is greater.

So you first multiply this by -1 okay to make it less than equal to so all those constrains

all the sign will change and it is less than equal to 4 -1 and x1 x2 x3 non negative.

So basically in this formulation if we compare with this formulation though this is CT, and

this is x this is a matrix A of orders 2x3 this is x less than equal to b this is a vector b and this

x greater than equal to 0 okay. So we can always express any linear programming problem in this

way that is minimizing CT x subject to x less than equal to P and x greater than equal to 0 okay.

Now if any with the objective function or any at least one of the constraints is non linear then

such problems are called non linear programming problems. Now there is a particular case of non

linear programming problem which is quadratic programming problem if the objective function

that is f(x) is of degree 2 that is quadratic and all constrains are linear then such problems

are called quadratic programming problems. We will discuss about quadratic programming

problems in further lectures. So next is convex set. Now a set S is called convex

if the line segment joining any two points of S is in S, so first what does it mean.

Suppose we have two points x1 and x2, so this is the line segment joining x1 x2. Now you take

any arbitrary point x in between x1 x2 suppose this point divide this line segment in the ratio

suppose 1 - lambda and lambda, now you want this point x in between x1 x2 therefore these ratios,

1- lambda and lambda must be non negative that means lambda should lying between 1 and 0 okay.

So now what will be x, so x will be nothing but lambda x1 + 1 - lambda x2 so this will be x.

Now for a convex set suppose we have region inside the circle we take any two arbitrary point in this

set suppose these are two arbitrary points, the line segment joining these two point must be

inside the set that means take any arbitrary point on the line segment joining these two

point for any lambda between 0 and 1 the point x which is lambdax1 + 1 - lambda x2 must be in S,

you take any two point here you take two point here join the line segment the line

segment must be in this set itself you take two point here join the line segment .

The line segment joining these two points must be inside the region, you take any two point here,

so line segment joining these two points must be inside the region that means for all x1 x2

and S and lambda between 0 and 1 the lambda x1 + 1 - lambda x2 must be in S, for all x1, x2 in

S okay. So if this result hold for all x1, x2 be in S, lambda between 0 and 1 this means the set is

convex okay. Now this sometimes we call it convex linear combination of x1 and x2, so sometimes we

call it convex linear combination of x1 and x2. So we can also define convex set like this,

it take any two arbitrary point in S the convex linear combination of points must be less. If this

property holds then we see the set is convex like we have two pictures here in the first picture

if you take any two arbitrary points in the S and join the line segment the line segment is totally

contained in the green portion of the set okay. Now if you take this second example, in a second

example if you take these two points x and y the line segment joining these two point is not

totally inside the set so this is not convex okay. Now we have some properties of convex

set the first property is intersection of any collection of convex sets is always convex.

The proof is very simple let us see. So we have to showed that the intersection of any collection of

convex set. So this we have to show this to prove okay and it is given to us that all Ci are convex

so whenever we have to show set of convex take any two arbitrary point in that set and try to show

that the convex linear combination of those two points is in S okay, and suppose you want to show

the set is not convex so try to show a counter example try to show that there are some point,

there exist the point x1 x2 and some lambda between 0 and 1 such that the convex linear

combination of those two point is not in S. So that means S is not convex okay, so here we

have to show that this is convex so take any two arbitrary point in this set okay,

now this implies x1, x2 belongs to Ci for All i okay and now you take x as convex

linear combination of these two points for lambda between 0 and 1, and since Ci for all i is are

convex. So this implies x belongs to Ci for all I, because Ci is convex for all i and x is nothing

but convex linear combination of x1, x2. So this x will be in Ci for all i and if it

is in Ci for all i this means x will be in intersection also. So that means this

intersection of Ci is a convex set because what we have shown that the convex linear combination

of any two arbitrary point of the set is in S is in the set. So that mean a set is convex okay.

Now the second property is the vector sum C1 + C2 of two convex set C1 and C2 is also convex.

So the proof is again simple let us see. So you take any two arbitrary point say x1

and x2 in C1 + C2, so we have to show that this set is convex so we have to prove that

the convex linear combination of x1 and x2 is in C1 + C2. So let this holds this

implies since x1 is in C1 + C2 this means there exists some x1' and x1'' in C1 and x2' and x2''

in C2 such that x1 will be equals to x1' + x2' and x2 will be equal to x1'' + x2'' okay.

Because these are in C1+ C2, so that means x1 can be expressed as some element of C1+

some element of C2 similarly for x2. Now you take convex linear combination of these two

points for lambda between 0 and 1 so this is nothing but lambda (x1' + x2') + (1 - lambda)

(x1''+x2'') = (lambda x1' + 1-lambda x1'') + (lambda x2' + 1 - lambda x2''). Now this element

is a convex linear combination of two points in C1 and it is given to a C1 is the convex set.

So this will belongs to C1 again this x2' and x2'' are in C2 and C2 is the convex set so this point

will be in C2, so this point is in C1 this point is in C2 so this will belong to C1+ C2. So that

means this x belongs to C1 + C2 and x is nothing but convex linear combination of these two points,

so this implies C1 + C2 is are convex set oaky is a convex set. So in this way we can show that

sum of two convex set is also convex. Now in the next is, the third property

that alpha times C is also convex for any convex set C and for S for a scalar alpha,

so this also can be prove very easily. You take two arbitrary points in alpha C.

Let x1 and x2 belongs to alpha times C this implies there exist some x1' and x2' such

that x1 = alpha x1' and x2 = alphax2', now take convex linear combination of these two points,

will lambda belongs to 0 and 1 okay, take convex linear combination of these two points and we have

to show that this x belongs to alpha times C okay. Now this is nothing but alpha times alpha x1' + 1

- lambda alpha x2' and this is alpha times lambda x1' + 1 - lambda x2' and this belongs to alpha C.

Why this belongs to alpha C because these are the point say in C these are the points belongs

to C okay, and C is the convex set so this belongs C. So alpha times C that means alpha

C is also a convex set okay. So now we have convex function, what convex functions are?

So let us be a subset of Rn be a convex set okay and a function f from S to R is set to be convex

over S if this condition hold for all x1, x2 to be in S lambda between 0 and 1 okay. So what does it

means let us see, so this definition means. f (lambda x1 + 1 - lambda x2) less than equal

to lambda f (x1 + 1 - lambda f x2) and for all x1, x2 in S and lambda between 0 and 1 okay.

So here S is the convex set okay, so if convex linear combination of any two point of S less

than equal to lambda fx1 + 1 - lambda fx2 then we say that the function f is a convex function. So

what is the geometrical interpretation of this definition let us see okay.

Let us see the geometrical inter protection of this definition, now suppose we have a function

of this type okay suppose this is the point x1 and this is some point x2 okay any arbitrary point

this is s okay suppose this is S. Now this point this is the function y = fx so this point will be

nothing but x1, fx1 and this point is nothing but x2, fx2. Now join the cord of joining these two

points now take any x in between x1 and x2 that is this x is the convex linear combination of these

two points. So this will be nothing but lambda x1 + 1- lambda x2 for lambda between 0 and 1.

So this ratio will be nothing but 1 - lambda and lambda, now you join this cord here so this

point will be nothing but x, fx okay, what is fx, f(lambdax1 + 1 - lambda x2) and what this point

will be the ratio will be here 1 - lambda/lambda because these three lines are parallel,

so whatever ratio we are having here the same ratio will be here. So what will be the quadrate

of this point? This point will be nothing but x, and x, it is lambda fx1 + 1 - lambda fx2.

So if we are calling as point A it is B it is C, so AC is AB is always less than equal to AC

clear because this height is less than equal to this height and this is nothing but f so f(x)

less than equal to and Ac is nothing but this height which is lambda fx1 + lambda fx2 this

height. So it is lambda fx1 + 1- lambda fx2, and what is x, x is lambda x1 + 1 - lambda x2,

so this height is always less than equal to this height so what is it mean? That if a function is

convex then you take any two arbitrary points on the curve join the cord the cord joining those two

point always lies above or on the curve okay. That means suppose we have this function suppose

you have to fx = x2 okay, f is from R to R okay. f is from R to R and f = x2,

now what is the graph of this function graph is something like this okay. Now you take any two

arbitrary points on the curve any two arbitrary point, join the cord the cord joining these two

points always lies above the curve okay you take two arbitrary points here join the cord

the cord joining those two point always lies above the curve you take two points here.

So if it is the function is convex so we can say that is the function x2 is a convex function okay,

now you take a function like this. suppose you take a function like this a boat shape

function you take two arbitrary points here join the cord the cord joining those

two point always lies above the curve you take two points here join the cord the cord joining

these two points lies above the curve. Now you take two points here the cord joining

these two points lies on the curve then the cord joining these two points any two points

on this curve either lies above the curve or on the curve, so this means there the function is

a convex function. Now if the inequalities reversed if these inequalities is reversed,

that is we have greater than equal to, then the function is called concave function that means a

function is concave a function is concave. If and only if negative of f is convex okay,

so how we can interpret geometrically for a concave function we can say that take

any two arbitrary point on the curve join the cord the cord joining those two points always

lies below or on the curve that means this is the geometrical interpretation of the concave function

on the similar lines, there are some examples. x2 is a convex function which we are already seen

this is x2 is a convex function because if you take any two arbitrary point join the cord the

cord joining these two point always lies above or on the curve, mode x, mode x is also convex

function because when you plot mode x, so mode x is something like this you take any two arbitrary

point on the curve the cord joining those two points always lies above the curve okay.

You take two points here it is one the curve, though the cord joining any two points on the

lies either lies above the curve or on the curve so that means it is a convex

function. ex is again a convex function that you can easily see graphically.

If you draw the graph of ex so this is ex, so when you take any two arbitrary point on

the curve the cord joining those two points always lies above the curve okay. If it is a

line segment joining those two points lies above the curve so that means it is a convex function,

negative x2 is of course concave function because it is negative which is x2 is convex,

ln x is also a concave function we can easily see graphically, if you draw the graph of ln x.

Ln x is something like this when you draw the graph of ln x; ln x is something like this

okay. This is one something like this so when you take ant two point the cord join those two

points' lies below the curve so it is a concave function. Now linear function 2x + 3 is both

convex and concave we can easily see because equality holds and the function x3 is neither

convex nor concave okay that we can visualized geometrically also. Suppose I have sin x.

Sin x is something like this okay, now when you take two points here so the cord joining these

two points lies below the curve and here it is above the curve so it the neither convex nor

concave because in some portion the cord is below the curve and some portion the cord is above the

curve so the such functions are neither convex nor concave okay. What convex set and convex functions

are that we have seen in this lecture that we will discuss in the next lectures. Thank you.