imported>Etone |
imported>Addbot |
| Line 1: |
Line 1: |
| = Linear Programming =
| | In [[number theory]] a '''Carmichael number''' is a [[composite number|composite]] positive [[integer]] <math>n</math>, which satisfies the [[congruence]] <math>b^{n-1}\equiv 1\pmod{n}</math> for all integers <math>b</math> which are [[coprime|relatively prime]] to <math>n</math>. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after [[Robert Daniel Carmichael|Robert Carmichael]]. |
| Given a function <math>f:\mathbb{R}^n\rightarrow\mathbb{R}</math> and a set <math>\mathcal{F}\subseteq\mathbb{R}^n</math>, an '''optimization problem''' is the problem of finding an <math>x\in\mathcal{F}</math> with the optimal (minimum) <math>f(x)</math>. Formally, the problem can be expressed as:
| |
| ::<math>
| |
| \begin{align}
| |
| \mbox{minimize} & \quad f(x)\\
| |
| \mbox{subject to} &\quad x\in\mathcal{F}
| |
| \end{align}
| |
| </math> | |
| where <math>x\in\mathcal{R}^n</math> is a vector of <math>n</math> variables. For the problem of maximizing a function <math>f</math>, we just minimizes <math>-f</math> instead.
| |
|
| |
|
| We call the function <math>f</math> the '''objective function''' and call any <math>x\in\mathcal{F}</math> a '''feasible solution''' of the problem. A feasible solution that minimizes <math>f(x)</math> is called an '''optimal solution'''. Our task is to find an optimal solution.
| | All [[prime number]]s <math>p</math> satisfy <math>b^{p-1}\equiv 1\pmod{p}</math> for all integers <math>b</math> which are relatively prime to <math>p</math>. This has been proven by the famous mathematician [[Pierre de Fermat]]. In most cases if a number <math>n</math> is composite, it does '''not''' satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number. |
| | | {{Math-stub}} |
| The feasible set <math>\mathcal{F}</math> is usually given by a number of '''constraints''' <math>P_1,P_2,\ldots,P_m</math>, which are predicates defined on <math>x</math>. An <math>x</math> is a feasible solution if it satisfies all the constraints.
| | [[Category:Number theory]] |
| | |
| A '''linear programming (LP)''' problem is an optimization problem with a linear objective function subject to a number of linear constraints. Formally, an LP is a problem that can be expressed in the following form:
| |
| ::<math>
| |
| \begin{align}
| |
| \mbox{minimize} & \quad c_1x_1+c_2x_2+\cdots+c_nx_n\\
| |
| \mbox{subject to} & \quad a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n\le b_1\\
| |
| & \quad a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n\le b_2\\
| |
| & \qquad\qquad \vdots\\
| |
| & \quad a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n\le b_m\\
| |
| \end{align}
| |
| </math> | |
| where <math>a_{ij}</math>, <math>b_i</math> and <math>c_j</math> are constants and <math>x_j</math> are variables. For maximization problem, or constraints given by "<math>\ge</math>", we can multiply the coefficients by <math>-1</math> and still write the LP in the above form.
| |
| | |
| We can describe the programming in the vector form. Let <math>x</math> be a vector of <math>n</math> variables. Let <math>A=(a_{ij})</math> be an <math>m\times n</math> matrix of constant entries, <math>b=(b_1,\ldots,b_m)</math> be a vector of <math>m</math> constant entries, and <math>c=(c_1,\ldots,c_n)</math> be a vector of <math>n</math> constant entries. Then an LP is expressed as:
| |
| ::<math>
| |
| \begin{align}
| |
| \mbox{minimize} & \quad c^T x\\
| |
| \mbox{subject to} & \quad Ax\le b
| |
| \end{align}
| |
| </math>
| |
| We call it the '''canonical form''' of linear programming.
| |
| | |
| = The geometry of LPs =
| |
| For <math>n</math>-dimensional space <math>\mathbb{R}^n</math>, a linear constraint <math>ax\le b</math> specifies a [http://en.wikipedia.org/wiki/Half-space halfspace]. The feasible set specified by <math>m</math> constraints together is an intersection of <math>m</math> halfspaces, thus, a [http://en.wikipedia.org/wiki/Convex_polytope convex polytope].
| |
| | |
| The convex polytope is defined by <math>Ax\le b</math>.
| |
| | |
| The LP can be thought as given an <math>n</math>-dimensional polytope and a linear (affine) function <math>f:\mathbb{R}^n\rightarrow \mathbb{R}</math>, looking for a point <math>x</math> in the polytope with the smallest function value <math>f(x)</math>.
| |
| | |
| We can choose a number of constraints in the system <math>Ax\le b</math>, and make them hold with equality. This would define a subspace of <math>\mathbb{R}^n</math>. In particular, if we choose <math>n</math> linearly independent constraints to form an <math>n\times n</math> submatrix <math>A'</math> and the corresponding <math>n</math>-dimensional vector <math>b'</math>, solving <math>A'x=b'</math> would give us exactly one point <math>x</math>. If this <math>x</math> is in the polytope, i.e. <math>x</math> satisfies that <math>Ax\le b</math>, we call such <math>x</math> a '''vertex''' of the polytope <math>Ax\le b</math>. In the context of LP, it is also called a '''basic feasible solution (''bfs'')''' of the LP.
| |
| | |
| A key observation for LP is that there is a basic feasible solution which is optimal, i.e. the optimal solution is a vertex of the polytope.
| |
| | |
| = The simplex algorithms =
| |
| The [http://en.wikipedia.org/wiki/Simplex_algorithm simplex algorithm] by George Dantzig solves the linear programming by moving from vertex to vertex of the convex polytope, each time making some progress towards optimizing the objective function. Eventually the algorithm reaches a vertex which is a [http://en.wikipedia.org/wiki/Local_optimum local optimum]. In a convex set, a locally optimal point is also global optimal, thus the simplex algorithm returns an optimal solution in finite steps.
| |
| | |
| The problem with the simplex algorithm is that in some bad polytopes, it takes the simplex algorithm exponentially many steps to reach the optimum. The simplex algorithm is actually a class of algorithms defined by various '''pivoting rules''', which describe how to move locally from one vertex to another. The original pivoting rule proposed by Dantzig has an exponentially large worst-case time complexity (though works very good in practice). To-date, it is still unknown whether there exists any deterministic simplex algorithm with sub-exponential worst-case complexity.
| |
| | |
| People have tried randomized pivoting rules, and there are some amazing progresses have been made:
| |
| * Kalai 1992: there is a randomized simplex algorithm with sub-exponential time complexity.
| |
| * Kelner-Spielman 2006: there is a polynomial time randomized simplex algorithm.
| |
| | |
| Although we do not know whether there exists deterministic poly-time simplex algorithm, we do know that LP can be solved by deterministic poly-time algorithms, i.e. LP is in '''P'''. The following two algorithms use different ideas than the simplex algorithm, and are both in poly-time:
| |
| * The ellipsoid algorithm.
| |
| * Interior point methods.
| |
| Although these algorithms guarantee polynomial time complexity in the worst-case, their performances are worse than the simplex algorithms. However, the ideas of these algorithms can be used to solve more general mathematical programmings, such as [http://en.wikipedia.org/wiki/Convex_programming convex programmings].
| |