#constrained optimization

아래는 [영문 위키의 ‘Lagrange multiplier’][lm]의 내용을 바탕으로 쓴 글이다. ------------------------------------ ‘수학적 최적화’([mathematical optimization][mo])라는 분야에서, **라그랑주 승수법**은 제약 등식([equality constraint][ec])을 조건으로 갖는 함수의 극댓값과 극솟값을 찾는 전략이다. 예를 들어, 다음의 최적화 문제를 고려해보자. *g(x, y)=k 인 조건에서 f(x, y)를 최대화하라.*[^1] 이 전략에서 f와 g는 일계 편도함수가 연속이어야 한다. 이제 **라그랑주 승수**라고 불리는 새로운 변수 λ를 도입하고, **라그랑주 함수** 또는 ***Lagrangian***이라고 불리는 다음과 같이 정의된 함수를 살펴보자. Λ(x, y, λ) = f(x, y) + λ·(g(x, y)-k) ***여기서, 제약(constraint) 조건 g(x, y)=k 를 고려하는 기발한 방법은 g(x, y)-k = 0 으로 바꿔 쓰고, 0은 원하는 만큼 여러번 f에 더해도 f에 아무런 변화를 주지 않으므로 λ를 곱해 f에 더하여 얻은 윗 식 Λ가 최대가 되도록 하는 것이다.***[^2] 만약 f(x0 , y0)가 본래의 제약 조건에서 f(x, y)의 최댓값이면, Λ가 모든 변수에 대하여 편미분 가능하므로 (x0, y0, λ0)가 라그랑주 함수 Λ에 대한 임계점([stationary point][sp])이 되는 λ0가 존재한다. 따라서 ∇Λ(x0, y0, λ0)=0 이다. 그러나 역으로 ∇Λ=0 이 되는 모든 임계점이 본래 문제의 해답이 되지는 않는다. 따라서, 라그랑주 승수법은 제한된 문제에서 최적화에 대한 필요조건을 찾는 것이다. ------------------------------------ 이제는 기하학적 의미를 통해 라그랑주 승수법을 알아보자. c의 다양한 값에 대하여 f(x, y)=c 의 등치선(contour)을 그리고, 마찬가지로 주어진 g(x, y)=k 의 등치선을 그리자.

Question:

Given an expectation vector for assets

\[ \mu = \begin{pmatrix}0.04 \\\\ 0.08 \\\\ 0.12 \\\\ 0.15 \end{pmatrix}\]

and an asset covariance matrix

\[ \Sigma = \begin{pmatrix}0.0049 & 0.00168 & 0.0063 & 0.00546 \\\\ 0.00168 & 0.0144 & 0.01512 & 0.01248 \\\\ 0.0063 & 0.01512 & 0.0324 & 0.03744 \\\\ 0.00546 & 0.01248 & 0.03744 & 0.0676\end{pmatrix} \]

What does the optimization below mean?

\[ min_{w}\frac{1}{2}w^{T}\Sigma w \]

subject to

\[ w^{T}\mathbf{1} \]

Solve the optimization using the method of Lagrange.

Solution:

Meaning of the Optimization:

Starting with the constraints.

\[ w^{T}\mathbf{1} = 1 \]

This constraint, called the weight constraint says that the sum of the weights of assets in the portfolio is 1 i.e. all the money in the portfolio has to be invested in the assets from the asset matrix in some proportion.

This constrained optimization

\[ min_{w} \frac{1}{2}w^{T}\Sigma w \]

means choosing the asset weights to minimize the portfolio risk/variance for any return given that you invest all the money in the available assets. This portfolio allocation will be called the Global Minimum Variance portfolio in modern portfolio theory.

\( \)

Solving the optimization:

We can use the Method of Lagrange to solve this constrained optimization problem.

Step 1: Forming the Lagrangian

\[ L(w, \lambda) = \frac{1}{2}w^{T}\Sigma w + \lambda(1 - w^{T}\mathbf{1}) \]

or

\[ L(w, \lambda) = \frac{1}{2}w^{T}\Sigma w + \lambda(1 - \mathbf{1}^{T}w) \]

where

\( L(w, \lambda) \) - Lagrangian function

\( \lambda \) - Lagrangian multiplier

The second form makes it easier to calculate the gradient and the hessian as we need to differentiate w.r.t \( w \).

\( \)

Step 2: Reformulate the optimization

\[ min_{w}\frac{1}{2}w^{T}\Sigma w = min_{w, \lambda} L(w, \lambda) \]

\( \)

Step 3: Gradient vector

\[ \nabla L(w, \lambda) = \begin{pmatrix}L_{w} \\\\ L_{\lambda}\end{pmatrix} = 0 \]

Looking at the two terms separately

\[ L_{w} = 0 \implies \frac{\partial L(w, \lambda)}{\partial w} = 0 \]

\[ \implies \frac{\partial}{\partial w}(\frac{1}{2}w^{T}\Sigma w + \lambda(1 - \mathbf{1}^{T}w)) = 0 \]

\[ \implies w^{T}\Sigma - \lambda\mathbf{1}^{T} = 0 \]

Taking a transpose for the final equation, we have

\[ \Sigma w - \lambda\mathbf{1} = 0 \implies w = \Sigma^{-1}\mathbf{1}\lambda \]

The other equation would be

\[ L_{\lambda} = 0 \implies 1 - \mathbf{1}^{T}w = 0 \]

\( \)

Step 4: Hessian matrix

\[ \frac{\partial^2L(w, \lambda)}{\partial w^2} = \frac{\partial^2}{\partial w}(\frac{1}{2}w^{T}\Sigma w + \lambda(1 - \mathbf{1}^{T}w)) \]

\[ = \frac{\partial}{\partial w}(\Sigma w - \lambda\mathbf{1}^{T}) = \Sigma \]

\[ L_{w\lambda} = L_{\lambda w} = -\mathbf{1}^{T}  \]

\[ L_{\lambda\lambda} = 0 \]

\[ \nabla^2L(w, \lambda) = \begin{pmatrix}\Sigma & -\mathbf{1} \\\\ -\mathbf{1}^{T} & 0 \end{pmatrix} \]

I will write about checking for the Hessian being positive definite in another post.

\( \)

Step 5: Solving for \( w, \lambda \):

We have two equations and two variables from Gradient vector section

\[ w = \Sigma^{-1}\mathbf{1}\lambda \]

\[ \mathbf{1}^{T}w = 1 \]

Substituting for \( w \) from the first equation in the second, we get

\[ \mathbf{1}^T\Sigma^{-1}\mathbf{1}\lambda = 1 \]

Setting

\[ A = \mathbf{1}^{T}\Sigma^{-1}\mathbf{1} \]

we can write the equation and solve for \( \lambda \) as

\[ A\lambda = 1 \implies \lambda = \frac{1}{A} \]

Once we evaluate \( \lambda \), we can substitute in the first equation and get the weight vector \( w \).

I will add the code for evaluating these matrices in a different post. The values from the calculations for this problem are

\[ A = 1505.260875 \]

\[ \lambda = 0.000664 \]

\[ w = \begin{pmatrix}0.905413 \\\\ 0.829084 \\\\ -1.37464 \\\\ 0.640142 \end{pmatrix} \]

Question:

Given an expectation vector for assets

\[ \mu = \begin{pmatrix}0.04 \\\\ 0.08 \\\\ 0.12 \\\\ 0.15 \end{pmatrix}\]

and an asset covariance matrix

\[ \Sigma = \begin{pmatrix}0.0049 & 0.00168 & 0.0063 & 0.00546 \\\\ 0.00168 & 0.0144 & 0.01512 & 0.01248 \\\\ 0.0063 & 0.01512 & 0.0324 & 0.03744 \\\\ 0.00546 & 0.01248 & 0.03744 & 0.0676\end{pmatrix} \]

What does the optimization below mean?

\[ min_{w}\frac{1}{2}w^{T}\Sigma w \]

subject to

\[ w^{T}\mathbf{1} \]

\[ w^{T}\mu = 0.1 \]

Solve the optimization using the method of Lagrange.

Solution:

Meaning of the Optimization:

Starting with the constraints.

\[ w^{T}\mathbf{1} = 1 \]

This constraint, called the weight constraint says that the sum of the weights of assets in the portfolio is 1 i.e. all the money in the portfolio has to be invested in the assets from the asset matrix in some proportion.

\[ w^{T}\mathbf{\mu} = 0.1 \]

This constraint, called the return constraint says that the expected return of the portfolio of assets should be 0.1 or 10%.

This constrained optimization

\[ min_{w} \frac{1}{2}w^{T}\Sigma w \]

means choosing the asset weights to minimize the portfolio risk/variance given that you invest all the money in the available assets with a return expectation of 10%. This portfolio is called the minimum variance portfolio in modern portfolio theory.

\( \)

Solving the optimization:

We can use the Method of Lagrange to solve this constrained optimization problem.

Step 1: Forming the Lagrangian

\[ L(w, \lambda) = \frac{1}{2}w^{T}\Sigma w + \lambda_{1}(1 - w^{T}\mathbf{1}) + \lambda_{2}(0.1 - w^{T}\mathbf{\mu}) \]

or

\[ L(w, \lambda) = \frac{1}{2}w^{T}\Sigma w + \lambda_{1}(1 - \mathbf{1}^{T}w) + \lambda_{2}(0.1 - \mathbf{\mu}^{T}w) \]

where

\( L(w, \lambda) \) - Lagrangian function

\( \lambda_{1}, \lambda_{2} \) - Lagrangian multipliers

The second form makes it easier to calculate the gradient and the hessian as we need to differentiate w.r.t \( w \).

\( \)

Step 2: Reformulate the optimization

\[ min_{w}\frac{1}{2}w^{T}\Sigma w = min_{w, \lambda} L(w, \lambda) \]

\( \)

Step 3: Gradient vector

\[ \nabla L(w, \lambda) = \begin{pmatrix}L_{w} \\\\ L_{\lambda_{1}} \\\\ L_{\lambda_{2}}\end{pmatrix} = 0 \]

Looking at each of the terms separately

\[ L_{w} = 0 \implies \frac{\partial L(w, \lambda)}{\partial w} = 0 \]

\[ \implies \frac{\partial}{\partial w}(\frac{1}{2}w^{T}\Sigma w + \lambda_{1}(1 - \mathbf{1}^{T}w) + \lambda_{2}(0.1 - \mathbf{\mu}^{T}w)) = 0 \]

\[ \implies w^{T}\Sigma - \lambda_{1}\mathbf{1}^{T} - \lambda_{2}\mathbf{\mu}^{T} = 0 \]

Taking a transpose for the final equation, we have

\[ \Sigma w - \lambda_{1}\mathbf{1} - \lambda_{2}\mathbf{\mu} = 0 \implies w = \Sigma^{-1}(\lambda_{1}\mathbf{1} + \lambda_{2}\mathbf{\mu}) \]

The other two equations would be

\[ L_{\lambda_{1}} = 0 \implies 1 - \mathbf{1}^{T}w = 0 \]

\[ L_{\lambda_{2}} = 0 \implies 0.1 - \mathbf{\mu}^{T}w = 0 \]

\( \)

Step 4: Hessian matrix

\[ \frac{\partial^2L(w, \lambda)}{\partial w^2} = \frac{\partial^2}{\partial w}(\frac{1}{2}w^{T}\Sigma w + \lambda_{1}(1 - \mathbf{1}^{T}w) + \lambda_{2}(0.1 - \mathbf{\mu}^{T}w)) \]

\[ = \frac{\partial}{\partial w}(\Sigma w - \lambda_{1}\mathbf{1}^{T} - \lambda_{2}\mathbf{\mu}^{T}) = \Sigma \]

\[ L_{w\lambda_{1}} = L_{\lambda_{1}w} = -\mathbf{1}^{T}  \&  L_{w\lambda_{2}} = L_{\lambda_{2}w} = -\mathbf{\mu}^{T} \]

\[ L_{\lambda_{1}\lambda_{1}} = L_{\lambda_{2}\lambda_{2}} = L_{\lambda_{1}\lambda_{2}} = 0 \]

\[ \nabla^2L(w, \lambda) = \begin{pmatrix}\Sigma & -\mathbf{1} & -\mathbf{\mu} \\\\ -\mathbf{1}^{T} & 0 & 0 \\\\ -\mathbf{\mu}^{T} & 0 & 0 \end{pmatrix} \]

I will write about checking for the Hessian being positive definite in another post.

\( \)

Step 5: Solving for \( w, \lambda \):

We have three equations and three variables from Gradient vector section

\[ w = \Sigma^{-1}(\lambda_{1}\mathbf{1} + \lambda_{2}\mathbf{\mu}) \]

\[ \mathbf{1}^{T}w = 1 \]

\[ \mathbf{\mu}^{T}w = 0.1 \]

Substituting for \( w \) from the first equation in the next two equations, we get

\[ \mathbf{1}^T\Sigma^{-1}\mathbf{1}\lambda_{1} + \mathbf{1}^{T}\Sigma^{-1}\mathbf{\mu}\lambda_{2} = 1 \]

\[ \mathbf{\mu}^{T}\Sigma^{-1}\mathbf{1}\lambda_{1} + \mathbf{\mu}^{T}\Sigma^{-1}\mathbf{\mu}\lambda_{2} = 0.1 \]

Setting

\[ A = \mathbf{1}^{T}\Sigma^{-1}\mathbf{1} \]

\[ B = \mathbf{1}^{T}\Sigma^{-1}\mathbf{\mu} = \mathbf{\mu}^{T}\Sigma^{-1}\mathbf{1} \]

\[ C = \mathbf{\mu}^{T}\Sigma^{-1}\mathbf{\mu} \]

The equations can be written as

\[ A\lambda_{1} + B\lambda_{2} = 1  \&  B\lambda_{1} + C\lambda_{2} = 0.1 \]

We can solve these two equations for \( \lambda_{1}  \&  \lambda_{2} \) as

\[ \lambda_{1} = \frac{C - 0.1B}{AC - B^2}  \&  \lambda_{2} = \frac{0.1A - B}{AC - B^2} \]

Once we evaluate \( \lambda_{1}  \&  \lambda_{2} \), we can substitute for them in the first equation and get the weight vector \( w \).

I will add the code for evaluating these matrices in a different post. The values from the calculations for this problem are

\[ A = 1505.260875,  B = 50.58862248,  C = 1.961294709 \]

\[ \lambda_{1} = -0.007880819  \&  \lambda_{2} = 0.254260507 \]

\[ w = \begin{pmatrix}0.058676968 \\\\ 0.75902696 \\\\ -0.319545123 \\\\ 0.501841195\end{pmatrix} \]

Question:

What is Constrained Optimization? Explain the method of Lagrange for a constrained optimization subject to equality constraints.

Solution:

Constrained Optimization:

A constrained optimization problem can be specified mathematically as

\[ opt f(X) \]

subject to equality constraints

\[ g_{i}(X) = c_{i},  i = 1,...,m \]

and inequality constraints

\[ h_{i}(X) \le d_{i}, i = 1,...,n \]

where

\[ X = \begin{pmatrix}x_{1} \\\\ \vdots \\\\ x_{k} \end{pmatrix}\]

We cannot use the two-step process we used in the case of unconstrained optimization for finding the local maxima/minima due to the constraints. We can use the method of Lagrange to convert the optimization problem with equality constraints to an unconstrained optimization so we can use the two-step process.

\( \)

Method of Lagrange:

Given the constrained optimization

\[ min_{X} f(X) \]

subject to

\[ g_{i}(X) = c_{i}, i = 1,...,m \]

Step 1: Lagrangian Function

The first step in the method of Lagrange is to form a Lagrangian function, our new objective function by augmenting the function \( f(X) \) by adding the constraint equations. Each of these constraints is multiplied by a multiplier called the Lagrange multiplier. 

\[ L(X, \lambda) = f(X) + \sum_{i = 1}^{m}\lambda_{i}(g_{i}(X) - b_{i}) \]

where \( \lambda_{i}, i = 1,...,m \) are the Lagrange multipliers.

What we have done here is changed the constrained optimization with n variables and m constraints into an unconstrained optimization with n+m variables.

\( \)

Step 2: Reformulate the optimization

We can reformulate the problem as

\[ min_{X, \lambda}L(X, \lambda) \]

\( \)

Step 3: Gradient vector

We can now follow the two step process for the unconstrained equation.

\[ \nabla L = \begin{pmatrix}L_{x_{1}} \\\\ \vdots \\\\ L_{x_{n}} \\\\ L_{\lambda_{1}} \\\\ \vdots L_{\lambda_{m}} \end{pmatrix} = 0 \]

The partial derivatives w.r.t the Lagrangian multipliers represent the m constraints as can be seen below

\[ L_{\lambda_{i}} = 0 \implies g_{i}(X) - b_{i} = 0 \]

\( \)

Step 4: Hessian matrix

Question:

Define an Optimization problem. What are constrained and unconstrained optimizations?

Solution:

Optimization:

An optimization problem is to find an optimal value for a dependent variable or a function as you vary the independent variables.

Example:

\[ max_{x_{1},...,x_{n}}f(x_{1},...x_{n}) \]

\[ min_{x_{1},...,x_{n}}g(x_{1},...,x_{n}) \]

where \( f  \&  g \) are dependent variables and \( x_{1},...,x_{n} \) are independent variables, are examples of optimization problems.

\( \)

Unconstrained Optimization:

An unconstrained optimization is an optimization where the independent variables can take any possible values.

Example:

\[ max_{x_{1},...x_{n}}f(x_{1},...,x_{n}) \]

\[ x_{1},...,x_{n} \in \mathbb{R} \]

The above example allows the independent variables to take any real number values to optimize the dependent variable.

\( \)

Constrained Optimization:

A constrained optimization is an optimization where the independent variables have constraints on the possible set of values they can take.

Example:

\[ max_{x_{1},...,x_{n}}y(x_{1},...,x_{n}) \]

subject to:

\[ a_{1}(x_{1},...,x_{n}) = b_{1} \]

\[ ... \]

\[ a_{m}(x_{1},...,x_{n}) < b_{m} \]

The above example exerts constraints on the possible values of the independent variables using the above constraint equations/inequalities.

\( \)

Some Definitions:

Objective Function:

The function or the dependent variable we are trying the find the optimal value of is called the objective function for the optimization.

Decision variables:

The independent variables \( x_{1},...,x_{n} \) that we vary to get our optimal value for the objective functions are called the decision variables for the optimization.

Constraints: