A quick introduction to Simplex Method via an example

Below is the original problem: objective function is in green.	See step 1	Red variables below are called SLACK VARIABLES	See step 2	Below is the SIMPLEX TABLEAU. Compare RED symbols with Z = x1 + 2x2 – x3. Blue numbers below are the “ISM“.

The 1st SIMPLEX TABLEAU is below. Note missing z-column (correction by Steve Hulet)	See steps 3,4,5 of SIMPLEX METHOD as you handle INDICATORS, RATIOS, and PIVOTS.	Named below are the 4 row operations needed to pivot on the number “5” encircled in red

Below are the results of the row operations named above blue numbers are the new ISM	Since one INDICATOR (namely -1/5) remains negative, we must repeat steps 3-9	Below is the result of changing our pivot to “1”	Named below are 4 row operations needed to pivot on the number(16/5) encircled in red

Above there was a tie for least non-negative ratio: either row 1 or row 2 could have become the pivot row, and either choice leads to the final tableau after one additional pivoting. At the right is the result of the final 3 row operations.

All indicators {0, 0,	49 16	, 0,	1 16	and	3 8	} are now zero or bigger (“13” is NOT an indicator).
Thus, as in step 8 of the SIMPLEX METHOD, the last tableau is a FINAL TABLEAU.
Row operations of SIMPLEX METHOD are done.

Thus, the basic solution for the tableau above is the solution to our original problem. [1st] set equal to 0 all variables NOT associated with the blue ISM, as at the right. Each column of the final tableau has a label naming it’s variable. [2nd] convert each row of the final tableau (except the bottom row) back into equation form (as at the right) to find the values of the remaining variables. The value of the objective function is in the lower right corner of the final tableau.

Source: http://math.uww.edu/~mcfarlat/s-prob.htm

More: http://people.hofstra.edu/stefan_Waner/realworld/tutorialsf4/unit4_3.html

Karush–Kuhn–Tucker conditions, the 1st order optimality condition

In mathematics, the Karush–Kuhn–Tucker conditions (also known as the Kuhn-Tucker or the KKT conditions) are necessary for a solution in nonlinear programming to be optimal, provided some regularity conditions are satisfied. It is a generalization of the method of Lagrange multipliers to inequality constraints. The conditions are named for William Karush, Harold W. Kuhn, and Albert W. Tucker.

Let us consider the following nonlinear optimization problem:

Minimize

subject to

where is the function to be minimized, () are the inequality constraints and () are the equality constraints, and and are the number of inequality and equality constraints, respectively.

The necessary conditions for this general equality-inequality constrained problem were first published in the Masters thesis of William Karush, although they only became renowned after a seminal conference paper by Harold W. Kuhn and Albert W. Tucker.

Necessary conditions

Suppose that the objective function, i.e., the function to be minimized, is and the constraint functions are and . Further, suppose they are continuously differentiable at a point . If is a local minimum that satisfies some regularity conditions, then there exist constants and such that

Stationarity:

,

Primal feasibility:

.

Dual feasibility:

.

Complementary slackness:

.

Regularity conditions (or constraint qualifications)

In order for a minimum point  be KKT, it should satisfy some regularity condition, the most used ones are listed below

• Linear independence constraint qualification (LICQ): the gradients of the active inequality constraints and the gradients of the equality constraints are linearly independent at .
• Mangasarian-Fromowitz constraint qualification (MFCQ): the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly independent at .
• Constant rank constraint qualification (CRCQ): for each subset of the gradients of the active inequality constraints and the gradients of the equality constraints the rank at a vicinity of is constant.
• Constant positive linear dependence constraint qualification (CPLD): for each subset of the gradients of the active inequality constraints and the gradients of the equality constraints, if it is positive-linear dependent at then it is positive-linear dependent at a vicinity of () is positive-linear dependent if there exists ,…, not all zero such that ).
• Quasi-normality constraint qualification (QNCQ): if the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly independent at with associated multipliers for equalities and for inequalities than it doesn’t exist a sequence such that therefore and thus .
• Slater condition: for a convex problem, there exists a point such that and for all active in .
• Linearity constraints: If and are affine functions, then no other condition is needed to assure that the minimum point is KKT.

It can be shown that

LICQ⇒MFCQ⇒CPLD⇒QNCQ,

LICQ⇒CRCQ⇒CPLD⇒QNCQ

(and the converses are not true), although MFCQ is not equivalent to CRCQ. In practice weaker constraint qualifications are preferred since they provide stronger optimality conditions.

Sufficient conditions

In some cases, the necessary conditions are also sufficient for optimality. This is the case when the objective function and the inequality constraints are continuously differentiable convex functions and the equality constraints hi are affine functions. It was shown by Martin in 1985 that the broader class of functions in which KKT conditions guarantees global optimality are the so called invex functions. So if equality constraints are affine functions, inequality constraints and the objective function are continuously differentiable invex functions then KKT conditions are sufficient for global optimality.

Value function

If we reconsider the optimization problem as a maximization problem with constant inequality constraints

Minimize

subject to

The value function is defined as

subject to

.

(So the domain of is

.)

Given this definition, each coefficient, , is the rate at which the value function increases as increases. Thus if each is interpreted as a resource constraint, the coefficients tell you how much increasing a resource will increase the optimum value of our function . This interpretation is especially important in economics and is used, for instance, in utility maximization problems.

Source

How to apply the Runge–Kutta 4 method to the system of 1st order ODEs?

In numerical analysis, the Runge–Kutta methods are an important family of implicit and explicit iterative methods for the approximation of solutions of ordinary differential equations.

The common fourth-order Runge–Kutta method

One member of the family of Runge–Kutta methods is so commonly used that it is often referred to as “RK4” or simply as “the Runge–Kutta method”. Let an initial value problem be specified as follows.

, with .

We equally split the interval into subintervals by the following interior points

.

Of course, . The number , which will be denoted by , is called the step size. The value of at step is usually denoted by , that is, . Therefore, the initial value problem can be rewritten as , where and with . The Runge–Kutta 4 method tells us that, having the value of at , we can compute the value of at by using the following scheme

Thus, for each step, we need to compute all four , , constants.

The Runge–Kutta 4 method for a system of ODEs

Now we investigate the question in the title of this entry. An th-order system of 1st initial value problems has the form

for , with the initial conditions

, ,…,.

Let be . We denote by the following number

At each step , having all we can compute for all . To do this, for each , we need to compute all , . More precisely, we need to compute

As can be seen, at step and for each , all the values , with must be computed before any of the expressions .

Example

We now consider the following example

Therefore, at the step , we can compute and by using the following scheme

Linear Least Square Problem and QR Decomposition

In linear algebra, a decomposition (also called a factorization) of a matrix is a decomposition of the matrix into an orthogonal and a right triangular matrix. decomposition is often used to solve the linear least squares problem, and is the basis for a particular eigenvalue algorithm, the algorithm.

Square matrix

A QR decomposition of a real square matrix is a decomposition of as where is an orthogonal matrix (meaning that ) and is an upper triangular matrix (also called right triangular matrix). This generalizes to a complex square matrix and a unitary matrix . If is nonsingular, then this factorization is unique if we require that the diagonal elements of are positive.

Rectangular matrix

More generally, we can factor a complex matrix , with , as the product of an unitary matrix and an upper triangular matrix . As the bottom rows of an upper triangular matrix consist entirely of zeroes, it is often useful to partition , or both and :

where is an upper triangular matrix, is , is , and and both have orthogonal columns.

Golub & Van Loan call the thin factorization of . If is of full rank and we require that the diagonal elements of are positive then and are unique, but in general is not. is then equal to the upper triangular factor of the Cholesky decomposition of ( if is real).

, and decompositions

Analogously, we can define , , and decompositions, with being a lower triangular matrix.

How to solve the Linear Least Square problems

Having the decomposition, that is, , one can solve the Least Square Problem where a matrix, and with . To be precise, by mean of , we see that is an matrix and is an matrix. Therefore, we can assume both and to be

Now equation is equivalent to . Thus .

Computing the decomposition

There are several methods for actually computing the QR decomposition, such as by means of the Gram–Schmidt process, Householder transformations, or Givens rotations. Each has a number of advantages and disadvantages. In this section, we mainly consider the Gram–Schmidt process. More precisely, consider the Gram–Schmidt process, with the vectors to be considered in the process as the columns of the matrix . Assume that after finishing the Gram–Schmidt process, we obtain . Therefore, we put

and thus,

.

Example

Let us consider the case when

Then

From , we obtain from , that is,

To obtain , we firstly project onto , then we subtract this result from . More precisely,

where

which yields

Thus

and

Finally,

In Maple, you can practice as shown below.

Linear Least Square Problem and Singular Value Decomposition (SVD)

Linear Least Square Problem (linear least squares), or ordinary least squares (OLS), is an important computational problem, that arises primarily in applications when it is desired to fit a linear mathematical model to measurements obtained from experiments. The goals of linear least squares are to extract predictions from the measurements and to reduce the effect of measurement errors. Mathematically, it can be stated as the problem of finding an approximate solution to an overdetermined system of linear equations. In statistics, it corresponds to the maximum likelihood estimate for a linear regression with normally distributed error.

Linear least square problems admit a closed-form solution, in contrast to non-linear least squares problems, which often have to be solved by an iterative procedure.

Motivational example

As a result of an experiment, four data points were obtained, , , , and (shown in red in the picture on the right). It is desired to find a line that fits “best” these four points. In other words, we would like to find the numbers and that approximately solve the overdetermined linear system

.

of four equations in two unknowns in some “best” sense.

The least squares approach to solving this problem is to try to make as small as possible the sum of squares of “errors” between the right- and left-hand sides of these equations, that is, to find the minimum of the function

.

The minimum is determined by calculating the partial derivatives of in respect to and and setting them to zero. This results in a system of two equations in two unknowns, called the normal equations, which, when solved, gives the solution

and the equation of the line of best fit. The residuals, that is, the discrepancies between the values from the experiment and the values calculated using the line of best fit are then found to be , , , and (see the picture on the right). The minimum value of the sum of squares is

.

The general problem

Consider an overdetermined system (there are more equations than unknowns)

,

of linear equations in n unknown coefficients, ,,…,, with , written in matrix form as ,where

.

Such a system usually has no solution, and the goal is then to find the coefficients which fit the equations “best”, in the sense of solving the quadratic minimization problem.

.

A justification for choosing this criterion is given in properties below. This minimization problem has a unique solution, provided that the columns of the matrix are linearly independent, given by solving the normal equations

.

Singular value decomposition

In linear algebra, the singular value decomposition (SVD) is an important factorization of a rectangular real or complex matrix, with many applications in signal processing and statistics. Applications which employ the SVD include computing the pseudo-inverse, least squares fitting of data, matrix approximation, and determining the rank, range and null space of a matrix.

Suppose is an -by- matrix whose entries come from the field , which is either the field of real numbers or the field of complex numbers. Then there exists a factorization of the form

,

where is an -by- unitary matrix over , the matrix is -by- diagonal matrix with nonnegative real numbers on the diagonal, and denotes the conjugate transpose of , an -by- unitary matrix over . Such a factorization is called a singular-value decomposition of . A common convention is to order the diagonal entries in non-increasing fashion. In this case, the diagonal matrix is uniquely determined by (though the matrices and are not). The diagonal entries of are known as the singular values of .

In practice, matrix consists of eigenvectors of matrix while matrix consists of eigenvectors of matrix . Finally, matrix is the square root of a diagonal matrix forming by eigenvalues of either matrix or matrix .

Example

Let us consider the case when

.

Having yields

and

.

By simple calculation, one has

being eigenvalues of matrix (in the descending form), which helps us to write down

To construct matrix , one has to find eigenvectors corresponding to eigenvalues and . For the first one, that is, , one has the following linear system

which implies, for example,

.

Similar to , one has its corresponding eigenvector as follows

.

Thus

.

The numerical solution of is

which gives us

.

Having we can compute by the following formula or you can perform the same routine as above. That is

.

It is easy to see that

.

Having a SVD result, that is

one can see that the solution of can be computed by

.

Note that matrices and are not unique. Using Maple software, you can compute SVD as shown below.

Useful links

• http://web.mit.edu/be.400/www/SVD/Singular_Value_Decomposition.htm
• http://en.wikipedia.org/wiki/Overdetermined_system
• http://en.wikipedia.org/wiki/Singular_Value_Decomposition
• http://en.wikipedia.org/wiki/Linear_least_squares
• http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-3-full-svd.html

Schwarz Reflection Principle and several applications

Suppose that is an analytic function which is defined in the upper half-disk . Further suppose that extends to a continuous function on the real axis, and takes on real values on the real axis. Then can be extended to an analytic function on the whole disk by the formula

and the values for reflected across the real axis are the reflections of across the real axis. It is easy to check that the above function is complex differentiable in the interior of the lower half-disk. What is remarkable is that the resulting function must be analytic along the real axis as well, despite no assumptions of differentiability.

This is called the Schwarz reflection principle, and is sometimes also known as Schwarz’s symmetric principle (Needham 2000, p. 257). The diagram above shows the reflection principle applied to a function f defined for the upper half-disk (left figure; red) and its image (right figure; red). The function is real on the real axis, so it is possible to extend the function to the reflected domain (left and right figures; pink).

For the reflected function to be continuous, it is necessary for the values at the boundary to be continuous and to fall on the line being reflected. The reflection principle also applies in the generality of reflecting along any line, not just the real axis, in which case the function has to take values along a line in the range. In fact, any arc which has a neighborhood biholomorphic to a straight line can be reflected across. The basic example is the boundary of the unit circle which is mapped to the real axis by .

The reflection principle can also be used to reflect a harmonic function which extends continuously to the zero function on its boundary. In this case, for negative , defining

extends to a harmonic function on the reflected domain. Again note that it is necessary for  . This result provides a way of extending a harmonic function from a given open set to a larger open set (Krantz 1999, p. 95).

Perturbation in linear systems

In this small topic, I will show several traditional results regarding to the perturbation in matrix algebra. This comes from the study of the stability of solving system of linear equations in Numerical Analysis.

Let us consider the following matrix-form linear system . We split into three cases

• Perturbation on

If is a small perturbation on , then is a small perturbation on in the sense that the following system holds true. This together with the fact that gives . By some simple calculation, one has

Thus

• Perturbation on .

If is a small perturbation on , then is a small perturbation on in the sense that the following system holds true. This together with the fact that gives . By some simple calculation, one has

Thus

which implies that

• Perturbation on and .

If is a small perturbation on and is a small perturbation on , then is a small perturbation on in the sense that the following system holds true. This together with the fact that gives . By some simple calculation, one has

which implies that

Thus,

In the literature, the expression is called the condition number of the matrix , denoted by . It is easy to see that . If is small then the system is called to be well-posed. Alternatively, in the case when , the system is ill-posed.

Finite difference method: Local truncation error and consistency

Truncation error or local truncation error is error made by numerical algorithms that arises from taking finite number of steps in computation. It is present even with infinite-precision arithmetic, because it is caused by truncation of the infinite Taylor series to form the algorithm.

Use of arbitrarily small steps in numerical computation is prevented by round-off error, which are the consequence of using finite precision floating point numbers on computers.

Let represent the difference equation approximating the PDE at the -th mesh point, with exact solution . For example,

represent the difference equation approximating the following PDE

at the -th mesh point. If is replaced by at the mesh points of the , where is the exact solution of the PDEs, the value of is called the local truncation error at the -th mesh point. clearly measures the amount by which the exact solution values of the PDE at the mesh points of the do not satisfy the at the point .

Continuing the above example gives us

.

Using Taylor expansions, it is easy to express in terms of power of and and partial derivatives of at . This leads us to the computation of the local truncation error.

It is sometimes possible to approximate a parabolic or hyperbolic equation by a finite-difference scheme that is stable (i.e. limits the amplification of all the components of the initial conditions), but which has a solution that converges to the solution of a different differential equation as the mesh lengths tend to zero. Such a difference scheme is said to be inconsistent or incompatible with the PDE.

The real importance of the concept of consistency lies in a theorem by Lax which states that if a linear finite-difference equation is consistent with a properly posed linear initial-value problem then stability guarantees convergence of to as the mesh lengths tend to zero. Consistency can be defined in either of two equivalent but slightly different ways.

The more general definition is as follows. Let represent the PDE in the independent variables and , with exact solution . Let represent the approximating finite-difference equation with exact solution . Let be a continuous function of and with a sufficient number of continuous derivatives to enable to be evaluated at the point .

Then the truncation error at the point is defined by

.

If as and , the difference equation is said to be consistent or compatible with the PDE. Most authors put because .

For example, let us consider the following parabolic equation

with

and

,

where and .

Backward Euler + second order central finite difference discretization.

We split equally the domain into parts and the domain into parts, i.e. -th mesh point is of the following form

.

We are now in a position to discretize the problem as follows

where . At , that is , one has

and at , that is , one obtains

.

The local truncation error and consistency

The above discretization can be rewritten as following

where with the following boundary conditions

and

Now we have

By Taylor’s expansion

and

and

Therefore,

which yields

Thus, the principle part of the local truncation error is

Hence

.

Consistency.

In view of the local truncation error, one can easily see that the local truncation error is a polynomial of two variables and which implies that the method is consistent.