Project a vector on the border of the region defined by a set of linear (in)equality restrictions.

Share:

Description

Compute a vector, closest to x in the Euclidean sense, satisfying a set of linear (in)equality restrictions.

Usage

1
2
project(x, A, b, neq = length(b), w = rep(1, length(x)), eps = 0.01,
  maxiter = 1000L)

Arguments

x

[numeric] Vector that needs to satisfy the linear restrictions.

A

[matrix] Coefficient matrix for linear restrictions.

b

[numeric] Right hand side of linear restrictions.

neq

[numeric] The first neq rows in A and b are treated as linear equalities. The others as Linear inequalities of the form Ax<=b.

w

[numeric] Optional weight vector of the same length as x. Must be positive.

eps

The maximum allowed deviation from the constraints (see details).

maxiter

maximum number of iterations

Value

A list with the following entries:

  • x: the adjusted vector

  • status: Exit status:

    • 0: success

    • 1: could not allocate enough memory (space for approximately 2(m+n) doubles is necessary).

    • 2: divergence detected (set of restrictions may be contradictory)

    • 3: maximum number of iterations reached

  • eps: The tolerance achieved after optimizing (see Details).

  • iterations: The number of iterations performed.

  • duration: the time it took to compute the adjusted vector

  • objective: The (weighted) Euclidean distance between the initial and the adjusted vector

Details

The tolerance eps is defined as the maximum absolute value of the difference vector \boldsymbol{Ax}-\boldsymbol{b} for equalities. For inequalities, the difference vector is set to zero when it's value is lesser than zero (i.e. when the restriction is satisfied). The algorithm iterates until either the tolerance is met, the number of allowed iterations is exceeded or divergence is detected.

See Also

sparse_project

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# the system 
# x + y = 10
# -x <= 0   # ==> x > 0
# -y <= 0   # ==> y > 0
#
A <- matrix(c(
   1,1,
  -1,0,
   0,-1), byrow=TRUE, nrow=3
)
b <- c(10,0,0)

# x and y will be adjusted by the same amount
project(x=c(4,5), A=A, b=b, neq=1)

# One of the inequalies violated
project(x=c(-1,5), A=A, b=b, neq=1)

# Weighted distances: 'heavy' variables change less
project(x=c(4,5), A=A, b=b, neq=1, w=c(100,1))

# if w=1/x0, the ratio between coefficients of x0 stay the same (to first order)
x0 <- c(x=4,y=5)
x1 <- project(x=x0,A=A,b=b,neq=1,w=1/x0)

x0[1]/x0[2]
x1$x[1] / x1$x[2]