Chapter 3: Annealing Machines, Quadratic Expressions, and Discrete Values
Section 3: Quadratic optimization problems (portfolio optimization)
So when does this second-order term appear in a real problem?
One example is the portfolio optimization problem in Chapter 1,
Optimization Problem 3. Suppose $s_i$ represents whether or not to buy the stock $x_i$ ($+1$ to
buy, $-1$ not to buy) and $s_j$ represents whether or not to buy the stock $x_j$.
Now, if the price of the stock $x_i$ goes up when the price of the stock $x_j$ also goes up
(i.e., positively correlated), we can represent a risk as a cost function by multiplying those
two values and a positive coefficient $a_{ij}$. If you buy both $x_i$ and $x_j$ stocks,
when the price of the $x_i$ stock drops, the price of the $x_j$ stock also drops,
indicating that you would lose a lot of money.
In other words, the positive larger value of $a_{ij}s_is_j$ indicates a larger risk.
On the other hand, if $x_i$ and $x_j$ move in opposite directions with
respect to the market price movement (i.e., negatively correlated), that is, if the price of $x_j$
falls when the price of $x_i$ rises, while the price of $x_i$ rises when the price of $x_j$ falls,
then buying them
simultaneously will prevent the prices from falling all at once. Thus,
setting the correlation coefficient $a_{ij}$ to a negative value indicates lower risk.
As you see above, well-designed correlation functions can express whether you should or should
not buy a stock.
The correlation appears not only in portfolio optimization
but also in other combinatorial optimization problems
when considering the relationship between variables affected by each other's choices.
The shift optimization problem in (4) is another example.
Suppose there are three staff members,
Mr. A, Mr. B, and Mr. C, and there is a time slot to which anyone should be assigned.
If Mr. A is assigned to the slot, Mr. B and Mr. C will not need to be assigned.
A relationship like that assigning someone affects another's assignment is called "interaction."
The selecting sweets problem described in "What is the combinatorial optimization problem?" is also a linear equation, similar to the mixed juice problem described in Section 1. However, if the satisfaction level changes with the combination of sweets, an interaction represented by a quadratic function appears. Suppose that the satisfaction level of chocolate was 10 points and the satisfaction level of potato chips was 8 points when eaten alone. If satisfaction is not particularly dependent on the combination of sweets, the total satisfaction would be 18 points when you eat chocolate and potato chips. However, in reality, some people feel that satisfaction increases when they eat something sweet and something salty. We can model such a situation as their satisfaction will be 36 points if you eat both chocolate and potato chips. In this case, a second-order term appears in the cost function because the combination of sweets makes satisfaction more than just an addition. Thus, a problem that looks the same may be first-order or second-order if the modeling is slightly different. Optimization problems with interactions are very difficult to solve with solvers for first-order formulas but are suit for annealing machines.
It is essential to select problems with interaction to take maximum advantage of annealing machines.
