General optimization problem definition

$$\boxed{\begin{array}{rl}\underset{\mathbf{x}\in S}{\mathrm{minimize}}& f(\mathbf{x}),\\ \text{subject to}& g_i(\mathbf{x})\le 0,i\in \mathcal{I}\\ & h_i(\mathbf{x})=0,i\in \mathcal{E}\\ & \mathbf{x}\in \mathrm{X}\end{array}}$$

Classification

Linear programming (LP)

• Linear objective function $f(\mathbf{x})={\mathbf{c}}^{\mathsf{T}}\mathbf{x}={\sum }_{j=1}^n{c}_j{x}_j$
• Affine constraint functions $g_i(\mathbf{x})={\mathbf{a}}_i^{\mathsf{T}}\mathbf{x}-b_i,i\in \mathcal{I}\cup \mathcal{E}$
• Ground set $\mathrm{X}\subset {\mathbb{R}}^n$ defined by affine equalities or inequalities.

Nonlinear programming (NLP)

• Some functions $f,g_i,i\in \mathcal{I}\cup \mathcal{E}$ are nonlinear.

Unconstrained optimization

• $\mathcal{I}\cup \mathcal{E}=\varnothing$
• $\mathrm{X}={\mathbb{R}}^n$

Constrained optimization

• $\mathcal{I}\cup \mathcal{E}\ne \varnothing$
• $\mathrm{X}\subset {\mathbb{R}}^n$

Integer programming (IP)

• $\mathrm{X}\subset {\mathbb{Z}}^n$ or $\mathrm{X}\subseteq \{0,1{\}}^n$

Convex programming (CP)

• $f,g_i,i\in \mathcal{I}$ are convex functions
• $g_i,i\in \mathcal{E}$ are affine
• $\mathrm{X}$ is closed and convex

Modeling

Formulating the problem

1. Define what sets the problem requires
2. Acknowledge what parameters the problem has and to what set it belongs to
3. What type of descision variables is suitable for the problem

Convexity

Convex set

A set $S\subseteq {\mathbb{R}}^n$ is convex if

$${\mathbf{x}}_1,{\mathbf{x}}_2\in S,\lambda \in (0,1)⟹\lambda {\mathbf{x}}_1+(1-\lambda ){\mathbf{x}}_2\in S$$

Affine hull

The affine hull of a finite set $V=\{{\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\mathbf{v}}^k\}$ is defined as

$$\text{aff}V:=\{{\lambda }_1{\mathbf{v}}^1+\cdots +{\lambda }_k{\mathbf{v}}^k|{\lambda }_1,\dots ,{\lambda }_k\in \mathbb{R},\sum _{i=1}^k{\lambda }_i=1\}$$

Convex hull

The convex hull of a finite set $V=\{{\mathbf{v}}^1,{\mathbf{v}}^2,\dots ,{\mathbf{v}}^k\}$ is defined as

$$\text{conv}V:=\{{\lambda }_1{\mathbf{v}}^1+\cdots +{\lambda }_k{\mathbf{v}}^k|{\lambda }_1,\dots ,{\lambda }_k\ge 0,\sum _{i=1}^k{\lambda }_i=1\}$$

Affine combination

An affine combination of the points $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_n\}$ is a vector satisfying

$$\mathbf{v}=\sum _{i=1}^n{\lambda }_i{\mathbf{v}}_i$$

where ${\sum }_{i=1}^n{\lambda }_i=1$

Convex combination

A convex combination of the points $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_n\}$ is a vector satisfying

$$\mathbf{v}=\sum _{i=1}^n{\lambda }_i{\mathbf{v}}_i$$

where ${\sum }_{i=1}^n{\lambda }_i=1$ and ${\lambda }_i\ge 0$ for every $i=1,\dots ,n$

Polytype

A set $P\subset {\mathbb{R}}^n$ is a polytype if it is the convex hull of finitely many points in ${\mathbb{R}}^n$.

Polyhedron

A set $P\subset {\mathbb{R}}^n$ is a polyhedron if there exists a matrix $A\in {\mathbb{R}}^{m\times n}$ and a vector $\mathbf{b}\in {\mathbb{R}}^m$ such that

$$P=\{\mathbf{x}\in {\mathbb{R}}^n|\mathbf{A}\mathbf{x}\le \mathbf{b}\}$$

The set $P$ is the intersection of $m$ half-spaces. Polyhedrons may be unbounded.

Cone

A set $C\subseteq {\mathbb{R}}^n$ is a cone if $\lambda \mathbf{x}\in C$ whenever $\mathbf{x}\in C$ and $\lambda >0$.

Polyhedral cone

The set $\{\mathbf{x}\in {\mathbb{R}}^n|\mathbf{A}\mathbf{x}\le 0^m\}$ where $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ is a cone but also a polyhedron, which is why it is usually called a polyhedral cone.

Half space

A half space is the set the cuts the space in two parts

$$\{\mathbf{x}\in {\mathbb{R}}^n|a_i\mathbf{x}\le b_i\}$$

Convex function

Suppose that $S\subseteq {\mathbb{R}}^n$ is a convex set, then a function $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex on $S$ if

$${\mathbf{x}}^1,{\mathbf{x}}^2\in S,\lambda \in (0,1)⟹f(\lambda {\mathbf{x}}^1+(1-\lambda ){\mathbf{x}}^2)\le \lambda f({\mathbf{x}}^1)+(1-\lambda )f({\mathbf{x}}^2)$$

• A function is strictly convex if the inequality is strict.
• A function $f$ is concave if $-f$ is convex.

Note that linear functions are both convex and concave.

Carathéodory's Theorem

Let $\mathbf{x}\in \text{conv}V$ where $V\subseteq {\mathbb{R}}^n$. Then $\mathbf{x}$ can be expressed as a convex combination of $n+1$ or fewer points of $V$.

Representation Theorem

The Representation Theorem states that every polyhedron that has at least one extreme point is the sum of a polytope and a polyhedral cone.

Farkas' Lemma

Let $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$. Then exactly one of the systems has a feasible solution

$$\begin{array}{rl}\mathbf{A}\mathbf{x}& =\mathbf{b}\\ \mathbf{x}& \ge 0\end{array}$$

and

$$\begin{array}{rl}{\mathbf{A}}^{\mathsf{T}}\mathbf{y}& \le 0\\ {\mathbf{b}}^{\mathsf{T}}\mathbf{y}& >0\end{array}$$

and the other one is inconsistent.

Existence of optimal solutions

Notation

• We say that a set $S\subseteq {\mathbb{R}}^n$ is open if for every $x\in S$ there exists an $ϵ>0$ such that $B_{ϵ}(\mathbf{x}):=\{\mathbf{y}\in {\mathbb{R}}^n|\Vert \mathbf{y}-\mathbf{x}\Vert <ϵ\}\subset S$.
• A set $S\subseteq {\mathbb{R}}^n$ is closed if ${\mathbb{R}}^n\backslash S$ is open.
• A limit point of a set $S\subseteq {\mathbb{R}}^n$ is a point $\mathbf{x}$ such that there exists a sequence $\{{\mathbf{x}}_k{\}}_{k=1}^{\infty }\subset S$ fulfilling ${\mathbf{x}}_k\to \mathbf{x}$.
• We can then define a closed set as a set which contains all its limit points.
• We say that a set $S\subseteq {\mathbb{R}}^n$ is bounded if there exists a constant $C>0$ such that $\Vert \mathbf{x}\Vert \le C$ for all $\mathbf{x}\in S$.
• If a set is both closed and bounded, we call it compact.

Definition

Weakly coercive function

A function $f$ is said to be weakly coercive with respect to the set $S$ if either $S$ is bounded or

$$\underset{\begin{array}{c}\Vert \mathbf{x}\Vert \to \infty \\ \mathbf{x}\in S\end{array}}{\lim }f(\mathbf{x})=\infty$$

Lower semi-continuity

A function $f$ is said to be lower semi-continuous at $\mathbf{x}$ if the value $f(\mathbf{x})$ is less than or equal to every limit of $f$ as ${\mathbf{x}}_k\to \mathbf{x}$

$${\mathbf{x}}_k\to \mathbf{x}⟹f(\mathbf{x})\le \underset{k\to \infty }{\text{lim inf}}f({\mathbf{x}}_k)$$

Feasible direction

Let $\mathbf{x}\in S$. A vector $\mathbf{p}\in {\mathbb{R}}^n$ defines a feasible direction at $\mathbf{x}$ if

$$\exists \delta >0:\mathbf{x}+\alpha \mathbf{p}\in S,\forall \alpha \in [0,\delta ].$$

The feasible direction is therefore a direction at a point where we can move without becoming infeasible.

Descent direction

Let $\mathbf{x}\in {\mathbb{R}}^n$. A vector $\mathbf{p}\in {\mathbb{R}}^n$ defines a descent direction with respect to $f$ at $\mathbf{x}$ if

$$\exists \delta >0:f(\mathbf{x}+\alpha \mathbf{p})<f(\mathbf{x}),\forall \alpha \in (0,\delta ].$$

Normal cone

Suppose the set $S$ is closed and convex. Let $\mathbf{x}\in S$. Then the normal cone to $S$ at $\mathbf{x}$ is the set

$$N_s(\mathbf{x}):=\{\mathbf{p}\in {\mathbb{R}}^n|{\mathbf{p}}^{\mathsf{T}}(\mathbf{y}-\mathbf{x})\le 0,\mathbf{y}\in S\}$$

Weierstrass' Theorem

Consider the problem where $S$ is a nonempty and closed set and $f$ is lower semi-continuous on $S$. If $f$ is weakly coercive with respect to $S$, then there exists a nonempty, closed and bounded (compact) set of optimal solutions to the problem.

Optimality conditions (S equal R^n)

When $S={\mathbb{R}}^n$ (unconstrained optimization problem), the following theorem holds

Necessary condition for optimality 1

If $f\in C^1$ on ${\mathbb{R}}^n$ then

$${\mathbf{x}}^{\ast }\text{is a local minimum of}f\text{on}{\mathbb{R}}^n⟹\nabla f({\mathbf{x}}^{\ast })=0$$

Necessary condition for optimality 2

If $f\in C^2$ on ${\mathbb{R}}^n$ then

$${\mathbf{x}}^{\ast }\text{is a local minimum of}f\text{on}{\mathbb{R}}^n⟹\{\begin{array}{l}\nabla f({\mathbf{x}}^{\ast })=0\\ {\nabla }^{2}f({\mathbf{x}}^{\ast })\ge 0\end{array}$$

Sufficient condition for optimality 2

If $f\in C^2$ on ${\mathbb{R}}^n$ then

$$\{\begin{array}{l}\nabla f({\mathbf{x}}^{\ast })=0\\ {\nabla }^{2}f({\mathbf{x}}^{\ast })>0\end{array}⟹{\mathbf{x}}^{\ast }\text{is a strict local minimum of}f\text{on}{\mathbb{R}}^n$$

Necessary and sufficient condition for optimality 1

If $f\in C^1$ is convex on ${\mathbb{R}}^n$ then

$${\mathbf{x}}^{\ast }\text{is a global minimum of}f\text{on}{\mathbb{R}}^n⟺\nabla f({\mathbf{x}}^{\ast })=0$$

Optimality conditions (S sub R^n)

Necessary condition for optimality 1

Suppose that $S\subseteq {\mathbb{R}}^n$ and that $f\in C^1$ on $S$.

a) If ${\mathbf{x}}^{\ast }\in S$ is a local minimum of $f$ over $S$ then

$$\nabla f({\mathbf{x}}^{\ast }{)}^{\mathsf{T}}\mathbf{p}\ge 0$$

holds for all feasible directions $\mathbf{p}$ at ${\mathbf{x}}^{\ast }$.

b) Suppose that $S$ is convex. If ${\mathbf{x}}^{\ast }$ is a local minimum of $f$ over $S$ then

$$\nabla f({\mathbf{x}}^{\ast }{)}^{\mathsf{T}}(\mathbf{x}-{\mathbf{x}}^{\ast })\ge 0,\mathbf{x}\in S$$

Neecssary and sufficient conditions for optimality 1

Suppose that $S\subseteq {\mathbb{R}}^n$ is a convex nonempty set and that $f\in C^1$ is a convex function on $S$ then

$${\mathbf{x}}^{\ast }\text{is a global minimum of}f\text{over}S⟺\nabla f({\mathbf{x}}^{\ast }{)}^{\mathsf{T}}(\mathbf{x}-{\mathbf{x}}^{\ast })\ge 0,\mathbf{x}\in S$$

When $S={\mathbb{R}}^n$ the expression can be reduced to $\nabla f({\mathbf{x}}^{\ast })=0$, because then we don't need to worry about boundary points.

Stationary point in optimality condition

If $S$ is convex and $f\in C^1$ a point $\mathbf{x}\in S$ fulfilling the four equivalent statements a)-d) are called a stationary point.

a)

$$\nabla f({\mathbf{x}}^{\ast }{)}^{\mathsf{T}}(\mathbf{x}-{\mathbf{x}}^{\ast })\ge 0,\mathbf{x}\in S$$

b)

$$\underset{\mathbf{x}\in S}{\min }\nabla f({\mathbf{x}}^{\ast }{)}^{\mathsf{T}}(\mathbf{x}-{\mathbf{x}}^{\ast })=0$$

c)

$${\mathbf{x}}^{\ast }={\text{Proj}}_S[{\mathbf{x}}^{\ast }-\nabla f({\mathbf{x}}^{\ast })]$$

d)

$$-\nabla f({\mathbf{x}}^{\ast })\in N_S({\mathbf{x}}^{\ast })$$

where ${\text{Proj}}_S$ is the projection onto the set $S$, and $N_s$ is the normal cone.

Unconstrained optimization

1. Begin by finding a descent direction. The vector ${\mathbf{p}}_k$ is a descent direction if $f({\mathbf{x}}_k+\alpha {\mathbf{p}}_k)<f({\mathbf{x}}_k)$ for all $\alpha \in [0,\delta ]$ for some $\delta >0$.

Steepest descent direction

$${\mathbf{p}}_k=-\nabla f({\mathbf{x}}_k)$$

Newton's search direction

$${\nabla }^{2}f({\mathbf{x}}_k){\mathbf{p}}_k=-\nabla f({\mathbf{x}}_k)$$

Lewenberg-Marquardt

$$[{\nabla }^{2}f({\mathbf{x}}_k)+\lambda I]{\mathbf{p}}_k=-\nabla f({\mathbf{x}}_k)$$

2. Then choose step length

Exact line search

$$\begin{array}{rl}\text{min}& f({\mathbf{x}}_k+\alpha {\mathbf{p}}_k)\\ s.t.& \alpha >0\end{array}$$

Newton's method

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\frac{{\phi }^{\prime }({\mathbf{x}}_k)}{{\phi }^{\prime \prime }({\mathbf{x}}_k)}$$

Armijo rule

$$f({\mathbf{x}}_k+\alpha {\mathbf{p}}_k)\approx f({\mathbf{x}}_k)+\alpha \nabla f({\mathbf{x}}_k{)}^{\mathsf{T}}{\mathbf{p}}_k$$

then keep decreasing $\alpha =\alpha /2$ until the following holds

$$f({\mathbf{x}}_k+\alpha {\mathbf{p}}_k)-f({\mathbf{x}}_k)\le \mu \alpha \nabla f({\mathbf{x}}_k{)}^{\mathsf{T}}{\mathbf{p}}_k$$

3. Stop the algorithm when at least two of the following holds

$$\begin{array}{rl}||\nabla f({\mathbf{x}}_k)||& \le {ϵ}_1(1+f({\mathbf{x}}_k))\\ f({\mathbf{x}}_{k-1})-f({\mathbf{x}}_k)& \le {ϵ}_2(1+f({\mathbf{x}}_k))\\ ||{\mathbf{x}}_{k-1}-{\mathbf{x}}_k||& \le {ϵ}_3(1+||{\mathbf{x}}_k||)\end{array}$$

Different cone sets

Cone of feasible directions

$$R_s(\mathbf{x})=\{\mathbf{p}\in {\mathbb{R}}^n|\exists \delta >0,\mathbf{x}+\alpha \mathbf{p}\in S,\forall \alpha \in [0,\delta ]\}$$

Tangent cone

$$T_s(\mathbf{x})=\{\mathbf{p}\in {\mathbb{R}}^n|\exists \{{\mathbf{x}}_k{\}}_{k=0}^{\infty }\subset S,\{{\lambda }_k{\}}_{k=0}^{\infty }\subset (0,\infty ),\text{ such that }\underset{k\to \infty }{\lim }{\mathbf{x}}_k=\mathbf{x},\underset{k\to \infty }{\lim }{\lambda }_k({\mathbf{x}}_k-\mathbf{x})=\mathbf{p}\}$$

Cone of descent directions

$$F^o(\mathbf{x})=\{\mathbf{p}\in {\mathbb{R}}^n|\nabla f(\mathbf{x}{)}^{\mathsf{T}}\mathbf{p}<0\}$$

Active constraints

$$I(\mathbf{x})=\{i\in 1,...,m|g_i(\mathbf{x})=0\}$$

Inner gradient cone

$$G^o(\mathbf{x})=\{\mathbf{p}\in {\mathbb{R}}^n|\nabla g_i(\mathbf{x}{)}^{\mathsf{T}}\mathbf{p}<0,\forall i\in I(\mathbf{x})\}$$

Gradient cone

$$G(\mathbf{x})=\{\mathbf{p}\in {\mathbb{R}}^n|\nabla g_i(\mathbf{x}{)}^{\mathsf{T}}\mathbf{p}\le 0,\forall i\in I(\mathbf{x})\}$$

Nicely behaving set

$$G^o(\mathbf{x})\subseteq R_s(\mathbf{x})\subseteq T_s(\mathbf{x})\subseteq G(\mathbf{x})$$

Fritz John conditions

$$x^{\ast }\text{local min}⟹F^o(\mathbf{x})\cap G^o(\mathbf{x})=\varnothing$$

Constraint qualification (CQ)

Defines some regularity over the set

Abadie's CQ

Holds at a point $\mathbf{x}\in S$ if $T_s(\mathbf{x})=G(\mathbf{x})$

Linear independence CQ (LICQ)

We say that LICQ holds at $\mathbf{x}$ if the gradients $\nabla g_i(\mathbf{x}),i\in I(\mathbf{x})$ for the active constraints are linearly independent.

Affine CQ

We say that the Affine CQ holds if all the constraints $g_i$ are affine.

Slater CQ

We say that Slater's CQ holds if all $g_i$ are convex and an inner point exists.

Karush-Kuhn-Tucker conditions (KKT)

Assume that Abadie's CQ holds at a point ${\mathbf{x}}^{\ast }$ which is feasible in (P), then

$$x^{\ast }\text{local min}⟹\{\begin{array}{ll}\nabla f({\mathbf{x}}^{\ast })+{\sum }_{i=1}^m{\mu }_i\nabla g_i({\mathbf{x}}^{\ast })& =0\\ {\mu }_i{g}_i({\mathbf{x}}^{\ast })& =0,i=1,...,m\\ {\mu }_i& \ge 0,i=1,...,m\end{array}$$

Sufficiency of KKT conditions

If the objective function $f$ is convex and all constraint functions $g_i$ are convex, the the following holds

$${\mathbf{x}}^{\ast }\text{KKT point}⟹{\mathbf{x}}^{\ast }\text{global optimum}$$

Lagrangian duality/relaxation

A relaxation to

$$\begin{array}{rl}\text{min}& f(\mathbf{x})\\ s.t.& \mathbf{x}\in S\end{array}$$

is

$$\begin{array}{rl}\text{min}& f_R(\mathbf{x})\\ s.t.& \mathbf{x}\in S_R\end{array}$$

where $S\subseteq S_R$ and $f_R(\mathbf{x})\le f(\mathbf{x}),\forall \mathbf{x}\in S$

Relaxation Theorem

$$\begin{array}{rl}a)& f_R^{\ast }\le f^{\ast }\\ b)& \text{If the relaxed problem is infeasible, the original is as well}\\ c)& \text{If the relaxed problem has an optimal solution }{\mathbf{x}}_R^{\ast }\text{ for which it holds that }{\mathbf{x}}_R^{\ast }\in S\text{ and }{f}_R^{\ast }({\mathbf{x}}_R^{\ast })=f({\mathbf{x}}_R^{\ast })\text{ then }{\mathbf{x}}_R^{\ast }\text{ is also optimal in the original problem.}\end{array}$$

Lagrangian relaxation

This is the primal problem

$$\begin{array}{rl}\text{inf}& f(\mathbf{x})\\ \text{s.t.}& g_i(\mathbf{x})\le 0,i=1,...,m\\ & \mathbf{x}\in X\end{array}$$

and this is the dual problem

Lagrangian dual function

$$\begin{array}{rl}\underset{\mathbf{x}\in X}{\min }L(\mathbf{x},\mu )=q(\mu )=\text{inf}& [f(\mathbf{x}+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x}))]\\ \text{s.t.}& \mathbf{x}\in X\end{array}$$

Weak duality

For any $\mu \ge 0$ and any feasible $\mathbf{x}$ to the primal problem, it holds that

$$q(\mu )\le f(\mathbf{x})$$

Lagrangian dual problem

The dual function $q$ is concave and its effective domain is convex.

$$\boxed{\begin{array}{rl}{q}^{\ast }=\text{sup}& q(\mu )\\ \text{s.t.}& \mu \ge 0\end{array}}$$

Lagrange multiplier

${\mu }^{\ast }$ is a Lagrange multiplier if $q({\mu }^{\ast })=f^{\ast }$

Strong duality

Assume that there exists a inner pint to the primal problem, and that $f^{\ast }\ge -\inf$, that $f$ is a convex function, that $g_i,qi=1,...,m$ are convex functions and that $X$ is a convex set. Then the following holds

$$q^{\ast }=f^{\ast }$$

Linear programming (LP)

For linear problems of the sort

$$\begin{array}{rl}\text{min}& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& \mathbf{x}\in P\end{array}$$

we can use the Simplex method to solve for an optimal solution. We first convert to standard form:

$$\begin{array}{rl}\text{min}& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& A\mathbf{x}=\mathbf{b}\\ & \mathbf{x}\ge 0\end{array}$$

where $\mathbf{b}\ge 0$.

Basic solution

A point $\mathbf{x}$ is a basic solution if $A\mathbf{x}=\mathbf{b}$ and the columns of A corresponding to non-zero elements of $\mathbf{x}$ are linearly independent.

Basic feasible solution (BFS)

A point $\mathbf{x}$ is a BFS if $\mathbf{x}\ge 0$, $A\mathbf{x}=\mathbf{b}$ and the columns of A corresponding to non-zero elements in $\mathbf{x}$ are linearly independent.

Degenerate BFS

Consider a BFS with $\mathbf{x}=[{\mathbf{x}}_B{\mathbf{x}}_N{]}^{\mathsf{T}}$. By definition ${\mathbf{x}}_N=0$ and ${\mathbf{x}}_B=B^{-1}\mathbf{b}$. If some elements of ${\mathbf{x}}_B$ are zero the BFS is called degenerate.

Simplex method

Consider

$$\begin{array}{rl}\text{min}& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& \mathbf{x}\in P\end{array}$$

Convert this problem to standard form. To find an initial BFS solve the Phase I problem. That is add as many artificial variables as you need to form the initial base vector as the identity matrix and consider minimizing the artificial variables. Use the Simplex method to move out all artificial variables from the base vector. When this is achieved we have solved the Phase I problem. If we can form the identity matrix without artificial variables go directly to the Phase II problem with this as the base. When we have an initial BFS we solve the Phase II problem, that is the original problem. For each iteration begin by determining ${\mathbf{x}}_B=B^{-1}\mathbf{b}$ and ${\mathbf{x}}_N=0$, e.g. we could have ${\mathbf{x}}_B=[x_1{x}_2{]}^{\mathsf{T}}$ and ${\mathbf{x}}_N=[s_1{s}_2{]}^{\mathsf{T}}$. We also calculate $B$ and $N$ which corresponds to the same variables for the partition in $A$, as well as ${\mathbf{c}}_B$ and ${\mathbf{c}}_N$ in a similar manner. Then we calculate the incoming variable (from $N$) with the following formula:

$${\tilde{\mathbf{c}}}_N^{\mathsf{T}}={\mathbf{c}}_N^{\mathsf{T}}-{\mathbf{c}}_B^{\mathsf{T}}{B}^{-1}N$$

Then we need to calculate the outgoing variable (from $B$). We do this by

$$\underset{k:(B^{-1}{N}_j{)}_k>0}{\text{arg min}}=\frac{(B^{-1}\mathbf{b}{)}_k}{(B^{-1}{N}_j{)}_k}$$

We update the variables and go back and start over. We need to check that $B^{-1}\mathbf{b}\ge 0$ for feasible solution, that $B^{-1}{N}_j\ge 0$ so that we do not have an unbounded solution. We terminate the algorithm when our cost vector $c_N^{\mathsf{T}}\ge 0$.

LP duality

This problem is called the primal (P)

$$\begin{array}{rl}{z}^{\ast }=\text{inf}& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& A\mathbf{x}=\mathbf{b}\\ & \mathbf{x}\ge 0\end{array}$$

and this is the corresponding dual problem (D)

$$\begin{array}{rl}{q}^{\ast }=\text{sup}& {\mathbf{b}}^{\mathsf{T}}\mathbf{y}\\ \text{s.t.}& A^{\mathsf{T}}\mathbf{y}\le \mathbf{c}\\ & \mathbf{y}\in {\mathbb{R}}^n\end{array}$$

The following relation holds for the primal and dual

	Primal		Dual
Objective	min		max
Variables	$\ge 0$ (canonical)	Constraints	$\le$
	$\le 0$ (non-canonical)		$\ge$
	free		$=$
Constraints	$\ge$ (canonical)	Variables	$\ge 0$
	$\le$ (non-canonical)		$\le 0$
	$=$		free

Weak duality theorem

If $\mathbf{x}$ is a feasible point in (P) and $\mathbf{y}$ is a feasible point in (D) then

$${\mathbf{c}}^{\mathsf{T}}\mathbf{x}\ge {\mathbf{b}}^{\mathsf{T}}\mathbf{y}$$

Strong duality theorem

If both (P) and (D) are feasible then

1. There exists ${\mathbf{x}}^{\ast }$ optimal in (P) and ${\mathbf{y}}^{\ast }$ optimal in (D)
2. ${\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast }={\mathbf{b}}^{\mathsf{T}}{\mathbf{y}}^{\ast }$ (meaning $z^{\ast }=q^{\ast }$)

Possibilities in (P) and (D)

P\D	Finite optima	Unbounded	Infeasible
Finite optima	X
Unbounded			X
Infeasible		X	X

Perturbation

A perturbation is a small change to either $A,\mathbf{c}$ or $\mathbf{b}$.

Subgradient method

For convex problems we can relax the differentiability assumption and use something like the subgradient method. Let $S\subseteq {\mathbb{R}}^n$ be a nonempty convex set and let $f:S\to \mathbb{R}$ be a convex function. The $\mathbf{p}\in {\mathbb{R}}^n$ is called a subgradient of $f$ at $\bar{\mathbf{x}}\in S$ if

$$f(\mathbf{x})\ge f(\bar{\mathbf{x}})+{\mathbf{p}}^{\mathsf{T}}(\mathbf{x}-\bar{\mathbf{x}}),\text{for any }\mathbf{x}\in S.$$

The set of all subgradients to $f$ at $\bar{\mathbf{x}}$ is called the subdifferential of $f$ and is defined as

$$\partial f(\bar{\mathbf{x}})=\{\mathbf{p}\in {\mathbb{R}}^n|f(\mathbf{x})\ge f(\bar{\mathbf{x}})+{\mathbf{p}}^{\mathsf{T}}(\mathbf{x}-\bar{\mathbf{x}}),\text{for all }\mathbf{x}\in S\}$$

Integer Linear Programming (ILP)

Logical constraints

• if $x$ then $y⟹x\le y$
• xor $⟹x+y=1$
• or $⟹x+y\ge 1$
• exactly one $⟹{\sum }_{i=1}^n{x}_i=1$
• at least one $⟹{\sum }_{i=1}^n{x}_i\ge 1$

Disjoint feasible sets

$$\begin{array}{rl}0\le x\le 1\cup 5& \le x\le 8⟹\\ x\ge 0& \\ x\le 8& \\ x\le 1+7y& \\ x\ge 5y& \\ y=\{0,1\}& \end{array}$$

Feasible direction methods

These methods are just as local as unconstrained methods, but we find search direction in different ways and termination criteria is often based on KKT. For general sets it could be tricky to find search directions and step lengths. Three well known methods are the Frank-Wolfe method, Simplicial decomposition and the Gradient projection algorithm. These method apply on polyhedron.

Frank-Wolfe method

The idea of the Frank-Wolfe method is to calculate the direction of a linear approximation at a point $x$, find the nearest extreme point with the simplex method and go in the direction of the extreme point.

Simplicial decomposition

It works like the Frank-Wolfe algorithm but it remembers previous extreme points and searches in the convex hull of these points for the next iterations.

Gradient projection algorithm

Based on the idea that this holds at a local min:

$${\mathbf{x}}^{\ast }={\text{Proj}}_X[{\mathbf{x}}^{\ast }-\nabla f({\mathbf{x}}^{\ast })]$$

For every iteration choose the next $x_{k+1}$ as follows

$${\mathbf{x}}_{k+1}={\text{Proj}}_X[{\mathbf{x}}_k-{\alpha }_{k}f({\mathbf{x}}_k)]$$

where ${\alpha }_k>0$ for some feasible direction.

Penalty methods

The idea of penalty methods is to transform a constrained problem to a unconstrained problem.

$$\boxed{\begin{array}{rl}\text{min}& f(\mathbf{x})\\ \text{s.t.}& \mathbf{x}\in S\end{array}}⟺\boxed{\begin{array}{rl}\text{min}& f(\mathbf{x})+{\chi }_S(\mathbf{x})\\ \text{s.t.}& \mathbf{x}\in {\mathbb{R}}^n\end{array}}$$

where ${\chi }_S(\mathbf{x})=\{\begin{array}{ll}0& \text{if }\mathbf{x}\in S\\ +\infty & \text{otherwise}\end{array}$

Exterior penalty method

Suppose that

$$\begin{array}{rl}\underset{\mathbf{x}\in S}{\mathrm{minimize}}& f(\mathbf{x}),\\ \text{subject to}& g_i(\mathbf{x})\le 0,i\in \mathcal{I}\\ & h_i(\mathbf{x})=0,i\in \mathcal{E}\\ & \mathbf{x}\in \mathrm{X}\end{array}$$

Choose a penalty method, e.g.

$$\begin{array}{r}{\psi }_1(s)=|s|\\ {\psi }_2(s)=s^2\end{array}$$

Approximate the indicator function ${\chi }_s(\mathbf{x})$

$${\chi }_s(\mathbf{x})\approx \nu {\bar{\chi }}_s(\mathbf{x})=\nu [\sum _{i=1}^m\psi (\text{max}(0,g_i(\mathbf{x})))+\sum _{j=1}^l\psi (h_j(\mathbf{x}))]$$

Interior penalty method

Suppose that

$$\begin{array}{rl}\underset{\mathbf{x}\in S}{\mathrm{minimize}}& f(\mathbf{x}),\\ \text{subject to}& g_i(\mathbf{x})\le 0,i\in \mathcal{I}\\ & \mathbf{x}\in \mathrm{X}\end{array}$$

Assume that $g_i(\bar{\mathbf{x}})<0,i=1,...,m,\exists \bar{\mathbf{x}}\in {\mathbb{R}}^n$ (an interior point should exist)

Choose a penalty method, e.g.

$$\begin{array}{rl}{\varphi }_1(s)& =-\frac{1}{s}\\ {\varphi }_2(s)& =-\text{log}(\text{min}(1,-s))\end{array}$$

Approximate the indicator function ${\chi }_s(\mathbf{x})$

$${\chi }_s(\mathbf{x})\approx \nu {\bar{\chi }}_s(\mathbf{x})=\{\begin{array}{ll}\nu {\sum }_{i=1}^m\varphi (g_i(\mathbf{x}))& \text{if }{g}_i(\mathbf{x})<0,i=1,...,m\\ +\infty & \text{otherwise}\end{array}$$