Implementation of the algorithms from the paper Self-concordant analysis of Frank-Wolfe algorithms (Proceedings of the 37 th International Conference on Machine Learning, Vienna, Austria, PMLR 119, 2020. Copyright 2020 by the author(s)).
All methods are implemented on Python 3.7 with mathematical packages:
- numpy 1.18.1
- scipy 1.4.1
You need to define the problem for optimization task:
from problems.portfolio import PortfolioProblem
portfolio_problem = PortfolioProblem(path='./data/syn_1000_800_10_50.mat')And run the method with parameters:
from scfw.frank_wolfe import run_frank_wolfe
result = run_frank_wolfe(portfolio_problem, alpha_policy='backtracking', max_iter=100, print_every=10)Problems:
- Poisson Inverse Problem
- Portfolio Optimization Problem
- Distance Weighted Discrimination Problem
- Nonnegative Linear Systems (general KL) Problem
- Inverse Covariance Estimation Problem
Methods:
- Frank-Wolfe with policies:
- standard (with stepsize 2/(k+2))
- line search (exact line search)
- sc (FW-GSC)
- backtracking (BackTrackFW-GSC)
- lloo (LLOO-based convex optimization)
- Proximal Newton
- Proximal Gradient
Proximal Newton and Proximal Gradient implemetations are based on methods from Matlab SCOPT package
Poisson Inverse Problem
The maximum likelihood formulation of the Poisson inverse problem under sparsity constraints leads to the objective function:
Portfolio Optimization Problem
The goal of this problem is to minimize the utility function of the investor by choosing the weights of the assets in the portfolio. The task is to design a portfolio solving the problem:
Distance Weighted Discrimination Problem
In Distance Weighted Discrimination problem, the classification loss attains the form:
over the compact set:
Nonnegative Linear Systems (general KL) problem
Solving Nonnegative linear systems is a GSC optimization problem of the same form as in the Poisson linear inverse problem:
where:
Inverse Covariance Estimation Problem
In Inverse Covariance Estimation Problem we minimize the loss function:
over: