Problems

From OpenOpt

This is an overview of most common numerical optimization problems. Some definitions are accompanied with usage example from OpenOpt framework, 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} \min_{x} &\left[\mu_1(x), \mu_2(x),\dots, \mu_n(x) \right]^T & \\ \text{subjected to} & \\ g(x) & \le 0 \\ h(x) & = 0 \\ x_l \le & x \le x_u \\ x \in & R^n \end{align}$

Some other problems our soft can handle

Integration Problem (IP) $\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}$	Ordinary differential equations (ODE) $\mathbf{\ dy/dt=f(y,t)}$ $\mathbf{y(t_0)=y_0\in R^n}$