Home Install Documentation Problems Tree Applications Forum

Increase your income
via IT outsourcing!
Ukrainian HI-TECH Initiative Ukrainian HI-TECH Initiative

Problems

From OpenOpt

Jump to: navigation, search
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

See also: New! Stochastic Programming


Matrix Problems Group


\mathbf{A} \mathbf{x} = \mathbf{b}
\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}
\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\}
 \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}}
\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}
 \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{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}}
\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
 \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}
 \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}

(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}
\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}
\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}
search for \mathbf{ \lambda \in C, x \in C^n}:
\mathbf{A  x = \lambda  x}
(A has to be square matrix)


NonLinear Problems Group


\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}


\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}
\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}
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}
\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}
\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}
 \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}
\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}


\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}

Image:gdp.jpg


Network Problems Group


\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 }
\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 }


Find a hamiltonian cycle of graph with optimal cost
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}
Retrieved from "http://openopt.org/Problems"
Personal tools
Latest OOSuite 0.54

from 2014-06-15