Eﬀects of local minima and bifurcation delay on combinatorial optimization with continuous variables

2025-08-18 0 0 1.09MB 12 页 10玖币

侵权投诉

Eﬀects of local minima and bifurcation delay on combinatorial optimization with

continuous variables

Shintaro Sato1

1NTT Computer and Data Science Laboratories, NTT Corporation, Musashino 180-8585, Japan

(Dated: November 3, 2022)

Combinatorial optimization problems can be mapped onto Ising models, and their ground state

is generally diﬃcult to ﬁnd. A lot of heuristics for these problems have been proposed, and one

promising approach is to use continuous variables. In recent years, one such algorithm has been

implemented by using parametric oscillators known as coherent Ising machines. Although these

algorithms have been conﬁrmed to have high performance through many experiments, unlike other

familiar algorithms such as simulated annealing, their computational ability has not been fully

investigated. In this paper, we propose a simple heuristic based on continuous variables whose

static and dynamical properties are easy to investigate. Through the analyses of the proposed

algorithm, we ﬁnd that many local minima in the early stage of the optimization and bifurcation

delay reduce its performance in a certain class of Ising models.

I. INTRODUCTION

Combinatorial optimization problems are generally

hard to solve, and a lot of algorithms to tackle them have

been proposed. Such computationally diﬃcult problems

can be mapped onto the ground state search problem for

the Ising models [1]. Algorithms based on this corre-

spondence have also been proposed, and many of them

are inspired by physical phenomena. Some use discrete

spin variables, which appear in Ising models. Simulated

Annealing (SA) is known as a representative example [2],

and its implementation and development have been ac-

tively pursued. Moreover, many diﬀerent types of algo-

rithms based on continuous variables such as soft spins

have also been proposed [3–10].

The coherent Ising machine (CIM) is one of the heuris-

tics that use continuous variables. It basically consists of

degenerate optical parametric oscillators (DOPOs) and

their phases are interpreted as Ising spins [4]. It is de-

vised in the expectation that by controlling the interac-

tions among DOPOs corresponding to the Ising coupling

matrix, the system stabilizes to the ground state conﬁgu-

ration of the Ising models. The high performance of such

methods in optimization has actually been reported in

both numerical simulations [4,11] and experiments with

optical devices [12–15]. To describe the dynamics of the

CIM, theoretical models have been discussed [16–18]. In

addition, various methods have been devised to improve

the performance [18–21].

Despite such experimental, numerical, and theoreti-

cal developments, the principle of optimization in the

CIM itself has not been studied extensively. Unlike other

heuristics such as SA [22], no ﬁrm theoretical basis has

been found to guarantee its high performances. The CIM

is a type of gradient based optimization. It consists of

bosons interacting via the Ising coupling matrix, and

through the optimization, the state evolves under the

time dependent external ﬁelds. Even within the mean

ﬁeld approximation, it is a nonlinear dynamical system

controlled by the time dependent parameter. Although

its nonlinearities play an important role for the optimiza-

tions [23], it is generally diﬃcult to analyze [4]. Re-

searchers have attempted to investigating the property

by researching the energy landscape or its steady state

through the optimizations [4,24,25]. However, these

analyses only deal with the small and simple Ising mod-

els, or the case of a large degrees of freedom limit. In

applying the CIMs to more complex problems, their po-

tentials need to be clariﬁed in more general cases from

the theoretical point of view.

In this paper, we propose a simple model, which fa-

cilitates analyses of its computational property by intro-

ducing time dependent Lagrange multipliers to the mean

ﬁeld CIM. In contrast to the usual mean ﬁeld CIM, posi-

tions of the ﬁxed points in the landscape are analytically

obtained in our model, so the linear stability around them

is also easy to discuss. In addition to its static aspect, we

also discuss the existence of the bifurcation delay [26–29].

It can also be observed in the usual CIM at least at the

mean ﬁeld level. These properties will aﬀect optimization

ability of the proposed model in a kind of gradient-like

algorithm. Finally, we numerically investigate these ef-

fects on the optimizations by using random matrices as

the Ising models. To verify that our model is a good toy

model for investigating the property of the CIM, we also

discuss the relation between our model and mean ﬁeld

CIM without noise.

The paper is organized as follows. In Sec. II, we intro-

duce a simple heuristic using continuous variables like the

CIM. In Sec. III, we analyze the linear stability around

its ﬁxed points and discuss the bifurcation delay as a

dynamical property. To see the relation between local

minima and the performance, we numerically simulate

the dynamics for a certain class of Ising models in Sec.

IV. Our conclusions are presented in Sec. V.

arXiv:2211.00822v1 [cond-mat.stat-mech] 2 Nov 2022

II. MODEL

We discuss the property of the algorithm show later

for solving Ising problems without magnetic ﬁelds. The

Ising problem is deﬁned as ﬁnding the ground state of

the following Ising Hamiltonian:

H(S) = 1

i6=j

Jij SiSj,(1)

where Sis a Ndimensional Ising spin vector with Si=

±1 (i, j = 1, . . . , N)in the elements. An N×Ndimen-

sional matrix Jij represents the Ising coupling matrix,

which is a symmetric Jij =Jji and Jii = 0. For later

discussion, the eigenvalues of Jij are represented as liand

the smallest ones are written as lmin.

We propose the mean ﬁeld approximated CIM algo-

rithm using continuous variables xi(t)with auxiliary vari-

ables yi(t)that obey the following equations:

dxi

dt=−

x3

i+m(t)xi+βX

Jij xj

+ 2κΘ(t−tc)yixi,

(2)

dyi

dt=−κΘ(t−tc)(−δm(t) + x2

i),(3)

where Θ(t)is the Heaviside step function and β > 0, κ ≥

0, tc, mcare time independent parameters. Time depen-

dent parameters m(t)and δm(t)can be arbitral functions

of time t, and in the later analysis, they are taken as lin-

ear functions.

This system can be regarded as a gain-dissipative sys-

tem with auxiliary variables or a kind of the Augmented

Lagrange method (see Ref. [30,31]). Some variations

have been proposed in the context of the Ising solver

[6,20,32,33]. We note that in particular for κ= 0 our

model reduces to the usual mean ﬁeld CIM [4,18] with-

out noise terms, and continuous variables xicorrespond

to amplitudes of DOPO signals. In solving the Ising prob-

lem, we set the matrix Jij as the Ising coupling matrix

and evolve the system from initial time t= 0 to ﬁnal

time t=T. Finally the ground state of the Hamiltonian

(1) is calculated on the basis of the ﬁnal state obtained

as Si=sgn(xi(T)). In this paper, initial conditions for

xi(0) are chosen uniformly at random from the interval

[−r, r], r ∈Rand those for the auxiliary variables are

yi(0) = 0.

III. MODEL PROPERTY

In this section, we analyze the static and dynamical

aspects of the systems especially related to the search-

ing ability of the solutions for the Ising problem. Our

algorithm is based on the gradient method, and we con-

sider the situation where the time dependent parameters

slowly change in time for suﬃciently large T. Then we

assume that its algorithmic property can be captured by

analyzing the ﬁxed points and their linear stability. Due

to the presence of auxiliary variables, ﬁxed point anal-

yses are much easier than the usual mean ﬁeld CIM.

In the following discussion, the forms of the time de-

pendent parameter are chosen as m(t) = −t +mcand

δm(t) = −m(t−tc)+mcwith  > 0and mc=tc−βlmin.

A. Static property

Let us consider here the static property of this sys-

tem that includes locations of the ﬁxed points and their

linear stability. In this section, we focus on a particular

situation where the time dependent parameters have a

certain ﬁxed value m(t) = m, δm(t) = δm.

When t≤tc, there is only a trivial ﬁxed point xi= 0,

and its linear stability can be obtained by considering

the corresponding Jacobian matrix for xideﬁned J0≡

−m−βJij . Because of the value of mc, it is linearly stable

as long as t<tc, and at t=tcit has zero eigenvalues.

On the other hand t>tc, non-trivial ﬁxed points are

given by the solutions of the simultaneous equations cal-

culated from Eqs.(2) and (3) as

xi=±pδm,(4)

yi=1

2κ

m+δm+βσiX

Jij σj

,(5)

where σi≡sgn(xi). It is found that the bifurcation oc-

curs through the changing parameters. We note that

these 2Nﬁxed points correspond to all conﬁgurations

that Scan take, so the ground state of the Hamiltonian

(1) is given as one of those.

Let us focus on the latter situation in which the non-

trivial ﬁxed points appear. Before going to the discussion

for the case of the non-trivial ﬁxed points, we note that

the origin is not a ﬁxed point for κ6= 0. The linear

stability analysis for these non-trivial ﬁxed points can be

performed by considering the eigenvalues of the following

2N×2Ndimensional matrix:

J = Jxx Jxy

Jyx Jyy ,(6)

where each N×Ndimensional matrices are deﬁned as

Jxx ≡diag(−2δm+βσiPjJij σj)−βJij ,Jxy =−Jyx ≡

2κ√δmdiag(σi),and Jyy ≡0. Here diag(vi)means N×N

dimensional diagonal matrix with the elements of some

Ndimensional vector vi. As reported in [20], the eigen-

values of this type of Jacobian matrix λ±

i(σ, δm)can be

expressed as follows:

λ±

i(σ, δm) = 1

2µi(σ)±qµ2

i(σ)−16κ2δm,(7)

by using µi(σ)which is deﬁned as the ith eigenvalues

of Jxx. Since the inside of the square root is not neces-

sarily positive, these eigenvalues are complex numbers

in general. These 2Neigenvalues consist of Npairs

of λ+

i(σ, δm)and λ−

i(σ, δm)for each index i. We note

that their signs are completely determined by µi(σ):

sgn(Re(λ±

i(σ, δm))) = sgn(µi(σ)), so it is suﬃcient to

examine the signs of µi(σ)to discuss the stability. In ad-

dition, if δmis suﬃciently large (i.e., near the ﬁnal time

of the evolution), µi(σ)will be dominated by the inﬂu-

ence of the −2δmterm in the diagonal component of Jxx

and all eigenvalues of the Jacobian Jbecome negative.

As a result, all ﬁxed points will be stable. By using these

results, we can discuss the number of local minima in the

optimizations.

B. Dynamical property

Now let us consider the eﬀect of the time dependent

parameters. In general, the time evolution of the system

is diﬃcult to obtain analytically, but within a particu-

lar time interval, their dynamics can be captured by lin-

earized equations. In this section, we discuss the dynam-

ical aspect of our model from the viewpoint of the bifur-

cation delay [26–29]. We will see that this phenomenon

delays the actual time when the bifurcation occurs due

to the time dependence of the parameter m(t).

To improve the perspective of the following analy-

sis, it is convenient to rewrite Eqs. (2) and (3) by us-

ing new variables ai(t)≡yi+κRt

0dt0Θ(t0−tc)δm(t)

and M(t;tc)≡m(t) + 2κ2Θ(t−tc)Rt

tcdt0δm(t0). We

set initial conditions for new introduced variables as

ai(0) = yi(0) = 0. From here, we consider the follow-

ing linear approximation around the origin like

dxi

dt=−X

(M(t;tc)δij +βJij )xj,(8)

dai

dt= 0,(9)

where δij is the Kronecker delta. These linear equations

can describe the dynamics if the eﬀect of the nonlinear

terms is negligible and such situations are expected to

occur from t= 0 to around tc.

Auxiliary variables ai(t)do not evolve in time, and we

only focus on the dynamics of xi(t)whose explicit forms

are given by

xi(t) = X

e−Uij (t;tc)xj(0),(10)

where we introduce the time dependent matrix

Uij (t;tc)≡Rt

0dt00 (M(t00;tc)δij +βJij ). To discuss the

bifurcation delay, its instantaneous eigenvalues play an

important role. They are represented as

Λi(t;tc) = U(t;tc) + βtli,(11)

0 50 100 150 200 250 300

100

200

300

400

500

600

κ=0

κ=0.01

FIG. 1. The bifurcation delay time tbas a function of tcfor

κ= 0 (Eq. (13)) and 0.01 (Eq. (14)).

and we here introduce U(t;tc)≡Rt

0dt00M(t00;tc)related

to m(t). They can take both positive and negative values.

While all Λi(t;tc)are positive, xi(t)approaches the

origin heading in vmin, which is the eigenvector of Jij

corresponding to lmin. Although the origin is no longer a

linearly stable ﬁxed point at t=tc, as long as all Λi(t;tc)

remain positive, xi(t)is still trapped in the neighborhood

of the origin and remains proportionally toward vmin.

This is known as the bifurcation delay, and its time of

trapping can be characterized by the bifurcation delay

time tbthat satisﬁes the following equation:

Λmin(tb;tc)=0,(12)

where Λmin(tb;tc) = U(tb;tc) + βtblmin is the smallest

eigenvalues of Uij . Because of the linear time dependence

of parameters m(t)and δm(t), we can obtain the explicit

form of tbas a function of tcand κ. For κ= 0, the

solution of the above equation is

tb= 2tc,(13)

and for κ6= 0, it is

tb=1

2κ2p4κ2tc+ 1 √3 sin θ

3+ cos θ

3+ 2κ2tc−1,

(14)

where π

2≤θ≤πsatisﬁes the following relation using

z≡κ2tcas θ= tan−12z√16z4+ 12z2+ 3. Due to

our deﬁnition of mc, the solution does not depend on β.

We plot the relations between tband tcin Fig. 1. From

these results, the eﬀective optimization is expected to

occur in T−tb. In addition, tbexhibits similar behavior

in both cases κ= 0 and 0.01. The important thing is

that tbis independent of . No matter how small is,

it takes a ﬁnite value and may aﬀect the results of the

Ising optimizations, which we will see in the numerical

experiments.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

EectsoflocalminimaandbifurcationdelayoncombinatorialoptimizationwithcontinuousvariablesShintaroSato11NTTComputerandDataScienceLaboratories,NTTCorporation,Musashino180-8585,Japan(Dated:November3,2022)CombinatorialoptimizationproblemscanbemappedontoIsingmodels,andtheirgroundstateisgenerallydicultto...

展开>> 收起<<

Eﬀects of local minima and bifurcation delay on combinatorial optimization with continuous variables.pdf

共12页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Eﬀects of local minima and bifurcation delay on combinatorial optimization with continuous variables

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: