1.2. Notation and Common Definitions

This section provides a summary of the notations and common definitions used throughout this guide on optimization methods.

1.2.1. Basic Notations

1.2.1.1. Vectors and Matrices

  • x: Vector of decision variables.

  • b: Vector of constants in linear constraints.

  • A: Matrix of coefficients in linear constraints.

  • B: Basis matrix, an \(m \times m\) non-singular submatrix of (A).

  • I: Identity matrix.

1.2.1.2. Functions and Derivatives

  • \(f(x)\): Objective function to be minimized or maximized.

    • The simplest way to maximize a function is to minimize its negative. So, maximizing \(f(x)\) is equivalent to minimizing \(-f(x)\).

  • \(\nabla f(x)\): Gradient of the objective function.

  • \(\nabla^{2} f(x)\): Hessian matrix (second-order partial derivatives) of the objective function.

  • \(g(x)\): Constraint function.

  • \(\nabla g(x)\): Gradient of the constraint function.

1.2.2. Sets and Indices

  • N: Set of all indices.

  • B: Set of basic variable indices.

  • N B: Set of non-basic variable indices.

  • i, j, k: Indices typically used for summation and iteration.

1.2.3. Common Definitions

1.2.3.1. Feasible Region

The feasible region \(\mathcal{F}\) is the set of all points that satisfy the problem’s constraints: \(\mathcal{F} = \{ x \in \mathbb{R}^n \mid Ax = b, \; x \geq 0 \}\)

1.2.3.2. Optimal Solution

An optimal solution \(x^{*}\) is a point in the feasible region that minimizes (or maximizes) the objective function: \(x^* = \arg \min_{x \in \mathcal{F}} f(x)\)

1.2.3.3. Basis and Basic Variables

A basis (B) is a set of linearly independent columns of the constraint matrix (A). Basic variables are those corresponding to the columns in (B).

1.2.3.4. Non-basic Variables

Non-basic variables are those not in the current basis. They are typically set to zero in basic feasible solutions.

1.2.3.5. Simplex Method

An iterative method for solving linear programming problems by moving from one basic feasible solution to another, improving the objective value at each step.

1.2.3.6. Lagrange Multipliers

Lagrange multipliers \(\lambda\) are used to solve constrained optimization problems. They represent the sensitivity of the objective function to the constraints.

  1. Lagrangian Function: \(L(x, \lambda) = f(x) + \lambda^T g(x)\)

  2. Stationarity: \(\nabla_x L(x^*, \lambda^*) = 0\)

  3. Complementary Slackness: \(\lambda_i g_i(x^*) = 0\)

  4. Primal Feasibility: \(g_i(x^*) \leq 0\)

  5. Dual Feasibility:

    • For minimization: \(\lambda^* \geq 0\)

    • For maximization: \(\lambda^* \leq 0\)

1.2.3.7. Karush-Kuhn-Tucker (KKT) Conditions

Necessary conditions for a solution in nonlinear programming to be optimal. They generalize the method of Lagrange multipliers.

  1. Stationarity: \(\nabla f(x^*) + \sum_{i} \lambda_i \nabla g_i(x^*) = 0\)

  2. Primal feasibility: \(g_i(x^*) \leq 0\)

  3. Dual feasibility: \(\lambda_i \geq 0\)

  4. Complementary slackness: \(\lambda_i g_i(x^*) = 0\)

1.2.3.8. Jacobian and Hessian

  • Jacobian Matrix: Matrix of all first-order partial derivatives of a vector-valued function.

  • Hessian Matrix: Square matrix of second-order mixed partial derivatives of a scalar-valued function.

1.2.3.9. Sensitivity Analysis

The study of how the variation in the output of a model can be apportioned to different sources of variation in the input.