Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· openaiHugging Face Suzhen/CodeChat

Introduction. Linear programming provides a powerful framework for modeling and solving…

  1. User

    Introduction. Linear programming provides a powerful framework for modeling and solving numerous problems in industrial applications like resource management, transportation, scheduling, structural design, telecommunications, etc. In many other important applications, however, non-linearity can be crucial for modeling the underlying problem accurately. In this laboratory, we will take our first steps into non-linear programming and study a problem in portfolio optimization, where the objective function is quadratic. The main purpose of this lab is to delve deeper into one area of the theory of linear programming. Part of the work is therefore to read and understand a fairly complex description of new material. We start by formulating the portfolio optimization problem. Then we derive an algorithm for solving this formulation and we prove convergence guarantees of the proposed algorithm. Finally, we implement and use this algorithm for solving the problem in a computer experiment. Problem and model: Portfolio Optimization. Sonya wants to build an investment portfolio and she needs to decide how to allocate her savings into different assets. She has a low tolerance for risk and her goal is to design a portfolio which minimizes the risk while maintaining an expected return roughly around the inflation rate. Her advisor in the bank provides historical data on monthly returns of N assets for the last T months. We denote the return of asset n = 1, . . . ,N in month t = 1, . . . , T by an,t. Empirically, the expected return of asset n is its average return, μn = 1 T PT t=1 an,t. We can write a mathematical program to model Sonya’s goals and constraints. Without loss of generality, we denote the total amount of investment by 1 and the amount invested in asset n by xn. We assume that xn must be non-negative (since we do not allow investing negative amounts, or shorting) and sum up to 1. She wants her savings to protect their value by maintaining a minimum expected value around the inflation rate. Her empirical expected return is PN n=1 μnxn. Let 2 R be the inflation rate. Then we have the following minimum expected return constraint: N Xn =1 μnxn . In statistics, we often model the risk as the variance. The variance associated to asset n (denoted by 2n ) is its expected squared deviation from its expected return, i.e., 2n

    1 T PT t=1 |an,t − μn|2. The goal is minimizing the total risk f(x1, . . . , xN), given by f(x1, . . . , xN) = N X n=1 1 T T X t=1 |an,txn − μnxn|2

    N X n=1 x2 n 1 T T X t=1 |an,t − μn|2

    N X n=1 x2 n2n . Hence, we can find a proper strategy for Sonya by solving the following program: (P) minimize N X n=1 2n x2 n subject to N X n=1 μnxn
    N X n=1 xn = 1 xn 0 n = 1, . . . ,N This problem has linear constraints but also a non-linear (convex quadratic) objective function. The algorithms that we learned in the course are not directly applicable because of this non-linearity. Nevertheless, we can find a solution to this problem by solving a sequence of linear programs. This classical approach in non-linear programming is called the conditional gradient method (CGM). Theory, solution method: Conditional Gradient Method. CGM (also known as the Frank-Wolfe Algorithm1) is a classical method in non-linear programming dating back to 1956. Despite its old age, CGM is still very popular today and widely used in the fields of computer vision and artificial intelligence. In this laboratory, we consider a basic version of CGM for solving the portfolio optimization problem. The main strategy of CGM is as follows: Initialize the algorithm from a feasible point x(1) = (x(1) 1 , . . . , x(1) N ). Then, for iteration k = 1, 2, . . ., (1) Form a linear surrogate ˆ fk for the objective function f by using its first-order Taylor expansion at the current estimate x(k): ˆ fk(x) = f(x(k)) + N X n=1 @f @xn (x(k)) · (x − x(k)) Recall that Taylor’s expansion gives the best linear approximation of function f around x(k). Note that · is the dot-product. NOTE! Since Calculus is not formally a prerequisite for this course, it is very much allowed to ask questions about this particular part of the theory. For (P), we can specify ˆ fk as ˆ fk(x) = N X n=1 2n 􀀀x(k) n 2 + 2 N X n=1 2n x(k) n (xn − x(k) n ) = 2 N X n=1 2n x(k) n xn − N X n=1 2n 􀀀x(k) n 2. (2) Form an auxiliary problem with the same constraints as the original problem, but with the linear surrogate objective ˆ fk instead of the original non-linear objective function. This auxiliary problem is a linear program, so we can use the simplex method for solving it. Denote the solution by y(k). 1Frank, M. & Wolfe, P. (1956). “An algorithm for quadratic programming”. Naval Research Logistics Quarterly. 3 (1–2): pp. 95–110. For (P), we can specify the auxiliary problem (ˆPk) as2 (ˆPk) minimize 2 N X n=1 2n x(k) n xn subject to N X n=1 μnxn
    N X n=1 xn = 1 xn 0 n = 1, . . . ,N (3) Update the estimate x(k+1) by moving from x(k) towards y(k): x(k+1) = (1 − k)x(k) + ky(k) with some step-size k 2 [0, 1]. Go back to step 1 and repeat the procedure. With a suitable choice of step-size k, the sequence x(k) generated by CGM converges to a solution of the original problem3. Common choices are the agnostic step-size k = 2/(k+1) and the greedy step-size k = argmin η∈[0,1] f􀀀(1 − )x(k) + y(k). 2We discarded the second term of ˆ fk in (ˆ Pk) because that term is constant with respect to x and does not affect the solution. 3The proof is simple and provided in the appendix of this document. You do not need to read the proof to complete this laboratory, but you are encouraged to read it, especially if you are interested in analysis. Computer Experiment The main task of this laboratory is to implement and use CGM for solving Sonya’s portfolio optimization problem. Download historical data on the return of S&P 500 stock companies from the website below: http://www.cs.technion.ac.il/rani/portfolios/portfolios.htm Suggested steps in the process: (1) Process the data format from the source above so that it can be used as input data for your software / programming language. (2) Implement an LP routine for solving the auxiliary problems in Step 2 of CGM. You are allowed to use, for instance, MatLab’s built-in LP solver as a component of your implementation. (3) Implement CGM. Your implementation should call the LP routine for Step 2 of the algorithm. (4) Suppose the inflation rate is = μav = 1 N PN n=1 μn. Run CGM for 1000 iterations and note the results. Do the results seem to be numerically stable after this many iterations? How many iterations do you need? What happens if you change the step size and re-run your implementation of CGM? Investigate this in a systematic way. (5) Try again with a more ambitious goal of expected return, = 1 2 (μav +μmax), where μmax = maxn μn. Compare your result (i.e., the total variance / risk) with your previous result. Does it increase or decrease? Is it reasonable? Investigate this in a systematic way, and comment on the results. do this in python with pulp

  2. Assistant

    To begin the implementation of the Conditional Gradient Method (CGM) for solving Sonya's portfolio optimization problem in Python, we will be using the PuLP library to handle the linear programming tasks. In the following code, we demonstrate how to process the data, implement CGM, and analyze the different types of step sizes.

    First, we need to install the PuLP library using !pip install pulp.

    Next, import the necessary libraries:

    import numpy as np
    import pandas as pd
    from pulp import *
    

    Now, let's process the data:

    # Read the csv file
    data = pd.read_csv('stock_data.csv')
    
    # Calculate the mu and variance for each asset
    mu = np.mean(data, axis=0)
    variance = np.var(data, axis=0)
    
    num_assets = len(mu)
    
    # Calculate the average and max mu values
    mu_av = np.mean(mu)
    mu_max = np.max(mu)
    

    Implement the LP routine for solving the auxiliary problems in CGM:

    def solve_auxiliary_problem(weights, mu, variance, v, epsilon):
        num_assets = len(mu)
        
        # Create a linear programming problem
        prob = LpProblem("Auxiliary_problem", LpMinimize)
        
        # Create the decision variables
        x = LpVariable.dicts("x", range(num_assets), lowBound=0)
        
        # Declare objective function
        prob += lpSum([2*variance[i]*weights[i]*x[i] for i in range(num_assets)])
        
        # Add constraints
        prob += lpSum([mu[i]*x[i] for i in range(num_assets)]) >= v
        prob += lpSum(x) == 1
        
        # Solve the linear programming problem
        prob.solve()
        
        # Get the solution
        solution = [x[i].varValue for i in range(num_assets)]
    
        return solution
    

    Now, let's implement CGM with different step size choices:

    def conditional_gradient_method(mu, variance, v, max_iter, step_size_choice="agnostik"):
        num_assets = len(mu)
        
        # Initialize the weight vector
        weights = np.ones(num_assets) / num_assets
        
        # Run the algorithm
        for k in range(1, max_iter + 1):
            # Solve the auxiliary problem
            y = solve_auxiliary_problem(weights, mu, variance, v, epsilon)
    
            if step_size_choice == "agnostik":
                step_size = 2 / (k + 1)
            elif step_size_choice == "greedy":
                step_size = np.argmin([np.dot(weights - y, weights - y) for y in range(len(y))])
    
            # Update the weight vector
            weights = (1 - step_size) * weights + step_size * y
            
        return weights
    

    Finally, let's run CGM with different step sizes and analyze the results:

    v1 = mu_av
    weights1_agnostik = conditional_gradient_method(mu, variance, v1, 1000, step_size_choice="agnostik")
    total_variance1_agnostik = np.dot(weights1_agnostik, variance)
    
    weights1_greedy = conditional_gradient_method(mu, variance, v1, 1000, step_size_choice="greedy")
    total_variance1_greedy = np.dot(weights1_greedy, variance)
    
    v2 = (mu_av + mu_max) / 2
    weights2_agnostik = conditional_gradient_method(mu, variance, v2, 1000, step_size_choice="agnostik")
    total_variance2_agnostik = np.dot(weights2_agnostik, variance)
    
    weights2_greedy = conditional_gradient_method(mu, variance, v2, 1000, step_size_choice="greedy")
    total_variance2_greedy = np.dot(weights2_greedy, variance)
    
    # Compare and analyze the total variances
    print("Agnostic step size:")
    print("Total variance (v = mu_av):", total_variance1_agnostik)
    print("Total variance (v = (mu_av + mu_max) / 2):", total_variance2_agnostik)
    print("\nGreedy step size:")
    print("Total variance (v = mu_av):", total_variance1_greedy)
    print("Total variance (v = (mu_av + mu_max) / 2):", total_variance2_greedy)
    

    Now you should see the results from both agnostic and greedy step size choices. You can further investigate the performance of different step size choices and the impact of the inflation rate on the total variance of the portfolio.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.