The problem of maximizing a linear function with linear and quadratic constraints is considered. The solution of the problem is obtained in a constructive form using the Lagrange function and the optimality conditions. Many optimization problems can be reduced to the problem of this type. In this paper, as an application, the problems of maximizing the profitability of an investment portfolio while limiting the variance or the probability of negative return are solved.
Maximization of a Linear Function with Linear and Quadratic Constraints (General Case)
⟨c; x⟩ → mx2aXx; X = {x| ⟨Dx; x⟩ ≤ d; Ax = b}:
Here x ∈ En, c ∈ En, b ∈ Em are column vectors, ⟨:,:⟩ denotes the scalar product of vectors, D is a symmetric positive definite matrix of a size n×n, A is a matrix of a size m×n. It is assumed that the set X is not empty. This is the case if the system Ax =b is consistent and d ≥ d0, where
d0 = xm2Xin0⟨Dx; x⟩; X0 = {x|Ax = b}: Let’s find d0, solving the auxiliary problem of quadratic programming (2).
We compose the Lagrange function L0(x; ) = ⟨Dx; x⟩ + ⟨ ; b − Ax⟩, differentiate it with respect to x and equate to zero the partial derivatives: Dx − AT = 0 (T – transpose sign). Since the matrix D is non-degenerate, the inverse matrix D 1 exists. So we have x = D 1AT and from the restriction AD 1AT = b. Let’s introduce the notation R = AD 1AT . The matrix R is symmetric and nonnegative definite. In what follows we assume that R is non-degenerate. Then we obtain = R 1b and x = D 1AT R 1b. Substituting x in the objective function (2), we have
d0 = ⟨AT R 1b; D 1AT R 1b⟩ = ⟨R 1b; AD 1AT R 1b⟩ = ⟨R 1b; RR 1b⟩ = ⟨R 1b; b⟩:
Let’s return to the main problem (1). We will assume that d > d0, since if d = d0, then the set X consists of one point x = D 1AT R 1b and the problem (1) becomes trivial. For this problem the Lagrange function has the form
L(x; ; ) = ⟨c; x⟩ + (d − ⟨Dx; x⟩) + ⟨ ; b − Ax⟩; ≥ 0: The problem (1) is a convex programming problem that satisfies the Slater condition under the assumptions made. Therefore, by the Kuhn-Tucker theorem, in order that x0 be a solution of (1), it is necessary and sufficient that there exists such y0 = ( 0; 0) that the pair (x0, y0) is a saddle point of the Lagrange function L. To find the saddle point (x0, y0), we differentiate the function L with respect to x and equate the derivatives to zero: c − 2 Dx − T A = 0. We assume that the restriction ⟨Dx; x⟩ ≤ d is essential, i.e. at the solution point it is active (otherwise (1) is simply a linear programming problem), and the conditions of strict complementary non-rigidity fulfill 0 > 0. Then x = 21 D 1(c − T A). We substitute x into the constraints of problem (1): (1) (2) Ax = ⟨D 1c; c⟩ − ⟨c; D 1AT R 1(r − 2 b)⟩ − 2 ⟨R 1(r − 2 b); b⟩ = 4 2d; and obtain a quadratic equation with respect to :
By virtue of the transpose properties of the matrix product and the symmetry of the matrices R 1 and D 1 coefficient for in equation (3) is zero. Indeed,
⟨R 1r; b⟩ − ⟨c; D 1AT R 1b)⟩ = ⟨R 1AD 1c; b⟩ − ⟨c; D 1AT R 1b)⟩ = = ⟨R 1AD 1c; b⟩ − ⟨(D 1AT R 1)T c; b)⟩ = ⟨R 1AD 1c; b⟩ − ⟨R 1AD 1c; b)⟩ = 0:
Then from (3) taking into account that problem (1)), we obtain 0 > 0 (the negative value of 0 corresponds to the minimum in 0 = 1 √ 2 ⟨D 1c; c⟩ − ⟨c; D 1AT R 1r⟩ d − ⟨R 1b; b⟩
: 0 = R 1(r − 2 0b); x0 =
D 1(c − AT 0):
The denominator in expression (4) is positive, because d > d0 = ⟨R 1b; b⟩, therefore the conditions for the essentiality of the quadratic restriction ⟨Dx; x⟩ ≤ d and the complementary non-rigidity are satisfied, if the numerator in (4) is positive. Wherein 3
Optimization of the Investment Portfolio by the Criterion of Expected Pro tability with Constraint on the Variance (a Special Case of the General Problem) As an application of the results obtained, let us consider the problem of finding an optimal portfolio of securities as a task for a maximum of the expected value of the portfolio’s profitability with the upper bound on its variance (risk):
⟨c; x⟩ → mx2aXx; X = {x| ⟨Dx; x⟩ ≤ d; ⟨x; e⟩ = 1}; where x is the vector of the shares of funds invested in various securities, c is the vector of expected returns of securities, D is the covariance matrix (it is always nonnegative definite, we will consider it to be non-degenerate), e = (1; : : : ; 1)T . Here in the investment task, it is assumed that there are short sales (sales without coverage), therefore in the problem (5) the condition of non-negativity x is absent. The problem (5) is a special case of the problem (1), in which A=e, b=1 (if there are sector restrictions on the portfolio structure, we simply have problem (1)).
The solution of problem (5) takes the form: R = ⟨e; D 1e⟩, r = ⟨e; D 1c⟩, d0 = R 1, Substituting the value of R, we have 0 = 1 √ ⟨D 1c; c⟩ − R 1r⟨c; D 1e⟩ = 1 √ R⟨D 1c; c⟩ − r⟨c; D 1e⟩ 2 d − R 1 2 Rd − 1 : ⟨D 1e; e⟩ ⟨D 1c; c⟩ − ⟨c; D 1e⟩2 :
d⟨D 1e; e⟩ − 1 Further, 0 = R 1(r − 2 0), x0 = 210 D 1(c − e 0) = 210 D 1(c − eR 1(r − 2 0)), whence x0 =
D 1c⟨e; D 1e⟩ − D 1e⟨e; D 1c⟩ + 2 0⟨e; D 1e⟩
D 1e ⟨e; D 1e⟩ :
We calculate the maximum value of the objective function: ⟨c; x0⟩ = ⟨c; ( D 1c⟨e; D 1e⟩ − D 1e⟨e; D 1c⟩ + 2 0⟨e; D 1e⟩ ⟨e; D 1e⟩
D 1e )⟩ = ⟨c; D 1c⟩ ⟨e; D 1e⟩ − ⟨c; D 1e⟩2 + ⟨c; D 1e⟩ : 2 0⟨e; D 1e⟩ ⟨e; D 1e⟩ Substituting 0, we have ⟨c; x0⟩ = √(⟨c; D 1c⟩ ⟨e; D 1e⟩ − ⟨c; D 1e⟩2)(d⟨e; D 1e⟩ − 1) + ⟨c; D 1e⟩
⟨e; D 1e⟩ 4
The Problem of Maximizing the Expected Return of the Investment Portfolio, while Limiting the Probability of Negative Returns (a Special Case of the General Problem) We define now the optimal portfolio as the solution of the problem for maximum of the mathematical expectation of the portfolio return, provided that the probability of a negative random value of portfolio returns does not exceed a given sufficiently small value ": ⟨c; x⟩ → mx2aXx;
X = {x| P (⟨r; x⟩ ≤ 0) ≤ "; ⟨x; e⟩ = 1}; where r = (r1; :::; rn)T is a vector of random values of returns, P – the probability of a negative value of profitability (in principle, any required value of profitability can be taken). Note that problem (9) is a special case of the linear stochastic programming problem, for which results analogous to those described below can be obtained. We’ll show that the problem (9) can be reduced to the problem of convex programming, and ultimately, to the solution of problem (5) for some choice of the parameter d.
Theorem. Let {ri} be a system of random variables, each of which is normally distributed, ci are their mathematical expectations, D = ( ij )n n is a covariance matrix. Then the solution of problem (9) coincides with the solution of the problem: ⟨c; x⟩ → mx2aXx;
X = {x| ⟨c; x⟩2 ≥ ⟨Dx; x⟩; ⟨x; e⟩ = 1}; where = (Φ 1(1−2")) 2, Φ(·) is Laplace function.
Proof. The random variable ⟨r; x⟩ is normally distributed with mathematical expectation m = ⟨c; x⟩ and standard deviation = ⟨Dx; x⟩1=2, so (9) (10) P (⟨r; x⟩ ≤ 0) = where z = t m or t = m + z: Further we have
P (⟨r; x⟩ ≤ 0) = √ By=c(oΦnd1it(i1o−n2o"f))(92) a21n−d h2ave the problem of convex programming (10). The theorem is proved.
1 Φ( m ) ≤ ", so m ≥ Φ 1(1 − 2") or m ≤ (Φ 1(1 − 2")) 1. We introduce the variable
In problem (10) the restrictions do not coincide with the type of constraints of problem (1) (or (5)) and are generally inconvenient for obtaining optimality conditions. Therefore, hereafter we reduce the problem (10) to the problem (5), in which the parameter d is connected with the parameter .
If the quadratic constraint in problem (5) and the risk restriction in problem (10) are active at the optimal point x0, then ⟨c; x0⟩2 = ⟨Dx0; x0⟩ = d. In the previous section we have obtained the optimal value of the objective function (8) in problem (5) for a given value of the parameter d. Using (8), we obtain the equation of the relation between d and : ( √(⟨c; D 1c⟩ ⟨e; D 1e⟩ − ⟨c; D 1e⟩2)(d⟨e; D 1e⟩ − 1) + ⟨c; D 1e⟩ )2 ⟨e; D 1e⟩ = d: After a series of transformations, we obtain a quadratic equation for finding d for a given . Indeed, we will open the expression in parentheses: (⟨c; D 1c⟩ ⟨e; D 1e⟩ − ⟨c; D 1e⟩2)(d⟨e; D 1e⟩ − 1)+ +2⟨c; D 1e⟩√(⟨c; D 1c⟩ ⟨e; D 1e⟩ − ⟨c; D 1e⟩2)(d⟨e; D 1e⟩ − 1) + ⟨c; D 1e⟩2 = 1d⟨e; D 1e⟩2: We transfer members without a root to the right-hand side and square both sides: 4⟨c; D 1e⟩2(⟨c; D 1c⟩ ⟨e; D 1e⟩ − ⟨c; D 1e⟩2)(d⟨D 1e; e⟩ − 1) = = ((⟨c; D 1c⟩ ⟨e; D 1e⟩ − ⟨c; D 1e⟩2)(1 − d⟨D 1e; e⟩) + 1d⟨e; D 1e⟩2 − ⟨c; D 1e⟩2)2: In the right-hand side of the last equality, we group the terms for d: 4⟨c; D 1e⟩2(⟨c; D 1c⟩ ⟨e; D 1e⟩ − ⟨c; D 1e⟩2)(d⟨e; D 1e⟩ − 1) = = (d(⟨c; D 1e⟩2 − ⟨e; D 1e⟩ ⟨c; D 1c⟩)⟨e; D 1e⟩ + 1⟨e; D 1e⟩2) − 2⟨c; D 1e⟩2 + ⟨c; D 1c⟩ ⟨e; D 1e⟩)2: We expand the square on the right-hand side, transfer all the terms to the left-hand side and group the terms for d2 and d. Introduce the notation k1( ) = (⟨c; D 1e⟩2⟨e; D 1e⟩ − ⟨e; D 1e⟩2⟨c; D 1c⟩ + 1⟨e; D 1e⟩2)2; k2( ) = −2⟨e; D 1e⟩3⟨c; D 1c⟩2 + 2 +2⟨c; D 1e⟩2⟨e; D 1e⟩2⟨c; D 1c⟩ − 4 1⟨e; D 1e⟩3⟨c; D 1c⟩+ 1⟨e; D 1e⟩2⟨c; D 1e⟩2;
= ⟨c; D 1c⟩2⟨e; D 1e⟩2: k1( )d2 + k2( )d + k3 = 0: (11)
If there exists a real root of this equation and it satisfies the condition d > d0, then problem (10) has a solution. We note that, although the Kuhn-Tucker conditions for the convex programming problem are necessary and sufficient, in view of the transformations (squaring), equation (11) gives only a necessary condition for determining d, so a side root may appear. If both roots of equation (11) turn out to be real and satisfy the condition d > d0, then it is necessary to check which of them converts the quadratic constraint to the active one. If a root does not convert this restriction into equality, and according to formula (6), the corresponding 0>0, then this root is discarded. 5
Determination of the Optimal Portfolios of Russian Companies Shares (Numerical Calculations) Example 1. Let’s find the solution of the problem (5) for the portfolio of shares of Aeroflot, MTS and Megafon. The rate of return of shares of the companies under consideration were determined using daily closing prices of trading sessions. For shares of these companies, using real statistics of the prices for the year, we obtain the vector of mathematical expectations of returns r¯ = (0:967; 0:189; 0:327)T and the covariance matrix 0:65 0:466 −0:18 K = 0:466 1:678 −0:189 :
−0:18 −0:189 0:379
We calculate d0=0.149 and choose d=0.5>d0. We find by formula (6) 0=0.68. Then by formula (7) x0=(1.017, -0.315, 0.299)T . Note that the restriction in problem (5) at the optimal point is active, i.e. it is satisfied as an equality.
Example 2. Suppose that in problem (9) " = 0:1. Then 1 − 2" = 0:8 and the value of the inverse Laplace function is Φ 1(1−2") = 1:282, and = (Φ 1(1−2")) 2 = 0:609. We solve the quadratic equation (11) for finding d and substituting it in the restriction of problem (5). In this case k1 = 1979.225, k2 = -2335.312, k3 = 309.957 and equation (11) gives two roots d1=1.027, d2=0.152. Both these roots satisfy condition d > d0 = 0.149. Then for d1=1.027, using formulas (6) and (7), we obtain 0=0.43, x10=(1.404, -0.533, 0.129)T . Note that the constraints in problems (1) and (10) at the point x10 are active. For d2=0.152 by formulas (6) and (7) we obtain 0= 7.385, x2=(0.413, 0.023, 0.563)T . But the restriction ⟨A; x2⟩2 ≥ ⟨Dx2; x2⟩ = d2 of the problem (10) at the point x 2 is not active (0.211 > 0.152); this case corresponds to = 0, therefore x 2 cannot be a solution of the problem (9). Thus, x10 is the optimal point in problem (9) (using the built-in optimization method of Mathcad for problem (10) we get the same solution with high accuracy). Note that for "=0.07435 we obtain d =0.5 as one of the roots of equation (11) and have the same solution as in Example 1.
Maximization of a Linear Function with Linear and Quadratic Constraints and the Condition of Non-negativity We have obtained in an explicit form a solution of the problem of maximizing a linear function with linear constraints of the type of equalities and a quadratic restriction of the type of inequality. Naturally, the question arises: what will happen in the case of linear inequality restriction, in particular, when the condition of nonnegativity of x is present. In this case, the Kuhn-Tucker conditions give us systems of linear equations for the non-zero components of the vectors x0, y0. Therefore, in all the formulas obtained instead of these vectors, the ”reduced” vectors will appear, and there will be instead of the matrices A and D some of their sub-matrices (square for D ). Of course, this will lead to back-to-back algorithm and complicate the calculations. However, for small dimensions, in principle, everything is quite feasible. Here we consider those changes in the solution that are associated with the addition of the non-negativity condition x ≥0, which is widespread in the linear programming. In this case, the Kuhn-Tucker conditions for the problem (1) have the form For nonzero components x0 we have a system of equations c − 2 D1x0 − T A1 = 0, where D1 is the square sub-matrix of the matrix D obtained by deleting rows and columns with numbers corresponding to the zero components of x0, and A1 is the sub-matrix of the matrix A with deleted corresponding rows. The square submatrices of a positive definite matrix D are also positive definite and, consequently, non-degenerate. Therefore, we get x˜0 = 210 D1 1(c − A1T 0); where x˜0 is the vector of nonzero components x0, and in the expressions for 0 and 0 there are also sub-matrices D1 and A1. We note that, for the given case, the Kuhn-Tucker conditions are necessary and sufficient, so the search stops as soon as the point satisfying it is found. In particular, in the task of forming portfolios without short sales, the condition of non-negativity appears, however, according to market professionals, the portfolio dimension of more than eight components does not make sense (further increase in dimension does not reduce the risk). Thus, if we add the non-negativity condition x ≥0 in Example 2, we obtain the optimal portfolio x0=(0.898, 0, 0.102)T corresponding to the root of equation (11) d1=0.495. 7
Thus, we have obtained a solution of the problem of maximizing a linear function with linear constraints of the equality type and a quadratic restriction of the type of inequality, and as its specification the problems of optimizing the investment portfolio are considered. However, the scope of applications of the results obtained is much broader. In the future, we plan to apply them to the correction of improper and unstable problems of linear and quadratic programming.
Acknowledgements This work was performed within the State project no. 1.8535.2017 of the Ministry for Science and Education of the Russian Federation.