Chapter 13 - Nonlinear BOOK

Question 1

Formally define the non linear programming problem

Answer 1

We use something like the standard form here.

We want to find x = (x1, x2, …, xn) such that we

max f(x)

subject to

gi(x) <= bi, for i=1,..,m

and

x>= 0

So, we do a couple of changes relative to the linear programming problem:
1) We refer to the objective function as f(x), indicating that we are essentially using any type of function here. This stands in contrast with the linear programming objective function, that is explicitly given as a sum of products, making it linear.

2) The same argument/point with the constraints.

Question 2

Why is non linear programming a particularily large subject?

Answer 2

It is large because there are a huge variety of classes of functions we can look at. We have some methods that work very well on some problems, and not at all on others etc.

Question 3

Define a convex function of a single variable

Answer 3

A function of a single variable is said to be convex if the following applies:

For each pair of values, x’ and x’’, such that x’ < x’’, we have that:

f[λx’’ + (1 - λ)x’] <= λf(x’’) + (1-λ)f(x’)

.. for all values of lamda between 0 and 1.
We furhter say that the function is strictly convex if we can replace ‘<=’ with ‘<’.

So, what is this saying?

The LHS takes the function value of the sum of lambda times the x’’ and (1-lambda) times x’. In this case, lambda is sort of like a weight. If lambda is 0.25, it means that we are at 25% of the distance between x’ and x’’. So, when LHS take this as the function parameter/argument, the argument becomes the x-value of 25% between x’ and x’’. Therefore, the f(x) gives the y-value corresponding to this specific point.

The RHS does the same, but with y-value. RHS follow straight line, LHS follow the non-linear path.
IF the non-linear path is below the straight line at all value sof lambda and any pair of x’ and x’’, then we have a convex function.

IT IS ALSO WORTH NOTING that if we flip the inequality from <= to >=, we basically do the concavity test instead of convexity.

Question 4

What is the formal mathematical definition/requirement of convexity?

Answer 4

A function is convex if and only if the second derivative is always greater than 0.
NB: This is single variable.

Question 5

What is the formal mathematical definition/requirement of convexity when the function is of many variables?

Answer 5

We say the function is convex if its Hessian is positive semi-definite for all possible values of x1, x2, …, xn

Question 6

What is the “negative” property of convex/concave functions?

Answer 6

If we have a convex function f(x1,x2,..,xn), then g= -f(x1,x2,…,xn) is CONCAVE and vice versa.

Question 7

What is the sum property of convex/concave functions?

Answer 7

A sum of convex functions is convex. A sum of concave functions is also concave.

Question 8

Define a convex set

Answer 8

Say we have a convex function. Then the collection of points lying ABOVE and ON the graph of the convex function, is said to be a convex set.

We can also get a convex set from a concave function:
If we have a concave function, then the collection of points lying BELOW and ON the graph of the concave function, is said to be a convex set.

Question 9

What is an important property of convex sets?

Answer 9

For any collection of convex sets, the collection of points lying in ALL (/both) sets are convex in both, i.e. the intersection of the convex sets, is a convex set in itself.

the image illustrate this property. Notice how the third graph(s) is the intersection set.

Question 10

Formally define the convex set

Answer 10

A convex set is a collection of points such that, for each pair of points in the set, a straight line connecting the pair of points is also in the collection.

Question 11

Will the solution for non linear programming problems be CPF solutions?

Answer 11

Not necessarily. There exists constraints and objectiuve functions that will give this, but generally they do not.

Question 12

If we have a linear objective function and non-linear constraint(s), what do we get graphiucally?

Answer 12

We get a straight line as the objectiuve function. This line will be pushed as far out the feasible region as possible. the feasible region will be given as some curves instead of lines.

Question 13

What is required for a problem to be considered convex?

Answer 13

Depends on whether it is maximization or minimizaiton.

If MAX: We need a concave objective function f(x), and every gi(x)<=bi must be convex.

if MIN, we the objective function is also convex.

Question 14

Why do we require gi(x)<= bi to be convex?

Answer 14

Because the region defined by being below the function gi(x) will be convex. Thus, the feasible region becomes convex.

Question 15

Why do we need convex problems?

Answer 15

The property of convex problems is that they guarantee that any local optimum is actually a global optimum.

Question 16

what is the relationship between integers and convexity?

Answer 16

Ax <= b can never be convex.

But the LP relaxation konvex.

Question 17

Name important properties of the Hessian

Answer 17

The hessian matrix is a square matrix that is also symmetric if all second derivatives are continuous. it is symmetric according to the symmetry of second derivates.

If all eigenvalues in the Hessian is non-negative, we have a positive semidefinite matrix, which results in convex function.

Question 18

Name an important property of functions and concavity/convexity

Answer 18

If a function is a sum of smaller functions, and each of the smaller functions are ALL convex, or all concave, then the total overall function will be the same.

The important application of this is that we can use the 2x2 test, rather then more complicated ones.

Question 19

Say we have no constraints. What can guarantee that a local optimum is a global optimum?

Answer 19

If the objective function is concave, it will have a local/global maximum.

If the objective function is convex, it will have a local/global minimum.

Question 20

If we have constraints, what is required for local/global optimum?

Answer 20

We need ot use the requirement regarding hte objective function, and we NEED the feasible region to be convex set.

Question 21

Why do we need convex sets to guarantee the shit?

Answer 21

It lies in the definition of hte convex set: Any pair of points inside the set have a line segment connecting them, such that the entire line is always inside of the set.
Consider what happens if this is not the case. We will likely get 2 or more points that represent local optimums. However, we cannot tell whether they are local or global. We would ahve to manually check all candidates.

Question 22

What is perhaps the biggest downside of nonlinear programming compared to linear programming?

Answer 22

We now have to consider every damn possible solution. With LP, we are actually only looking at CPF solutions, which is a heavily reduced set of solutions. With non linear problems, we dont have this luxury.

We can also add the fact that we have local optimums that are not necessarily global optimums. this is a problem because optimization methods are generally not able to distinguish between local and global optimums, except for finding better ones (comparisons). THEREFORE, we need to spend considerable time and effort into figuring out specific contexts in which we can guarantee that some local optimum is also a global optimum.

Question 23

How can we determine whether a funciton of many variables is convex or concave?

Answer 23

When the function consists of a sum of smaller individual functions, each of max 2 variables each, then if all the individual functions are concave, the entire shit is concave. IF all are convex, the entire shit is convex.

To check the smaller ones, we can use the same test we would use for two variables, as given in the appendix.

Question 24

Quickly define a convex set

Answer 24

A convex set is a set where ANY pair of points within the set can be connected by a line, and all points on that line will also lie inside of the set.