Chapter 13 - Nonlinear

Question 1

Why is there a need for non linear pgoramming?

Answer 1

Because a lot of models dont actually model well with only linear funciton

Question 2

Formally define a non linear progrmaming problem

Answer 2

We want to find x=(x1, x2, …, xn) so as to maximize f(x)

subject to the constriants

gi(x) <= bi, for all i.

and

x >= 0

Question 3

Give the function for profit.

Is it linear?

Answer 3

P(x) = xp(x) - cx

non linear.

Question 4

What would be the objective function for a case where we want to produce different products at different quantities?

Answer 4

We need to sum the different profit functions:

Pj(xj) is the profit of selling xj amount of product j.

f(x) = ∑Pj(xj) [j=1, n]

Question 5

Name some reasons for non linearity

Answer 5

Marginal costs can decrease or increase as production differ. This relationship requires a non linear development.

Learning curve effects resemble the marginal case, and represent non linear relationships.

In essence, every scenario where we dont have the very same price regardless of the number of units we sell, etc. It is about change.

Question 6

Source of non linearity in regards to transportation?

Answer 6

Volume discounts.

Question 7

What happens with CPF solutions in non linear programming?

Answer 7

no longer guaranteed to be CPF. This means that we are not able to use this simplification. Searching in the set of CPF’s is extremely easy compared to the entire other space.

Question 8

Can otpimal solutions to non linear programming problems lie inside of the feasbiel region, and not just on the boundary+

Answer 8

Yes.

Question 9

Elaborate on local vs global maxima

Answer 9

In general, OR algos are not able to distinguish between local maximas and global maximas. Therefore, it is absolutely crucial that we as programmers understand the conditions that can guarantee a global maxima.

Question 10

How can we use calculus to tell whether our function is global or local maxima?

Answer 10

if the double derivative is always smaller than or equal to 0, we know that we have a guaranteed global maxima.

We are talking about concave vs convex functions. Concave functions are always “not smiling”. Convex are smiling.

Question 11

What is the concave “sum” theorem?

Answer 11

The sum of concave functions will always be concave.
This also applies to convex functions.

Question 12

Hva er substitusjonsmetoden?

Answer 12

Når vi har kun en likhetsfunksjon som restriksjon kan vi substituere den inn i målfunksjonen.

max Z = 10x1 - 0.02x1^2 + 12x2 - 0.03x2^2
s.t. 0.2x1 + 0.1x2 = 40

Kan skrive restriksjonen som:

0.2x1 = 40 - 0.1x2
x1 = 200 - 0.5x2

Så setter vi dette inn i målfunksjonen:

Z = 10(200 - 0.5x2) - 0.02(200-0.5x2)^2 + 12x2 - 0.03x2^2

Nå kan vi derivere med hensyn på x2.

∂z/∂x2 = -5 - 0.02(200-0.5X2) + 12….

= 11 - 0.07x2

Setter derivat lik 0.

x2 = 157.14

Vi finner x1 ved å bruke substitusjonen vi brukte tidligere. Finner da at x1 = 121.5.

Da kan vi finne Z, og Z = 2064.78

IMPORTANT: Vi vet ikke hvordan punkt dette egentlig er. Dette må vi finne ut av. Vi trenger andre derivert. Vi sier at vi “kontrollerer om det er maximum eller minimum eller sadelpunkt ved å bruke andrederivert”.

∂2z/∂x2^2 = -0.07, som er strikt negativt, sim betyr at vi har et globalt maximumpunkt. Funksjonen en konkav.

Question 13

Hva definerer en konkav funksjon?

Answer 13

Kurve som har strengt fallende stigningstall.

Question 14

Hva definerer en konveks funksjon?

Answer 14

Kurver som har strengt økende stigningstall.

Question 15

Hva er en konvekskombinasjon?

Answer 15

En konvekskombinasjon er:

x’’’ = lambda x’’ + (1 - lambda)x’, lambda between 1 and 0.

x’’’ er altså mulig alle punkter mellom x’ og x’’, bestemt av hva lambda er.

Question 16

Er en lineær funksjon konveks eller konkav?

Answer 16

Den tiflredstiller begge deler.

Question 17

Hva er kravet for å si at en funksjon kun har ett ekstremalpunkt?

Answer 17

Funksjonen må være strengt konkav eller strengt konveks.

Question 18

Forklar litt om Hessian

Answer 18

Hessian er en matrise med andrederivater. Antallet entries er lik kombinasjoner av andre derivat-variabler. Funksjonen i seg selv er alltid andrederivert. Men variablen(e) vi deriverer med hensyn på, vil variere:

Konveksitetstest for en funksjon med to variabler gjøres med å se på determinanten

Question 19

Hvordan kan vi gjøre konveksitetstest for en funksjon med flere variabler?

Answer 19

Vi finner først Hessian. Deretter bruker vi de to testene:

1) Determinant må være større enn null
2) Hoveddiagonalen i Hessianen har verdier som er kun større enn 0 (konveks) eller kun mindre enn 0 (konkav).

Question 20

Why is non linear programming models difficult?

Answer 20

For one thing, there is no universal algorithm. in the case of LP problems, simplex could solve it all. For non linear programming, different procedures work for different types of problems.

Question 21

Name some classes of non linear problems

Answer 21

Unconstrained optimization: No constraints. The goal is simply to optimize a function. Function can have a single variable, but is typically multivariable. We differentiate and equal to 0 to find this optimal solution.

Linearly constrained optimization: The objective function is non-linear, but the constraints are all linear.

Quadratic programming: Linear constraints, but f(x) MUST be both quadratic AND concave, and we must maximize.

Question 22

What is difficult with unconstrained non linear problems?

Answer 22

First of all, we must understand what a non linear unconstrained problem is. We are basically reducing the equation to solving a set of slightly simpler equations (derivative). However, these solutions may very well be non linear as well. In this case, we can only pray to find an analytical solution.

Question 23

We usually solve unconstrained non linear prblems with ∂f/∂x = 0. Are there any cases where this is not the case?

Answer 23

Consider the case where the variable have a non-negativity constraint. This means that we are in the upper right or lower right quadrant.
IF the function is such that its maximum point is at the very beginning (x=0), then we obviously wont find derivative equal to 0. If the function is concave, meaning the slope will be strictly decreasing, the maximized point is at the very beginning, where x=0. However, to find it we have to accept ∂f/∂x <= 0

Question 24

If we have an unconstrained non linear problem, what is the necessary and sufficient condition for a particular solution x=x’ to be optimal, when the function is concave?

Answer 24

∂f/∂x = 0, at x=x’.

Note that a numerical solution may be required.

Question 25

When is a function convex?

Answer 25

A function is convex if its second derivative is positive for all values of X.

Question 26

What is the difference between convex and strictly convex?

Answer 26

Convex requires that the second derivative is greater than, or equal to, 0 for all values of X.

Strictly convex requires that the second derivative is greater than 0 for all values of X.

Question 27

When is a function concave?

Answer 27

A function is concave if the second derivative is smaller than or equal to 0 for all values of x.

A function is called “strictly concave” if its second derivative is smaller than 0 for all x.

Question 28

in a non-linear problem, will the optimal point be on the boundary?

Answer 28

No, not necessarily. It may, but it is probably more likely to not be there.

Question 29

Hvorfor er vi så opptatte av konvekse problemer?

Answer 29

et konvekst problem har egenskapen at alle lokale optimal også er globale optimale.

Question 30

Forklar faenskapet med x-hatt og det der

Answer 30

Vi definerer x-hatt = lambda x’’ + (1 - lambda)x’

Det dette betyr er at vi definerer variabelen x-hatt til å kunne være hvilket som helst punkt mellom x’ og x’’. Ved å variere lambda mellom 0 og 1 tillates dette. Lambda vil fungere som en prosentvis greie også. Dersom lambda er 0.5 vil vi være nøyaktig midt mellom puntkene osv.

Denne dritten bruker vi for å teste enkel konveksitet. Dersom vi ser for oss en funksjon, f(x): Dersom f(x-hatt) alltid ligger under “en rett linje mellom x’ og x’’”, så er f(x) konveks.

Matematisk:

f(lambda x’’ + (1-lambda)x’) <= lambda f(x’’) + (1-lambda) f(x’)

LHS er korrsponderende til x-hatt, bare f(x-hatt).
RHS er korresponderende til y-verdien, eller f(x) verdien, til den rette linjen.

Dermed kan vi bruke dette resultatet for en enkel konveksitetstest i 2D. Vi kan derfor også justere for konkavitet.

Question 31

Hva kan vi si om Hessian?

Answer 31

Symmetrisk matrise bestående av andrederiverte.

Siden Hessianen består av andre-deriverte, så kan vi bruke den for å finne konveksitet. Kravet da er at alle entries langs diagonalen må være større enn, eller lik 0. Dette gir mening, dersom vi ser for oss tilfellet med kun en variabel. Andre derivert som er positiv gir en smilende uderivert. Dermed konveks.

Question 32

Forklar om Hessian konveksitetstest i forhold til determinanter og egenverdier

Answer 32

Vi kan finne konveksitet ved å bruke determinant til H og til submatriser dersom større enn 2x2. MEN, dette er ikke veldig skalerbart. Derfor brukes ofte egenverdier i større matriser.

Vi må selvfølgelig også sjekke diagonal-entriene for større enn, eller lik, 0 for å være konveks.

Question 33

Relationship between eigenvalues and determinants?

Answer 33

THe product of all eigenvalues is equal to the determinant of the matrix.

Question 34

Why is the convexity test different between 2x2 and nxn cases?

Answer 34

In the 2x2 case, assessing the convexity of a function through its Hessian matrix can effectively be done by examining the determinant. The determinant of a 2x2 matrix is equal to the product of its eigenvalues. Given that a 2x2 matrix has exactly two eigenvalues, the condition for convexity (which requires non-negative eigenvalues) or concavity (which requires non-positive eigenvalues) can indeed be inferred from the determinant. For convexity, both eigenvalues should be non-negative, leading to a non-negative determinant. For concavity, both eigenvalues should be non-positive, which also results in a non-negative determinant since the product of two negative numbers is positive. Thus, a non-negative determinant indicates that the eigenvalues are either both non-negative or both non-positive, suggesting the function is either convex or concave, respectively. To determine which one specifically, we must look beyond the determinant.

This method, however, does not extend directly to larger matrices because the relationship between the determinant and the signs of the eigenvalues becomes more complex with more than two eigenvalues. The determinant being positive in larger matrices does not exclusively indicate that all eigenvalues are of the same sign due to the potential for an even number of negative eigenvalues to multiply to a positive product. Thus, for matrices larger than 2x2, more detailed analysis of the Hessian’s eigenvalues or its leading principal minors is necessary to ascertain convexity or concavity.

Question 35

What exactly is the lagrange method

Answer 35

We solve a system of equations where we include the constraints. This way, we force the value of the equality constraints.

Also, the equations we use in the system ensure optimality because of differentiation.

Question 36

What is the requirements of using KKT conditions?

Answer 36

Convex problem.

We achieve a convex problem by maximizing a concave function subject to convex constraints, OR minimizing a convex function subject to concave constraints.

Recall that a convex feasible region is one where we can draw a line between any two points in the region, and all points on the line will be inside the region.

Question 37

what determines the sign of the lambda (whether we add or subtract the lambda term) when using lagrange?

Answer 37

Max problems have negative. Min have positive.

Question 38

Why does the lagrange method with inequalities only work for convex problems?

Answer 38

Yes, your explanation captures a key reason why the method works reliably for convex problems and not always for non-convex problems. In convex optimization problems, because there is only one global maximum (for a concave objective function) or one global minimum (for a convex objective function), and the feasible region defined by convex constraints is also convex, the first solution you find that satisfies the constraints (whether it’s from directly solving the unconstrained problem or by adjusting for active constraints) is indeed the global optimum. This is due to the properties of convex functions and convex sets, where local optima are also global optima.

In contrast, non-convex problems can have multiple local optima. If you find a solution that satisfies the constraints, you cannot be sure it’s the best possible solution without exploring other potential optima. This complexity arises because moving slightly from one point does not guarantee proximity to the global optimum due to the presence of multiple local optima.