Theorems TMA 947 - association

Question 1

Separation Theorem

Answer 1

Suppose: set c, point y. Then there exists vector Pi and alfa, for all x

Question 2

Farkas’ Lemma

Answer 2

Consider the two systems. Exactly one is feasible, other inconsistent

Question 3

Characterization of convex functions in C1

Answer 3

If f is member of C1, then derivative def and gradient diff hold

Question 4

The Fundamental Theorem of global optimality

Answer 4

Consider unconstrained problem, is S and f {S} loc min —> also global

Question 5

Necessary optimality conditions, C1 case

Answer 5

Definera ett set, en funktion runt en punkt och visa om vi har ett loc min så håller p-dir och (x-x^*)

Question 6

Necessary and sufficient global optimality con- ditions

Answer 6

Suppose set S, let f map f -> R and member of C1.
Then logical eq. holds for x* global min & gradient*diff is semi pos definite

Question 7

Karush–Kuhn–Tucker necessary conditions

Answer 7

Given x* belonging to S fulfills abadies. If x* is loc min of f over S –> there exists a my belonging to R^m, such that the KKT cond. hold

List conditions.

Question 8

Sufficiency of the Karush–Kuhn–Tucker condi- tions for convex problems

Answer 8

Assume unconstrained prob, w/ feasible set S (gi, hj), convex problem.
Further x* satisfies KKT conditions —> global opt of problem.

Question 9

Relaxation theorem (RIOr)

Answer 9

Given problem f-inf, f -> R and S subset R —> define relaxation to this prob.
Relaxed fR, again fR -> R, with properties that fR < f and S c Sr .
RIOr

Question 10

Weak Duality Theorem

Answer 10

Consider the two problems, f:= inf, st. x in X, gi<=0, & [f->R, gi->R, X subset R^n, F not +/- infintiy],
the dual version of the same prob, q(my) = inf L(x,my) L dual func.
Let x, my be feasible in each respectivly, the q(my) <= f(x), q < f*

Question 11

Global optimality conditions in the absence of a duality gap

Answer 11

The vector (x, my) is pair of primal opt sol. and lang. multipl. vector IFF
Df, Lo[x* belongs arg min L(x, my) ], Pf, Cs [MYi (x) = 0]

Question 12

Existence and properties of optimal solutions

Answer 12

Let P:={Ax=b, x >= 0^n} & V:= {sequence Vk} —> set of extreme points of P
and C:={Ax=0^m, x >= 0^n} & D:= {sequence Dr} —> set of extreme directions of C

Consider the LP (min z= c^t * x,
st. x belongs to P) then—>
a) log. equivalence LP has finite opt sol [IFF] P is non-empty and c^t*d^j >= 0 , for all d^j belonging to D. AND
b) If LP prob has finite opt sol. the there exists [–>] an opt sol. among the extreme points in V.

Question 13

Finiteness of the Simplex method

Answer 13

If all BFS are non-degenerate,
then simplex algorimth terminates after a finite numer of iterations.

Question 14

Strong Duality Theorem

Answer 14

Consider LP (P), and its dual LP (D), where A, B and C belong to different dimensions.

Question 15

Complementary Slackness Theorem (I)

Answer 15

Let x be feasible sol to P and y feasible sol to D.
Then logical equlity holds that Xj (Cj - A^tj*y)=0). Where Aj is column

Question 16

Complementary Slackness Theorem (II)

Answer 16

Comp. slack. thm stated for the primal-dual pair:
max. c^t*x,
st Ax <= b, x>=0^n

min. b^t*y,
st Ax >= b, y>=0^m

Let x, y be feasible to each probs respectively, [then –>] x,y, are opt. in each prob.

Question 17

Global convergence of a penalty method

Answer 17

Consider constrianed prob. min f(x) […] where S subset of R^n, f ->R is given differentiable func.
Assume this prob has opt sol. Then every limit point of seq. {X*v} v —> +infinity, of globally opt sol. to min f(x) + νχ ̃S(x) is also globally opt in the fist problem.

Question 18

Farkas’ Lemma for an inequality system (3.31)

Answer 18

EJ KLAR

Question 19

Weak Duality Theorem 10,4, [tidigare (6.5) är med]

Answer 19

EJ KLAR