# Transforms for Multiplicative and Fractional Programming with Broad
Applications in Edge Computing and Communication Networks

Yitong Wang  Chang Liu  Jun Zhao The authors are all with the School of
Computer Science and Engineering, Nanyang Technological University (NTU),
Singapore. (Contact E-mail: JunZHAO@ntu.edu.sg). A 6-page short version
containing partial results is under review for the 2024 IEEE International
Conference on Communication (ICC) in [1]. IEEE Communications Society (ComSoc)
writes “It is possible to submit the journal and conference version at the
same time” at https://www.comsoc.org/publications/journals/ieee-transactions-
wireless-communications/conference-vs-journal

###### Abstract

Multiplicative Programming (MP) pertains to a spectrum of optimization
problems that involve product term(s). As computational paradigms of
communication systems continue to evolve, particularly concerning the
offloading strategies of computationally intensive tasks simultaneously to
centralized or decentralized servers, designing or optimizing effective
communication systems with MP techniques becomes increasingly indispensable.
Similarly, Fractional Programming (FP) is another significant branch in the
optimization domain, addressing various essential scenarios in communication.
For instance, in minimization optimization problems, transmission power and
processing delay of communication systems are considered critical metrics. In
a very recent JSAC paper by Zhao et al. [2], an innovative transform (Zhao’s
Optimization Transform) was proposed for solving the minimization of MP and FP
problems. Nevertheless, the resolution of optimization problems in
communication systems encounters several limitations when adopting Zhao’s
optimization transform, especially in MP problems. Primarily, objective
functions proposed in these optimization problems typically involve sum-of-
products terms and the optimization variables are always discrete leading to
NP-hard problems. Furthermore, multiple functions mapping to the non-negative
domain in these scenarios can result in auxiliary variables being zero values,
while the same situation is avoidable in FP problems due to the presence of
these functions in the denominator. In this paper, we introduce an updated
transform, building on the foundations of Zhao’s original method, designed to
effectively overcome these challenges by reformulating the original problem
into a series of convex or concave problems. This introduced problem
reformulation provides a superior iteration algorithm with demonstrable
convergence to a stationary point. Additionally, we conduct an in-depth
analysis of application scenarios for the proposed updated transform and
provide comparative evaluations with traditional MP methodologies.

###### Index Terms:

Non-convex optimization, multiplicative programming, fractional programming,
sum-of-products, edge computing, communication networks.

##  I Overview

Fractional programming (FP), which solves the optimization problem consisting
of ratio term(s), is a critical tool in the development of current
communication systems and the enhancement of communication application
performance. In a very recent paper accepted to JSAC, Zhao et al. [2]
introduced an innovative transformation technique, referred to as Zhao’s
Transform. This method is tailored to tackle the minimization of FP problems,
characterized by sum-of-ratios that are commonly encountered in the design of
resource allocation strategies within wireless communication networks. The
previously proposed Zhao’s optimization transform distinguishes itself by
demonstrating superior performance when compared to previous optimization
techniques, such as Dinkelbach’s Method [3]. This enhancement in performance
underscores its potential effectiveness and applicability in optimizing
complex communication network scenarios.

Zhao’s Transform has great potential not only in FP problems but is equally
effective in multiplicative programming (MP) problems [4]. MP in wireless
networks is a complex optimization technique used to enhance various aspects
of system performance. This approach primarily involves solving nonlinear
problems where the objective function is a product of several variables or
functions, such as signal strength, bandwidth, or power levels. These
optimization problems are crucial in areas like resource allocation [5], where
it is formulated to optimize the distribution of network resources for maximum
utility [6], and in physical layer security, for relaying selection strategy
to improve system robustness [7]. The non-linear and non-convex properties of
these problems make them challenging, necessitating advanced and heuristics
algorithms, including gradient-based methods [8], alternative optimization
(AO) approach [9], and genetic algorithms [10], to find optimal solutions.
However, these methods still have limitations in terms of the computation
complexity, convergence rate, and sensitivity of parameter modification.

In this paper, we extend the potential of Zhao’s Transform in the MP problems
with multiple products to prove the effectiveness of this proposed transform.
Unique obstacles, which would not be encountered in FP problems, are met in
applying the transform to MP problems. First, there are some common scenarios
related to MP problems having the special case that $B(\bm{x})=0$, where this
special case can be unconsciously avoided in formulated FP problems as
$B(\bm{x})$ participating in the algorithm as denominators. However, this case
cannot be disregarded in the multiplicative case. Therefore, the first
obstacle is introduced that auxiliary variables derived from $B(\bm{x})$ will
equal zero, which conflicts with the iteration algorithms where auxiliary
variables will be used as denominators. Furthermore, there are some other
cases relating to discrete or mixed discrete-continuous optimization variables
that result in the optimization problems as NP-hard problems, while the
proposed Zhao’s Transform focuses on the continuous variables. Therefore,
resolving the NP-hard problem due to discrete variables becomes another
challenge.

In an effort to broaden the applicability of Zhao’s Transform across a wider
range of wireless communication networks, particularly for the purposes of
design enhancement and optimization, we introduce an Updated Transform in this
paper. This novel transform builds upon the foundational principles of the
original transform in [2]. Its primary aim is to address and overcome the
challenges previously identified in the context of wireless communication
networks.

The goals of this paper are to show the scalability of Zhao’s Transform and
the generalizability of Updated Transform. The main contributions of this
paper are as follows:

  * •

Scalability of Zhao’s Transform: In this paper, we review the proposed
transform by Zhao et al. in [2] and make a comprehensive conclusion of this
transform in FP problems and MP problems under the assumptions of functions
$A(\bm{x})$ and $B(\bm{x})$. Additionally, we describe various corollaries
that emerge in different scenarios, with a particular emphasis on optimization
challenges associated with sum-of-ratios and sum-of-products formulations.
This comprehensive conclusion aims to illustrate the broader applicability of
the former Zhao’s transform proposed in diverse computational contexts.

  * •

Updated Transform for the Intractable Obstacles: We investigate the proposed
updated transform in this paper and mainly focus on resolving the challenges
mentioned above including $B(\bm{x})=0$ and optimization variables which are
discrete or mixed discrete-continuous. After illustrating each of these
challenges, we analyze the essential properties of the updated transform and
further present the corollaries derived.

  * •

Joint Partial Offloading Ratio and Computation Resource: To validate the
effectiveness, the proposed updated transform is first applied to the
minimization of the overall computation latency of a communication network by
jointly optimizing the partial offloading rate and computation frequencies of
the mobile edge server and local devices (i.e., the product of the offloading
ratio of computational task and the cost function of the communication
system). Instead of adopting existing toolboxes to solve the problem, we
obtain the optimum by adopting Karush-Kuhn-Tucker (KKT) conditions analysis
and verify the generalizability of the proposed updated transform at
$B(\bm{x})=0$.

  * •

Joint User Association and Resource Allocation: We also apply the proposed
updated transform into the 5G heterogeneous mobile edge computing system to
make an in-depth analysis on the minimization of the energy consumption and
processing delay by jointly optimizing the user association decision vector,
computation offloading vector, computation resource, and transmission power.
In this application scenario, we proposed a novel algorithm with the
integration of the introduced updated transform and successive convex
approximation (SCA) technique to tackle the NP-hard optimization problems.

Throughout this paper, we use $\mathbb{R}$ to denote the set of real numbers,
$\mathbb{R}_{+}$ to denote the set of non-negative real numbers, and
$\mathbb{R}_{++}$ to denote the set of positive real numbers. The finite-
dimension vector space consisting of real $n$-dimensional vectors is denoted
as $\mathbb{R}^{n}$. $\mathbb{N}$ is used to represent the set of natural
numbers. The bold lower-case letter represents a vector. The script capital
denotes a set. The bold script capital denotes a vector space in the proposed
algorithm. In general, for a vector $\bm{v}$ in this paper, we denote its
$i$-th dimension by $v_{i}$.

##  II Zhao’s Transform[2]

In this section, we have a brief review of the previously proposed Zhao’s
Transform in terms of FP and MP. More details and proofs can be found in the
prior paper [2].

###  II-A Convexity and Concavity

In this subsection, we introduce basic definitions pertaining to convexity and
concavity. To begin with,

######  Definition 1 (Convex set).

A set $\mathcal{C}$ is convex if the line segment between any two points in
$\mathcal{C}$ lies in $\mathcal{C}$, i.e., if for
$\bm{x}_{1},\bm{x}_{2}\in\mathcal{S}$ and $t\in[0,1]$, we have
$t\bm{x}_{1}+(1-t)\bm{x}_{2}\in\mathcal{C}$.

Let $f(\bm{x})$ be a function defined on a convex set $\mathcal{S}$, where
$\mathcal{S}$ is also a subset of a real vector space. Then we have the
following from (3.1) of [11].

######  Definition 2 (Convexity).

$f$ is convex in $\bm{x}$ if and only if for any
$\bm{x}_{1},\bm{x}_{2}\in\mathcal{S}$ and $t\in[0,1]$, it holds that
$f(t\bm{x}_{1}+(1-t)\bm{x}_{2})\leq tf(\bm{x}_{1})+(1-t)f(\bm{x}_{2})$.

With convexity above, Lemma 1 below presents concavity.

######  Lemma 1 (Convexity versus Concavity).

A function $f$ is said to be concave if and only if $-f$ is convex.

###  II-B Fractional Programming

######  Theorem 1 (Rigorously and formally presenting the fractional
programming transform of Section IV in [2]).

Let $\bm{x}$ be an $n$-dimensional vector. Consider functions
$A(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$,
$B(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$, and
$E(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}$ which all have definitions on
a set $\mathcal{X}\subseteq\mathbb{R}^{n}$. Functions $A(\bm{x})$ and
$B(\bm{x})$ are respectively convex and concave with respect to $\bm{x}$. We
aim to solve the following minimization problem $\mathbb{P}_{1}$, which
belongs to fractional programming with a single ratio:

Problem $\mathbb{P}_{1}$:
$\displaystyle\underset{\bm{x}}{\text{minimize}}\hskip
15.0ptE(\bm{x})+\frac{A(\bm{x})}{B(\bm{x})}$ (1) $\displaystyle\text{subject
to}\hskip 14.0pt\bm{x}\in\mathcal{X}.$ (1a)

To solve Problem $\mathbb{P}_{1}$, we will solve Problem $\mathbb{P}_{2}$
below. After defining

$\displaystyle
F(\bm{x},y)\coloneqq[A(\bm{x})]^{2}y\\!+\\!\cfrac{1}{4[B(\bm{x})]^{2}y},\text{~{}where
$y\in\mathbb{R}_{++}$,}$ (2)

we consider

Problem $\mathbb{P}_{2}$:
$\displaystyle\underset{\bm{x},y}{\text{minimize}}\hskip
15.0ptE(\bm{x})+F(\bm{x},y)$ (3) $\displaystyle\text{subject to}\hskip
14.0pt\bm{x}\in\mathcal{X}\text{ and }y\in\mathbb{R}_{++},$ (3a)

The relationship between Problems $\mathbb{P}_{1}$ and $\mathbb{P}_{2}$ is as
follows: If the alternating optimization method (detailed in Algorithm 1) to
solve Problem $\mathbb{P}_{2}$ converges to $(\bm{x}^{*},y^{*})$, then under
Assumption 1 (presented later), $\bm{x}^{*}$ is a stationary point for solving
Problem $\mathbb{P}_{1}$.

######  Assumption 1.

Slater’s condition holds for Problem $\mathbb{P}_{2}(y)$ of (6), where
$\mathbb{P}_{2}(y)$ belongs to convex optimization. Specifically, when we
write out the constraint “$\bm{x}\in\mathcal{X}$” of (6a) according to the
standard form of (4.1) in [11] as follows:

$\displaystyle\mathcal{Q}_{q}(\bm{x})\leq 0,$ for $q=1,2,\ldots,Q$, (4a)
$\displaystyle\mathcal{R}_{r}(\bm{x})=0,$ for $r=1,2,\ldots,R$, (4b)
$\displaystyle\bm{x}\in\mathbb{R}^{n},$ (4c)

Slater’s condition means there exists $\widehat{\bm{x}}\in\mathbb{R}^{n}$ such
that

$\displaystyle\mathcal{Q}_{q}(\widehat{\bm{x}})<0,$ for $q=1,2,\ldots,Q$, (5a)
$\displaystyle\mathcal{R}_{r}(\widehat{\bm{x}})=0,$ for $r=1,2,\ldots,R$. (5b)

In other words, for $\widehat{\bm{x}}$, (5a) “strictly” holds while (4b)
holds.

######  Remark 1.

Theorem 1 means that to solve Problem $\mathbb{P}_{1}$ which involves the
fraction $\frac{A(\bm{x})}{B(\bm{x})}$, we can introduce an additional
variable $y$, replace $\frac{A(\bm{x})}{B(\bm{x})}$ with $F(\bm{x},y)$ in Eq.
(2) to obtain Problem $\mathbb{P}_{2}$, and then solve Problem
$\mathbb{P}_{2}$ via alternating optimization (AO).

######  Remark 2.

The AO process to solve Problem $\mathbb{P}_{2}$ means solving Problems
$\mathbb{P}_{2}(y)$ and $\mathbb{P}_{2}(\bm{x})$, where $\mathbb{P}_{2}(y)$ is
to optimize $\bm{x}$ after $y$ in Problem $\mathbb{P}_{2}$ is given, and
$\mathbb{P}_{2}(\bm{x})$ is to optimize $y$ after $\bm{x}$ in Problem
$\mathbb{P}_{2}$ is given. Specifically, Problems $\mathbb{P}_{2}(y)$ and
$\mathbb{P}_{2}(\bm{x})$ are as follows:

Problem $\mathbb{P}_{2}(y)$:
$\displaystyle\underset{\bm{x}}{\text{minimize}}\hskip
15.0ptE(\bm{x})+F(\bm{x},y)$ (6) $\displaystyle\text{subject to}\hskip
14.0pt\bm{x}\in\mathcal{X},$ (6a)

and

Problem $\mathbb{P}_{2}(x)$: $\displaystyle\underset{y}{\text{minimize}}\hskip
15.0ptE(\bm{x})+F(\bm{x},y)$ (7) $\displaystyle\text{subject to}\hskip
14.0pty\in\mathbb{R}_{++},$ (7a)

From the expression of $F(\bm{x},y)$ in Eq. (2), it is straightforward to
obtain that Problem $\mathbb{P}_{2}(x)$ just means setting $y$ as
$\frac{1}{2A(\bm{x})B(\bm{x})}$. Based on the above, Algorithm 1 contains the
AO procedure to solve Problem $\mathbb{P}_{2}$. In Algorithm 1, Line 1
optimizes $\bm{x}$ given $y$, while Line 1 optimizes $y$ given $\bm{x}$.

1

2Initialize $j\leftarrow-1$ and a feasible $\bm{x}^{(0)}$ which satisfies
Problem $\mathbb{P}_{2}$’s constraint(s); i.e., $\bm{x}^{(0)}\in\mathcal{X}$;

3repeat

4

5 Let $j\leftarrow j+1$;

6 With $\mathbb{P}_{2}(y)$ in (6) denoting the problem of $\mathbb{P}_{2}$
given $y$, we use the Karush-Kuhn-Tucker (KKT) conditions or optimization
tools like CVX [12] to solve $\mathbb{P}_{2}(y^{(j)})$, which is a convex
optimization problem with $\bm{x}$ as the decision variable. Denote the
obtained solution for $\bm{x}$ as $\bm{x}^{(j+1)}$;
//Comment: Line 1 above optimizes $\bm{x}$ given $y$.

7 $y\leftarrow\frac{1}{2A(\bm{x}^{(j+1)})B(\bm{x}^{(j+1)})}$;
//Comment: Line 1 above optimizes $y$ given $\bm{x}$.

8until the relative difference between
$\textrm{OBJ}_{\mathbb{P}_{2}}(\bm{x}^{(j)},y^{(j)})$ and
$\textrm{OBJ}_{\mathbb{P}_{2}}(\bm{x}^{(j+1)},y^{(j+1)})$ is no greater than
$\epsilon_{1}$ for a small positive number $\epsilon_{1}$ (i.e.,
$\frac{\textrm{OBJ}_{\mathbb{P}_{2}}(\bm{x}^{(j)},y^{(j)})}{\textrm{OBJ}_{\mathbb{P}_{2}}(\bm{x}^{(j+1)},y^{(j+1)})}-1\leq\epsilon_{1}$),
where $\textrm{OBJ}_{\mathbb{P}_{2}}(\bm{x},y)$ denotes the objective function
of $\mathbb{P}_{2}$;

Algorithm 1 Solve Problem $\mathbb{P}_{2}$ of (3) using alternating
optimization. Based on Theorem 1, under Assumption 1 which holds in practical
problems of interest, the obtained solution for $\bm{x}$ from Algorithm 1
converges to a stationary point for solving the fractional programming problem
$\mathbb{P}_{1}$.

######  Remark 3.

Assumption 1 ensures that the Karush–Kuhn–Tucker (KKT) conditions are both
necessary and sufficient to find the optimal solution of the convex
optimization problem111Note that convex optimization may even have so
solution; e.g., minimizing $x$ subject to $x\in\mathbb{R}$. However, this
paper excludes the very degenerate case where there is even no solution for
the convex optimization problem $\mathbb{P}_{2}(y)$ since that case won’t
appear in practical problems that are of interest. $\mathbb{P}_{2}(y)$.

This proposed transform can also be applied to the optimization problems with
sum-of-ratios terms which are illustrated as follows.

######  Corollary 1 (Extending Theorem 1 to solving sum-of-ratios problems).

Given the $K$ pairs of positive functions
$A_{k}(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$ and
$B_{k}(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$ where
$n\in\mathbb{N}$ and $k=1,2,...,K$, and a function
$E(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$, the minimization problem
with multiple ratio terms is:

Problem $\mathbb{P}_{3}$:
$\displaystyle\underset{\bm{x}}{\text{minimize}}\hskip
15.0ptE(\bm{x})+\sum_{k=1}^{K}\frac{A_{k}(\bm{x})}{B_{k}(\bm{x})}$ (8)
$\displaystyle\text{subject to}\hskip 14.0pt\bm{x}\in\mathcal{X}.$ (8a)

This problem can also be transformed to:

Problem $\mathbb{P}_{4}$:
$\displaystyle\underset{\bm{x},\bm{y}}{\text{minimize}}\hskip
15.0ptE(\bm{x})+\sum_{k=1}^{K}F_{k}(\bm{x},y_{k})$ (9)
$\displaystyle\text{subject to}\hskip 14.0pt\bm{x}\in\mathcal{X}\text{ and
}\bm{y}\in\mathbb{R}^{K},$ (9a)

where we define $F_{k}(\bm{x},y_{k})$ below for each $k=1,2,\ldots,K$:

$\displaystyle
F_{k}(\bm{x},y_{k})\coloneqq[A_{k}(\bm{x})]^{2}y_{k}+\frac{1}{4[B_{k}(\bm{x})]^{2}y_{k}},$

and the collection of variables $[y_{1},y_{2},...,y_{K}]$ is denoted as
$\bm{y}$ with
$y_{k}^{(t)}\coloneqq\cfrac{1}{2A_{k}(\bm{x}^{(t)})B_{k}(\bm{x}^{(t)})}\in\mathbb{R}_{++}$,
where $t$ is the iteration index.

By transforming the single-ratio (resp., multiple-ratio) problem to a series
of sub-problems, the global optimum (resp., stationary point) is obtained when
the function $E(\bm{x})$ is convex of the optimization variables [13].

###  II-C Multiplicative Programming

Based on the prior paper [2], Zhao’s optimization transform not only can be
adapted to the FP but also to the MP. To further reveal the generalization of
the proposed transform, we next delve into the potential of this transform to
MP techniques.

######  Theorem 2 (Single-Product Problem).

Given a non-empty feasible set $\mathcal{X}$, a pair of positive convex
functions $A(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$ and
$B(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$, where $n\in\mathbb{N}$,
and a function $E(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$, a
minimization MP with single product is:

$\displaystyle\underset{\bm{x}}{\text{minimize}}\hskip
15.0ptE(\bm{x})+A(\bm{x})B(\bm{x})$ (10) $\displaystyle\text{subject to}\hskip
14.0pt\bm{x}\in\mathcal{X}.$ (10a)

Based on the characteristics as well as the generality of the functions (e.g.
Shannon’s formula and edge-device association formula) in the wireless
communication system, the objective function (i.e. the product of two convex
functions) does not always maintain the convexity of the optimization
variables (e.g. offloading ratios and power allocations). The extension of the
proposed transform is further expanded and this MP problem is reformulated as:

$\displaystyle\underset{\bm{x},y}{\text{minimize}}\hskip
15.0ptE(\bm{x})+F(\bm{x},y)$ (11) $\displaystyle\text{subject to}\hskip
14.0pt\bm{x}\in\mathcal{X},$ (11a)

where

$\displaystyle
F(\bm{x},y)\coloneqq[A(\bm{x})]^{2}y+\frac{[B(\bm{x})]^{2}}{4y},$

and the introduced auxiliary variable $y\in\mathbb{R}_{++}$ in the
$t$-iteration is equal to
$y^{(t)}\coloneqq\frac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})}$.

######  Corollary 2 (Sum-of-Products Problem).

Given the $K$ pairs of positive convex functions
$A_{k}(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$ and
$B_{k}(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$ where
$n\in\mathbb{N}$ and $k=1,2,...,K$, and a function
$E(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$, the minimization problem
with multiple product terms is:

$\displaystyle\underset{\bm{x}}{\text{minimize}}\hskip
15.0ptE(\bm{x})+\sum_{k=1}^{K}A_{k}(\bm{x})B_{k}(\bm{x})$ (12)
$\displaystyle\text{subject to}\hskip 14.0pt\bm{x}\in\mathcal{X},$ (12a)

which is reformulated to:

$\displaystyle\underset{\bm{x},\bm{y}}{\text{minimize}}\hskip
15.0ptE(\bm{x})+\sum_{k=1}^{K}F_{k}(\bm{x},y_{k})$ (13)
$\displaystyle\text{subject to}\hskip 14.0pt\bm{x}\in\mathcal{X},$ (13a)

where

$\displaystyle
F(\bm{x},y_{k})\coloneqq[A_{k}(\bm{x})]^{2}y_{k}+\frac{[B_{k}(\bm{x})]^{2}}{4y_{k}},~{}\forall
k,$

$\bm{y}$ refers to $[y_{1},y_{2},...,y_{K}]$, where
$y_{k}^{(t)}\coloneqq\frac{B_{k}(\bm{x}^{(t)})}{2A_{k}(\bm{x}^{(t)})}\in\mathbb{R}_{++}$
and $t$ is the iteration index.

Likewise, when function $E(\bm{x})$ exhibits convexity, it becomes feasible to
ascertain the globally optimal solution and stationary point for the single-
product and sum-of-products optimization problems respectively. A stationary
point in the context of a non-convex problem, where the objective function may
not be differentiable, is defined as a point that adheres to the generalized
KKT conditions [14]. In scenarios where the objective function is
differentiable, the generalized KKT conditions simplify to align with the
traditional KKT conditions.

##  III Updated Transform

The core methodology proposed by Zhao et al. [2] is predominantly employed to
tackle continuous problem spaces wherein the functions $A(\bm{x})$ and
$B(\bm{x})$ are constricted to positive domains. This approach, however, is
contingent upon specific assumptions and extant empirical scenarios, which
consequentially result in the persistence of two significant yet unresolved
exceptional instances. In pursuit of mitigating the constraints inherent to
the aforementioned transform and to promulgate its generalizability,
especially within practical sum-of-products problems, two thorny dilemmas are
introduced as follows:

  * •

Dilemma 1: Problems with given functions mapped to the non-negative domain,
i.e., function $A(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$ or
$B(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$;

  * •

Dilemma 2: Problems with a given discrete or mixed discrete-continuous
feasible set, i.e., optimization variable $\bm{x}$ can be discrete or mixed
discrete-continuous.

For Dilemma 1, the situation where $A(\bm{x})$ equals zero for certain values
of $\bm{x}$ within the domain $\mathcal{X}$ presents a significant challenge.
In such instances, the auxiliary variable approach in [2] is rendered
ineffective due to the zero-denominator issue inherent in the auxiliary
variable expression. A similar complication arises when $B(\bm{x})=0$, leading
to the auxiliary variable $y$ becoming zero. This creates a conflict as the
auxiliary variable is the denominator of the reformulated objective function
(i.e., $y\neq 0$), thus resulting in the ineffective of the transformed
objective function $F(\bm{x},y)$. For Dilemma 2, dealing with discrete or
mixed discrete-continuous problems, which are recognized as NP-hard problems,
poses another set of difficulties. Finding an optimum solution becomes
particularly challenging, as the proposed Zhao’s transform is not applicable.
This dilemma will be more complicated in special cases where the set
$\\{\bm{x}|A(\bm{x})=0\lor B(\bm{x})=0\\}\subseteq\mathcal{X}$, rendering the
transform process further infeasible.

To solve the dilemmas introduced in the above cases, we make updates to Zhao’s
optimization transform while keeping the updated transform adaptable to all
mentioned problems. Firstly, we formally re-delineate the properties that the
updated transform is required to have when expanding to MP and reformulating
the original MP objective functions:

  * •

Decoupling (P1): Updated transform proposed should have the same decoupling
property as the proposed transform in [2] with the form
$F(\bm{x},y)=F_{1}(A(\bm{x}))f_{1}(y)+F_{2}(B(\bm{x}))f_{2}(y)$, where $y$ is
an auxiliary variable;

  * •

Equivalent Solution (P2): Variable $\bm{x}^{*}$ are the optimum of
$A(\bm{x})B(\bm{x})$ if and only if $\bm{x}^{*}$ and $y^{*}$ minimize
$F(\bm{x},y)$;

  * •

Relaxed Objective (P3): For $B(\bm{x})>0$,
$F(\bm{x},y^{*})=A(\bm{x})B(\bm{x})$ for variable $\bm{x}$ if and only if
$y^{*}=\arg\min_{y}F(\bm{x},y)$ ; While for $B(\bm{x})=0$,
$F(\bm{x},y^{*})=\min_{y}F(\bm{x},y)$ if and only if
$y^{*}=\arg\min_{y}F(\bm{x},y)$.

  * •

Convexity (P4): Function $F(\bm{x},y)$ is convex of $y$ for fixed variable
$\bm{x}$, i.e., its Hessian is positive semidefinite;

  * •

Robustness (P5): Updated transform is not only applicable for positive-value
functions which proposed in prior paper (Zhao’s Transform) but also
nonnegative-value functions, i.e., $\\{\bm{x}|A(\bm{x})\geq 0\lor
B(\bm{x})\geq 0\\}\subseteq\mathcal{X}$.

Properties incorporated by the updated transform guarantee that the resultant
optimization problem retains the same optimal solution as the original
optimization problem. Regarding the objective functions’ values, the
relaxation to this property will be introduced and analyzed in Section III-B.
In order to verify the properties we deﬁne by mathematical theories, we next
present and prove the pursued updated transform in detail.

###  III-A Updated Transform

######  Theorem 3 (Updated Transform).

Given a non-empty feasible set $\mathcal{X}$, a pair of positive convex
functions222For the case $A(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$
and $B(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$, updated transform
can also be adopted to find the stationary point.
$A(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$ and
$B(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$, where $n\in\mathbb{N}$,
the updated transform for the single-product term is:

$\displaystyle
F_{\text{update}}(\bm{x},y)\coloneqq[A(\bm{x})]^{2}(y+c)+\frac{[B(\bm{x})]^{2}}{4(y+c)},$
(14)

where $c$ is an adaptive constant derived as follows which depends on the
value of $B(\bm{x})$:

$\displaystyle c^{(t)}=\left\\{\begin{array}[]{ll}0,&\text{if
}B(\bm{x}^{(t)})>0,\\\ c_{1}>0,&\text{others},\end{array}\right.$ (17)

and $y\in\mathbb{R}_{+}$ is the introduced auxiliary variable. Specifically,

$\displaystyle
y^{(t)}=\left\\{\begin{array}[]{ll}\cfrac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})}-c^{(t)},&\text{if
}\cfrac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})}\geq c^{(t)},\\\ \hskip
2.0pt0,&\text{others},\end{array}\right.$ (20)

where $t$ is the iteration index.

Proof: Please see Appendix A. $\hfill\blacksquare$

Based on the proof, we can further derive that when $B(\bm{x}^{(t)})\neq 0$,
then the auxiliary variable $y^{(t)}=\frac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})}$
and constant $c^{(t)}=0$. Conversely, auxiliary variable $y^{(t)}=0$ and
constant $c^{(t)}=c_{1}$.

To further reduce the complexity derived from the identification of the
adaptive constant and auxiliary variable, we also propose the simplified
version of the updated transform to obtain the optimum of the single-product
problem.

######  Corollary 3 (Simplified Transform).

Given a non-empty feasible set $\mathcal{X}$, a pair of positive convex
functions $A(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$ and
$B(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$, where $n\in\mathbb{N}$,
the updated transform for the single-product term is:

$\displaystyle
F_{\text{update}}(\bm{x},y)\coloneqq[A(\bm{x})]^{2}(y+c)+\frac{[B(\bm{x})]^{2}}{4(y+c)},$
(21)

where $c$ is a given constant and $y\in\mathbb{R}_{+}$ is the introduced
auxiliary variable. Specifically,
$y^{(t)}=\frac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})}$ and $t$ is the iteration
index.

In order to guarantee the completeness and research-oriented of the paper, we
will analyze the Updated Transform in the following parts of this paper.

###  III-B Properties Analysis

The proof of Theorem 3 rigorously substantiates the applicability of the
introduced auxiliary variable $y$ and constant $c$, establishing their
mathematical significance. We further extended the analysis and verification
of this theorem with a focus on the proposed properties. Property (P1) is
strictly satisfied through the introduction of auxiliary variables; i.e.,
$f_{1}(y)=y+c$ and $f_{2}(y)=\frac{1}{4(y+c)}$, with the values illustrated as
(20). Upon defining the auxiliary variable, the surrogate function of the
original objective function is obtained by defining the quadratic of each
function, resulting in $F_{1}(A(\bm{x}))=[A(\bm{x})]^{2}$ and
$F_{2}(B(\bm{x}))=[B(\bm{x})]^{2}$. Subsequently, we derive the second-order
partial derivative of the surrogate function with respect to $y$ with
$\frac{\partial^{2}F_{\text{update}}}{\partial
y^{2}}=\frac{[B(\bm{x})]^{2}}{2(y+c)^{3}}\geq 0\vspace{+1pt}$. This outcome
demonstrates that the transformed function maintains the convexity of the
auxiliary variable for given variable $\bm{x}$, thereby satisfying Property
(P4).

In the context of Property (P5) robustness, we specifically take the case
where $A(\bm{x})$ and $B(\bm{x})$: $\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$
into consideration, as initially introduced in [2] (Zhao’s Transform), then
the value of $c$ can always be set as zero in each iteration for convergence.
Consequently, the updated transform $F_{\text{update}}$ proposed is aligned
with Zhao’s optimization transform. Moreover, for the generalized case
$A(\bm{x})\text{ or }B(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$, our
revised transform is adaptable and effective in reaching the optimum, as
substantiated by the theorem’s proof. Thus, we conclude that Property (P5) is
satisfactorily met.

In light of the detailed exploration of Property (P5), we ascertain that the
equivalent objective emerges conspicuously in instances where the constant $c$
is consistently assigned the value of zero. This observation holds paramount
significance, aligning with the findings elucidated in [2] of our analysis.
Furthermore, the fulfillment of the equivalent solution property (P2) is
corroborated within this specific context. The rigorous proof, presented in
[2], delineates the conditions under which this equivalence is maintained,
thereby reinforcing the updated theorem’s applicability and robustness in
scenarios characterized by the stipulated value of $c$. When $c$ is set to
$c_{1}$ in Eq. (17), it leads to a critical inference regarding the
transformed objective functions. Specifically, the transformed function cannot
attain equivalence with the original objective function. This disparity arises
because the transformed function with $B(\bm{x})=0$ cannot reach its lower
bound. Nonetheless, the optimization variables can achieve equivalent values
owing to the non-decreasing nature of $F_{\text{update}}$ within the interval
$[\frac{B(\bm{x})}{2A(\bm{x})}-c,+\infty)$. Consequently, this adheres to the
relaxed objective property (P3), thus enhancing the theorem’s applicability
and robustness property (P5).

###  III-C Updated Transform for Multiple-Product MP

By analyzing the properties of Theorem 3, it can be easy to obtain the updated
transform to cater to the proposed properties aforementioned. We now apply the
updated transform to general multiple-product MP problems. Given $K$ pairs of
functions $A_{k}(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{++}$ and
$B_{k}(\bm{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$ for $k=1,2,...K$, the
multiple-product MP problem is:

$\displaystyle\underset{\bm{x}}{\text{minimize}}\hskip
15.0pt\sum_{k=1}^{K}A_{k}(\bm{x})B_{k}(\bm{x})$ (22)
$\displaystyle\text{subject to}\hskip 14.0pt\bm{x}\in\mathcal{X}.$ (22a)

As analysis mentioned above, Property (P2) guarantees the optimal solutions of
original optimization problems are equivalent to the updated problem, though
the objective functions are not equivalent as a result of Property (P3).
Nevertheless, the transformed problem is:

$\displaystyle\underset{\bm{x},\bm{y}}{\text{minimize}}\hskip
15.0pt\sum_{k=1}^{K}F_{\text{update},k}(\bm{x},y_{k})$ (23)
$\displaystyle\text{subject to}\hskip 14.0pt\bm{x}\in\mathcal{X},$ (23a)

with

$\displaystyle
F_{\text{update},k}(\bm{x},y_{k})\\!\coloneqq\\![A_{k}(\bm{x}^{(t)})]^{2}(y_{k}^{(t)}\\!\\!+\\!c_{k}^{(t)})\\!+\\!\frac{[B_{k}(\bm{x}^{(t)})]^{2}}{4(y_{k}^{(t)}\\!\\!+\\!c_{k}^{(t)})},\forall
k,$

where we define $c_{k}^{(t)}$ (resp., $y_{k}^{(t)}$) by replacing $A$ and $B$
with $A_{k}$ and $B_{k}$ in (17) (resp., (20)). Most importantly, when
$B(\bm{x})>0$ in each iteration of finding the optimum, the objective value of
the transformed optimization problem is equivalent to that of the original
optimization problem, i..e, property (P3) reaches the equivalent objective.

Next, to generalize the updated transform, the updated transform is further
extended to the more general sum-of-functions-of-product problem.

######  Corollary 4.

Given a sequence of non-decreasing functions $G_{k}(\cdot)$ and a sequence of
products $A_{k}(\bm{x})B_{k}(\bm{x})$ where $k=1,2,...,K$, the sum-of-
functions-of-product problem is:

$\displaystyle\underset{\bm{x}}{\text{minimize}}\hskip
15.0pt\sum_{k=1}^{K}G_{k}(A_{k}(\bm{x})B_{k}(\bm{x}))$ (24)
$\displaystyle\text{subject to}\hskip 14.0pt\bm{x}\in\mathcal{X}.$ (24a)

Then, the equivalent optimum is obtained from the transformed problem by
adopting the updated transform as below:

$\displaystyle\underset{\bm{x},\bm{y}}{\text{minimize}}\hskip
15.0pt\sum_{k=1}^{K}G_{k}(F_{\text{update},k}(\bm{x},y_{k}))$ (25)
$\displaystyle\text{subject to}\hskip
14.0pt\bm{x}\in\mathcal{X},~{}\bm{y}=[y_{1},...,y_{k}]\in\mathbb{R}_{+}.$
(25a)

Proof: Please see Appendix B. $\hfill\blacksquare$

###  III-D Iterative Optimization of Multiple-products MP

Thus far, the analysis and generalization have been presented, considering the
design aspects of communication systems while validating the proposed theories
and corollaries. Moving forward, we shall refocus on the sum-of-products
problems, which are pivotal to the functionality of wireless communication
networks, and reiterate the specific assumptions underpinning the function
formulations.

  * •

Functions $A_{k}(\bm{x})$ and $B_{k}(\bm{x})$ are all convex functions;

  * •

Product of each pair $A_{k}(\bm{x})$ and $B_{k}(\bm{x})$ does not maintain the
convexity;

  * •

Feasible set $\mathcal{X}$ is convex and nonempty which can be expressed as
the standard form.

These assumptions imply that the non-convexity of the sum-of-products MP
problems poses considerable analytical complexity. However, for the simpler
case of a single-product scenario, the non-convexity barrier can be surmounted
more readily. By leveraging decoupling techniques, such as Logarithmic
Transformation (Page 65, Section 6.2 in [15]), Dinkelbach’s Algorithm [3], and
Branch and Bound (B&B) Method [16], it is feasible to converge upon a global
optimum.

To further tackle the optimization problems with multiple-products by using
the updated transform, we take the scalar case of the objective functions into
account and consider the problems mentioned on (22) and (24). Additionally, we
assume that function $G_{k}(\cdot)$ in (24) is not only nondecreasing but also
convex. Then transformed optimization problems proposed with updated transform
are all becoming convex problems.

Therefore, we present the systematic iteration approach in the Algorithm 2 for
these above non-convex MP problems with the introduced adaptive constant
$c^{(t)}$ in (17) and auxiliary variables $y_{k}^{(t)}$ in (20) of $t$-th
iteration. Specifically, optimization variables and auxiliary variables can be
continuously optimized until convergence by adopting a block coordinate
descent algorithm with fixed values for each block variable.

1 Initialize: $i=0$; optimization variable $\bm{x}^{(0)}$;

2Calculate and derive auxiliary variable $\bm{y}^{(0)}$ and the adaptive
constant $\bm{c}^{(0)}$ based on (20) and (17) where
$\bm{y}^{(0)}=[y_{1}^{(0)},...,y_{K}^{(0)}]$ and
$\bm{c}^{(0)}=[c_{1}^{(0)},...,c_{K}^{(0)}]$;

3Reformulate original problem with updated transform based on Theorem 3;

4repeat

5 Obtain the optimal solution $\bm{x}^{(i+1)}$ of $(i+1)$-th iteration by
solving reformulated problem when given auxiliary variable $\bm{y}^{(i)}$ and
adaptive constant $\bm{c}^{(i)}$;

6 Update $\bm{y}^{(i+1)}$ and $\bm{c}^{(i+1)}$ by (20) with fixed
$\bm{x}^{(i+1)}$;

7 $i\leftarrow i+1$;

8until Convergence or reach the max iteration number $I$;

Algorithm 2 Iteration of Non-convex MP Problems

###  III-E Convergence

To verify the convergence of the Algorithm 2, we first can obtain via the
proof in Appendix A that the values of optimization variables are converged
when fixed auxiliary variable and constant are given in each iteration as
illustrated in Step 5-6. When the optimization variable is fixed, the values
of the auxiliary are also converged iteratively with the given adaptive
constant. without loss of optimality, we can derive that the proposed
algorithm will converge to the stationary point with less computation
complexity.

##  IV Application Scenarios

In this section, we delve into the practical applications of the updated
transformation, especially focusing on scenarios differentiated by the nature
of the optimization variables. In cases where these variables are continuous,
our analysis focuses on computation resource allocation and offloading
strategies within communication systems, particularly addressing the
challenges in the mobile edge computing (MEC) system [17]. This involves
optimizing resource allocation strategies in a dynamic and often constrained
environment.

Furthermore, for mixed-integer optimization (MIO) scenarios, our attention
shifts to user association challenges in hierarchical network structures [18,
19, 20]. Here, we investigate strategies for efficient resource and service
allocation across the hierarchical network, aiming to enhance the overall
network performance.

A pivotal contribution of our work in mixed discrete-continuous cases is the
development of an innovative algorithm designed to tackle Dilemma 2 instead of
using conventionally alternating optimization (AO) [21] approaches with a low
convergence rate. This algorithm represents a significant step forward in
solving such intricate optimization challenges where complex problems are
characterized by the presence of discrete variables that render them NP-hard.

###  IV-A Partial Offloading with Resource Allocation

In recent years, the strategy of partial offloading has gained significant
traction in the realm of mobile computing and the Internet of Things (IoT)
[22]. Despite the advancements in hardware, the computational capacities and
battery life of these mobile devices remain limited. Partial offloading [23]
emerges as a strategic solution to this limitation. It involves offloading a
portion of the computational tasks from the mobile device to more powerful
external servers, either in the cloud or at the edge of the network. This
approach not only alleviates the computational burden on mobile devices,
enhancing their performance and battery efficiency but also addresses latency-
sensitive applications by leveraging the proximity and processing power of
edge servers.

System Model: To formulate the optimization problem from practical application
scenarios, we consider the mobile edge computing system with $N$ user
equipment (UEs) and one edge server. Assume that each UE $n$ processes the
compute-intensive task that can relate to the Vehicular Edge Computing (VEC)
[24], Metaverse [25], or encryption computation [26], and the size of the task
is denoted as $C_{n}$. In order to enhance spectral efficiency and minimize
cross-channel interference, OFDMA (Orthogonal Frequency-Division Multiple
Access) is adopted to reduce inter-channel interference in this proposed
system. With the computational limitation of each UE, we denote the partial
rate of offloaded computation tasks as $x_{n}$ with $x_{n}\in[0,1]$. $x_{n}=0$
indicates the UE $n$’s task will be processed locally on the mobile device,
while $x_{n}=1$ indicates that the computation task is totally offloaded to
the edge server and processed. Specifically, when $0<x_{n}<1$, it indicates
the proportion of tasks that are offloaded to the edge server. By denoting the
number of CPU cycles required to process task one bit in the local device and
edge server as $q_{n}^{\text{local}}$ and $q_{n}^{\text{edge}}$, we can then
obtain the delay for UE $n$’s computation task at different points as

$\displaystyle T_{n}=T_{n}^{\text{local}}+T_{n}^{\text{edge}},$ (26)

specifically,

$\displaystyle
T_{n}^{\text{local}}=\frac{C_{n}^{\text{local}}q_{n}^{\text{local}}}{f_{n}^{l}}=\frac{(1-x_{n})C_{n}q_{n}^{\text{local}}}{f_{n}^{l}},$
$\displaystyle
T_{n}^{\text{edge}}=\frac{C_{n}^{\text{edge}}q_{n}^{\text{edge}}}{f_{n}^{e}}=\frac{x_{n}C_{n}q_{n}^{\text{edge}}}{f_{n}^{e}},$

where $f_{n}^{l}$ and $f_{n}^{e}$ represent the computation frequency of UE
$n$ and edge server respectively. Compared with the latency of processing, we
omit transmission latency due to the proximity of the edge server to mobile
devices.

Therefore, the total energy consumption is derived as:

$\displaystyle
E_{n}=k_{n}T_{n}^{\text{local}}{f_{n}^{l}}^{3}+k_{e}T_{n}^{\text{edge}}{f_{n}^{e}}^{3},$
(27)

where $k_{n}$ is the coefficient reflecting the power efficiency of UE $n$ and
$k_{e}$ represents the analogous coefficient related to the power efficiency
of the edge server.

We next infer the cost function which jointly considers the offloading ratio
and power limitation of each UE as $O_{n}=w_{1}T_{n}+w_{2}E_{n}$ and after
mathematical transformation, it can be expressed as:

$\displaystyle O_{n}=(1-x_{n})H_{n,1}(f_{n}^{l})+x_{n}H_{n,2}(f_{n}^{e}),$
(28)

where

$\displaystyle
H_{n,1}(f_{n}^{l})=C_{n}q_{n}^{\text{local}}(\frac{w_{1}}{f_{n}^{l}}+w_{2}k_{n}{f_{n}^{l}}^{2}),$
$\displaystyle
H_{n,2}(f_{n}^{e})=C_{n}q_{n}^{\text{edge}}(\frac{w_{1}}{f_{n}^{e}}+w_{2}k_{e}{f_{n}^{e}}^{2}),$

and $w_{1}$, $w_{2}$ serve as weight parameters specifically designated to
modulate the magnitudes of the cost components.

Problem Formulation: UE $n$ can choose the offloading decision
$\bm{x}\coloneqq(x_{1},x_{2},...,x_{N})$ based on its own and the edge
server’s computational ability. Meanwhile, the task computation frequency
locally $\bm{f^{l}}\coloneqq(f_{1}^{l},f_{2}^{l},...,f_{N}^{l})$, the edge
computation frequency $\bm{f^{e}}\coloneqq(f_{1}^{e},f_{2}^{e},...,f_{N}^{e})$
allocated to each mobile equipment can be jointly optimized to achieve
optimum. Then, the joint optimization problem incorporating energy cost
expenditure, offloading determinations, and computation resources is
formulated as:

$\displaystyle\underset{\bm{x},\bm{f^{l}},\bm{f^{e}}}{\text{minimize}}~{}~{}$
$\displaystyle\sum_{n\in\mathcal{N}}(1-x_{n})H_{n,1}(f_{n}^{l})+x_{n}H_{n,2}(f_{n}^{e})$
(29) subject to $\displaystyle~{}\text{($\mathbf{C}_{1}$):}~{}0\leq x_{n}\leq
1,\forall n\in\mathcal{N},$ (29a)
$\displaystyle~{}\text{($\mathbf{C}_{2}$):}~{}\sum\nolimits_{n=1}^{N}f_{n}^{e}\leq
F^{e},$ (29b) $\displaystyle~{}\text{($\mathbf{C}_{3}$):}~{}0\leq
f_{n}^{l}\leq F_{n}^{l},\forall n\in\mathcal{N},$ (29c)
$\displaystyle~{}\text{($\mathbf{C}_{4}$):}~{}0\leq f_{n}^{e}\leq
F_{n}^{e},\forall n\in\mathcal{N},$ (29d)

where $\mathcal{N}=\\{1,2,...,N\\}$ is the set of UEs. $F^{e}$ in
$(\mathbf{C}_{2})$ and $F_{n}^{l}$ in $(\mathbf{C}_{3})$ indicate the maximum
computation frequency of the edge server and UE $n$. $F_{n}^{e}$ in
$(\mathbf{C}_{4})$ represented the maximum allocated computation frequency by
the edge server to UE $n$. For each constraint, $(\mathbf{C}_{1})$ indicates
the offloading decision and the ratio of the offloaded computation task of
each UE. $(\mathbf{C}_{2})$ restricts the total computation frequency of the
edge server. $(\mathbf{C}_{3})$ represents that the local processing frequency
cannot exceed the device limit. For constraint $(\mathbf{C}_{4})$, it
mitigates the potential for specific computation tasks to greedily consume
computational resources on the edge server.

Solution with Updated Transform: To solve the above model of the practical
offloading strategy, the proposed transformed in this work are adopted. The
original optimization is divided into the sub-problem and the coupling of the
optimization variables $\bm{x}$, $\bm{f^{l}}$, and $\bm{f^{e}}$ can be
resolved by introducing auxiliary variables in (20). In the $(k+1)$-th
iteration, the transformed objective function is expressed as:

$\displaystyle
G(\bm{x},\bm{f^{l}},\bm{f^{e}}|\bm{u}^{(k)}\\!\\!,\bm{v}^{(k)}\\!\\!,\bm{c}^{(k)})\\!=\\!\\!\\!\underset{n\in\mathcal{N}}{\sum}g_{n}(x_{n},f_{n}^{l},f_{n}^{e}|u_{n}^{(k)}\\!\\!,v_{n}^{(k)}\\!\\!,c_{n}^{(k)}),$

where $u_{n}^{(k)}=\frac{(1-x_{n}^{(k)})}{2H_{n,1}({f_{n}^{l}}^{(k)})}$ and
$v_{n}^{(k)}=\frac{x_{n}^{(k)}}{2H_{n,2}({f_{n}^{e})}^{(k)}}\in\mathbb{R}^{+}$
are the introduced auxiliary variables related to the convergence of the
proposed algorithm when $0<x_{n}<1$ according to (20). Function
$g_{n}(x_{n},f_{n}^{l},f_{n}^{e}|u_{n}^{(k)},v_{n}^{(k)})$ is defined as shown
in (30), where $c_{n}^{(k)}$ is the introduced constant according to (17).

$\displaystyle
g_{n}=[H_{n,1}(f_{n}^{l})]^{2}(u_{n}^{(k)}+c_{n}^{(k)})+\frac{(1-x_{n})^{2}}{4(u_{n}^{(k)}+c_{n}^{(k)})}+[H_{n,2}(f_{n}^{e})]^{2}(v_{n}^{(k)}+c_{n}^{(k)})+\frac{x_{n}^{2}}{4(v_{n}^{(k)}+c_{n}^{(k)})}$
(30)

Then sub-problem of the original optimization problem in the $(k+1)$-th
iteration is reformulated as:

$\displaystyle\underset{\bm{x},\bm{f^{l}},\bm{f^{e}}}{\text{minimize}}~{}~{}~{}$
$\displaystyle
G(\bm{x},\bm{f^{l}},\bm{f^{e}}|\bm{u}^{(k)},\bm{v}^{(k)},\bm{c}^{(k)})$ (31)
subject to $\displaystyle\text{(\ref{p1c1}), (\ref{p1c2}), (\ref{p1c3}),
(\ref{p1c4})}.$

Until now, the original optimization problem can be solved iteratively, and
the process of solution is listed in Algorithm 3. Instead of using the general
convex toolboxes, we adopt Karush-Kuhn-Tucker (KKT) conditions analysis to
obtain the solution to the problem in a faster way.

1 Initialize the index of iteration: $k=0$; optimization variable
$\bm{\mathcal{X}}^{(0)}\\!=\\![\bm{x}^{(0)}\\!,{\bm{f^{l}}}^{(0)},{\bm{f^{e}}}^{(0)}]$;

2Calculate and derive auxiliary variable space:
$\bm{\mathcal{A}}^{(0)}=[\bm{u}^{(0)}\\!\\!,\bm{v}^{(0)}]$, where
$u_{n}^{(0)}\\!=\frac{(1-x_{n}^{(0)})}{2H_{n,1}({f_{n}^{l}}^{(0)})}$,
$v_{n}^{(k)}\\!=\frac{x_{n}^{(0)}}{2H_{n,2}({f_{n}^{e}}^{(0)})}$, $\forall
n\in\mathcal{N}$; Derive the constant vector: $\bm{c}^{(0)}$ based on (17).

3repeat

4 Obtain the optimal variable $\bm{\mathcal{X}}^{(k+1)}$ of $((k+1))$-th
iteration by adopting the Algorithm 4 when given auxiliary variable space
$\bm{\mathcal{A}}^{(k)}$;

5 Update $\bm{\mathcal{A}}^{(k+1)}=[\bm{u}^{(k+1)}\\!\\!,\bm{v}^{(k+1)}]$ and
$\bm{c}^{(k+1)}$ with given $\bm{\mathcal{X}}^{(k+1)}$;

6 $k\leftarrow k+1$;

7until Convergence or reach the max iteration number $K$;

Algorithm 3 Partial Offloading Programming

KKT Analysis: Before proceeding with the analysis of each KKT condition, we
first derive the Lagrange function of each sub-problem by introducing
multipliers for constraints as shown at the (32).

$\displaystyle
L\\!=\\!G(\bm{x}\\!,\bm{f^{l}}\\!\\!,\bm{f^{e}}|\bm{u}^{(k)}\\!\\!,\bm{v}^{(k)}\\!\\!,\bm{c}^{(k)})\\!+\\!\\!\\!\\!\underset{n\in\mathcal{N}}{\sum}\\![\gamma_{n}\cdot(x_{n}\\!\\!-\\!\\!1)\\!-\\!\beta_{n}x_{n}]\\!\\!+\\!\delta\cdot[(\\!\underset{n\in\mathcal{N}}{\sum}f_{n}^{e})\\!-\\!F^{e}]\\!+\\!\\!\\!\\!\underset{n\in\mathcal{N}}{\sum}\\![\zeta_{n}\cdot(f_{n}^{l}\\!-\\!F_{n}^{l})-\epsilon_{n}f_{n}^{l}]\\!\\!+\\!\\!\\!\\!\underset{n\in\mathcal{N}}{\sum}\\![\theta_{n}\cdot(f_{n}^{e}\\!\\!-\\!F_{n}^{e})-\eta_{n}f_{n}^{e}]$
(32)

Then based on the multipliers and Lagrange function, we get KKT conditions as
follows:

Stationary:

$\displaystyle\frac{\partial L}{\partial
x_{n}}=D_{n}(x_{n})-\beta_{n}+\gamma_{n}=0,$ (33a)
$\displaystyle\frac{\partial L}{\partial
f_{n}^{l}}=Q_{n}(f_{n}^{l})-\epsilon_{n}+\zeta_{n}=0,$ (33b)
$\displaystyle\frac{\partial L}{\partial
f_{n}^{e}}=R_{n}(f_{n}^{e},\delta)-\eta_{n}+\theta_{n}=0.$ (33c)

where
$D_{n}(x_{n})=\frac{x_{n}-1}{2(u_{n}^{(k)}+c_{n}^{(k)})}+\frac{x_{n}}{2(v_{n}^{(k)}+c_{n}^{(k)})}$
relating to the variable $x_{n}$,
$Q_{n}(f_{n}^{l})=2H_{n,1}(f_{n}^{l})H_{n,1}^{{}^{\prime}}(f_{n}^{l})(u_{n}^{(k)}+c_{n}^{(k)})$
relating to the variable $f_{n}^{l}$, and
$R_{n}(f_{n}^{e},\delta)\\!=\\!2H_{n,2}(f_{n}^{e})H_{n,e}^{{}^{\prime}}(f_{n}^{e})(v_{n}^{(k)}\\!+\\!c_{n}^{(k)})+\delta$
relating to the variable $f_{n}^{e}$ and the multiplier $\delta$.

Complementary Slackness:

$\begin{split}&\text{(\ref{kktC}a): }\beta_{n}\cdot(-x_{n})=0;\hskip
10.0pt\text{(\ref{kktC}b): }\gamma_{n}\cdot(x_{n}-1)=0;\\\
&\text{(\ref{kktC}c):
}\delta\cdot[(\sum\nolimits_{n\in\mathcal{N}}f_{n}^{e})-F^{e}]=0;\\\
&\text{(\ref{kktC}d): }\epsilon_{n}\cdot(-f_{n}^{l})=0;\hskip
12.0pt\text{(\ref{kktC}e): }\zeta_{n}\cdot(f_{n}^{l}-F_{n}^{l})=0;\\\
&\text{(\ref{kktC}f): }\eta_{n}\cdot(-f_{n}^{e})=0;\hskip
12.5pt\text{(\ref{kktC}g):
}\theta_{n}\cdot(f_{n}^{e}-F_{n}^{e})=0;\end{split}$ (34)

Primal Feasibility:  (29a), (29b), (29c), (29d);

Dual Feasibility:

$\begin{split}\text{(\ref{kktD}a)-(\ref{kktD}e)}:\beta_{n},\gamma_{n},\delta,\epsilon_{n},\zeta_{n},\eta_{n},\theta_{n}\geq
0,\forall n\in\mathcal{N}.\end{split}$ (35)

Under the aforementioned conditions, we then proceed to seek the optimal
solutions by analyzing the KKT conditions and employing the proposed algorithm
which is listed in Algorithm 4.

######  Theorem 4.

The optimal solution of the proposed objective function can be obtained by
Algorithm 4 and is expressed as:

$\displaystyle\left\\{\begin{array}[]{l}x_{n}^{*}=\max\\{\min\\{\widetilde{x}_{n},1\\},0\\};\\\
{f_{n}^{l}}^{*}=\max\\{\min\\{\widetilde{f}_{n}^{l},F_{n}^{l}\\},0\\};\\\
{f_{n}^{e}}^{*}=\max\\{\min\\{\widehat{f}_{n}^{e}(\delta^{*}),F_{n}^{e}\\},0\\};\end{array}\right.$
(39)

where $\widetilde{x}_{n}$ meets the condition (33a) with
$D_{n}(x_{n})|_{x_{n}=\widetilde{x}_{n}}=0$, $\widetilde{f}_{n}^{l}$ and
$\widehat{f}_{n}^{e}(\delta)$ meets the condition (33b) and (33c) with
$Q_{n}(f_{n}^{l})|_{f_{n}^{l}=\widetilde{f}_{n}^{l}}=0$ and
$R_{n}(f_{n}^{e},\delta)|_{f_{n}^{e}=\widehat{f}_{n}^{e}(\delta)}=0$,
respectively.

Proof: Please see Appendix C. $\hfill\blacksquare$

1: Given the auxiliary variable space $\bm{\mathcal{A}}=[\bm{u},\bm{v}]$;

2: for $n\leftarrow 1\text{ to }N$ do

3: Obtain $\widetilde{x}_{n}$ by assuming function $D_{n}(x_{n})$ on the
condition (33a) equal to 0;

4: Obtain $\widetilde{f}_{n}^{l}$ by assuming function $Q_{n}(f_{n}^{l})$ on
the condition (33b) equal to 0;

5: Obtain $\widehat{f}_{n}^{e}(\delta)$ when assuming
$R_{n}(f_{n}^{l},\delta)=0$ in the condition (LABEL:kktCc);

6: end for

7:
$\delta^{*}\\!\\!\leftarrow\\!\\!\left\\{\\!\\!\\!\small\begin{array}[]{l}0,\text{if}\sum_{n\in\mathcal{N}}\widetilde{f}_{n}^{e}(0)\leq
F^{e};\\\ \text{Solution to
}\sum_{n\in\mathcal{N}}\widetilde{f}_{n}^{e}(0)>F^{e};\end{array}\right.$

8: update $~{}x_{n}^{*}$, ${f_{n}^{l}}^{*}$, and ${f_{n}^{e}}^{*}$ based on
Theorem 4;

9: return The optimal variable value
$\mathcal{X}^{*}\\!\\!=[\bm{x}^{*}\\!\\!,\\!{\bm{f^{l}}}^{*}\\!\\!,\\!{\bm{f^{e}}}^{*}]$.

Algorithm 4 Analyze Corresponding KKT Conditions

###  IV-B User Association with Resource Allocation

After solving the practical scenarios with continuous variables, we now
consider the optimization problems with mixed discrete-continuous optimization
variables. In this subsection, we take the 5G heterogeneous mobile edge
computing system [27, 28] consisting of one Macro Base Station (MBS) [29] and
one Small Base Station (SBS) [30] as an example and propose a novel two-tier
computation offloading algorithm with the convergence of the updated transform
and successive convex approximation (SCA) approach [31].

System Model: In the proposed system, we assume each base station with one MEC
server to execute the offloaded computation task, and we denote the set of
base stations as $\mathcal{M}=\\{1,2\\}$ where $m=1$ is the SBS and $m=2$
represents the MBS. SBS is connected to the MBS via wired links. There are $N$
mobile users, denoted as $\mathcal{N}=\\{1,2,...,N\\}$. The SBS and mobile
users are randomly distributed within the convergence of MBS. Each mobile user
is connected to the SBS via wireless links and has a computation-intensive and
delay-sensitive task. We define the task of each user $n$ as
$D_{n}=(d_{n},c_{n})$, where $d_{n}$ denotes the data size of the computation
task, $c_{n}$ is the number of CPU cycles for computing one bit of task
$D_{n}$.

For this two-tier computation offloading framework, a mobile user can
partition the task into two parts. One part is offloaded to the MEC server
which is associated with the base stations, and the other part is executed
locally. As the computation resource of the MEC server in SBS is limited, the
part offloaded will further be partitioned into two parts when the computation
resource of the MEC server on SBS is exhausted. The SBS will offload the
remaining part of the task to the MEC server on the MBS. Furthermore, each
mobile user can also offload the task directly to the MBS. We denote the part
offloaded to the base stations as $d_{n,m}(0\leq d_{n,m}\leq d_{n})$ and the
part processed locally as $d_{n}-d_{n,m}$. In the second tier, SBS further
divides the fragment $d_{n,1}$ as $d_{n,1}-d_{n,1}^{{}^{\prime}}$ and
$d_{n,1}^{{}^{\prime}}(0\leq d_{n,1}^{{}^{\prime}}\leq d_{n,1}\leq d_{n})$,
and the latter part is offloaded to the MBS. For the offloading decision of
each user, we denote $x_{n,m}=\\{0,1\\}$ as the association variable, where
$x_{n,m}=0$ if user $n\in\mathcal{N}$ is associated with base station
$m\in\mathcal{M}$ and $x_{n,m}=0$ otherwise.

For the communication model, we also adopt the OFDMA technique between mobile
users and base stations, and the channel power gain is denoted as $H_{n,m}$.
Then when mobile user $n$ is associated with the SBS, the signal-to-
interference plus noise ratio (SINR) of the uplink will be expressed as:=

$\displaystyle\gamma_{n,1}=\frac{P_{n}H_{n,1}}{\sigma^{2}},$ (40)

where $P_{n}$ is the transmission power of mobile user $n$, and $\sigma^{2}$
is defined as the noise power. The inter-user interference is not taken into
consideration with the adoption of OFDMA. Assuming the SBS allocates bandwidth
equally to its associated users, the achievable uplink data rate of mobile
user $n$ can be inferred as:

$\displaystyle
R_{n,1}=\frac{B_{1}}{\sum_{n=1}^{N}x_{n,1}}\ln(1+\gamma_{n,1}),$ (41)

where $B_{1}$ represents the bandwidth of the SBS and $\sum_{n=1}^{N}x_{n,1}$
denotes the amount of mobile users associates the SBS. Similarly, if a mobile
user is associated with MBS, the SINR is expressed as:

$\displaystyle\gamma_{n,2}=\frac{P_{n}H_{n,2}}{\sigma^{2}},$ (42)

and the achievable data rate will be:

$\displaystyle
R_{n,2}=\frac{B_{2}}{\sum_{n=1}^{N}x_{n,2}}\ln(1+\gamma_{n,2}),$ (43)

where $B_{2}$ are the total bandwidth of the MBS and $\sum_{n=1}^{N}x_{n,2}$
are the amount of users associated with MBS.

Then we further infer the cost function of the local computation in terms of
the latency and energy consumption. We denote $f_{n}^{l}$ as the computation
resource when processing the task locally. Then we obtain the computation time
as:

$\displaystyle T_{n,m}^{\text{local}}=\frac{(d_{n}-d_{n,m})c_{n}}{f_{n}^{l}},$
(44)

and the corresponding energy consumption is:

$\displaystyle
E_{n,m}^{\text{local}}=k^{l}(d_{n}-d_{n,m})c_{n}{f_{n}^{l}}^{2},$ (45)

where $k_{n}$ is the effective switched capacitance depending on the chip
architecture.

For the task offloaded to the SBS, we denote the allocated computation
frequency by the SBS to the task as $f_{n}^{s}$ and assume that MBS allocates
fixed computation frequency $f_{0}$ to each offloaded task. Then the
processing time in SBS is:

$\displaystyle
T_{n,1}^{\text{SBS}}=\frac{d_{n,1}}{R_{n,1}}+\frac{(d_{n,1}-d_{n,1}^{{}^{\prime}})c_{n}}{f_{n}^{s}}+\frac{d_{n,1}^{{}^{\prime}}}{r_{0}}+\frac{d_{n,1}^{{}^{\prime}}c_{n}}{f_{0}},$
(46)

where $r_{0}$ represents the data rate of the wired link. Then the
corresponding energy consumption is derived below:

$\displaystyle
E_{n,1}^{\text{SBS}}\\!=\\!\frac{P_{n}d_{n,1}}{R_{n,1}}\\!+\\!k^{S}\\!(d_{n,1}\\!\\!-\\!d_{n,1}^{{}^{\prime}}\\!)c_{n}{f_{n}^{s}}^{2}\\!\\!+\\!\\!\frac{\bar{P}d_{n,1}^{{}^{\prime}}}{r_{0}}\\!\\!+\\!\\!k^{M}d_{n,1}^{{}^{\prime}}c_{n}f_{0}^{2},$
(47)

where $\bar{P}$ is the offloading power via wired line, $k^{S}$ and $k^{M}$
are the coefficients reflecting the power efficiency of the MEC server in SBS
and MBS respectively.

When the mobile user directly offloads the task to the MEC server in MBS, the
execution time is:

$\displaystyle
T_{n,2}^{\text{MBS}}=\frac{d_{n,2}}{R_{n,2}}+\frac{d_{n,2}c_{n}}{f_{0}},$ (48)

and the energy consumption is:

$\displaystyle
E_{n,2}^{\text{MBS}}=\frac{P_{n}d_{n,2}}{R_{n,2}}+k^{M}d_{n,2}c_{n}f_{0}^{2}.$
(49)

Then the total latency and energy consumption of the task for each user can be
concluded as:

$\displaystyle
T_{n}=(\sum_{m\in\mathcal{M}}x_{n,m}T_{n,m}^{\text{local}})+x_{n,1}T_{n,1}^{\text{SBS}}+x_{n,2}T_{n,2}^{\text{MBS}},$
(50) $\displaystyle
E_{n}=(\sum_{m\in\mathcal{M}}x_{n,m}E_{n,m}^{\text{local}})+x_{n,1}E_{n,1}^{\text{SBS}}+x_{n,2}E_{n,2}^{\text{MBS}}.$
(51)

Problem Formulation: We define $\bm{x}\coloneqq\\{x_{n,m}\\}$ as the user
association decision vector, $\bm{f^{l}}\coloneqq\\{f_{n}^{l}\\}$ and
$\bm{f_{n}^{s}}\coloneqq\\{f_{n}^{s}\\}$ as the vector of local and SBS
computation frequency respectively,
$\bm{P}\coloneqq[P_{n}|_{n\in\mathcal{N}}]$ as the transmission power vector,
and $\bm{d}\coloneqq\\{d_{n,m},d_{n,1}^{{}^{\prime}}\\}$ as the computation
offloading vector. Then the optimization problem can be formulated as:

$\displaystyle\underset{\bm{x},\bm{f^{l}},\bm{f^{s}},\bm{P},\bm{d}}{\text{minimize}}~{}~{}$
$\displaystyle\sum_{n=1}^{N}(w_{1}T_{n}+w_{2}E_{n})$ (52) subject to
$\displaystyle(\mathbf{C}_{1})\sum_{m\in\mathcal{M}}x_{n,m}=1,\forall
n\in\mathcal{N},$ (52a) $\displaystyle(\mathbf{C}_{2})~{}~{}0\leq
f_{n}^{l}\leq F_{n},\forall n\in\mathcal{N},$ (52b)
$\displaystyle(\mathbf{C}_{3})~{}\sum_{n=1}^{N}x_{n,1}f_{n}^{s}\leq F^{s},$
(52c) $\displaystyle(\mathbf{C}_{4})~{}~{}0\leq P_{n}\leq
P_{n}^{\text{max}},\forall n\in\mathcal{N},$ (52d)
$\displaystyle(\mathbf{C}_{5})~{}~{}0\leq d_{n,1}^{{}^{\prime}}\leq
d_{n,1},\forall n\in\mathcal{N},$ (52e)
$\displaystyle(\mathbf{C}_{6})~{}~{}0\leq d_{n,m}\leq d_{n},\forall
n\in\mathcal{N},m\in\mathcal{M},$ (52f)
$\displaystyle(\mathbf{C}_{7})~{}~{}f_{n}^{s}\geq 0,\forall n\in\mathcal{N},$
(52g) $\displaystyle(\mathbf{C}_{8})~{}~{}x_{n,m}\in\\{0,1\\},\forall
n\in\mathcal{N},m\in\mathcal{M}.$ (52h)

where $w_{1}$ and $w_{2}$ represent the weight parameters designed to modulate
the magnitudes of the cost components. The offloading decision constraints
relate to constrains $(\mathbf{C}_{1})$, $(\mathbf{C}_{3})$ and
$(\mathbf{C}_{8})$. Constraints $(\mathbf{C}_{2})$, $(\mathbf{C}_{3})$, and
$(\mathbf{C}_{7})$ limit the frequency of computation locally and in SBS
respectively. Also, constraints $(\mathbf{C}_{5})$ and $(\mathbf{C}_{6})$ also
constructed as the limitation of computation resource. $(\mathbf{C}_{4})$
limits the power resource of mobile user $n$.

Solution with Updated Transform and SCA: Based on the constraints of the user
association vector, we first adopt SCA technology to solve the discrete
optimization variables $\bm{x}$ resulting in the problem as NP-hard. Without
loss of equivalence, $(\mathbf{C}_{8})$ can be rewritten as:

$\displaystyle~{}~{}~{}~{}x_{n,m}\in[0,1],\forall
n\in\mathcal{N},m\in\mathcal{M},$ (53) $\displaystyle\text{ {and}
}\sum\nolimits_{n\in\mathcal{N}}\sum\nolimits_{m\in\mathcal{M}}x_{n,m}(1-x_{n,m})\leq
0.$ (54)

Note that the optimization problem has been transitioned into a continuous
optimization problem, resulting in a notable reduction in computational
complexity when contrasted with the direct resolution of the original discrete
variable $x_{n,m}$. Nonetheless, the function
$\sum\nolimits_{n\in\mathcal{N}}\sum\nolimits_{m\in\mathcal{M}}x_{n,m}(1-x_{n,m})$
in constraint (54) is a concave function. To further facilitate the solution,
we adopt a method that introduces a penalty term for this concave constraint
into the objective function, which is expressed as:

$\displaystyle\sum_{n=1}^{N}(w_{1}T_{n}+w_{2}E_{n})-\tau\cdot\sum\nolimits_{n\in\mathcal{N}}\sum\nolimits_{m\in\mathcal{M}}x_{n,m}(x_{n,m}-1),$

where $\tau$ is the penalty parameter with $\tau>0$. Then the objective
function becomes concave due to the concavity of the second term.
Simultaneously, given the second term is differentiable, we utilize the first-
order Taylor series to linearize it at each iteration. Specifically, at the
$(i+1)$-th iteration333To differ the iterations of intra-sub-problem and
inter-sub-problems, we symbolize the iterations of intra-sub-problem and
inter-sub-problems as $k$ and $i$ respectively., we approximate each
$\sum\nolimits_{n\in\mathcal{N}}\sum\nolimits_{m\in\mathcal{M}}x_{n,m}(x_{n,m}-1)$
with
$\sum\nolimits_{n\in\mathcal{N}}\sum\nolimits_{m\in\mathcal{M}}x_{n,m}^{(i)}(x_{n,m}^{(i)}-1)+(2x_{n,m}^{(i)}-1)(x_{n,m}-x_{n,m}^{(i)})$
denoted as $H(\bm{x}|\bm{x}^{(i)})$, where $\bm{x}^{(i)}$ is the optimal
solution of the $i$-th sub-problem. Therefore, the objective function is
reformulated as:

$\displaystyle\sum_{n=1}^{N}(w_{1}T_{n}+w_{2}E_{n})-\tau\cdot
H(\bm{x}|\bm{x}^{(i)}),$ (55)

After the mathematical transformation, we can obtain the objective function
as:

$\displaystyle\sum_{n=1}^{N}Q_{n}(\bm{x},\bm{f^{l}},\bm{f^{s}},\bm{P},\bm{d})-\tau\cdot
H(\bm{x}|\bm{x}^{(i)})$ (56)

where
$Q_{n}(\bm{x},\bm{f^{l}},\bm{f^{s}},\bm{P},\bm{d})=O_{n}(\bm{x},\bm{f^{l}},\bm{d})+S_{n}(\bm{x},\bm{P},\bm{d})+U_{n}(\bm{x},\bm{f^{s}},\bm{d})+V_{n}(\bm{x},\bm{d})$
and specifically,

$\displaystyle
O_{n}(\bm{x},\bm{f^{l}},\bm{d})=\underset{m\in\mathcal{M}}{\sum}x_{n,m}(d_{n}-d_{n,m})(\frac{w_{1}}{f_{n}^{l}}+w_{2}k^{l}{f_{n}^{l}}^{2})c_{n},$
$\displaystyle
S_{n}(\bm{x},\bm{P},\bm{d})=\underset{m\in\mathcal{M}}{\sum}x_{n,m}\frac{d_{n,m}(\sum_{n=1}^{N}x_{n,m})}{B_{m}\ln(1+\frac{P_{n}H_{n,m}}{\sigma^{2}})}(w_{1}+w_{2}P_{n}),$
$\displaystyle
U_{n}(\bm{x},\bm{f^{s}},\bm{d})=x_{n,1}(d_{n,1}-d_{n,1}^{{}^{\prime}})(\frac{w_{1}}{f_{n}^{s}}+w_{2}k^{S}{f_{n}^{s}}^{2})c_{n},$
$\displaystyle
V_{n}(\bm{x},\bm{d})=x_{n,1}d_{n,1}^{{}^{\prime}}C+x_{n,2}d_{n,2}(C-\frac{w_{1}+w_{2}\bar{P}}{r_{0}}),$

and the constant
$C=\frac{w_{1}+w_{2}\bar{P}}{r_{0}}+(\frac{w_{1}}{f_{0}}+w_{2}k^{M}f_{0}^{2})c_{n}$.

######  Theorem 5.

The proposed objective function
$Q_{n}(\bm{x}\\!\\!,\bm{f^{l}}\\!\\!,\bm{f^{s}}\\!\\!,\bm{P}\\!\\!,\bm{d})$
with coupled optimization variables can be transformed to the convex function
with updated transform, which is expressed as
$\widetilde{Q}_{n}(\bm{\mathcal{X}}|\bm{\mathcal{A}},\bm{\mathcal{B}})$, where
$\mathcal{X}\coloneqq[\bm{x},\bm{f^{l}},\bm{f^{s}},\bm{P},\bm{d}]$ is the
space of optimization variables,
$\bm{\mathcal{A}}\coloneqq[\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\delta},\bm{\epsilon},\bm{\zeta},\bm{\eta},\bm{\theta}]$
is the auxiliary variables space, and
$\bm{\mathcal{B}}\coloneqq[\bm{b},\bm{e},\bm{g},\bm{h},\bm{j},\bm{l},\bm{q},\bm{z}]$
is the constant space.

Proof: Please see Appendix D. $\hfill\blacksquare$

Then the transformed objective function can be derived as:

$\displaystyle\sum_{n=1}^{N}\widetilde{Q}_{n}(\bm{\mathcal{X}}|\bm{\mathcal{A}},\bm{\mathcal{B}})-\tau\cdot
H(\bm{x}|\bm{x}^{(i)}),$ (57)

where
$\widetilde{Q}_{n}(\bm{\mathcal{X}}|\bm{\mathcal{A}},\bm{\mathcal{B}})=\widetilde{O}_{n}+\widetilde{S}_{n}+\widetilde{U}_{n}+\widetilde{V}_{n}$
is explained in Appendix D.

However, this optimization problem is not convex as the optimization variables
are still coupled in the constraint (52c). Thus, we apply the proposed updated
transform to decouple the variables as follows:

$\displaystyle\sum_{n=1}^{N}[(f_{n}^{s})^{2}(\lambda_{n}^{(k)}+u_{n}^{(k)})+\frac{x_{n,1}^{2}}{4(\lambda_{n}^{(k)}+u_{n}^{(k)})}]-F^{s}\leq
0,$ (58)

where auxiliary variable $\lambda_{n}^{(k)}$ and constant $u_{n}^{(k)}$ obey
the rules in Theorem 3. And
$\lambda_{n}^{(k)}=\frac{x_{n,1}^{(k)}}{2f_{n}^{s(k)}}$ in the $(k+1)$-th
iteration.

The the sub-problem of the original problem in the $(k+1)$-th iteration of
updated transform under the $(i+1)$-th iteration of SCA approach is
reformulated as:

$\displaystyle\underset{\bm{x},\bm{f^{l}},\bm{f^{s}},\bm{P},\bm{d}}{\text{minimize}}~{}~{}$
$\displaystyle\sum_{n=1}^{N}\widetilde{Q}_{n}(\bm{\mathcal{X}}|\bm{\mathcal{A}}^{(k)},\bm{\mathcal{B}}^{(k)})-\tau\cdot
H(\bm{x}|\bm{x}^{(i)})$ (59) subject to
$\displaystyle(\ref{userc1}),(\ref{userc2}),(\ref{userc4}),(\ref{userc5}),(\ref{userc6}),(\ref{userc7}),(\ref{userc8_1}),(\ref{userC3_1})$

Then the original optimization problem can be addressed through an iterative
process. For this user association practical application, various analysis
methods can be considered. To prevent unnecessary repetition in analyses, the
CVX toolboxes are utilized for solving each convex sub-problem efficiently.

Proposed Algorithm: In the proposed method with the convergence of SCA
technique, a penalty function is employed to further facilitate the
transformation of various conditions, effectively segmenting the algorithm
into two complementary components: Inter-Sub-Problem Programming and Intra-
Sub-Problem Programming. For the inter-sub-problem programming as illustrated
in Algorithm 5, it focused on deriving the optimal solution $\bm{x}^{(i)}$ in
the $i$-th sub-problem. This solution is subsequently utilized in the
succeeding iteration of the SCA method. Then the proposed intra-sub-problem
programming as illustrated in Algorithm 6 which is obtained after adopting the
updated transform will be utilized to derive the optimal solution in this
succeeding iteration. Therefore, the proposed algorithm will converge and get
the optimal solutions.

1 Initialization of the iteration index: $i=1$;

2Initialization of the optimal solution space:
$\bm{\mathcal{S}}^{(0)}\\!\\!\\!=\\!\\![\bm{x}^{(0)}\\!\\!,{\bm{f^{l}}}^{(0)}\\!\\!,{\bm{f^{s}}}^{(0)}\\!\\!,\bm{P}^{(0)}\\!\\!,\bm{d}^{(0)}]$;

3Adopt SCA method to obtain the problem (59);

4repeat

5 Obtain the $i$-th sub-problem by using $\bm{x}^{(i-1)}$;

6 Solve the $i$-th sub-problem by using Algorithm 6 to get the optimal optimal
variable value
$\mathcal{X}^{*}\\!=\\![\bm{x}^{*}\\!\\!,{\bm{f^{l}}}^{*}\\!\\!,{\bm{f^{s}}}^{*}\\!\\!,\bm{P}^{*}\\!\\!,\bm{d}^{*}]$;

7 Let $\bm{\mathcal{S}}^{i}\leftarrow\mathcal{X}^{*}$ of $i$-th sub-problem;

8 Set $i\leftarrow i+1$;

9until
$|\bm{\mathcal{S}}^{(i)}-\bm{\mathcal{S}}^{(i-1)}|\leq\bar{\epsilon}_{0}$ or
reach the maximum iteration number $I$;

return
$\bm{\mathcal{S}}^{(i)}=[\bm{x}^{(i)}\\!\\!,{\bm{f^{l}}}^{(i)}\\!\\!,{\bm{f^{s}}}^{(i)}\\!\\!,\bm{P}^{(i)}\\!\\!,\bm{d}^{(i)}]$
as the optimal solution of the original optimization problem.

Algorithm 5 Inter-Sub-Problem Programming

1

2Initialization of the iteration index: $k=0$;

3Initialization of the optimization variable space:
$\bm{\mathcal{X}}^{(0)}\\!=\\![\bm{x}^{(0)}\\!\\!,{\bm{f^{l}}}^{(0)}\\!\\!,{\bm{f^{s}}}^{(0)}\\!\\!,\bm{P}^{(0)}\\!\\!,\bm{d}^{(0)}]$;

4Calculate and derive auxiliary variable space: $\bm{\mathcal{A}}^{(0)}$ and
constant space: $\bm{\mathcal{B}}^{(0)}$ based on the analysis of Theorem 5;

5repeat

6 Obtain the optimal variable $\bm{\mathcal{X}}^{(k+1)}$ of $(k+1)$-th
iteration by adopting CVX toolboxes when given auxiliary variable space
$\bm{\mathcal{A}}^{(k)}$ and constant $\bm{\mathcal{B}}^{(k)}$;

7 Update $\bm{\mathcal{A}}^{(k+1)}$ and $\bm{\mathcal{B}}^{(k+1)}$ with given
$\bm{\mathcal{X}}^{(k+1)}$;

8 $k\leftarrow k+1$;

9until Convergence or reach the max iteration number $K$;

return $\bm{\mathcal{X}}^{*}\leftarrow\bm{\mathcal{X}}^{(k)}$ as the optimal
solution of the $i$-th sub-problem.

Algorithm 6 Intra-Sub-Problem Programming

##  V Experimental Comparioson

In this section, we conduct experiments based on the two optimization
scenarios to evaluate the performance of the proposed updated transform.

###  V-A Scenarios 1: Partial Offloading

Based on the partial offloading scenario, in this experiment, we consider a
communication network model with the integration of AIGC technology and take
the maximum diffusion steps of the reverse diffusion stage into consideration.
To further greatly and clearly evaluate the performance of the proposed
transform, we set the total number of users $N$ is 30. To generalize the
experimental result without any distortion and error, the original value of
the average error rate is set as 1, which implies the original content is
complete Gaussian noise. Based on the resource limitation, the fixed
discretization steps are $\Delta t_{n,0}=1/500$ and $\Delta t_{n,1}=1/1000$.
The computing capacity $g_{n}$ and frequency of mobile user $f_{n}$ are set as
$10$GHz and $1.5$GHz by default. The computation energy efficiency coefficient
$k_{n}$ and $k_{e}$ is $10^{-26}$. For the penalty parameter, we set the value
as $10^{5}$.

(a)

(b)

(c)

Figure 1: Consumption under Different Maximum Limitations of Resources.

Figure 2: Joint Optimization Performance.

Fig. 2 and Fig. 2 illustrate the performance of the partial offloading
scenarios adopting the proposed updated transform. We can derive that the
proposed updated transform method can achieve better objective function values
by comparing it with diverse joint optimization scenarios. Especially, in Fig.
2, with the increment of the resource, all three lines exhibit an initial
decline followed by a stabilization phase upon reaching an optimal solution.
This observation underscores that as the system benefits from a higher
resource allocation for task processing, it tends to prioritize the
augmentation of the utility function to achieve superior joint optimization
performance.

###  V-B Scenarios 2: User Association

To evaluate the performance of the proposed transform in heterogeneous
communication networks, we consider a network that consists of $N=20$ users.
The location of the MBS is fixed at the centre of the network. Locations of
the SBS and mobile users are randomly distributed. We set the maximum
transmission power of each mobile user as $100$mW. The path-loss between the
MBS and the mobile user is simulated by $128.1+36.7\log_{10}(d)+\mu$ (in dB),
and that between the SBS and the mobile user is set as
$140.7+36.7\log_{10}(d)+\mu$ (in dB), where $d$ is the distance in km and
$\mu$ satisfies the log-distribution $\mathcal{N}(0,8\text{dB})$. We set the
AWGN noise power as $\sigma^{2}=-110$dBm. The bandwidth of MBS and SBS are set
as 10MHz and 5MHz respectively. For the computation frequency of the SBS and
mobile user, we set $F^{s}=20$GHz and $F_{n}=1$GHz. The data size and required
number of CPU cycles per bit follow the of each computation task are set as
$d_{n}=350$KB and $c_{n}=75$ cycles/bit. For the computation resource of MBS,
we set the $f_{0}=5$GHz and $r_{0}=1$Gbps. The computation energy efficiency
coefficient $k^{l}$, $k^{S}$, and $k^{M}$ are set as $1\times 10^{-25}$. For
the penalty parameter $\tau$, we set the value as $10^{5}$.

To evaluate the superiority of the transform we are pursuing, we compare the
optimization performance using different methods including our proposed
transform and AO method. Fig. 3 shows the result of the values of cost
functions with the iterations. AO method in this proposed scenario has a
larger number of iterations to converge and a worse optimization result due to
the increasing computational complexity of the optimization variables and the
objective function. Our proposed updated transform approach not only has a
better convergence rate but also a greater optimum after iterations.
Therefore, we can derive that the updated transform has a superior performance
in this practical scenario based on the analysis of numerical experiments.

Figure 3: Joint Optimization Performance of Distinct Methods

##  VI Conclusion

In this paper, we introduced the updated transform based on the optimization
transform in prior JSAC work [2] introduced by Zhao et al., which can be
adopted in the MP and FP problems to improve the communication network
performance. The proposed updated transform is mainly focused on tackling the
intractable dilemmas which exist in the minimization optimization problem in
practical scenarios, especially mobile edge computing networks and 5G
heterogeneous computing systems. By comparing with the traditional
optimization techniques, e.g., alternative optimization and Newton’s Method,
the proposed updated transform reformulates the original optimization problem
into a sequence of convex sub-problems to obtain the stationary point with
less computational complexity.

## References

  * [1] Y. Wang, C. Liu, and J. Zhao, “Offloading and Quality Control for AI Generated Content Services in Edge Computing Networks,” submitted to the 2023 IEEE International Conference on Communication (ICC), available at https://personal.ntu.edu.sg/JunZhao/ICC2024AIGC.pdf .
  * [2] J. Zhao, L. Qian, and W. Yu, “Human-centric resource allocation in the Metaverse over wireless communications,” _IEEE Journal on Selected Areas in Communications (JSAC)_ , 2023, The paper has been accepted to JSAC, but has not yet appeared in IEEE Xplore. The pdf can be downloaded from https://arxiv.org/pdf/2304.00355.pdf or https://personal.ntu.edu.sg/JunZhao/JSAC2023.pdf .
  * [3] Y. Jong, “An Efficient Global Optimization Algorithm for Nonlinear Sum-of-Ratios Problem,” _Optimization Online_ , pp. 1–21, 2012.
  * [4] P. Shen, K. Wang, and T. Lu, “Global optimization algorithm for solving linear multiplicative programming problems,” _Optimization_ , vol. 71, no. 6, pp. 1421–1441, 2022.
  * [5] J. Feng, W. Zhang, Q. Pei, J. Wu, and X. Lin, “Heterogeneous Computation and Resource Allocation for Wireless Powered Federated Edge Learning Systems,” _IEEE Transactions on Communications_ , vol. 70, no. 5, pp. 3220–3233, 2022.
  * [6] F. Pervez, L. Zhao, and C. Yang, “Joint User Association, Power Optimization and Trajectory Control in an Integrated Satellite-Aerial-Terrestrial Network,” _IEEE Transactions on Wireless Communications_ , vol. 21, pp. 3279–3290, Oct. 2021.
  * [7] J. Moon, S. H. Lee, H. Lee, and I. Lee, “Proactive Eavesdropping With Jamming and Eavesdropping Mode Selection,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 7, pp. 3726–3738, 2019.
  * [8] P. H. Li and H. Y. Youn, “Gradient-Based Adaptive Modeling for IoT Data Transmission Reduction,” _Wirel. Netw._ , vol. 26, no. 8, p. 6175–6188, nov 2020. [Online]. Available: https://doi.org/10.1007/s11276-020-02426-9
  * [9] H. Amiriara, F. Ashtiani, M. Mirmohseni, and M. Nasiri-Kenari, “IRS-User Association in IRS-Aided MISO Wireless Networks: Convex Optimization and Machine Learning Approaches,” Oct. 2022.
  * [10] K.-D. Lu and Z.-G. Wu, “Genetic Algorithm-Based Cumulative Sum Method for Jamming Attack Detection of Cyber-Physical Power Systems,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 71, pp. 1–10, 2022.
  * [11] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, March 2004.
  * [12] M. Grant, S. Boyd, and Y. Ye, “CVX: Matlab software for disciplined convex programming,” 2009. [Online]. Available: http://cvxr.com/cvx/
  * [13] S. Schaible, “Fractional Programming,” _Handbook of global optimization_ , pp. 495–608, 1995.
  * [14] S. Boyd, L. Xiao, and A. Mutapcic, “Subgradient Methods,” _lecture notes of EE392o, Stanford University, Autumn Quarter_ , vol. 2004, pp. 2004–2005, 2003.
  * [15] R. Horst and P. M. Pardalos, _Handbook of Global Optimization_. Springer Science & Business Media, 2013, vol. 2.
  * [16] S. Boyd and J. Mattingley, “Branch and Bound Methods,” _Notes for EE364b, Stanford University_ , vol. 2006, p. 07, 2007.
  * [17] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “Mobile Edge Computing: Survey and Research Outlook,” _arXiv preprint arXiv:1701.01090_ , pp. 1–37, 2017.
  * [18] M. Asim, M. ELAffendi, and A. A. A. El-Latif, “Multi-IRS and Multi-UAV-Assisted MEC System for 5G/6G Networks: Efficient Joint Trajectory Optimization and Passive Beamforming Framework,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 24, no. 4, pp. 4553–4564, Apr. 2023.
  * [19] Q. Chen, G. Yu, R. Yin, and G. Y. Li, “Energy-Efficient User Association and Resource Allocation for Multistream Carrier Aggregation,” _IEEE TVT_ , vol. 65, no. 8, pp. 6366–6376, Aug. 2016.
  * [20] Q. Li, A. Nayak, Y. Zhang, and F. R. Yu, “A Cooperative Recharging-Transmission Strategy in Powered UAV-Aided Terahertz Downlink Networks,” _IEEE Transactions on Vehicular Technology_ , vol. 72, no. 4, pp. 5479–5484, Apr. 2023.
  * [21] C. Ding, J.-B. Wang, H. Zhang, M. Lin, and G. Y. Li, “Joint Optimization of Transmission and Computation Resources for Satellite and High Altitude Platform Assisted Edge Computing,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 2, pp. 1362–1377, Feb. 2022.
  * [22] E. Sisinni, A. Saifullah, S. Han, U. Jennehag, and M. Gidlund, “Industrial Internet of Things: Challenges, Opportunities, and Directions,” _IEEE transactions on industrial informatics_ , vol. 14, no. 11, pp. 4724–4734, 2018.
  * [23] U. Saleem, Y. Liu, S. Jangsher, X. Tao, and Y. Li, “Latency Minimization for D2D-Enabled Partial Computation Offloading in Mobile Edge Computing,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 4, pp. 4472–4486, 2020.
  * [24] M. S. Bute, P. Fan, L. Zhang, and F. Abbas, “An Efficient Distributed Task Offloading Scheme for Vehicular Edge Computing Networks,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 12, pp. 13 149–13 161, 2021.
  * [25] X. Zhou, C. Liu, and J. Zhao, “Resource Allocation of Federated Learning for the Metaverse with Mobile Augmented Reality,” _IEEE Transactions on Wireless Communications_ , 2023.
  * [26] H. Xiao, J. Zhao, J. Feng, L. Liu, Q. Pei, and W. Shi, “Joint Optimization of Security Strength and Resource Allocation for Computation Offloading in Vehicular Edge Computing,” _IEEE Transactions on Wireless Communications_ , 2023.
  * [27] Y. Dai, D. Xu, S. Maharjan, and Y. Zhang, “Joint Computation Offloading and User Association in Multi-Task Mobile Edge Computing,” _IEEE Transactions on Vehicular Technology_ , vol. 67, no. 12, pp. 12 313–12 325, 2018.
  * [28] Y. Li, H. Ma, L. Wang, S. Mao, and G. Wang, “Optimized Content Caching and User Association for Edge Computing in Densely Deployed Heterogeneous Networks,” _IEEE Transactions on Mobile Computing_ , vol. 21, no. 6, pp. 2130–2142, Jun. 2022.
  * [29] C. Wang, D. Deng, L. Xu, and W. Wang, “Resource Scheduling Based on Deep Reinforcement Learning in UAV Assisted Emergency Communication Networks,” _IEEE Transactions on Communications_ , vol. 70, no. 6, pp. 3834–3848, 2022.
  * [30] M. A. Qureshi, A. Nika, and C. Tekin, “Multi-User Small Base Station Association via Contextual Combinatorial Volatile Bandits,” _IEEE Transactions on Communications_ , vol. 69, no. 6, pp. 3726–3740, 2021.
  * [31] Y. Sun, P. Babu, and D. P. Palomar, “Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 3, pp. 794–816, 2016.

##  Appendix A Proof of Theorem 3

To verify the Theorem 3, We conduct the proof of the sufficiency and necessity
with respect to the range of functions $A(\bm{x})$ and $B(\bm{x})$.

###  A-A $A(\bm{x}^{(t)})\geq 0$ and $B(\bm{x}^{(t)})>0$

Deriving from the given adaptive constant in (17) and auxiliary variable in
(20) in the $t$-th iteration, we further obtain the exact value of $c^{(t)}$
and $y^{(t)}$ that

$\displaystyle
y^{(t)}=\left\\{\begin{array}[]{ll}\cfrac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})},&\text{if
}\cfrac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})}\geq 0,\\\ \hskip
2.0pt0,&\text{others},\end{array}\right.$ (62)

where $c^{(t)}=0$ based on the mapped domain of variable $\bm{x}^{(t)}$ on
$B(\bm{x})$. Then the update transform can be inferred upon the value of the
auxiliary variable and adaptive constant:

$\displaystyle
F_{\text{update}}(\bm{x},y^{(t)})=[A(\bm{x})]^{2}y^{(t)}+\frac{[B(\bm{x})]^{2}}{4y^{(t)}},$
(63)

which is equal to the proposed transform in [2]. Therefore, the optimum in
$t$-th iteration can be obtained based on the updated transform. Thus the
necessity in this case is verified.

Next, given the updated transform in (14) and assuming that
$y^{\prime}=y+c\in\mathbb{R}_{+}$, the transform is derived:

$\displaystyle
F_{\text{update}}(\bm{x},y^{\prime})=[A(\bm{x})]^{2}y^{\prime}+\frac{[B(\bm{x})]^{2}}{4y^{\prime}}.$
(64)

Then the first-order partial derivative can be derived:

$\displaystyle\frac{\partial F_{\text{update}}}{\partial
y^{\prime(t)}}=[A(\bm{x})]^{2}-\frac{[B(\bm{x})]^{2}}{4y^{\prime 2}},$ (65)

where the stationary point can be obtained when
$y^{\prime(t)}=\frac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})}$. Based on the
monotonicity of the function by deriving the second-order partial derivative,
we further obtain that the stationary point is the optimum in the current
iteration.

However, if the optimal solution can be always reached under the current
assumptions and the robustness property of the transform is preserved by
introducing the adaptive $c$ in each iteration, the constraints following need
to be met:

$\displaystyle y^{\prime(t)}=y^{(t)},~{}y^{\prime(t)}\geq
0,\text{and}~{}y^{(t)}\geq 0,$ (66)

Therefore, we can get that
$y^{(t)}=\frac{B(\bm{x}^{(t)})}{2A(\bm{x}^{(t)})}-c^{(t)}$ where $c^{(t)}=0$.
Thus, the sufficiency and robustness (P5) of this theorem in this case are
verified.

###  A-B $A(\bm{x}^{(t)})\geq 0$ and $B(\bm{x}^{(t)})=0$

In this subsection, because the property (P3) relaxed objective, we get that
when $B(\bm{x})=0$, the original objective function and transformed function
can not be equivalent. Therefore, what we need to verify is whether the
optimal solutions between the original problem and the transformed problem are
equivalent given values of $c^{(t)}$ and $y^{(t)}$.

Firstly, we focus on the monotonicity of transformed function
$F_{\text{update}}(\bm{x},y)$. By taking the derivative of the transformed
function and solving for stationary point based on $\frac{\partial
F_{\text{update}}}{\partial y}=0$, we categorize and discuss the monotonicity
of $F_{\text{update}}(\bm{x},y)$ in terms of the availability of the
stationary point as follows:

  * •

Case 1: In this case where the stationary point exists, we infer the
formulation of stationary point in the $t$-th iteration as
$\frac{B(\bm{x^{(t)}})}{2A(\bm{x^{(t)}})}-c^{(t)}$ with condition
$\frac{B(\bm{x^{(t)}})}{2A(\bm{x^{(t)}})}\geq c^{(t)}$. Therefore, it can be
derived that the transformed function is decreasing within
$[0,\frac{B(\bm{x^{(t)}})}{2A(\bm{x^{(t)}})}-c^{(t)}]$ and increasing within
$[\frac{B(\bm{x^{(t)}})}{2A(\bm{x^{(t)}})}-c^{(t)},+\infty)$ with fixed
$x^{(t)}$. The value of $y^{(t)}$ can be further determined.

  * •

Case 2: Instead, when the stationary point is not available, it is
underlyingly implied that condition
$\frac{B(\bm{x^{(t)}})}{2A(\bm{x^{(t)}})}\geq c^{(t)}$ is conflicted. Then the
proposed transformed function is turned into being monotonically increasing
for $y^{(t)}$ with the range $[0,+\infty)$.

The above discussion of stationary point needs to be able to both satisfy the
nature of each proposed property and to bring Dilemma 1 to a resolution. Thus
we further take case 2 into account and utilize the property that its feasible
domain contains 0 and its non-decreasing nature to solve Dilemma 1.

Next, we further prove the feasibility of auxiliary variable values and
adaptive constant values when $B(\bm{x}^{(t)})=0$. It can be inferred that the
value of $y^{(t)}$ equals zero and the value of $c^{(t)}$ is also set as
$c_{1}>0$. The updated transform is thus able to substitute the auxiliary
variables and obtain the minimum value of the transformed function based on
the analysis of monotonicity in case 2.

Until now, the theorem has been proved. We can derive that the proposed
transform satisfies the properties and converges the original MP problem.
$\hfill\blacksquare$

##  Appendix B Proof of Corollary 3

To verify this corollary, we rewrite the original problem (24) by assuming
$t_{k}=A_{k}(\bm{x})B_{k}(\bm{x})$ and the rewritten vision is as:

$\displaystyle\underset{\bm{x},\bm{t}}{\text{minimize}}\hskip
15.0pt\sum_{k=1}^{K}G_{k}(t_{k})$ (67a) $\displaystyle\text{subject to}\hskip
14.0pt\bm{x}\in\mathcal{X},$ (67b) $\displaystyle\hskip
46.0ptt_{k}=A_{k}(\bm{x})B_{k}(\bm{x}),\forall k.$ (67c)

Based on the property (P3), we obtain that each $t_{k}$ can be replaced with
$\underset{y_{k}}{\min}[A_{k}(\bm{x})]^{2}(y_{k}+c_{k})+\frac{[B_{k}(\bm{x})]^{2}}{4(y_{k}+c_{k})}$
for both cases $B_{k}(\bm{x})=0$ and $B_{k}(\bm{x})\neq 0$ which has been
verified in Appendix A. Furthermore, as function $G_{k}(\cdot)$ is non-
decreasing, the objective function can be formulated as
$\underset{\bm{x}}{\min}\sum_{k=1}^{K}G_{k}(\underset{y_{k}}{\min}\\{[A_{k}(\bm{x})]^{2}(y_{k}+c_{k})+\frac{[B_{k}(\bm{x})]^{2}}{4(y_{k}+c_{k})}\\})$.
This is equivalent to objective function in (25). Therefore, the corollary is
proved and the optimum of the transformed problem is equal to the original
problem. $\hfill\blacksquare$

##  Appendix C Proof of Theorem 4

In order to find the optimal $[\bm{x}^{*},{\bm{f^{l}}}^{*},{\bm{f^{e}}}^{*}]$
that satisfies KKT conditions, the ensuing analysis rooted in principles of
optimization theory is presented.

Deriving from the functional expression $D_{n}(x_{n})$ as delineated in (33a),
two properties of this condition can be inferred contingent upon the values of
auxiliary variables and Lagrange multipliers: 1). $D_{n}(x_{n})$ is non-
decreasing for $x_{n}$ and 2). Specifically, we can obtain the explicit
expression $\widetilde{x}_{n}=D_{n}^{-1}(0)$ by setting $\beta=0$ and
$\gamma_{n}=0$ if $D_{n}(x_{n})=0$ has a solution. Then we proceed to discuss
the different cases based on conditions (LABEL:kktCa) and (LABEL:kktCb) which
are outlined below:

  * •

Case 1: $\widetilde{x}_{n}\geq 1$. In this case, we can infer that
$D_{n}(x_{n})$ is equal to or less than zero (i.e. $D_{n}(1)\leq 0$).
Therefore, the optimal solution can be set that $\widetilde{x}_{n}=1$ and
$\beta_{n}=0$ to meet the conditions, and then the value of $\gamma_{n}$ is
equal to $-D_{n}(1)$ which exactly meets the condition (LABEL:kktCb).

  * •

Case 2: $0<\widetilde{x}_{n}<1$. We can simply set the optimal value of
optimization variable $x_{n}$ as $\widetilde{x}_{n}$ with $\beta_{n}=0$ and
$\gamma_{n}=0$ based on the second property.

  * •

Case 3: $\widetilde{x}_{n}\leq 0$. Conversely with case 1,
$\widetilde{x}_{n}\leq 0$ means when $x_{n}\\!=\\!0$, $D_{n}(0)$ is equal to
or better than 0. Therefore, we choose the feasible solution as
$\widetilde{x}_{n}=0$,$\gamma_{n}=0$, and $\beta_{n}=D_{n}(0)$.

Thus, we summarize all of the above cases as follows:

$\displaystyle\left\\{\begin{array}[]{l}x_{n}^{*}=\max\\{\min\\{\widetilde{x}_{n},1\\},0\\};\\\
\beta_{n}^{*}=\max\\{D_{n}(0),0\\};\\\
\gamma_{n}^{*}=-\min\\{D_{n}(1),0\\};\end{array}\right.$ (71)

Based on the convexity of the function $H_{n,1}(f_{n}^{l})$, it can be
inferred that the term $[H_{n,1}(f_{n}^{l})]^{2}(u_{n}^{(k)}+c_{n}^{(k)})$
maintains convexity with the scalar composition theory (Page 84 in [11]). We
next obtain the non-decreasing nature of the function $Q_{n}(f_{n}^{l})$ as
the decoupling of each optimization variable and being obtained by first-order
derivation of the mentioned term. Then we can discuss the similar cases with
$x_{n}$ by assuming $\widetilde{f}_{n}^{l}=Q_{n}^{-1}(0)$ and summarize the
discussion as follows:

$\displaystyle\left\\{\begin{array}[]{l}{f_{n}^{l}}^{*}=\max\\{\min\\{\widetilde{f}_{n}^{l},F_{n}^{l}\\},0\\};\\\
\epsilon_{n}^{*}=\max\\{Q_{n}(0),0\\};\\\
\zeta_{n}^{*}=-\min\\{Q_{n}(F_{n}^{l}),0\\};\end{array}\right.$ (75)

According to the analysis of the optimization variable $f_{n}^{l}$, we obtain
similar characteristics of the variable $f_{n}^{e}$ in the function
$R_{n}(f_{n}^{e},\delta)$. Assume that when $R_{n}(f_{n}^{e},\delta)=0$, the
value expression of $f_{n}^{e}$ is denoted as $\widehat{f}_{n}^{e}(\delta)$.
We discuss the cases based on the (33c):

  * •

Case 1: $\widehat{f}_{n}^{e}(\delta)\geq F_{n}^{e}$. In this case, we can
infer that $R_{n}(F_{n}^{e},\delta)\leq 0$). Therefore, the optimal solution
can be set that $\widehat{f}_{n}^{e}(\delta)=F_{n}^{e}$ and $\eta_{n}=0$ to
meet the conditions, and then the value of $\theta_{n}$ is
$-R_{n}(F_{n}^{e},\delta)$ which exactly meets the conditions.

  * •

Case 2: $0<\widehat{f}_{n}^{e}(\delta)<1$. We can set the optimal value as
$\widehat{f}_{n}^{e}(\delta)$ with $\eta_{n}=0$ and $\theta_{n}=0$ based on
the second property.

  * •

Case 3: $\widehat{f}_{n}^{e}(\delta)\leq 0$. Unlike case 1,
$\widehat{f}_{n}^{e}(\delta)\leq 0$ means when
$\widehat{f}_{n}^{e}(\delta)\\!=\\!0$, $R_{n}(0,\delta)$ is equal to or better
than 0. Therefore, we choose the feasible solution as
$\widehat{f}_{n}^{e}(\delta)=0$, $\theta_{n}=0$, and
$\eta_{n}=R_{n}(0,\delta)$.

Therefore, for the above analysis, we summarise that:

$\displaystyle\left\\{\begin{array}[]{l}\widetilde{f}_{n}^{e}(\delta)=\max\\{\min\\{\widehat{f}_{n}^{e}(\delta),F_{n}^{e}\\},0\\};\\\
\widetilde{\eta}_{n}(\delta)=\max\\{R_{n}(0,\delta),0\\};\\\
\widetilde{\theta}_{n}(\delta)=-\min\\{R_{n}(F_{n}^{e},\delta),0\\};\end{array}\right.$
(79)

For the optimization variable $f_{n}^{e}$, we cannot directly obtain the
feasible solution while getting the formulation related to the multiplier
$\delta$. Drawing from the condition (LABEL:kktCc), we discuss the value of
$\delta$ based on the scenarios assuming $\delta=0$:

  * •

Case 1: $\sum_{n\in\mathcal{N}}\widetilde{f}_{n}^{e}(0)\leq F^{e}$. In this
situation, we set $\delta=0$ to meet the condition (35c).

  * •

Case 2: $\sum_{n\in\mathcal{N}}\widetilde{f}_{n}^{e}(0)>F^{e}$. Conversely, we
need to find the optimal value denoted as $\widetilde{\delta}$ of the $\delta$
based on the condition (LABEL:kktCc) by adopting the bisection method.

Consequently, the feasible solution of $\delta$ is expressed as:

$\displaystyle\delta^{*}=\left\\{\begin{array}[]{ll}0,&\sum_{n\in\mathcal{N}}\widetilde{f}_{n}^{e}(0)\leq
F^{e},\\\ \widetilde{\delta},&\text{others}.\end{array}\right.$ (82)

Until now, the optimal solution of the optimization variables
$[\bm{x}^{*}\\!\\!,\\!{\bm{f^{l}}}^{*}\\!\\!,\\!{\bm{f^{e}}}^{*}]$ and
Lagrange multiplier
$[\bm{\beta}^{*}\\!,\\!\bm{\gamma}^{*}\\!,\\!\delta^{*}\\!,\\!\bm{\epsilon}^{*}\\!,\\!\bm{\zeta}^{*}\\!,\\!\bm{\eta}^{*}\\!,\\!\bm{\theta}^{*}]$
can be obtained by above analysis. $\hfill\blacksquare$

##  Appendix D Proof of Theorem 5

To decouple the optimization variables in each term of the objective function,
we adopt the updated transform and introduce auxiliary variables in $(k+1)$-th
iteration as follows:

For the function $O_{n}(\bm{x},\bm{f^{l}},\bm{d})$, we introduce the auxiliary
variables $\bm{\alpha}$ and $\bm{\beta}$. Then the function in $(k+1)$-th
iteration can be transformed into
$\widetilde{O}_{n}(\bm{x},\bm{f^{l}},\bm{d}|\bm{\alpha}^{(k)},\bm{\beta}^{(k)},\bm{b}^{(k)},\bm{e}^{(k)})$
which equals to:

$\displaystyle\sum_{m\in\mathcal{M}}[\widehat{O}_{n,m}(\bm{f^{l}}\\!\\!,\bm{d}|\bm{\beta}^{(k)}\\!\\!,\bm{e}^{(k)})]^{2}(\alpha_{n,m}^{(k)}\\!+\\!b_{n,m}^{(k)})\\!+\\!\frac{x_{n,m}^{2}c_{n}}{4(\alpha_{n,m}^{(k)}\\!+\\!b_{n,m}^{(k)})},$

where
$\widehat{O}_{n,m}(\bm{f^{l}}\\!\\!,\bm{d}|\bm{\beta}^{(k)}\\!\\!,\bm{e}^{(k)})\\!\\!=\\!\\!(\frac{w_{1}}{f_{n}^{l}}\\!+\\!w_{2}k^{l}{f_{n}^{l}}^{2})^{2}(\beta_{n,m}^{(k)}+e_{n,m}^{(k)})+\frac{(d_{n}-d_{n,m})^{2}}{4(\beta_{n,m}^{(k)}+e_{n,m}^{(k)})}$.
When $x_{n,m}\neq 0$ and $d_{n}-d_{n,m}\neq 0$, values of auxiliary variables
are:

$\displaystyle\beta_{n,m}^{(k)}=\frac{d_{n}-d_{n,m}^{(k)}}{2[\frac{w_{1}}{{f_{n}^{l}}^{(k)}}+w_{2}k^{l}({f_{n}^{l}}^{(k)})^{2}]},$
$\displaystyle\alpha_{n,m}^{(k)}=\frac{x_{n,m}^{(k)}c_{n}}{2\widehat{O}_{n,m}({\bm{f^{l}}}^{(k)},\bm{d}^{(k)}|\bm{\beta}^{(k)},\bm{e}^{(k)})},$

and the selection of constant $\bm{b}^{(k)}$ and $\bm{e}^{(k)}$ follows the
rule in (17) and the following constants obey the same rule.

For function $S_{n}(\bm{x},\bm{P},\bm{d})$, it can be transformed as
$\widetilde{S}_{n}(\bm{x},\bm{P},\bm{d}|\bm{\gamma}^{(k)},\bm{\delta}^{(k)},\bm{g}^{(k)},\bm{h}^{(k)})$
which equals to:

$\displaystyle\sum_{m\in\mathcal{M}}[\widehat{S}_{n,m}(\bm{P}\\!\\!,\bm{d}|\bm{\delta}^{(k)}\\!\\!,\bm{h}^{(k)})]^{2}(\gamma_{n,m}^{(k)}\\!+\\!g_{n,m}^{(k)})\\!+\\!\frac{x_{n,m}^{2}}{4(\gamma_{n,m}^{(k)}\\!+\\!g_{n,m}^{(k)})},$

where

$\displaystyle\widehat{S}_{n,m}(\bm{P}\\!\\!,\bm{d}|\bm{\delta}^{(k)}\\!\\!,\bm{h}^{(k)})\\!\\!=\\!\\![\overline{S}(P_{n})]^{2}(\delta_{n,m}^{(k)}\\!\\!+\\!\\!h_{n,m}^{(k)})\\!\\!+\\!\\!\frac{d_{n,m}^{2}}{4(\delta_{n,m}^{(k)}+h_{n,m}^{(k)})},$
$\displaystyle\hskip
60.0pt\overline{S}(P_{n})=\frac{w_{1}+w_{2}P_{n}}{B_{m}\ln(1+\frac{P_{n}H_{n,m}}{\sigma^{2}})},$

$\bm{g}^{(k)},\bm{h}^{(k)}$ are the constant and auxiliary variables are
expressed as:

$\displaystyle\delta_{n,m}^{(k)}=\frac{d_{n,m}^{(k)}}{2\overline{S}(P_{n}^{(k)})},$
$\displaystyle\gamma_{n,m}^{(k)}=\frac{x_{n,m}^{(k)}}{2\widehat{S}_{n,m}(\bm{P}^{(k)},\bm{d}^{(k)}|\bm{\delta}^{(k)},\bm{h}^{(k)})},$

when the constants are equal to zero.

For function $U_{n}(\bm{x},\bm{f^{s}},\bm{d})$, we introduce the auxiliary
$\bm{\epsilon}$ and $\bm{\zeta}$ to transform it to
$\widetilde{U}_{n}(\bm{x},\bm{f^{s}},\bm{d}|\bm{\epsilon}^{(k)},\bm{\zeta}^{(k)},\bm{j}^{(k)},\bm{l}^{(k)})$
being equal to:

$\displaystyle[\widehat{U}_{n}(\bm{f^{s}},\bm{d}|\bm{\zeta}^{(k)},\bm{l}^{(k)})]^{2}(\epsilon_{n}^{(k)}+j_{n}^{(k)})+\frac{x_{n,1}^{2}}{4(\epsilon_{n}^{(k)}+j_{n}^{(k)})},$

where the constants are denoted as $\bm{j}^{(k)}$ and $\bm{l}^{(k)}$. Function
$\widehat{U}_{n}$ is expressed as:

$\displaystyle\widehat{U}_{n}(\bm{f^{s}}\\!\\!,\bm{d}|\bm{\zeta}^{(k)}\\!\\!,\bm{l}^{(k)})\\!\\!=\\!\\!(\frac{w_{1}}{f_{n}^{s}}\\!\\!+\\!\\!w_{2}k^{S}{f_{n}^{s}}^{2})^{2}(\zeta_{n}^{(k)}\\!\\!\\!+\\!\\!l_{n}^{(k)})\\!\\!+\\!\\!\frac{(d_{n,1}\\!\\!-\\!d_{n,1}^{{}^{\prime}})^{2}}{4(\zeta_{n}^{(k)}\\!\\!\\!+\\!l_{n}^{(k)})}.$

Based on the (20), if constants are equal to 0, auxiliary variables can be
inferred as:

$\displaystyle\epsilon_{n}^{(k)}=\frac{x_{n,1}^{(k)}}{2\widehat{U}_{n}({\bm{f^{s}}}^{(k)},\bm{d}^{(k)}|\bm{\zeta}^{(k)},\bm{l}^{(k)})},$
$\displaystyle\zeta_{n}^{(k)}=\frac{d_{n,1}^{(k)}-{d_{n,1}^{{}^{\prime}(k)}}}{2[\frac{w_{1}}{f_{n}^{s(k)}}\\!\\!+\\!\\!w_{2}k^{S}(f_{n}^{s(k)})^{2}]}.$

For the last function $V_{n}(\bm{x},\bm{d})$, it can be similarly transformed
to
$\widetilde{V}_{n}(\bm{x},\bm{d}|\bm{\eta}^{(k)},\bm{\theta}^{(k)},\bm{q}^{(k)},\bm{z}^{(k)})$
where $\bm{\eta}$ and $\bm{\theta}$ are auxiliary variables, and $\bm{q}$ and
$\bm{z}$ are the constants. Then the details of $\widetilde{V}_{n}$ is:
$\widetilde{V}_{n}=[d_{n,1}^{{}^{\prime}2}(\eta_{n}^{(k)}+q_{n}^{(k)})+\frac{x_{n,1}^{2}}{4(\eta_{n}^{(k)}+q_{n}^{(k)})}]C+[d_{n,2}^{2}(\theta_{n}^{(k)}+z_{n}^{(k)})+\frac{x_{n,2}^{2}}{4(\theta_{n}^{(k)}+z_{n}^{(k)})}](C-\frac{w_{1}+w_{2}\bar{P}}{r_{0}})$.
When auxiliary variables are not equal to zero, auxiliary variables are
expressed as:

$\displaystyle\eta_{n}^{(k)}=\frac{x_{n}^{(k)}}{2d_{n,1}^{{}^{\prime}(k)}},~{}~{}\theta_{n}^{(k)}=\frac{x_{n,2}^{(k)}}{2d_{n,2}^{(k)}}.$

Until now, the optimization variables in the term $w_{1}T_{n}+w_{2}E_{n}$ of
the objective function in (55) are transformed into a convex function by using
the updated transform. $\hfill\blacksquare$


* Sidoli et al. (2012b) Sidoli L., Mereghetti S., Sguera V., Pizzolato F., 2012b, MNRAS, 420, 554
  * Sidoli et al. (2008) Sidoli L. et al., 2008, ApJ, 687, 1230
  * Strüder et al. (2001) Strüder L. et al., 2001, A&A, 365, L18
  * Suleimanov, Meyer & Meyer-Hofmeister (2003) Suleimanov V., Meyer F., Meyer-Hofmeister E., 2003, A&A, 401, 1009
  * Takeuchi, Koyama & Warwick (1990) Takeuchi Y., Koyama K., Warwick R. S., 1990, PASJ, 42, 287
  * Tawara et al. (1989) Tawara Y., Yamauchi S., Awaki H., Kii T., Koyama K., Nagase F., 1989, PASJ, 41, 473
  * Thompson & Rothschild (2009) Thompson T. W. J., Rothschild R. E., 2009, ApJ, 691, 1744
  * Thompson et al. (2007) Thompson T. W. J., Tomsick J. A., in ’t Zand J. J. M., Rothschild R. E., Walter R., 2007, ApJ, 661, 447
  * Torrejón et al. (2010) Torrejón J. M., Negueruela I., Smith D. M., Harrison T. E., 2010, A&A, 510, A61
  * Torrejón et al. (2010) Torrejón, J. M., Schulz, N. S., Nowak, M. A., & Kallman, T. R. 2010, ApJ, 715, 947
  * Turner et al. (2001) Turner M. J. L. et al., 2001, A&A, 365, L27
  * Ulmer et al. (1973) Ulmer, M. P., Baity, W. A., Wheaton, W. A., & Peterson, L. E. 1973, Nature Physical Science, 242, 121
  * Vacca, Garmany & Shull (1996) Vacca W. D., Garmany C. D., Shull J. M., 1996, ApJ, 460, 914
  * Val Baker, Norton & Quaintrell (2005) Val Baker A. K. F., Norton A. J., Quaintrell H., 2005, A&A, 441, 685
  * van der Meer et al. (2005a) van der Meer A., Kaper L., di Salvo T., Méndez M., van der Klis M., Barr P., Trams N. R., 2005a, A&A, 432, 999
  * van der Meer et al. (2005b) van der Meer A., Kaper L., di Salvo T., Méndez M., van der Klis M., Barr P., Trams N. R., 2005b, A&A, 432, 999
  * van der Meer et al. (2007) van der Meer A., Kaper L., van Kerkwijk M. H., Heemskerk M. H. M., van den Heuvel E. P. J., 2007, A&A, 473, 523
  * Varun et al. (2019) Varun, Maitra C., Pradhan, P., Raichur H., & Paul B. 2019, MNRAS, 484, L1
  * Walter et al. (2004) Walter R. et al., 2004, The Astronomer’s Telegram, 229
  * Walter & Zurita Heras (2007) Walter R., Zurita Heras J., 2007, A&A, 476, 335
  * Walter et al. (2006) Walter R. et al., 2006, A&A, 453, 133
  * Weaver et al. (1996) Weaver K. A., Nousek J., Yaqoob T., Mushotzky R. F., Makino F., Otani C., 1996, ApJ, 458, 160
  * White (1978) White N. E., 1978, Nature, 271, 38
  * White, Kallman & Swank (1983) White N. E., Kallman T. R., Swank J. H., 1983, ApJ, 269, 264
  * Wojdowski et al. (1998) Wojdowski P., Clark G. W., Levine A. M., Woo J. W., Zhang S. N., 1998, ApJ, 502, 253
  * Wojdowski, Liedahl & Sako (2001) Wojdowski P. S., Liedahl D. A., Sako M., 2001, ApJ, 547, 973
  * Woo et al. (1996) Woo J. W., Clark G. W., Levine A. M., Corbet R. H. D., Nagase F., 1996, ApJ, 467, 811
  * Zurita Heras et al. (2006) Zurita Heras J. A., De Cesare G., Walter R., Bodaghee A., Bélanger G., Courvoisier T. J.-L., Shaw S. E., Stephen J. B., 2006, A&A, 448, 261
  * Zycki et al. (1994) Zycki P. T., Krolik J. H., Zdziarski A. A., Kallman T. R., 1994, ApJ, 437, 597