# Problems

 This is an overview of most common numerical optimization problems. Some definitions are accompanied with usage example from OpenOpt and/or FuncDesigner frameworks, and, maybe, with some more info; some others have no OpenOpt-connected solvers yet. If your needs are beyond the solvers currently present in OpenOpt, you could take into account that some commercial solvers (e.g. mosek, CPLEX, GuRoBi) have their own Python API.

You can view the set of OpenOpt problems along with lists of solvers and usage samples in a little bit classified representation:

MatrixProblems NonLinearProblems NetworkProblems Other Problems

Matrix Problems Group

 System of linear equations (SLE) $\mathbf{A} \mathbf{x} = \mathbf{b}$ Linear Problems (LP) $\mathbf{f^T x \to min,\ max}$ subjected to $\mathbf{lb \le x \le ub}$ $\mathbf{A x \le b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ Mixed-Integer Linear Problems (MILP) $\mathbf{f^T x \to min,\ max}$ subjected to $\mathbf{lb \le x \le ub}$ $\mathbf{A x \le b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\forall \mathbf{i} \in \mathbf{intVars}: \mathbf{x_i} \in \mathbf{Z}$ $\forall \mathbf{j} \in \mathbf{boolVars}: \mathbf{x_j} \in \{0,1\}$ Quadratic Problems (QP) $\mathbf{\frac{1}{2} x^T Hx + f^T x \rightarrow min}$ subjected to $\mathbf{lb \le x \le ub}$ $\mathbf{A x \le b}$ $\mathbf{A_{eq} x = b_{eq}}$ Linear Least Squares Problems (LLSP) $\frac{1}{2} \mathbf{\| C x - d \|^2} + \frac{1}{2} \mathbf{\mu \| x - \widehat{x} \|^2 \rightarrow min}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ Quadratically Constrained Quadratic Problems (QCQP) $\mathbf{\frac{1}{2} x^T Hx + f^T x \rightarrow min}$ subjected to $\mathbf{lb \le x \le ub}$ $\mathbf{A x \le b}$ $\mathbf{A_{eq} x = b_{eq}}$ $\mathbf{\forall i = 0...I: \frac{1}{2}x^T Q_i x + p_i ^T x + s_i \le 0 }$ Second-Order Cone Problems (SOCP) $\mathbf{f^T x \to min}$ subjected to $\mathbf{lb \le x \le ub}$ $\mathbf{A} \mathbf{x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\mathbf{\forall i = 0,\dots,I: \lVert C_i x + d_i \rVert_2 \leq q_i^T x + s_i}$ $x,\ f \in \mathbb{R}^n$ $C_i \in \mathbb{R}^{{m_i}\times n}, \ d_i \in \mathbb{R}^{m_i}$ $q_i \in \mathbb{R}^n, \ s_i \in \mathbb{R}$ $A_{eq} \in \mathbb{R}^{p_{eq}\times n}, \ b_{eq} \in \mathbb{R}^{p_{eq}}$ Semidefinite Problems (SDP) $\mathbf{f^T x \to min}$ subjected to $\mathbf{lb \le x \le ub}$ $\mathbf{A x \le b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\mathbf{\forall i = 0,...,I: \sum_{j=0}^{n-1} S^{ij} x_j \le d^i}$ (matrix componentwise inequalities) $\mathbf{x \in R^n;\ S^{ij}, d^i \in R^{m_i \times m_i}}$ $\mathbf{i = 0,...,I;\ j = 0,...,n-1}$ $\mathbf{S^{ij}}$ are positive semidefinite matrices Mixed-Integer Quadratic Problems (MIQP) $\mathbf{\frac{1}{2} x^T Hx + f^T x \rightarrow min}$ subjected to $\mathbf{lb \le x \le ub}$ $\mathbf{A x \le b}$ $\mathbf{A_{eq} x = b_{eq}}$ $\mathbf{\forall i \in intVars: x_i \in N}$ Mixed-Integer Quadratically Constrained Quadratic Problems (MIQCQP) $\mathbf{\frac{1}{2} x^T Hx + f^T x \rightarrow min}$ subjected to $\mathbf{lb \le x \le ub}$ $\mathbf{A x \le b}$ $\mathbf{A_{eq} x = b_{eq}}$ $\mathbf{\forall i = 0...I: \frac{1}{2}x^T Q_i x + p_i ^T x + s_i \le 0 }$ $\mathbf{\forall j \in intVars: x_j \in N}$ Linear Least Absolute Values Problems (LLAVP) (aka LLADP - Linear Least Absolute Deviation Problem) $\mathbf{\| C x - d \|_1} + \mathbf{\mu \| x - \widehat{x} \|_1 \rightarrow min}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ Linear Complementarity Problems (LCP) $\mathbf{find \ w, z: w = M z + q}$ subjected to $\mathbf{M \in R^{n \times n}, q \in R^n}$ $\mathbf{w \in R^n, w \ge 0 }$ $\mathbf{z \in R^n,z \ge 0}$ $\mathbf{w^T z = 0}$ Linear Uniform Norm Problems (LUNP) $\mathbf{\| C x - d \|_{\infty} (= max |C x - d|) \rightarrow min}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ Eigenvalue problems (EIG) search for $\mathbf{ \lambda \in C, x \in C^n}$: $\mathbf{A x = \lambda x}$ (A has to be square matrix)

NonLinear Problems Group

 Non-Linear Problems (NLP) $\mathbf {f(x) \to min,\ max}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\mathbf{\forall i=0,...,I: c_i(x) \le 0}$ $\mathbf{\forall j=0,...,J: h_j(x) = 0}$ $\mathbf{ \{ {f, c_i, h_j :R^n \to R \} \subset C^1}}$ (smooth differentiable functions) $\mathbf{x \in R^n}$ Non-Smooth Problems (NSP) $\mathbf {f(x) \to min,\ max}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\mathbf{\forall i=0,...,I: c_i(x) \le 0}$ $\mathbf{\forall j=0,...,J: h_j(x) = 0}$ $\mathbf{ \{ {f, c_i, h_j :R^n \to R \} \subset C^0}}$ (continuous functions, sometimes with some numerical noise) $\mathbf{x \in R^n}$ Global Problems (GLP) $\mathbf {f(x) \to min,\ max\ \ }$ (global) subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{\forall i=0,...,I: c_i(x) \le 0}$ $\mathbf{\forall j=0,...,J: h_j(x) = 0}$ $\mathbf{ f, c_i, h_j :R^n \to R }$ $\mathbf{x \in R^n}$ System of Non-Linear Equations (SNLE) Solve system of non-linear equations $\mathbf{F(x)=0}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{\forall i=0,...,I: c_i(x) \le 0}$ $\mathbf{F: R^n \to R^n}$ $\mathbf{x \in R^n}$ Non-Linear Least Squares Problems (NLLSP) $\mathbf {\sum_{k=0}^{K} f_k(x)^2 \to min}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\mathbf{\forall i=0,...,I: c_i(x) \le 0}$ $\mathbf{\forall j=0,...,J: h_j(x) = 0}$ $\mathbf{ \{ {f_k, c_i, h_j :R^n \to R \} \subset C^1}}$ (smooth differentiable functions) $\mathbf{x \in R^n}$ Data Fit Problems (DFP) $\mathbf {\sum_{k=0}^{K} \|f(x, X_k)-Y_k\| ^2 \to min}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\mathbf{\forall i=0,...,I: c_i(x) \le 0}$ $\mathbf{\forall j=0,...,J: h_j(x) = 0}$ $\mathbf{f, c_i, h_j :R^n \to R}$ $\mathbf{x \in R^n,\ X_k \in R^m, Y_k \in R^s}$ MiniMax Problems (MMP) $\mathbf{max_{k=0,...,K}\{f_k(x)\} \to min}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\mathbf{\forall i=0,...,I: c_i(x) \le 0}$ $\mathbf{\forall j=0,...,J: h_j(x) = 0}$ $\mathbf{ \{ {f, c_i, h_j :R^n \to R \} \subset C^1}}$ (smooth differentiable functions) $\mathbf{x \in R^n}$ Mixed-Integer Non-Linear Problems (MINLP) $\mathbf {f(x) \to min,\ max}$ subjected to $\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}$ $\mathbf{A x} \le \mathbf{b}$ $\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}$ $\mathbf{\forall i=0,...,I: c_i(x) \le 0}$ $\mathbf{\forall j=0,...,J: h_j(x) = 0}$ $\mathbf{\forall k \in \{k_1,k_2,...k_m\}: x_k \in S_k}$ $\mathbf{S_k\ is\ a\ set\ of\ values\ from\ R}$ $\mathbf{ \{ {f, c_i, h_j :R^n \to R \} \subset C^1}}$ (smooth differentiable functions) $\mathbf{x \in R^n}$ Multi-Objective Problems (MOP) \begin{align} \vec f(\vec x) \to \vec F \\ \text{subjected to} \\ \vec g(\vec x) & \le \vec 0 \\ \vec h(\vec x) & = \vec 0 \\ \vec x_l \le & \vec x \le \vec x_u \\ \vec x \in & R^n \\ \vec f: R^n \to R^m\\ \vec F \in (R \cup \{-\infty,\infty\})^m\\ \end{align} Generalized Disjunctive Problems (GDP)

Network Problems Group

 Maximum clique problem (MCP) $\mathbf{For\ graph\ G = (V, E)}$ $\mathbf{find\ V' \subseteq V}$ of maximum size subjected to: $\mathbf{\forall v1 \in V', v2 \in V': (v1,v2) \in E }$ Maximum stable set of graph (STAB) $\mathbf{For\ graph\ G = (V, E)}$ $\mathbf{find\ V' \subseteq V}$ of maximum size subjected to: $\mathbf{\forall v1 \in V', v2 \in V': (v1,v2) \notin E }$ Traveling salesman problem (TSP) Find a hamiltonian cycle of graph with optimal cost Dominating set problem (DSP) For a graph G = (V, E) find a subset D of V such that every vertex not in D is adjacent to at least one member of D

Some other problems our soft can handle

$\mathbf{get \int\limits_D} \mathbf{f(x) dx}$
$\mathbf{x \in R^n}$
$\mathbf{D \subset R^n}$
$\mathbf{f :R^n \to R}$
$\mathbf{\ dy/dt=f(y,t)}$
$\mathbf{y(t_0)=y_0\in R^n}$
$\qquad \sum_{i=1}^n v_ix_i \to max$
subject to
$\qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad \quad x_i \in \{0,1,\ldots,c_i\}$
 minimize $B = \sum_{i=1}^n y_i$ subject to $\sum_{j=1}^n a_j x_{ij} \leq V y_i,$ $\forall i \in \{1,\ldots,n\}$ $\sum_{i=1}^n x_{ij} = 1,$ $\forall j \in \{1,\ldots,n\}$ $y_i \in \{0,1\},$ $\forall i \in \{1,\ldots,n\}$ $x_{ij} \in \{0,1\},$ $\forall i \in \{1,\ldots,n\} \, \forall j \in \{1,\ldots,n\}$

Solve

$\mathbf{F(\dot x(t),\, x(t),\,t)=0}$
$\mathbf{x: R \to R^n}$
$\mathbf{t \in R}$