Search

This paper focuses on the cardinality constrained mean-variance portfolio optimization, in which only a small number of assets are invested. We first treat the covariance matrix of asset returns as a diagonal matrix with a special matrix processing technique. Using the dual theory, we formulate the lower bound problem of the original problem as a max-min optimization. For the inner minimization problem with the cardinality constraint, we obtain its analytical solution for the portfolio weights. Then, the lower bound problem turns out to be a simple concave optimization with respect to the Lagrangian multipliers. Thus, the interval split method and the supergradient method are developed to solve it. Based on the precise lower bound, the depth-first branch and bound method are designed to find the global optimal investment selection strategy. Compared with other lower bounds and the current popular mixed integer programming solvers, such as CPLEX and SCIP, the numerical experiments show that our method has a high searching efficiency. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the National Natural Science Foundation of China [Grants 12101317, 12271071, and 11991024], the Natural Science Foundation of Jiangsu Province [Grant BK20200819], the Team Project of Innovation Leading Talent in Chongqing [Grant CQYC20210309536], the Contract System Project of Chongqing Talent Plan [Grant cstc2022ycjh-bgzxm0147], and the Philosophy and Social Science Fund of Education Department of Jiangsu Province [Grant 2020SJA0168]. K.F.C. Yiu is supported in part by the Research Grants Council of Hong Hong [Grant PolyU 15223419], the Hong Kong Polytechnic University [Grants 4-ZZPT and 1-WZ0E], and the Research Centre for Quantitative Finance [Grant 1-CE03]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0344) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0344). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We introduce DiffOpt.jl, a Julia library to differentiate through the solution of optimization problems with respect to arbitrary parameters present in the objective and/or constraints. The library builds upon MathOptInterface, thus leveraging the rich ecosystem of solvers and composing well with modeling languages like JuMP. DiffOpt offers both forward and reverse differentiation modes, enabling multiple use cases from hyperparameter optimization to backpropagation and sensitivity analysis, bridging constrained optimization with end-to-end differentiable programming. DiffOpt is built on two known rules for differentiating quadratic programming and conic programming standard forms. However, thanks to its ability to differentiate through model transformations, the user is not limited to these forms and can differentiate with respect to the parameters of any model that can be reformulated into these standard forms. This notably includes programs mixing affine conic constraints and convex quadratic constraints or objective function. History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: The work of A. Sharma on DiffOpt.jl was funded by the Google Summer of Code program through NumFocus. M. Besançon was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research [Grant 05M14ZAM, 05M20ZBM]. J. Dias Garcia was supported in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001. B. Legat was supported by a BAEF Postdoctoral Fellowship, the NSF [Grant OAC-1835443], and the ERC Adv. [Grant 885682]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0283), as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0283). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

For an unbalanced cooperative game, its grand coalition can be stabilized by some instruments, such as subsidization and penalization, that impose new cost terms to certain coalitions. In this paper, we study an alternative instrument, referred to as cost adjustment, that does not need to impose any new coalition-specific cost terms. Specifically, our approach is to adjust existing cost coefficients of the game under which (i) the game becomes balanced so that the grand coalition becomes stable, (ii) a desired way of cooperation is optimal for the grand coalition to adopt, and (iii) the total cost to be shared by the grand coalition is within a prescribed range. Focusing on a broad class of cooperative games, known as integer minimization games, we formulate the problem on how to optimize the cost adjustment as a constrained inverse optimization problem. We prove NP -hardness and derive easy-to-check feasibility conditions for the problem. Based on two linear programming reformulations, we develop two solution algorithms. One is a cutting-plane algorithm, which runs in polynomial time when the corresponding separation problem is polynomial time solvable. The other needs to explicitly derive all the inequalities of a linear program, which runs in polynomial time when the linear program contains only a polynomial number of inequalities. We apply our models and solution algorithms to two typical unbalanced games, including a weighted matching game and an uncapacitated facility location game, showing that their optimal cost adjustments can be obtained in polynomial time. History: Accepted by Area Editor Andrea Lodi for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72022018 and 72091210]; the Research Grants Council of the Hong Kong SAR, China [Grant 16210020]; Hong Kong Polytechnic University [Grant P0032007]; and the Youth Innovation Promotion Association, Chinese Academy of Sciences [Grant 2021454]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0268. [ABSTRACT FROM AUTHOR]