Summary 1-4

Convex Functions

Epigraph

Set of points lying on or above its graph

Show that g assumes a global minimum of value m_V on V as well as a global maximum of value M_V on V

The set V is compact. The map g is continuous since it is affine (ax + b).

Applying the property ”A continuous function on a compact set assumes a global minimum and a global maximum” gives that g assumes a global minimum m_V and a global maximum M_V on V .

Useful (in)equalities

Strictly Convex Functions

Algebraic Definition

Level set of a function =

Quasi-Convex Functions

Balls Notation Reminder

Hyperplanes

Half-spaces

Separation Theorem (duality)

Closure of a set =

smallest closed set that contains the original set = union of the set and all of its limit points

Closed Sets

Property 2.3

Property 2.4

Convex Hull

the smallest convex polygon or shape that encloses a given set of points

Polyhedral Convex Set

Properties

Extreme points

Formal Definition

Profile of V =

Collection of all extreme points of V

= vertices = intersections of equations

check if found intersection is feasible in other (unused) equation

Points that can be written as the midpoint of any segment lying within V and points that were not in the original set (the case of before making it a convex hull) can never be extreme points of V

Theorem

Non-empty compact convex sets

If D is compact …

LP in Standard Form

Any LP can be brought into standard form by following the transformation scheme:

Fundamental Theorem of Linear Programming

When do we have at least one corner point?

Theorem

Non-Optimal and Optimal Corner Points

Primal → Dual

Table

Dual Form

Weak & Strong Duality

Potential Outcomes

Weak & Strong Duality

Complementary Slackness Conditions

Robust Linear Optimization

Robust Optimisation

in one sentence

Robust optimisation replaces "I hope the data is right" with "I will be safe even if the data is at its worst."

Uncertainty in the Objective Function

Theorem

Dual of Dual

The dual of the dual is the primal LP.

Farkas’ Lemma

Farkas’ Lemma Variant

When to prefer Dual over Primal?

When the number of constraints is (much) larger than the number of decision variables

#constraints = m > n = #variables

Simplex Algorithm

How can we compute a corner point / solution?

Simplex Tableau Terminology

Variables

Revised Simplex Algorithm

Full Algorithm

Revised Simplex Algorithm

Tableau at Start

Revised Simplex Algorithm

Full Tableau Matrix

Revised Simplex Algorithm

Revised Simplex Equations

Degeneracy

A LP is said to be degenerate, when more than n constraints (including domain definitions) are tight in a corner point.

=> can get stuck in corner point

Bland’s Rule

With Bland’s Rule → (R)SA cannot cycle