O&C Test 2

A sqare matrix $A$ is called unimodular if $A$ is integral (has integer entries) and the determinant of $A$ is $1$ or $-1$ (i.e. $\det(A)=\pm1$)

A matrix that is both full row rank and unimodular

Let $A$ be a full row rank matrix $A$ is called unimodular if and only if all its invertible $m \times m$ submatrices are unimodular.

An integral matrix $A$ is called totally unimodular if and only if every square invertible submatrix of $A$ is unimodular

A matrix $A$ is called full row rank matrix is $rank(A) = $ number of rows of $ A$.

A matrix is $A$ is full row rank if all of its rows are linearly independent.

Remove the integrality constraints and allow decision variables to take any real values that satisfy the other constraints

A bipartite graph $G=(V,E)$ consists of a set of nodes (or vertices) and as set of undirected edges denoted $e$, such that $V = X \cup Y, X \cap Y = \emptyset$ and every edge has one end in $X$ and the other in$Y$.

An $n \times n$ matrix is called symmetric if $A=A^\top$

Let $A$ be a symmetric $n \times m$ matrix then $A$ is called:
positive definite if $\vec{x}^\top A \vec{x}>0 \quad \forall \vec{x}\neq \vec{0}\in \mathbb{R}^n$
positive semi-definite if $\vec{x}^\top A \vec{x}\geq0 \quad \forall \vec{x}\in \mathbb{R}^n$
negative definite if $\vec{x}^\top A \vec{x}<0 \quad \forall \vec{x}\neq \vec{0}\in \mathbb{R}^n$
negative semi-definite if $\vec{x}^\top A \vec{x}\leq0 \quad \forall \vec{x}\in \mathbb{R}^n$

Let $D$ be a $n \times n$diagonal matrix then:
$D$ is positive definite $\iff \lambda_i > 0 \quad \forall 1 \leq i \leq n$
$D$ is positive semi-definite $\iff \lambda_i \geq 0 \quad \forall 1 \leq i \leq n$
$D$ is negative definite $\iff \lambda_i < 0 \quad \forall 1 \leq i \leq n$
$D$ is negative semi-definite $\iff \lambda_i \leq 0 \quad \forall 1 \leq i \leq n$

The Hessian matrix $H_f $of a scalar-valued function $f(x_1,\dots,x_n)$ defined as $H_{f}(x)=\left[\frac{\partial^2 f}{\partial x_i \partial x_j}\right]$ for $1\leq i \leq m$ and $1 \leq j \leq m$

If $F: \mathbb{R}^n \to \mathbb{R}$ is a function with continuous second partial derivatives, then
$F$ convex $\iff H_F(\vec{x}^*)$ is positive semi-definite
$F$ concave $\iff H_F(\vec{x}^*)$ is negative semi-definite

Given an NLP $\max z = F(\vec{x})$ such that $g_i(\vec{x})=b_i \quad \forall 1 \leq i \leq m$ with feasible set $S = \{\vec{x} \mid g_i(\vec{x}) = b_i, 1 \leq i \leq m\}$, we let $\lambda_1, ... , \lambda_m$ be variables. We define the langrangian function:
$L(x_1,...,x_n,\lambda_1,...,\lambda_m) = F(x_1,...,x_n)+\sum_{i = 1}^m[\lambda_i \cdot (b_i-g_i(\vec{x}))]$
$\iff L(\vec{x}, \vec{\lambda})=F(\vec{x})+\vec{\lambda}\cdot (\vec{b}-\vec{g}(\vec{x}))$

We also have $\vec{\nabla}L = \left( \frac{\partial L}{\partial x_1}, \ldots, \frac{\partial L}{\partial x_n}, \frac{\partial L}{\partial \lambda_1}, \ldots, \frac{\partial L}{\partial \lambda_m} \right)$ is a continous function.

If $L$ has a local max (min) at $P = (\vec{x}_0, \vec{\lambda}_0)$ then $P$ satisfies the following langrangian conditions:
1. $\vec{\nabla}F(\vec{x}_0) = \sum_{i=1}^m \lambda_i \cdot \vec{\nabla}g_i (\vec{x}_0)$
2. $\vec{g}(\vec{x}_0) = \vec{b}$

Let $A \in \mathbb{R}^{m \times n}, \vec{b} \in \mathbb{R}^n, \vec{c} \in \mathbb{R}^n$. The for each of the following variants:
$(P): Z_{LP} = \max\{\vec{c} \cdot \vec{x} \mid A\vec{x} \leq \vec{b}, \vec{x} \in \mathbb{R}^n_+\}$ and $(W): W_{LP} = \min\{\vec{y} \cdot \vec{b} \mid \vec{y}A \geq \vec{c}, \vec{y} \in \mathbb{R}^m_+\}$
or
$(P^*): Z_{LP} = \max\{\vec{c} \cdot \vec{x} \mid A\vec{x} \geq \vec{b}, \vec{x} \in \mathbb{R}^n_+\}$ and $(W^*): W_{LP} = \min\{\vec{y} \cdot \vec{b} \mid \vec{y}A \leq \vec{c}, \vec{y} \in \mathbb{R}^m_+\}$

If the primal or dual is finite then both are finite and $Z_{LP} = W_{LP}$.

$\vec{x}^* \in \mathbb{R}^n$ is an optimal solution for the primal problem if and only if $\vec{x}^*$ satisfied the following (KKT) conditions:
(i) $A\vec{x}^* \geq \vec{b}, \vec{x} \geq 0$ (primal feasible solution)

There exists $\vec{w} \in \mathbb{R}^m, \vec{v}\in \mathbb{R}^n$ such that:
(ii) $\vec{w}^\top A + \vec{v} = \vec{c}^\top, \vec{w},\vec{v} \geq 0$ (dual feasible solution)
(iii) $\vec{w}^\top(A\vec{x}^*-\vec{b}) = 0$ and $\vec{v}\cdot \vec{x}^*=0$ (complementary slackness)

If $\vec{x}^* \in \mathbb{R}^n$ is an optimal solution for the NLP then it satisfies the following (KKT) conditions:
(i) $g_i(\vec{x}^*) \leq b^*_i \quad 1 \leq i \leq m$ and $\vec{x}^* \geq 0$ (feasibility condition)

There exists a $\vec{v} \in \mathbb{R}^m$ such that:
(ii)$\frac{\partial F}{\partial x_j}(\vec{x}^*)-\sum_{i=1}^m \mu_i \frac{\partial g_i}{\partial x_j}(\vec{x}^*) \leq 0 \quad \forall 1 \leq j \leq n$
(iii)$\mu_i \cdot (b_i -g_i(\vec{x}^*)) = 0$ and $x_j^*\left(\frac{\partial F}{\partial x_j}(\vec{x}^*)-\sum_{i=1}^n \mu_i \frac{\partial g_i}{\partial x_j}(\vec{x}^*)\right)=0 \quad \forall 1 \leq j \leq n, \forall 1 \leq i \leq m$ for $\vec{x}^* = (x_1^*, ..., x_n^*)$
(iv) $\mu_i = 0$ or $g_i(\vec{x}^*)=b_i$ and $\vec{x}_j^*=0$ or $\frac{\partial F}{\partial x_j}(\vec{x}^*)=\sum_{i=1}^n \mu_i \frac{\partial g_i}{\partial x_j}(\vec{x}^*)$