Hello! In 2013, Madeleine Udell and Stephen Boyd defined a class of convex, NP-hard problems called
sigmoidal programs, which resemble convex programs but allow a controlled deviation from convexity in the objective function. Maximizing the sum of sigmoidal functions over convex sets is a problem with many applications, including problems dealing with decreasing marginal returns to investment, mathematical marketing, network bandwidth allocation, revenue optimization, optimal bidding, and lottery design. In this paper, we concentrate on maximizing the sum of sigmoidal functions as related to the Affordable Care Act. We demonstrate the hardness of sigmoidal programming, and discuss possible approximation algorithms. Additionally, in their paper, Udell and Boyd described an approximation algorithm to find a globally optimal approximate solution to the problem of maximizing a sum of sigmoidal functions over a convex constraint set. To demonstrate the power of the algorithm, we compute the optimal state ACA allocations which may allow states in the US to maximize their overall level of health, as measured by birth rates, number of cancer cases, number of cancer deaths, and number of nursing homes.
We consider the
latex sigmoidal programming problem as considered by Udell and Boyd, namely
where is a sigmoidal function for each , and the variable is constrained to lie in a nonempty bounded closed convex set .
A continuous function is defined to be $sigmoidal$ if it is either convex, concave, or convex for and concave for . Equivalently, we call a function sigmoidal if it can be written as the integral of a quasi-concave, bounded function on the same domain.
Motivation for Sigmoids
The effect of funding on societal health can be described using sigmoidal functions: society expects to enjoy increasing marginal returns as the amount of money given to each individual increases and their level of health increases. However, as more resources are allocated to a single individual, the marginal return for that individual will eventually diminish. Further, it is not a bad assumption that eventually the marginal return for that individual will increase again — at very large increases in money allocated to each individual, the funds available begin to enable very expensive cures to be possible, completely eradicating issues and permanently increasing the level of health of that individual. In particular, in this project, we look at one specific type of sigmodial function: the
The logistic function is a function of the equation:
The initial state of growth is approximately exponential; then, as saturation begins, the growth slows, and at long time, the growth stops. The logistic function has a large number of applications, particularly within economics. In particular, it describes the impact of ACA funding on the general state of health well: when funding is introduced there is dramatic improvement in quality of healthcare received, which leads to a period of rapid growth in the effect on health indicators. Eventually, dramatic improvement opportunities are exhausted, however, and the effect of increased funding stabilizes.
Solving the Sigmoidsal Program with ACA Data
Madeleine Udell developed a python package to solve sigmoidal programs based on this method, which we use to solve our problem.
To use Udell’s solver, we first best-fitted coefficients for each of the four logistic functions, corresponding to the four indicators, of each state. Then, we averaged the coefficients for each state to acquire one set of coefficients for one objective function that represents a state. The solution to the objective function then would represent the percentage of each dollar of government grant that would maximize the impact of the grant in that state.
Please see below for the Python script for Alabama, which we adapted from Udell’s original script:
In the code, we defined both a logistic function for each state using the averaged coefficients as well as that function’s first derivative as parts of the input for the solver.
And using this script, we acquired the following results:
The first column signifies the optimal solution that means the percentage of each dollar of ACA grant that would have the optimal impact on health outcomes of a particular state. Summing the solutions across 50 states, we get a number greater than 1, which makes some sense because ideally states would like more than they have been receiving to improve further the current healthcare outcomes. We normalized the solutions so that they would add up exactly to 1. In this way, the `Normalized’ column represents the recommendation we give for how big a fraction of ACA grant could be given to any U.S. state to maximize the improvement on health outcomes of that state.
When our datasets get much larger, we run the risk of being unable to solve the problem because of its NP-hardness. Because certain sigmoidal optimization problems are generalized forms of MAXCUT, some approximation algorithms for MAXCUT such as
Simple Randomized 0.5-Approximation Algorithm and
Semidefinite Programming Algorithm could be used to solve our problem, when the number of years or factors considered for optimization may rise in the future.
Thank you very much!
Jasmine and Jinzhao