# A Novel SEPIC-Ćuk Based High Gain Solar Micro-Inverter for Grid Integration

Arup Ratan Paul, Arghyadip Bhattacharya, and Kishore Chatterjee

###### Abstract

Solar micro-inverters are becoming increasingly popular as they are modular,
and they posses the capability of extracting maximum available power from the
individual photovoltaic (PV) modules of a solar array. For realizing micro-
inverters single stage transformer-less topologies are preferred as they offer
better power evacuation efficacy. A SEPIC-Ćuk based transformer-less micro-
inverter, having only one high frequency switch and four line frequency
switches, is proposed in this paper. The proposed converter can be employed to
interface a 35 V PV module to a 220 V single phase ac grid. As a very high
gain is required to be achieved for the converter, it is made to operate in
discontinuous conduction mode (DCM) for all possible operating conditions.
Since the ground of the each PV modules is connected to the ground of the
utility, there is no possibility of leakage current flow between the module
and the utility. Detailed simulation studies are carried out to ascertain the
efficacy of the proposed micro-inverter. A laboratory prototype of the
inverter is fabricated, and detailed experimental studies are carried out to
confirm the viability of the proposed scheme.

###### Index Terms:

Solar PV, Micro-inverter, Ćuk converter, SEPIC, DCM, dc-ac Conversion.

##  I Introduction

Though the fossil fuel based power generation remains to be the dominant
source of electrical energy, harvesting of energy from the renewable sources
(solar, wind etc.) are strongly being encouraged as they are more environment
friendly, and inexhaustible in nature. In India, as the solar energy is
abundant all over the country throughout the year, it is becoming a viable
alternative to the conventional methods of generation of electrical energy.
The Ministry of New & Renewable Energy, Govt. of India, has set a target of
100 GW grid connected solar power generation by the year 2021-22 under
National Solar Mission, out of which 40 GW should be from the rooftop
installations [1]. The solar modules are generally interfaced to the utility
by employing the following configurations, (i) central inverter, (ii) string
inverter and (iii) micro-inverter. The major advantages of the micro-inverter
over the central and string inverter are as follows [2],

  * •

capability of individual maximum power point tracking (MPPT) of the PV modules
during non-uniform shading,

  * •

the aspect of modularity bestows it with the flexibility in future expansion
of the plant whenever required,

  * •

the existence of plug and play feature imparts flexibility in operation and
coordination of the system.

Typically, the power rating of a micro-inverter is 250-350 W, and hence their
efficiency remains to be low compared to that of the schemes based on central
and string inverters. In order to improve the efficiency of micro-inverters,
lower number of power conversion stages are incorporated [3]. In order to
accomplish this feature, transformer-less single stage topologies for micro-
inverter are generally preferred [4]. However, in case of transformer-less
topologies, there exists a path for the leakage current to flow through the
parasitic capacitance of the PV module to the grid [5, 6]. The flow of leakage
current deteriorates the life of the modules. Further, it posses hazard to the
working personnel as the potential of the mountings of the PV module may
become high with respect to the mother earth. Hence, the magnitude of the
leakage current needs to be limited within the standard limit as stipulated by
various regulatory authorities [7].

Generally the MPP voltage of a PV module is 35 V. However it has to be
interfaced to the single phase 110/230 V grid. Hence, the micro-inverter needs
to have a very high gain, which is one of the main challenges to be addressed.

The requirements pertaining to topological configuration, and its design can
be summarized as follows,

  * •

the magnitude of the leakage current must be within the limits as specified by
various standards,

  * •

the inverter system should have a very high voltage gain to interface a PV
module having a $V_{mpp}$ of 35 V to a single phase 110/230 V ac grid,

  * •

the micro-inverter needs to made as compact as possible.

There are several single stage non-isolated topologies reported in the
literature [4]. The issue related to the leakage current has been addressed to
by shorting the module ground with that of the ac grid [8, 9, 10, 11, 12, 13,
14, 15]. A buck-boost based micro-inverter topology with only one high
frequency switch is proposed in [8]. In [9], a buck-boost based and in [10], a
Ćuk converter based single stage micro-inverter topologies are reported,
wherein the PV module and the ac grid shares the common ground. In [9], the
MPP voltage is chosen to be 55 V, and the ac grid voltage is considered to be
110 V. Though the converter is operated in continuous conduction mode (CCM),
the source current is discontinuous thereby increasing the filtering
requirement at the input side. Moreover, the switches are operated in such a
way that, the decoupling of second order harmonic component is achieved at the
terminals of the PV module. In [10], Ćuk derived topology is reported wherein,
5 high frequency (HF) switches are employed, and the converter is operated in
CCM. A similar power decoupling strategy, as reported in [9], is incorporated
in the topology presented in[10], and reported in [12]. The designed switching
frequency in all the aforesaid configurations are 50 kHz. In [11] and [13], a
four switch topology with different switching configurations have been
proposed. However, all the switches of these converters [9, 10, 11, 13]
operate at high frequency. All these converters are designed to be operated in
CCM. This facilitates the inverters to get interfaced to a single phase
voltage level up to 110 V. A modification to the circuit reported in [10] has
been accomplished by adding another HF switch for controlling the reactive
power fed to the grid, and is presented in [14]. However, the designed
switching frequency is 10 kHz, and hence the size of passive elements are
significantly large. A three switch micro-inverter topology with common ground
is reported in [15] wherein the voltage gain of the converter can be made both
positive and negative, and therefore it does not require the service of an
unfolding circuit but then it involves three inductors in the main converter.

In India, the ac distribution voltage level is 220 V. However, all the
aforementioned converters are designed to get interfaced to single phase 110 V
system, and hence they are not suitable for Indian conditions. However in [16]
a micro-inverter topology is presented, which can be interfaced to a single
phase 220 V grid. However, it requires six switches, out of which, two are
required to be high frequency switches. In view of this an effort has been
made in this paper to design a transformer-less micro-inverter suitable for
getting interfaced to a single phase 220 V grid while utilizing only one high
frequency switch and four line frequency switches in order to reduce the
switch count and reliability of the system.

In order to accomplish these features a SEPIC-Ćuk based micro-inverter
topology is proposed in [17] by the authors of the current paper. The
converter is operated in SEPIC mode during positive half cycle and in Ćuk mode
during negative half cycle. By merging SEPIC and Ćuk configurations into one
topology, the number of HF switches has been reduced to one. The designed
switching frequency of the system is 100 kHz, hence the size of passive
elements have been reduced considerably. The presence of the common ground
between the module and the grid ensures negligible leakage current flow.
However, the circuit was explored for getting interfaced to single phase 110 V
ac grid. In this paper, an attempt has been made to get interfaced to a single
phase 220 V ac, which is suitable for Indian distribution network, utilizing
the converter proposed in [17] from a PV module having $V_{mpp}$ of 35 V.
Detailed simulation studies are carried out on MATLAB/Simulink platform to
ascertain the effectiveness of the proposed converter. A semi-engineered
laboratory prototype of the inverter has been fabricated, and detailed
experimental studies are carried out to confirm the viability of the proposed
scheme.

##  II Principle of Operation of the Proposed Topology

The schematic diagram of the proposed SEPIC-Ćuk based micro-inverter is shown
in Fig. 1. Four line frequency switches are utilized to derive the combine
effect of SEPIC and Ćuk configuration. In [17] the IGBTs are used to realize
the line frequency switches. In this paper MOSFETs are used instead of IGBTs
to reduce the losses. The diode, $D$ is employed to block the reverse current
flow through the four MOSFETs. As sinusoidal current is required to be
injected to the grid, the high frequency switch is applied with switching
pulses which are obtained by comparing the rectified sine wave with a
triangular carrier wave. The instantaneous duty ratio of $S_{1}$ is determined
by multiplying a rectified sine wave with the peak duty ratio, $D_{peak}$. The
switch is operated with $D_{peak}$ when the instantaneous grid voltage is at
its peak. The current through $L_{2}$ is a rectified sine wave having high
frequency switching harmonics superimposed on it. In order to transform this
rectified current into a sinusoidal waveform the four switches,
$S_{2},S_{3},S_{4}$, and $S_{5}$ are appropriately switched. The output
capacitor, $C_{2}$ filters out the high frequency harmonic components form the
output current.

Figure 1: Schematic diagram of Ćuk-SEPIC based micro-inverter with dc side
filter

The inductors of the converter can be chosen in such a way so that the
converter can be operated either in CCM or in DCM. In CCM the voltage gain of
both SEPIC and Ćuk converter is $\frac{d}{1-d}$, wherein $d$ is the duty ratio
of the converter. However, for interfacing the 35 V module to a 220 V ac grid
whose peak voltage is 311 V, the requirement of the duty ratio at the peak of
the ac grid voltage is required to be maintained at 0.9. Operating the
inverter at this high duty ratio, would reduce the operating efficiency
significantly. In order to overcome this limitation, the proposed topology is
operated in DCM to obtain high voltage gain while maintaining reduced duty
ratio compared to that of CCM operation. In case of a SEPIC and Ćuk converter,
current through both $L_{1}$ and $L_{2}$ does not become zero either in CCM or
DCM mode of operation[18, 19]. Further, the DCM operation ensures that turn on
switching loss of $S_{1}$ is negligible. But this is achieved at the cost of
increased peak current that flows through the input inductor.

##  III Modes of Operation and Analysis

In order to simplify the analysis of the inverter, a dc source, $V_{dc}$ is
used instead of a PV module. The convention of voltage polarity and current
direction is shown in Fig. 1. Since the switching frequency is very high
compared to that of the line frequency, it is assumed that, the output voltage
and current requirement is almost constant throughout the switching time
period ($T_{s}$). The ripple in the voltages in the capacitors, $C_{1}$ and
$C_{2}$ can be considered to be negligible. The average value of $v_{C1}$ and
$v_{o}$ over a switching time period are assumed to be $V_{C1}$ and $V_{o}$
respectively. The current and voltage waveforms over a switching cycle is
shown in Fig. 4. The switching time period ($T_{s}$) is divided into three
time intervals as follows, (i) $T_{1}(=DT_{s})$, (ii) $T_{2}$ and (iii)
$T_{3}(=D_{0}T_{s})$ respectively. As $T_{1}+T_{2}+T_{3}=T_{s}$, therefore
$T_{2}=(1-D-D_{0})T_{s}$.

(a)

(b)

(c)

Figure 2: Modes of operation for positive half cycle: (a) Mode-I, (b) Mode-II,
and (c) Mode-III

(d)

(e)

(f)

Figure 3: Modes of operation for negative half cycle: (a) Mode-I, (b) Mode-II,
and (c) Mode-III

###  III-A Positive half cycle (SEPIC mode)

Switch $S_{2}$ and $S_{3}$ both are turned on, while $S_{4}$ and $S_{5}$ are
kept off. At steady state, as the switching time average voltages across
$L_{1}$ and $L_{2}$ are zero,

$\displaystyle V_{C1}$ $\displaystyle=V_{dc}$ (1)

####  III-A1 Mode I ($0\leq t<T_{1}$)

$S_{1}$ is turned on and the current through $L_{1}$ increases as it flows
through the path, $V_{dc}-L_{1}-S_{1}-V_{dc}$ as shown in Fig. 3(a). The
intermediate capacitor, $C_{1}$ gets discharged while the current flowing
through $L_{2}$ increases as it flows through the path,
$C_{1}-S_{1}-S_{2}-L_{2}-C_{1}$. The capacitor, $C_{2}$ supplies power to the
grid in this interval. The diode, $D$ blocks the current through the switch
$S_{3}$ even though it is receiving the gating pulse. Hence,

$\displaystyle V_{dc}$
$\displaystyle=L_{1}\frac{di_{L1}}{dt}=L_{1}\frac{I_{L1p}-I_{L1v}}{DT_{s}}=L_{1}\frac{\Delta
I_{L1}}{DT_{s}}$ (2) $\displaystyle V_{C1}$
$\displaystyle=L_{2}\frac{di_{L2}}{dt}=L_{2}\frac{I_{L2p}-I_{L2v}}{DT_{s}}=L_{2}\frac{\Delta
I_{L2}}{DT_{s}}$ (3) $\displaystyle i_{2}$ $\displaystyle=0$ (4)

where, $\Delta I_{L1}=(I_{L1p}-I_{L1v})$ and $\Delta
I_{L2}=(I_{L2p}-I_{L2v})$.

(a)

(b)

Figure 4: Waveform of different converter parameters over a switching time
period: (a) for positive half cycle and (b) for negative half cycle

####  III-A2 Mode II ($T_{1}\leq t<(T_{1}+T_{2})$)

$S_{1}$ is turned off. The current flows through the path,
$V_{dc}-L_{1}-C_{1}-D-S_{3}-Load-V_{dc}$ as shown in Fig. 3(b) thereby
charging $C_{1}$. The energy stored in $L2$ is transferred to the grid as well
as to $C_{2}$ through the path, $L_{2}-D-S_{3}-Load-S_{2}-L_{2}$. This mode
ends when $i_{L1}=-i_{L2}$. At the end of this mode, let the magnitude of the
currents through $L_{1}$ and $L_{2}$ be $I_{L1m}$ and $I_{L2m}$ respectively.
Therefore,

$\displaystyle V_{dc}-V_{C1}-V_{o}$
$\displaystyle=L_{1}\frac{di_{L1}}{dt}=L_{1}\frac{I_{L1m}-I_{L1p}}{(1-D-D_{0})T_{s}}$
(5) $\displaystyle-V_{o}$
$\displaystyle=L_{2}\frac{di_{L2}}{dt}=L_{2}\frac{I_{L2m}-I_{L2p}}{(1-D-D_{0})T_{s}}$
(6) $\displaystyle i_{2}$ $\displaystyle=i_{L1}+i_{L2}.$ (7)

####  III-A3 Mode III ($(T_{1}+T_{2})\leq t<T_{s}$)

This mode starts when the current through the diode, $D$ becomes zero. The
diode turns off and blocks the current flowing through $S_{3}$. The current
path in this mode is $V_{dc}-S_{2}-L_{2}-C_{1}-L_{1}-V_{dc}$ as shown in Fig.
3(c). Since $V_{C1}=V_{dc}$, the currents in the inductors will remain
unchanged in this mode. The capacitor $C_{2}$ supplies power to the grid in
this interval. Hence,

$\displaystyle I_{L1m}$ $\displaystyle=I_{L1v}=-I_{L2m}=-I_{L2v}.$ (8)

Solving (2), (3), (5), (6) and (8), the expression for the voltage gain can be
obtained as,

$\displaystyle\frac{V_{o}}{V_{dc}}=\frac{D}{\mathinner{\left(1-D-D_{0}\right)}}.$
(9)

###  III-B Negative half cycle (Ćuk Mode):

Switch $S_{4}$ and $S_{5}$ both are turned on, while $S_{2}$ and $S_{3}$ are
kept off. At steady state, as the switching time average voltages across
$L_{1}$ and $L_{2}$ are zero,

$\displaystyle V_{C1}$ $\displaystyle=V_{dc}-V_{o}.$ (10)

####  III-B1 Mode I ($0\leq t<T_{1}$)

$S_{1}$ is turned on and the current through $L_{1}$ increases as it flows
through the path, $V_{dc}-L_{1}-S_{1}-V_{dc}$ as shown in Fig. 3(a). The
intermediate capacitor, $C_{1}$ gets discharged while the current flowing
through $L_{2}$ increases as it flows through the path, $C_{1}-S_{1}-Load-
S_{4}-L_{2}-C_{1}$. The diode, $D$ blocks the current through the switch
$S_{5}$ even though it is receiving the gating pulse. Hence,

$\displaystyle V_{dc}$
$\displaystyle=L_{1}\frac{di_{L1}}{dt}=L_{1}\frac{I_{L1p}-I_{L1v}}{DT_{s}}$
(11) $\displaystyle V_{C1}+V_{o}$
$\displaystyle=L_{2}\frac{di_{L2}}{dt}=L_{2}\frac{I_{L2p}-I_{L2v}}{DT_{s}}.$
(12)

####  III-B2 Mode II ($T_{1}\leq t<(T_{1}+T_{2})$)

$S_{1}$ is turned OFF. The current flows through the path,
$V_{dc}-L_{1}-C_{1}-D-S_{5}-V_{dc}$ as shown in Fig. 3(b) thereby charging
$C_{1}$. The energy stored in $L2$ is transferred to the load as well as to
$C_{2}$ through the path, $L_{2}-D-S_{5}-Load-S_{4}-L_{2}$. This mode ends
when $i_{L1}=-i_{L2}$. At the end of this mode, let the magnitude of the
currents through $L_{1}$ and $L_{2}$ be $I_{L1m}$ and $I_{L2m}$ respectively.
Therefore,

$\displaystyle
V_{dc}-V_{C1}=L_{1}\frac{di_{L1}}{dt}=L_{1}\frac{I_{L1m}-I_{L1p}}{(1-D-D_{0})T_{s}}$
(13) $\displaystyle
V_{o}=L_{2}\frac{di_{L2}}{dt}=L_{2}\frac{I_{L2m}-I_{L2p}}{(1-D-D_{0})T_{s}}.$
(14)

####  III-B3 Mode III ($(T_{1}+T_{2})\leq t<T_{s}$)

This mode starts when the current through the diode, $D$ becomes zero. The
diode turns off and blocks the current flowing through $S_{5}$. The current
path in this mode is $V_{dc}-Load-S_{4}-L_{2}-C_{1}-L_{1}-V_{dc}$ as shown in
Fig. 3(c). Since $V_{C1}=V_{dc}-V_{o}$, the currents in the inductors will
remain unchanged in this mode. Hence,

$\displaystyle I_{L1m}$ $\displaystyle=I_{L1v}=-I_{L2m}=-I_{L2v}.$ (15)

Solving (11)–(15), the expression for the voltage gain can be obtained as,

$\displaystyle\frac{V_{o}}{V_{dc}}$
$\displaystyle=-\frac{D}{\mathinner{\left(1-D-D_{0}\right)}}.$ (16)

###  III-C Combined operation

From (9) and (16) the common expression for the voltage gain can be written
as,

$\displaystyle\frac{V_{o}}{V_{dc}}$
$\displaystyle=\operatorname{sgn}(V_{o})\frac{D}{\mathinner{\left(1-D-D_{0}\right)}}.$
(17)

From (1) and (10), it can be inferred that, the expression for $V_{C1}$ is
different in the positive and in the negative half cycle. By substituting the
expression of $V_{C1}$ from (1) and (10) to (2), (3), (5), (6), (11), (12),
(13) and (14), the model of the system can be simplified as follows:

$\displaystyle L_{1}\frac{\Delta I_{L1}}{DT_{s}}$
$\displaystyle=L_{2}\frac{\Delta I_{L2}}{DT_{s}}=V_{dc}$ (18) $\displaystyle
L_{1}\frac{\Delta I_{L1}}{(1-D-D_{0})T_{s}}$ $\displaystyle=L_{2}\frac{\Delta
I_{L2}}{(1-D-D_{0})T_{s}}=|V_{o}|.$ (19)

From Fig. 4, in both the half cycles the expression of switching time average
of the dc side current is obtained as,

$\displaystyle I_{dc}$ $\displaystyle=I_{L1v}+\frac{\Delta
I_{L1}}{2}(1-D_{0}).$ (20)

Further, from Fig. 4 it can be observed that in the positive half cycle the
wave shape of $i_{2}$ in a switching time period is different from that in the
negative half cycle. Let the switching time average of $i_{2}$ is $I_{2}$, and
it can be approximated to be equal to the grid current, $i_{o}$. It can be
noted that, this waveform is exactly negative to that of $i_{L2}$ in Ćuk mode
of operation. Hence, in this mode, $I_{2}$ is equal to the switching time
average of $i_{L2}$ but with a negative sign. Therefore,

$\displaystyle|I_{2}|_{Cuk}$ $\displaystyle=I_{L2v}+\frac{\Delta
I_{L2}}{2}\mathinner{\left(1-D_{0}\right)}.$ (21)

For SEPIC mode, $I_{2}$ can be expressed as,

$\displaystyle|I_{2}|_{SEPIC}$
$\displaystyle=\frac{\mathinner{\left(1-D-D_{0}\right)}}{2}(I_{L1p}+I_{L2p})$
$\displaystyle=\frac{\mathinner{\left(1-D-D_{0}\right)}}{2}(\Delta
I_{L1}+\Delta I_{L2}).$ (22)

Considering the system to be loss-less,

$\displaystyle\frac{I_{dc}}{|I_{2}|_{SEPIC}}=\frac{V_{o}}{V_{dc}}=\frac{D}{\mathinner{\left(1-D-D_{0}\right)}}.$
(23)

Using (18), (20) and (22),

$\displaystyle\frac{(1-D-D_{0})\frac{DT_{s}V_{dc}}{L_{eq}}}{2I_{L1v}+(1-D_{0})\frac{DT_{s}V_{dc}}{L1}}=\frac{\mathinner{\left(1-D-D_{0}\right)}}{D}$
(24)

where $L_{eq}=L_{1}||L_{2}$. Simplifying (24),

$\displaystyle
I_{L1v}=\frac{DT_{s}V_{dc}}{2}\mathinner{\left[\frac{D}{L_{2}}-\frac{\mathinner{\left(1-D-D_{0}\right)}}{L_{1}}\right]}.$
(25)

If, $I_{L1v}$ has to be positive,

$\displaystyle\frac{L_{2}}{L_{1}}<\frac{D}{1-D-D_{0}}=\frac{V_{o}}{V_{dc}}$
(26)

needs to be satisfied. However in that case when $V_{o}$ becomes zero at the
zero crossing instants as per (26), $L_{2}$ needs to assume a negative value
which is not possible. Hence the value of $L_{2}$ is chosen so that, $I_{L1v}$
remains negative for all possible operating conditions.

In SEPIC mode of operation, the average current through $L_{2}$ is given by,

$\displaystyle I_{L2}$ $\displaystyle=I_{L2v}+\frac{\Delta
I_{L2}}{2}(1-D_{0})$
$\displaystyle=\frac{DT_{s}V_{dc}}{2}\mathinner{\left[\frac{1-D-D_{0}}{L_{1}}-\frac{D}{L_{2}}\right]}+\frac{DT_{s}V_{dc}}{2L_{2}}(1-D_{0})$
$\displaystyle=(1-D-D_{0})\frac{DT_{s}V_{dc}}{2L_{eq}}$
$\displaystyle=\frac{\mathinner{\left(1-D-D_{0}\right)}}{2}(\Delta
I_{L1}+\Delta I_{L2}).$ (27)

From (22) and (27) it can be inferred that, $I_{2}$ is equal to $I_{L2}$ in
SEPIC mode of operation as well. Hence in combined operation,
$I_{L_{2}}=|I_{2}|$, which means that, $i_{L2}$ can be manipulated to control
$i_{o}$. Since the absolute value of the output current expression is same in
both the half cycles it can be inferred that (25) and (26) are also valid for
Ćuk mode of operation as well. Therefore the design condition for $L_{2}$
remains the same in both the half cycles.

Substituting $I_{L1v}$ in (20),

$\displaystyle I_{dc}$
$\displaystyle=\frac{DT_{s}V_{dc}}{2}\Big{[}\frac{D}{L_{2}}-\frac{1-D-D_{0}}{L_{1}}\Big{]}+\frac{DT_{s}V_{dc}}{2L_{1}}(1-D_{0})$
$\displaystyle=\frac{D^{2}T_{s}V_{dc}}{2L_{eq}}.$ (28)

Since the output voltage and current is sinusoidal and they are in phase with
each other,

$I_{dc}(t)=2I_{pv}\sin^{2}\omega t$ (29)

wherein, $I_{pv}$ is the average current drawn from PV module. Further,
$V_{pv}=V_{dc}$ and $D(t)$ being positive, its expression can be written as

$\displaystyle\begin{gathered}D(t)=D_{peak}|\sin\omega
t|\quad\text{where,}\quad
D_{peak}=2\sqrt{\frac{I_{pv}L_{eq}}{T_{s}V_{pv}}}\end{gathered}$ (31)

Hence $D(t)$ needs to be a rectified sine wave with an amplitude of
$D_{peak}$. The value of $D_{peak}$ will be dictated by the irradiance level
experienced by the solar PV module.

##  IV Control Configuration

In the Fig. 5 the schematic of the control block diagram is shown. The rms
value of the output current is measured and compared with the reference,
$I_{orms}^{*}$, which is to be generated by the MPPT controller. The PI
controller processes the error so obtained to determine $D_{peak}$. A
rectified sinusoidal signal having an amplitude of unity is multiplied with
$D_{peak}$ to obtain the instantaneous duty ratio, $D(t)$. The reference sine
wave is generated by employing a single phase PLL. Switching pulses for
$S_{1}$ are obtained by comparing $D(t)$ with a triangular carrier wave.

Figure 5: Block diagram of the control configuration

Switches $S_{2}$ and $S_{3}$ are turned on during the positive half cycle of
the reference sine wave to operate the circuit in SEPIC mode, while $S_{4}$
and $S_{5}$ are turned on during its negative half cycle to operate the
circuit in Ćuk mode.

##  V Selection of Parameters

###  V-A Design of input inductor ($L_{1}$)

At the limiting condition, when the converter operates at the verge of
discontinuous and continuous mode of operation at the peak of the grid voltage
and operating at the rated condition,

$\displaystyle D\leq\frac{v_{o}}{v_{o}+V_{dc}}=\frac{V_{om}}{V_{om}+V_{pv}}$
(32)

where, $V_{om}$ is the amplitude of the grid voltage, $v_{o}$. At this
instant, the switching time average of $i_{L1}$ is $2I_{pv}$. Hence,

$\displaystyle 2I_{pv}$
$\displaystyle=\dfrac{I_{L1p}}{2}=\dfrac{DT_{s}V_{pv}}{2L_{1}}$
$\displaystyle\Rightarrow L_{1}$
$\displaystyle=\dfrac{DT_{s}V_{pv}}{4I_{pv}}\leq\dfrac{T_{s}V_{om}V_{pv}}{4I_{pv}(V_{pv}+V_{om})}$
(33)

###  V-B Design of intermediate capacitor ($C_{1}$)

As the average voltage of $v_{C1}$ is less in SEPIC mode of operation, the
voltage ripple of $C_{1}$ is much higher in this mode compared to the
operation of the inverter in the Ćuk mode. Hence the design of $C_{1}$ is
carried out considering the operation of the converter in SEPIC mode which is
as follows,

$\displaystyle C_{1}$ $\displaystyle=\dfrac{\Delta Q_{C1}}{\Delta
V_{C1}}=\dfrac{(1-D-D_{0})T_{s}I_{L1p}}{2V_{pv}(\frac{\Delta
V_{C1}}{V_{C1}})}=\frac{(DT_{s})^{2}V_{pv}}{2V_{o}L_{1}(\frac{\Delta
V_{C1}}{V_{C1}})}.$ (34)

###  V-C Design of output inductor ($L_{2}$)

The switching time average current through $L_{2}$ is the current fed to the
grid during this interval. The current ripple in $L_{2}$ is derived and
subsequently the design criterion of $L_{2}$ is obtained as follows,

$\displaystyle\Delta I_{L2}=\dfrac{DT_{s}V_{dc}}{L_{2}}\Rightarrow
L_{2}=\dfrac{DV_{pv}T_{s}}{I_{o}(\frac{\Delta I_{L2}}{I_{L2}})}.$ (35)

###  V-D Design of output capacitor ($C_{2}$)

The output capacitor is chosen so that the cut off frequency, $f_{c}$ of the
$L_{2}-C_{2}$ filter is way above the grid frequency, $f_{g}$, and way below
the switching frequency, $f_{s}$, i.e. $f_{g}<<f_{c}<<f_{s}$ and the value of
$C_{2}$ is obtained to be,

$C_{2}=\frac{1}{4\pi^{2}f_{c}^{2}L_{2}}$ (36)

##  VI Simulated Performance of the Proposed Converter

TABLE I: Simulation Parameters: (a) system parameters and (b) converter
parameters

Parameters |  | Values
---|---|---
$V_{dc}$ |  | 35 V
$V_{o}$ |  | 220 V
$f_{g}$ |  | 50 Hz
$f_{s}$ |  | 100 kHz
$R_{o}$ |  | 194 $\Omega$
(a)

Parameters |  | Values
---|---|---
$L_{1}$, $r_{L1}$ |  | 8 $\mu$H, 20 m$\Omega$
$L_{2}$, $r_{L2}$ |  | 100 $\mu$H, 0.6 $\Omega$
$C_{1}$, $r_{C1}$ |  | 0.47 $\mu$F, 30 m$\Omega$
$C_{2}$, $r_{C2}$ |  | 0.47 $\mu$F, 30 m$\Omega$
$L_{g}$ |  | 1 mH
(b)

Detailed simulation studies of the proposed converter have been carried out on
MATLAB/Simulink platform. For simplicity, the grid is replaced by a load
resistance while maintaining the voltage across this resistance to be equal to
220 V ac. In a realistic grid connected system, reference output current,
$I_{rms}^{*}$ would be determined by the MPPT controller. However, in this
simplistic system $I_{rms}^{*}$ is obtained by employing a PI controller which
maintains the terminal voltage of the inverter at 220 V. The parameters chosen
for the simulation model along with the parasitic series resistances of the
converter are shown in Table I.

The proportional gain $K_{p}$ and integral gain $K_{i}$ values of the PI
controller used for controlling $I_{rms}$ are chosen to be 0.5 and 60 s-1
respectively.

Figure 6: Output voltage ($v_{o}$) and current ($i_{o}$) waveform Figure 7:
Waveform of the duty ratio, $d$ Figure 8:  Input inductor current ($i_{L1}$)
over two full cycles (0.04 s) and expanded view of $i_{L1}$ from 4.98 ms to
5.02 ms

The inverter is operated with the system parameters as depicted in Table I(a).
The steady state response of the output voltage and current of the proposed
inverter is shown in Fig. 6. It may be noted that the amplitude of the
sinusoidal output voltage $v_{op}$ of the inverter is 311 V. From Fig. 7 it
can be inferred that the converter is operated with the peak duty ratio
($D_{peak}$) of 0.8. The THD of the output voltage is found to be 1.21%.

The steady state response of the input inductor current is shown in Fig. 8. It
can be inferred from the aforementioned figures that the converter is
operating in DCM.

Figure 9: Intermediate capacitor voltage ($v_{C1}$) waveform

At steady state, the voltage across the intermediate capacitor, $C_{1}$ is
shown in Fig. 9. Form this figure it can be noted that the waveform of
$v_{C1}$ in the positive half cycle is different from that in the negative
half cycle. This difference arises as the converter operates in SEPIC mode
during positive half cycle, and in Ćuk mode during negative half cycle.

Figure 10: Output inductor current ($i_{L2}$) waveform

The steady state response of output inductor current, $i_{L2}$ is shown in
Fig. 10. It can be inferred that the waveform is a rectified sine wave having
switching frequency harmonic components.

Figure 11: Estimated efficiency plot of the proposed inverter

The plot of the estimated efficiency of the inverter with respect to the power
level is shown in Fig. 11. For efficiency estimation, the MOSFET, IPW60R024P7
is considered for $S_{1}$ and MOSFET, IPW60R037P7 is considered for
$S_{2}-S_{5}$. Although the inverter is developing 220 V ac from an input
voltage of 35 V dc, the efficiency of the proposed inverter is comparable with
the inverters which are reported in the literature for developing 110 V ac
from 35-50 V dc[10, 12, 14].

##  VII Experimental Validation

In order to confirm the the viability of the proposed inverter, a 250 W semi-
engineered laboratory prototype of the micro-inverter is fabricated, and
detailed experimental studies have been carried out. The passive components as
mentioned in Table I(b) are used to realize the prototype. In order to
increase the reliability, thin film capacitors are used. Switch $S_{1}$ is
realized by the MOSFET, IPW60R024P7 while $S_{2}-S_{5}$ are realized by
MOSFET, IPW60R037P7. The controller of the inverter is realized by utilising
DSP, TMS320F28355. A 1.5 kW programmable power supply (EPS power supply PSI
9360-15) is used as the input dc source. The photograph of the prototype is
shown in Fig. 12.

Figure 12: Photograph of the experimental prototype Figure 13: Experimental
performance: waveform of output voltage $v_{o}$ and output current $i_{o}$

The measured performance of the inverter is shown Fig. 13 wherein the input
voltage is maintained at 35 V dc and the load resistance of 660 $\Omega$ is
connected across its output terminals. It can be noted that the peak of the
output voltage developed across the load resistance is 311 V rms. In Fig. 15
the measured waveform of $i_{L1}$ is depicted which indicates that at light
load condition the circuit operates in DCM. The operating efficiency of the
inverter while it is made to deliver 73 W is found to be 89.5%. The THD in the
output voltage is 3.84% (Fig. 14) which is well within the stipulated
standards.

Figure 14: Experimental performance: FFT of output voltage waveform Figure 15:
Experimental performance: waveform of input inductor current $i_{L1}$ Figure
16: Experimental performance: voltage waveform across intermediate capacitor
$C_{1}$

The measured voltage across $C_{1}$ while the inverter is operating at steady
state is shown in Fig. 16 which resembles the simulated waveform of Fig. 9.
Since in the positive half cycle, $V_{C1}=V_{dc}$, it can be inferred from
Fig. 16 that the input voltage is maintained at 35 V. In negative half cycle
the peak value of the waveform is around 350 V since it is the sum of the
input voltage and peak of the sinusoidal output voltage, $v_{o}$.

Figure 17: Experimental performance: waveform of output inductor current
$i_{L2}$

The measured steady state current through $L_{2}$ is shown in Fig 17. It may
be noted that it is polluted with high frequency switching harmonics. It also
shows that for this operating condition $I_{L2v}$ remains to be positive.
However after getting manipulated by the the unfolding and filtering circuits
the output current, $i_{o}$ becomes almost sinusoidal current (Fig. 13) having
a THD of 3.84%.

##  VIII Conclusion

A combined SEPIC-Ćuk based micro-inverter topology has been proposed in this
paper. The salient features of the proposed inverter are as follows,

  * •

it operates in SEPIC mode for positive half cycle and in Ćuk mode for negative
half cycle

  * •

the inverter is realized by using single high frequency switch thereby
improving its reliability and cost

  * •

four line frequency switches are employed to interchange the modes between
SEPIC and Ćuk mode, and the switching losses associated with these switches
are negligible

  * •

in order to obtain high gain the inverter is made to operated in DCM. The DCM
operation also ensures that the turn on loss of the high frequency switch is
negligible

  * •

the neutral of the PV module is shorted with that of the grid thereby
eliminating the flow of leakage current

The operating principle, detailed mathematical modelling of the system, design
guidelines for the passive elements, control strategy are presented in the
paper. The viability of the micro-inverter is validated by carrying out
detailed simulation and experimental studies.

## References

  * [1] MNRE, Govt of India. (2020) Overview, MNRE. [Online]. Available: https://mnre.gov.in/img/documents/uploads/0ce0bba7b9f24b32aed4d89265d6b067.pdf
  * [2] A. Bidram, A. Davoudi, and R. S. Balog, “Control and Circuit Techniques to Mitigate Partial Shading Effects in Photovoltaic Arrays,” _IEEE Journal of Photovoltaics_ , vol. 2, no. 4, pp. 532–546, 2012.
  * [3] D. Meneses, F. Blaabjerg, O. Garcia, and J. A. Cobos, “Review and Comparison of Step-up Transformerless Topologies for Photovoltaic AC-module Application,” _IEEE Transactions on Power Electronics_ , vol. 28, no. 6, pp. 2649–2663, 2013.
  * [4] K. Alluhaybi, I. Batarseh, and H. Hu, “Comprehensive Review and Comparison of Single-Phase Grid-Tied Photovoltaic Microinverters,” _IEEE Journal of Emerging and Selected Topics in Power Electronics_ , vol. 8, no. 2, pp. 1310–1329, 2020.
  * [5] E. Gubia, P. Sanchis, A. Ursua, J. Lopez, and L. Marroyo, “Ground Currents in Single-Phase Transformerless Photovoltaic Systems,” _Progress in photovoltaics: research and applications_ , vol. 15, no. 7, pp. 629–650, 2007\.
  * [6] D. Debnath, “Reduced Stage Off-Grid and Buck-Boost Inverter based Grid Connected Solar Photovoltaic Systems,” Ph.D. dissertation, IIT Bombay, 2015\.
  * [7] W. Li, Y. Gu, H. Luo, W. Cui, X. He, and C. Xia, “Topology Review and Derivation Methodology of Single-Phase Transformerless Photovoltaic Inverters for Leakage Current Suppression,” _IEEE Transactions on Industrial Electronics_ , vol. 62, no. 7, pp. 4537–4551, July 2015.
  * [8] H. Patel and V. Agarwal, “A Single-Stage Single-Phase Transformer-Less Doubly Grounded Grid-Connected PV Interface,” _IEEE Transactions on Energy Conversion_ , vol. 24, no. 1, pp. 93–101, March 2009.
  * [9] A. Jamatia, V. Gautam, and P. Sensarma, “Single Phase Buck-Boost Derived PV Micro-inverter with Power Decoupling Capability,” in _Power Electronics, Drives and Energy Systems (PEDES), 2016 IEEE International Conference on_. IEEE, 2016, pp. 1–6.
  * [10] V. Gautam and P. Sensarma, “Design of Ćuk-Derived Transformerless Common-Grounded PV Microinverter in CCM,” _IEEE Transactions on Industrial Electronics_ , vol. 64, no. 8, pp. 6245–6254, 2017.
  * [11] A. Kumar and P. Sensarma, “A four-switch single-stage single-phase buck–boost inverter,” _IEEE Transactions on Power Electronics_ , vol. 32, no. 7, pp. 5282–5292, 2017.
  * [12] A. Jamatia, V. Gautam, and P. Sensarma, “Power Decoupling for Single-Phase PV System Using $\acute{\mathrm{C}}$uk Derived Microinverter,” _IEEE Transactions on Industry Applications_ , vol. 54, no. 4, pp. 3586–3595, July 2018.
  * [13] A. Kumar and P. Sensarma, “New switching strategy for single-mode operation of a single-stage buck–boost inverter,” _IEEE Transactions on Power Electronics_ , vol. 33, no. 7, pp. 5927–5936, 2018.
  * [14] M. Rajeev and V. Agarwal, “Analysis and Control of a Novel Transformer-Less Microinverter for PV-Grid Interface,” _IEEE Journal of Photovoltaics_ , 2018\.
  * [15] A. Sarikhani, M. M. Takantape, and M. Hamzeh, “A Transformerless Common-Ground Three-Switch Single-Phase Inverter for Photovoltaic Systems,” _IEEE Transactions on Power Electronics_ , vol. 35, no. 9, pp. 8902–8909, 2020.
  * [16] A. Bhattacharya, A. R. Paul, and K. Chatterjee, “A Single Phase Single Stage SEPIC-ĆUK Based Non-Isolated High Gain and Efficient Micro-Inverter,” in _2019 IEEE 46th Photovoltaic Specialists Conference (PVSC)_ , 2019, pp. 0708–0715.
  * [17] A. R. Paul, A. Bhattacharya, and K. Chatterjee, “A Novel SEPIC-Ćuk Based High Gain Solar Micro-Inverter for Integration to Grid,” in _2019 National Power Electronics Conference (NPEC)_ , 2019, pp. 1–5.
  * [18] Z. Shi, K. Cheng, and S. Ho, “Boundary Condition Analysis for Ćuk, SEPIC and Zeta Converters Using Energy Factor Concept,” _Journal of Circuits, Systems and Computers_ , vol. 22, 02 2013.
  * [19] V. Eng and C. Bunlaksananusorn, “Modeling of a SEPIC Converter Operating in Discontinuous Conduction Mode,” in _2009 6th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology_ , vol. 01, 2009, pp. 140–143.


degree $\frac{1}{2}(k-1)(k-2)$.

###### Proof.

This proof is similar to the proof of Section 6.3 since the lexicographic
termination has the same dependency graph as the multiphase template. Consider
the following coloring $\eta$.

$\displaystyle\bigwedge_{i=1}^{k}{\color[rgb]{0.7,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.7,0,0}\delta_{i}>0}$
$\displaystyle\land\;$
$\displaystyle\bigwedge_{i=1}^{k}{\color[rgb]{0.7,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.7,0,0}f_{i}(x)>0}$
$\displaystyle\land\;$
$\displaystyle{\color[rgb]{0.7,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.7,0,0}f_{1}(x^{\prime})\leq
f_{1}(x)}$ $\displaystyle\land\;$
$\displaystyle\bigwedge_{i=2}^{k-1}\Big{(}{\color[rgb]{0,0,0.7}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.7}f_{i}(x^{\prime})\leq
f_{i}(x)}\;\lor\;{\color[rgb]{0.7,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.7,0,0}f_{1}(x^{\prime})<f_{1}(x)-\delta_{1}}\;\lor\;\bigvee_{j=2}^{i-1}f_{j}(x^{\prime})<f_{j}(x)-\delta_{j}\Big{)}$
$\displaystyle\land\;$
$\displaystyle\Big{(}{\color[rgb]{0,0,0.7}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.7}f_{k}(x^{\prime})<f_{k}(x)-\delta_{k}}\;\lor\;{\color[rgb]{0.7,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.7,0,0}f_{1}(x^{\prime})<f_{1}(x)-\delta_{1}}\;\lor\;\bigvee_{i=2}^{k-1}f_{i}(x^{\prime})<f_{i}(x)-\delta_{i}\Big{)}$

We check the requirements of Section 6.1:

  1. a)

Every conjunct contains exactly one red atom.

  2. b)

$\\{f_{i},\delta_{i}\\}$ are the connected components of
${\scriptstyle\mathrm{T}}_{k\mathrm{-lex}}$ according to Section 6.1.

  3. c)

The coloring graph $G_{\eta}$ has the edges $([f_{i}],[f_{1}])$ for all $i>1$.
Hence it is acyclic.

We conclude that $\eta$ is a suitable coloring of
${\scriptstyle\mathrm{T}}_{k\mathrm{-lex}}$.

$\displaystyle\deg_{{\scriptstyle\mathrm{T}}_{k\mathrm{-lex}}}(\eta)=\frac{k(k+5)}{2}-(k-1)-3k=\frac{(k-1)(k-2)}{2}.$

The number of blue colored atoms is $k-1$ and the number of connected
components is $k$, therefore, by Section 6.1, this degree is minimal. ∎

######  Example .

The program $\mathbf{P}_{\mathrm{gcd}}$ from Section 4.4 instantiates the
2-lexicographic template. The two invariants $y_{1}\geq 1$ and $y_{2}\geq 1$
are non-decreasing. The coloring $\eta$ from Section 6.3 has degree

$\displaystyle\deg_{{\scriptstyle\mathrm{T}}_{2\mathrm{-lex}}}(\eta)=\frac{1}{2}\cdot
1\cdot 0=0.$

Consequently, by Section 6.2, the generated constraints are linear if we are
considering non-decreasing invariants, and otherwise

$\displaystyle\\#L^{\prime}=\\#L\cdot\\#I\cdot\\#M=1\cdot 6\cdot 2=12$

by Section 6.2.

###  6.4 Overview

Linear ranking function templates use affine-linear function variables to
synthesize a termination argument. When constructing a ranking function from
the assignment to these function variables, the ordinal ranking equivalents
(Section 4.1) of these linear functions turn out to be central components. The
image of the ranking functions constructed from the ordinal ranking
equivalents is an ordinal, namely the _ranking structure_ of
${\scriptstyle\mathrm{T}}$.

The following table gives an overview of the presented ranking function
templates: the affine template, the $k$-phase template, the $k$-piece template
and the $k$-lexicographic template. We state the number of conjuncts and atoms
when written in CNF, the number of connected components in their dependency
graph, their ranking structure and degree (as proven in Section 6.3).

| ${\scriptstyle\mathrm{T}}_{\mathrm{affine}}$ | ${\scriptstyle\mathrm{T}}_{k\mathrm{-phase}}$ | ${\scriptstyle\mathrm{T}}_{k\mathrm{-piece}}$ | ${\scriptstyle\mathrm{T}}_{k\mathrm{-lex}}$
---|---|---|---|---
Conjuncts | $3$ | $2k+1$ | $k^{2}+k+2$ | $3k$
Atoms | $3$ | $\frac{1}{2}k(k+5)$ | $3k^{2}+2k+1$ | $\frac{1}{2}k(k+5)$
Connected comp. | $1$ | $k$ | $k+1$ | $k$
Ranking structure | $\omega$ | $\omega\cdot k$ | $\omega$ | $\omega^{k}$
Degree | $0$ | $\frac{1}{2}k(k-1)$ | $2k^{2}-1$ | $\frac{1}{2}(k-1)(k-2)$

##  Chapter 7 Solving the Constraints

In Chapter 5 we constructed constraints that are satisfiable for a given
linear lasso program only if there exists a ranking function of a specialized
form. These constraints are of the existential fragment of non-linear real
arithmetic. In this chapter we want to discuss strategies available for
solving these constraints.

Since Tarski published the first decision procedure for the first order theory
of the reals [32], several other algorithms have been proposed (an overview
can be found in Grant Passmore’s PhD thesis [26]). The
Grigor’ev–Vorobjov–Theorem states that, in theory, the existential fragment of
non-linear real arithmetic can be solved in single exponential time [13].
However, this bound seems to be only of limited practical relevance [19].
_Cylindrical algebraic decomposition_ (CAD) is most successful in practice,
despite its doubly exponential worst case complexity bound. This is still an
active area of research and recently significant progress has been achieved in
terms of running time [21].

For Farkas’ Lemma based constraints, specialized solving algorithms have been
thought out, e.g. under-approximation using heuristics [9, 30] and bisection
search combined with linear constraint solving [4]. However, we found it is
both feasible and practical to utilize an off-the-shelf SMT solver to find a
solution to small and medium-sized examples. Nonetheless, in this section we
want to examine the CAD algorithm for our case in detail and discuss some
possible runtime mitigation. The goal is to motivate that while the generated
constraints are indeed non-linear, for most practical cases they are still not
vastly more difficult to solve than a linear constraint.

After a brief introduction to cylindrical algebraic decomposition in Section
7.1, we exemplary solve the constraints corresponding to one invariant
consecution in Section 7.2. We show that invariants that depend only on a
constant number of loop inequalities correspond to solutions of the non-linear
system that can be discovered in polynomial time.

###  7.1 Introduction to CAD

Cylindrical algebraic decomposition was first presented by Collins [8]. We
give a brief introduction by example based on Jirstrand’s technical report
[20].

The goal is to find a partition of $\mathbb{R}^{n}$ such that the given set of
polynomials have constant sign on each component. These components are
finitely represented by single points; satisfiability of the non-linear
constraints can be decided by checking these representative points.

######  Example .

Consider the following system of polynomial equations in the two variables $x$
and $y$.

$\displaystyle\begin{aligned} x^{2}+y^{2}-2&<0\\\ x^{3}-y^{2}&=0\end{aligned}$
(7.1)

The two involved polynomials are $p_{1}(x,y)=x^{2}+y^{2}-2$ and
$p_{2}(x,y)=x^{3}-y^{2}$.

$x$$y$ Figure 7.1: The zero sets of the polynomials in (7.1) and some
projections on the $x$-axis (solid dots).

The algorithm works in three phases:

  1. 1.

_The projection phase:_ all points of zero sets corresponding to vertical
tangents, singularities and intersections are projected to the lower dimension
eliminating one variable.

  2. 2.

_The base phase:_ For mono-variant polynomials, all roots can be enumerated
and we thus get a sign-invariant decomposition of $\mathbb{R}^{1}$.

  3. 3.

_The extension phase:_ The technique of the base phase is applied recursively
to lift the sign invariant decomposition from $\mathbb{R}^{i}$ to
$\mathbb{R}^{i+1}$.

In Section 7.1, projection to the $x$-axis yields the solid dots as depicted
in Figure 7.1. These are the two points $(-\sqrt{2},0)$ and $(\sqrt{2},0)$
corresponding to vertical tangents of $p_{1}$, as well as $(0,0)$, the
singularity of $p_{2}$, and finally $(1,0)$, the projection of the
intersection points $(1,1)$ and $(1,-1)$ of $p_{1}$ and $p_{2}$. This gives us
the decomposition on the $x$-axis defined by these four points as well as the
intervals inbetween them. We can evaluate the signs of the polynomials $p_{1}$
and $p_{2}$ on these regions:

$x$ | $(-\infty,-\sqrt{2})$ | $-\sqrt{2}$ | $(-\sqrt{2},0)$ | $0$ | $(0,1)$ | $1$ | $(1,\sqrt{2})$ | $\sqrt{2}$ | $(\sqrt{2},\infty)$
---|---|---|---|---|---|---|---|---|---
$\mathrm{sign}(p_{1}(x))$ | $+$ | $0$ | $-$ | $-$ | $-$ | $-$ | $-$ | $0$ | $+$
$\mathrm{sign}(p_{2}(x))$ | $-$ | $-$ | $-$ | $0$ | $+$ | $+$ | $+$ | $+$ | $+$

Over each region, we can calculate recursively the decomposition of
$\mathbb{R}^{2}$ and check for points that satisfy the system of inequalities
(7.1); in our example, the point $(0,0)$ is a possible solution.

For the precise definition of the projection phase, along with the required
notion of _principal subresultant coefficients_ ($\mathrm{psc}$) used in the
proof of Section 7.2, we reference Jirstrand’s report [20] as this would go
far beyond the scope of this work.

###  7.2 Solving with CAD

As an illustration we discuss the CAD of the invariant consecution. In theory
the arguments offered here also apply to the complete constraints, although
admittedly additional difficulties arise due to the simultaneous presence of
more than one variable that occurs in non-linear operations.

We start with a single invariant consecution (IC4):

$\displaystyle\forall
x,x^{\prime}.\;\psi_{\ell}(x)\land{\scriptstyle\mathrm{LOOP}}_{m}(x,x^{\prime})\rightarrow\psi_{\ell}(x^{\prime})$
(7.2)

For clarity, we drop the indices $m$ of ${\scriptstyle\mathrm{LOOP}}$ and
$\ell$ of $\psi$. Recall that we write

$\displaystyle{\scriptstyle\mathrm{LOOP}}(x,x^{\prime})$ $\displaystyle\equiv
Ax\leq b\;\land\;A^{\prime}x<b^{\prime},$ $\displaystyle\psi(x)$
$\displaystyle\equiv s^{T}x+t\geq 0.$

After applying Motzkin’s Theorem in transformation step 5, we get (IC5) and
fixing the value of $\chi_{2}$ according to Section 6.2, the constraints (IC6)
corresponding to (7.2) are

$\displaystyle\begin{aligned} \exists\lambda,\chi,\mu\geq
0.\;&\lambda^{T}A+\mu^{T}A^{\prime}+(^{0}_{s})^{T}-\chi(^{s}_{0})^{T}=0\\\
&\land\;\lambda^{T}c+\mu^{T}c^{\prime}+(1-\chi)t\leq 0\\\
&\land\;(\lambda^{T}c-\chi t<0\;\lor\;\sum\mu>0)\end{aligned}$ (7.3)

We are solving for the vectors $\lambda,\mu$, $s\in\mathbb{K}^{n}$, and the
variables $\chi\in\mathbb{K}$ and $t\in\mathbb{K}$. The matrices
$A,A^{\prime}$ and vectors $c,c^{\prime}$ are constant. Hence the only non-
linear terms are $\chi(^{s}_{0})^{T}$ and $\chi t$. If we find an assignment
for $\chi$, the constraints become linear and thus can be solved using an SMT
solver for linear arithmetic, which have polynomial runtime complexity [31].

For simplification, we focus on the first disjunct in (7.3) (classical case),
since the other case is structurally very similar. Let $A=(a_{i,j})$,
$\lambda=(\lambda_{1}\ldots\lambda_{m})^{T},$ and $s=(s_{1}\ldots s_{n})^{T}$.
We write (7.3) explicitly:

$\displaystyle\chi$ $\displaystyle\geq 0$ (7.4) $\displaystyle\lambda_{i}$
$\displaystyle\geq 0,$ $\displaystyle\text{for }1\leq i\leq m$ (7.5)
$\displaystyle\sum_{i=1}^{m}a_{i,j}\lambda_{i}-\chi s_{j}$ $\displaystyle=0,$
$\displaystyle\text{for }1\leq j\leq n$ (7.6)
$\displaystyle\sum_{i=1}^{m}a_{i,n+j}\lambda_{i}+s_{j}$ $\displaystyle=0,$
$\displaystyle\text{for }1\leq j\leq n$ (7.7)
$\displaystyle\sum_{i=1}^{m}c_{i}\lambda_{i}-(1-\chi)t$ $\displaystyle<0$
(7.8)

We solve (7.7) for $s_{j}$ and eliminate $s_{j}$ from (7.6) yielding the
following system of equations.

$\displaystyle\chi$ $\displaystyle\geq 0$ (7.9) $\displaystyle\lambda_{i}$
$\displaystyle\geq 0,$ $\displaystyle\text{for }1\leq i\leq m$ (7.10)
$\displaystyle\sum_{i=1}^{m}(a_{i,j}+a_{i,n+j}\chi)\lambda_{i}$
$\displaystyle=0,$ $\displaystyle\text{for }1\leq j\leq n$ (7.11)
$\displaystyle\sum_{i=1}^{m}c_{i}\lambda_{i}-(1-\chi)t$ $\displaystyle\leq 0$
(7.12)

We ignore the constraint (7.12) because in the case where $\chi\neq 1$, we can
always assign $t$ such that this inequality holds. For the projection we
choose the ordering $\lambda_{1},\ldots,\lambda_{m},\chi$. The set of
polynomials for the CAD is

$\displaystyle P=\\{\chi,\lambda_{i}\mid 0\leq i\leq
m\\}\cup\Big{\\{}\sum_{i=1}^{m}(a_{i,n+j}\chi+a_{i,j})\lambda_{i}\mid 0\leq
j\leq n\Big{\\}}.$ (7.13)

In particular, the coefficient polynomials to $\lambda_{i}$ in (7.13) are
linear in $\chi$.

######  Lemma .

In every projection step $k$ in the CAD of (7.13), the set of polynomials

$\displaystyle P_{k}=\\{\lambda_{i}\mid k\leq i\leq
m\\}\;\cup\;\Big{\\{}\sum_{i=k}^{m}p_{i,j}(\chi)\lambda_{i}\mid j\in
J_{k}\Big{\\}}\;\cup\;\\{q_{\ell}(\chi)\mid\ell\in L_{k}\\}$ (7.14)

for suitable index sets $J$ and $L$. The polynomials $p_{i,j}$ and $q_{\ell}$
only involve the variable $\chi$.

###### Proof.

We proceed inductively. Clearly (7.13) satisfies this criterion. Consider the
projection of $\lambda_{k}$.

  * •

For every polynomial $p\in P_{k}$, we take $p(\lambda_{k}=0)$. This yields
$\lambda_{k+1},\ldots,\lambda_{m}$, $\sum_{i=k+1}^{m}p_{i,j}(\chi)\lambda_{i}$
and preserves $q_{\ell}(\chi)$.

  * •

For every polynomial $p\in P_{k}$, we calculate
$\mathrm{psc}_{\lambda_{k}}(p,\frac{\partial p}{\partial\lambda_{k}})$. Since
$p$ is linear in $\lambda_{k}$, this yields the same results as the previous
step.

  * •

For every pair of polynomials $p_{j_{1}},p_{j_{2}}\in P_{k}$, we calculate

$\displaystyle\mathrm{psc}_{\lambda_{k}}(p_{1},p_{2})$ $\displaystyle=\;$
$\displaystyle\mathrm{psc}_{\lambda_{k}}\big{(}\sum_{i=k}^{m}p_{i,j_{1}}(\chi)\lambda_{i},\sum_{i=k}^{m}p_{i,j_{2}}(\chi)\lambda_{i}\big{)}$
$\displaystyle=\;$
$\displaystyle\sum_{i=k+1}^{m}\Big{(}\frac{\mathrm{lcm}(p_{k,j_{1}},p_{k,j_{2}})}{p_{k,j_{1}}}p_{i,j_{1}}(\chi)-\frac{\mathrm{lcm}(p_{k,j_{1}},p_{k,j_{2}})}{p_{k,j_{2}}}p_{i,j_{2}}(\chi)\Big{)}\lambda_{i}.$

This is again of the form given in (7.14). ∎

According to Section 7.2, after $m$ projection steps we are left with a set of
polynomials $P_{m}=\\{q_{\ell}(\chi)\mid\ell\in L_{m}\\}$ dependent only on
the variable $\chi$.

######  Lemma .

The following holds for $P_{m}$.

  1. I.

The degree of any $q_{\ell}\in P_{m}$ is at most $2^{m}$.

  2. II.

$\\#P_{m}\leq{n^{2}}^{m}$.

  3. III.

The number of distinct roots of all $q_{\ell}\in P_{m}$ is bounded by
$2^{m}n^{2^{m}}$.

###### Proof.

  1. I.

Initially, all polynomials are linear. In every projection step, the maximum
degree of polynomials can at most double as the least common multiple’s degree
is less or equal to the degree of the product.

  2. II.

Since each polynomial is connected with every other polynomial, the number of
distinct new polynomials is at most squared in every projection step.

  3. III.

Follows directly from I and II. ∎

More importantly, the number of projection steps depend on the number of
$\lambda$-variables $m$. Motzkin’s Theorem introduces one $\lambda$-variable
for every inequality in (M1). Therefore the runtime scales with the number of
statements relevant to prove the invariant consecution. We assume that in
practice, only a small (maybe even constant) number of inequalities is
required to prove an invariant. This greatly reduces the bound in Section 7.2
III.

######  Theorem .

Invariants that depend only on a constant number of loop inequalities can be
discovered in polynomial time.

###### Proof.

Let $e$ be the bound on the required loop inequalities. There are
$\binom{m}{e}\leq m^{e}$ possibilities to select $e$ of the $m$ inequalities.
We search for a solution to (7.2) by applying CAD to (7.10) and (7.11). The
result is described by Section 7.2 and Section 7.2 states the bound
$2^{e}n^{2^{e}}$ for distinct values of $\chi$. Given possible assignments to
$\chi$, we plug every one of these into the constraints (7.3) and solve using
a solver for linear arithmetic. Satisfiability for linear arithmetic is
decidable in polynomial time [31] and we only have polynomially many values
for $\chi$ to try since $e$ is constant. ∎

Although Section 7.2 gives a polynomial algorithm for solving the constraints,
it is not practical. It would be a great deal more efficient to follow the CAD
algorithm in constructing the solution, which has been omitted here for
simplicity of presentation. Additionally, there is no good reason not to
enlarge $e$ to take more loop inequalities into consideration until a
predefined time limit runs out.

##  Chapter 8 Conclusion

The scope of this work is a new method for synthesizing termination arguments
for linear lasso programs. This method generalizes existing methods and
extends them in various ways. In Section 1.1 we elaborated on how our method
relates to existing research.

We introduced the notion of _ranking function templates_ in Chapter 4 and
discussed the affine, multiphase, piecewise and lexicographic templates in
detail. For the affine-linear functions used in the ranking function
templates, we introduced the notion of _ordinal ranking equivalent_ in order
to naturally build ranking functions using ordinal arithmetic from assignments
for the template’s variables and functions symbols.

The _multiphase ranking function_ is a novel type of ranking function and
received some more detailed investigation. We showed that there are
conjunctive linear lasso programs that do not have a multiphase ranking
function (Section 4.2) and we showed that the existence of a multiphase
ranking function does not entail information about the program’s complexity
(Section 4.2).

Notable formal results in this work are the undecidability proof for
termination of linear lasso programs (Section 3.3) and the theorem regarding
the removal of quantifiers in our constraints (Section 6.2).

Other contributions include the soundness and completeness statements for our
method (Section 5.3 and Section 5.3), the discourse about the treatment of
mixed integer variable domains (Section 5.4), the assessment of the non-linear
dimension before and after our transformations to the constraints (Section
6.2, Section 6.2, Section 6.2 and Section 6.2) and the motivation why solving
the resulting constraints is not necessarily very difficult (Section 7.2). An
overview over the ranking function templates we consider and their properties
can be found in Section 6.4, including their non-linear dimension and their
ordinal ranking structure.

###  8.1 Future Work

For future work, it would be interesting to see new ranking function
templates. There certainly are more types of ranking functions that can be
formalized by ranking function templates. One could investigate the use of
affine-linear, multiphase, piecewise and lexicographic templates as a
‘construction kit’. For example, they could be combined to more general
templates by replacing single affine-linear functions in the lexicographic
template by a piecewise or multiphase ranking function.

Furthermore, it seems vital to implement our method and try it on real world
examples. Only experimental evaluation will tell which ranking function
templates are both computationally feasible and practically relevant. Ideally,
our method would be used in conjunction with a tool that is able to combine
termination arguments for lasso programs to a termination argument for a
complex program.

Moreover, the selection of a ranking function template is not part of our
method. A heuristic could be devised that intelligently suggests a template by
looking at the program code. This could reduce required human interaction
and/or speed up the termination argument synthesis.

Our method is not complete on integer lasso programs as discussed in Section
5.4. Possibly there is a way of making the polyhedra integral even though they
contain free variables. Otherwise, a different approach for integers needs to
be developed. As integer variables are extremely common in real life code,
this topic requests further attention.

The complexity of our method is centrally determined by the complexity of non-
linear algebraic constraint solving. Any progress being made in this field
improves the applicability of our method. Non-linear constraint solving is an
active area of research and recent progress [21] suggests that algorithmic
improvements are not yet exhausted.

Another plot line unfinished is the decidability of the termination of
conjunctive linear lasso programs. We conjectured in Section 3.3 that this is
decidable, but a proof remains due.

#### Acknowledgements

I would like to thank my supervisor Matthias Heizmann for all his patience and
support. The dialogue with him and his continued encouragement was invaluable
to this work. Furthermore, I extend my gratitude to Fabian Reiter and Pascal
Raiola for their very helpful corrections and suggestions.

### Errata

This is an error corrected version of the original thesis, updated last on
September 2, 2024. The most important changes are:

  * •

Removed Lemma 3.13 because its statement was false. Thanks go to Amir Ben-
Amram for pointing this out.

  * •

Added missing $\xi_{\ell}$ in Equation TI6.

  * •

Fixed step size in Section 4.1.

  * •

Corrected the coloring of ${\scriptstyle\mathrm{T}}_{k\mathrm{-lex}}$ in
Section 6.3.

  * •

Fixed Typos

## References

  * [1] E. Albert, P. Arenas, S. Genaim, and G. Puebla.  Closed-form upper bounds in static cost analysis.  J. Autom. Reasoning, 46(2):161–203, 2011.
  * [2] A. M. Ben-Amram and S. Genaim.  On the linear ranking problem for integer linear-constraint loops.  In POPL, pages 51–62, New York, NY, USA, 2013. ACM.
  * [3] A. M. Ben-amram, S. Genaim, and A. N. Masud.  On the termination of integer loops.  In VMCAI, pages 72–87. Springer, 2012.
  * [4] A. R. Bradley, Z. Manna, and H. B. Sipma.  Linear ranking with reachability.  In CAV, pages 491–504. Springer, 2005.
  * [5] A. R. Bradley, Z. Manna, and H. B. Sipma.  The polyranking principle.  In ICALP, pages 1349–1361. Springer, 2005.
  * [6] M. Braverman.  Termination of integer linear programs.  In CAV, pages 372–385. Springer, 2006.
  * [7] P. J. Charles, J. M. Howe, and A. King.  Integer polyhedra for program analysis.  In AAIM, pages 85–99. Springer, 2009.
  * [8] E. G. Collins.  Quantifier elimination for real closed fields by cylindrical algebraic decomposition.  In Automata Theory and Formal Languages, volume 33, pages 134–183. Springer, 1975.
  * [9] M. A. Colón, S. Sankaranarayanan, and H. B. Sipma.  Linear invariant generation using non-linear constraint solving.  In CAV, pages 420–432. Springer, 2003.
  * [10] B. Cook, J. Fisher, E. Krepska, and N. Piterman.  Proving stabilization of biological systems.  In VMCAI, pages 134–149, 2011.
  * [11] B. Cook, A. Podelski, and A. Rybalchenko.  Terminator: Beyond safety.  In CAV, pages 415–418, 2006.
  * [12] H.-D. Ebbinghaus, J. Flum, and W. Thomas.  Mathematical Logic.  Springer, 1984.
  * [13] D. Y. Grigor’ev and J. N. N. Vorobjov.  Solving systems of polynomial inequalities in subexponential time.  Journal of Symbolic Computation, 5(1-2):37–64, 1988.
  * [14] S. Gulwani and F. Zuleger.  The reachability-bound problem.  In PLDI, pages 292–304, 2010.
  * [15] A. Gupta, T. A. Henzinger, R. Majumdar, A. Rybalchenko, and R.-G. Xu.  Proving non-termination.  In POPL, pages 147–158, 2008.
  * [16] W. R. Harris, A. Lal, A. V. Nori, and S. K. Rajamani.  Alternation for termination.  In SAS, pages 304–319, 2010.
  * [17] M. Hartmann.  Cutting planes and the complexity of the integer hull.  Technical report, Ithaca, NY, USA, 1988.
  * [18] M. Heizmann, J. Hoenicke, J. Leike, and A. Podelski.  Linear ranking for linear lasso programs.  In ATVA, 2013.
  * [19] H. Hong and C. L.  Comparison of several decision algorithms for the existential theory of the reals.  Technical report, 1991.
  * [20] M. Jirstrand.  Cylindrical algebraic decomposition – an introduction.  Technical report, S-581 83 Linköping, Sweden, 1995.
  * [21] D. Jovanović and L. D. Moura.  Solving non-linear arithmetic.  In IJCAR, pages 339–354. Springer, 2012.
  * [22] D. Kroening, N. Sharygina, S. Tonetta, A. Tsitovich, and C. M. Wintersteiger.  Loop summarization using abstract transformers.  In ATVA, pages 111–125, 2008.
  * [23] D. Kroening, N. Sharygina, A. Tsitovich, and C. M. Wintersteiger.  Termination analysis with compositional transition invariants.  In CAV, pages 89–103, 2010.
  * [24] K. Kunen.  Set Theory.  Elsevier, 1980.
  * [25] M. Minsky.  Recursive unsolvability of post’s problem of ’tag’.  Annals of Mathematics, 74(3):437–455, 1961.
  * [26] G. O. Passmore.  Combined Decision Procedures for Nonlinear Arithmetics, Real and Complex.  PhD thesis, University of Edinburgh, 2011.
  * [27] A. Podelski and A. Rybalchenko.  A complete method for the synthesis of linear ranking functions.  In VMCAI, pages 239–251. Springer, 2004.
  * [28] A. Podelski and S. Wagner.  A sound and complete proof rule for region stability of hybrid systems.  In HSCC, pages 750–753, 2007.
  * [29] A. Rybalchenko.  Constraint solving for program verification theory and practice by example.  In CAV, pages 57–71. Springer, 2010.
  * [30] S. Sankaranarayanan, H. B. Sipma, and Z. Manna.  Constraint-based linear-relations analysis.  In SAS, pages 53–68. Springer, 2004.
  * [31] A. Schrijver.  Theory of linear and integer programming.  Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.
  * [32] A. Tarski.  A decision method for elementary algebra and geometry.  Technical report, RAND Corporation, 1951.
  * [33] A. Tiwari.  Termination of linear programs.  In CAV, pages 70–82. Springer, 2004.