Non Linear Programming, KKT, Quadratric

Question 1

NonLinear Programming

Answer 1

if the objective function or/and the constraints are non linear
-> no corner point, solution might not be at the boundary of the feasible region

We need convexity to solve it !
Convex constraints -> describes a convex feasible region (intersection will always be convex: convex set)
Objective function: Max Concave or Min Convex

Local optima guaranteed to be global optima then :)

Question 2

Convex / Concave

Answer 2

Concave: bends down, f’’ <= 0 (strict if = 0 (strict if >)
Line segment will be on or over it. Convex set: pair of point will have line segment inside.

The negation of a concave is convex!

Use convexity test (formula provided at the exam for 2 variables) to verify that objective function is max concave and the constraints are convex

Question 3

Convexity test

Answer 3

Need to do the partial derivatives (1st and 2nd)
Dont forget to check the 3 formula that conditions if its is concave or convex

if one variable, check the f’’ if > or < 0.
if linear -> convex and concave

Question 4

Necessary condition for a global optima

Answer 4

The first derivative = 0
Second derivative (-) -> max, (+) -> min

In the case of convex/concave this condition is necessary AND sufficient for optimality

To find global optima can thus solve the first derivative. Analytical is hard thus numerical better:
Bissection method for 1 variable
Gradient search for 2 variables
2 methods for unconstrained problems !

Question 5

Bissection method

Answer 5

To find f’ = 0

1) take f’
2) find 1 point such that f’ (-), and 1 point such that f’(+)
3) take p = p1+p2/2, if f(p) (-) then this becomes new (-) point if (+) then this becomes new (+)
4) continue until close to 0 difference of p1 and p2

Question 6

Gradient search

Answer 6

to find f’=0 with variable x1 and x2

1) Do the partial derivative of x1 and x2, put it in hessian vector H
2) initialize at eg 0,0, this is our p, compute H at this point, this gives us h
3) t is a scalar. do p + t*h = p’, do f(p’) then with the derivative of t solve t.
4) replace t in p’ and repeat process with this new point

Question 7

KKT

Answer 7

conditions for constrained problems
Necessary set of conditions for an optimal
if Convex program it is sufficient.
Can be used to find an optimal by finding x and u that satisfy the conditions

1) Check if Max concave (if not Max change it to max !) and constraints convex
2) use the KKT formula, gi are the constraints and we ui for each constraints
3) do the first and second partial derivatives of x1 and x2 + the derivative of x1x2

Question 8

Quadratic Programming + Modified Simplex Method

Answer 8

Subset of Nonlinear programming
solvable if Max concave and constraints convex
check for this !
KKT could be used to find an optimal solution

1) Write the KKT conditions
2) rewrite the conditions for LP (move independent numbers to RHS):
- make the conditions as = : add slack y for constraints with x, add slack v for constraints with u
- add conditions xy= 0 and uv = 0. Makes sure only 1 can be non zero such that they are complementary variables -> complementary constraint x1y1 + x2y2 + .. +u1v1 = 0
- if RHS is negative, multiply by -1 constraints (when it is of the form =, the slack will be thus negative)
3) add artificial variables z for the constrains x
- Two phase Method: Min sum Z then modify to Max
Artificial variables z and slack v start in base.
Eliminate z in top row such that they have identify columns
Entering variable: most negative top row /!\ entering variable cannot be complementary -> xi and yi cannot be there at the same time, ui and vi cannot be there at the same time (this restricted entry rule is the reason why we don’t expliclty need the complementary constraint)
Leaving variable: min ratio test (pos RHS divided by coef table)
Make identity column appear for new entering variable
Repeat until no more (-) in top row
This gives initial BFS

Then do simplex with the final table but put the normal Z objective and drop the columns of the artificial variables. Then do the gaussian elimination to have identity columns reappear for the basic variables

Question 9

Factor equation of d > 2

Answer 9

divide the factors of the constant term by the factors of the coef of the highest degrees. All these are our x to test for (do + and -)

Lets say we try with 2

Then do table, top row is the coef of the equation you want to factor. Bring down the first term, multiply this by 2 then sum this from the next coef, again multiply this sum by 2 and then sum it to next coef. Repeat until reaching the end. If the end is 0, this is a factor.

Do (x-2)(use the coef of the bottom of the table)