Search

Due to the advantages such as high flexibility, low cost and easy implementation offered by unmanned aerial vehicles (UAVs), a UAV-assisted network is regard as an appealing solution to a seamless coverage, high disaster-tolerant and on-demand wireless system. In this paper, we focus on the downlink transmission in a cache-enabled UAV-assisted wireless communication network, where UAVs cache popular content from a macro base station in advance and cooperatively transfer the content to users. We aim to minimize the average transmission latency of the system and to formulate an optimization problem that jointly optimizes the UAV location, beamforming and caching strategy. However, the formulated problem is very challenging because of its non-convexity and the highly coupled optimization variables. To solve this resulting problem efficiently, we decompose it into two subproblems, namely UAV location and beamforming optimization, and UAV caching strategy optimization. The first subproblem is an NP-hard joint optimization problem, while the second one is a linear programing problem. By adopting the first-order Taylor expansion, we propose a convex optimization algorithm based on the difference-of-convex (DC) method. Specifically, we bring out a method to apply linear approximation in the DC-based algorithm, which is particularly suitable to the problems involving complicated summations. The numerical results demonstrate that the proposed DC-based iterative optimization algorithm can efficiently reduce the average transmission latency of the system. [ABSTRACT FROM AUTHOR]

The Unsplittable Flow on a Path (UFP) problem has garnered considerable attention as a challenging combinatorial optimization problem with notable practical implications. Steered by its pivotal applications in power engineering, the present work formulates a novel generalization of UFP, wherein demands and capacities in the input instance are monotone step functions over the set of edges. As an initial step towards tackling this generalization, we draw on and extend ideas from prior research to devise a quasi-polynomial time approximation scheme under the premise that the demands and capacities lie in a quasi-polynomial range. Second, retaining the same assumption, an efficient logarithmic approximation is introduced for the single-source variant of the problem. Finally, we round up the contributions by designing a (kind of) black-box reduction that, under some mild conditions, allows to translate LP-based approximation algorithms for the studied problem into their counterparts for the Alternating Current Optimal Power Flow problem—a fundamental workflow in operation and control of power systems. [ABSTRACT FROM AUTHOR]

This paper introduces a general area-level model-based formulation to small area estimation based on generalized linear mixed models. By applying an optimization algorithm to the Laplace approximation of the likelihood, the maximum likelihood estimators of the model parameters are calculated. Empirical best predictors of small area quantities are derived and the corresponding mean squared errors are estimated by parametric bootstrap. Some simulation experiments are carried out to study the behavior of the fitting algorithm, the small area predictors and the estimators of the mean squared errors. By using data of the Spanish living condition survey of 2008, an application to the estimation of average annual net incomes in Spanish provinces by sex is given. [ABSTRACT FROM AUTHOR]

In a large cloud data center HPC system, a critical problem is how to allocate the submitted tasks to heterogeneous servers that will achieve the goal of maximizing the system’s gain defined as the value of completed tasks minus system operation costs. We consider this problem in the online setting that tasks arrive in batches and propose a novel deep reinforcement learning (DRL) enhanced greedy optimization algorithm of two-stage scheduling interacting task sequencing and task allocation. For task sequencing, we deploy a DRL module to predict the best allocation sequence for each arriving batch of tasks based on the knowledge (allocation strategies) learnt from previous batches. For task allocation, we propose a greedy strategy that allocates tasks to servers one by one online following the allocation sequence to maximize the total gain increase. We show that our greedy strategy has a performance guarantee of competitive ratio $\frac{1}{1+\kappa }$ 1 1 + κ to the optimal offline solution, which improves the existing result for the same problem, where $\kappa$ κ is upper bounded by the maximum cost-to-gain ratio of each task. While our DRL module enhances the greedy algorithm by providing the likely-optimal allocation sequence for each batch of arriving tasks, our greedy strategy bounds DRL’s prediction error within a proven worst-case performance guarantee for any allocation sequence. It enables a better solution quality than that obtainable from both DRL and greedy optimization alone. Extensive experiment evaluation results in both simulation and real application environments demonstrate the effectiveness and efficiency of our proposed algorithm. Compared with the state-of-the-art baselines, our algorithm increases the system gain by about 10% to 30%. Our algorithm provides an interesting example of combining machine learning (ML) and greedy optimization techniques to improve ML-based solutions with a worst-case performance guarantee for solving hard optimization problems. [ABSTRACT FROM AUTHOR]

The variational quantum algorithm (VQA) is a hybrid classical–quantum algorithm. It can actually run in an intermediate-scale quantum device where the number of available qubits is too limited to perform quantum error correction, so it is one of the most promising quantum algorithms in the noisy intermediate-scale quantum era. In this paper, two ideas for solving the learning with errors problem (LWE) using VQA are proposed. First, after reducing the LWE problem into the bounded distance decoding problem, the quantum approximation optimization algorithm (QAOA) is introduced to improve classical methods. Second, after the LWE problem is reduced into the unique shortest vector problem, the variational quantum eigensolver (VQE) is used to solve it, and the number of qubits required is calculated in detail. Small-scale experiments are carried out for the two LWE variational quantum algorithms, and the experiments show that VQA improves the quality of the classical solutions. [ABSTRACT FROM AUTHOR]

This article investigates the finite-time distributed approximate optimization problem of higher order multiagent systems, where the local cost functions are considered to be quadratic functions. This problem is solved via penalty-function-based method. First, by the penalty-function method, a global approximate cost function is constructed. Second, nonlinear distributed optimization algorithms are proposed for higher order multiagent systems by the tool of adding a power integrator technique. In the optimization algorithms design, the gradients of the approximate cost function are utilized. Under the proposed optimization algorithms, the agents approach the approximate optimal solution in finite time. Although there exist errors (they may be called approximation errors) between the approximate minimizers and the global accurate minimizer, the approximation errors can be regulated by penalty parameter and the relationship between the bound of the approximation errors and the penalty parameter is given explicitly. Furthermore, the proposed distributed approximate optimization algorithms are applied to the optimal rendezvous problem of wheeled multimobile robots, making the mobile robots achieve approximate optimization rendezvous in finite time. The effectiveness of the proposed distributed optimization algorithms and their applications to optimal rendezvous problem are validated by simulations. [ABSTRACT FROM AUTHOR]

In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window model. Based on the concept of diminishing-return ratio γ , we propose a (1 3 γ 2 −) -approximation algorithm with the memory O (k log 2 (k Φ 1 γ) 2 ) , where Φ is the ratio between maximum and minimum values of any singleton element of function f. Then, we improve the approximation ratio to (1 2 γ −) through the sub-windows at the expense of losing some memory. Our results generalize the corresponding results for the submodular case. [ABSTRACT FROM AUTHOR]

This article focuses on developing a static output feedback (SOF) control scheme for Takagi–Sugeno fuzzy systems. The proposed SOF controller does not share the same premise membership functions with the model, which permits enhancing the flexibility in controller design and implementation. By contrast with the state feedback case, the SOF control generally results in nonconvex design conditions. To circumvent this problem, we develop a successive convex optimization algorithm, which is based on solving a sequence of more tractable convex optimization problems obtained by approximating the nonconvex constraints with some convex ones. As a heuristic algorithm, the validity of the developed successive convex optimization algorithm is highly affected by initial conditions, and, recognizing this, we put forward an iterative procedure for determining the feasible initial condition. Finally, two illustrative examples are presented to validate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The design of a fuzzy neural network (FNN) has long been a challenging problem since most methods rely on approximation error to train an FNN, which may easily result in overfitting phenomenon to degrade the generalization performance. To improve the generalization performance, an FNN with a multiobjective optimization algorithm (MOO-FNN) is proposed in this article. First, the multilevel learning objectives are designed around the generalization performance to guide the training process of an FNN. Then, the method utilizes the approximation error, the structure complexity, and the output smoothness indicators instead of a single indicator to improve the evaluation accuracy of generalization performance. Second, an MOO algorithm with continuous–discrete variables is developed to optimize the FNN. Then, MOO is able to use a novel particle update method to adjust both the structure and parameters rather than adjusting them separately, thereby achieving suitable generalization performance of the FNN. Third, the convergence of MOO-FNN is analyzed in detail to guarantee its successful applications. Finally, the experimental studies of MOO-FNN have been performed on model identification of nonlinear systems to verify the effectiveness. The results illustrate that MOO-FNN has a significant improvement over some state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

We consider the problem of fairly allocating indivisible goods, focusing on a recently introduced notion of fairness called maximin share guarantee: each player's value for his allocation should be at least as high as what he can guarantee by dividing the items into as many bundles as there are players and receiving his least desirable bundle. Assuming additive valuation functions, we show that such allocations may not exist, but allocations guaranteeing each player 2/3 of the above value always exist. These theoretical results have direct practical implications. [ABSTRACT FROM AUTHOR]

Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithm (QAOA) constitutes a promising candidate for demonstrating tangible quantum advantages based on NISQ devices. In this paper, we consider the maximum likelihood (ML) detection problem of binary symbols transmitted over a multiple-input and multiple-output (MIMO) channel, where finding the optimal solution is exponentially hard using classical computers. Here, we apply the QAOA for the ML detection by encoding the problem of interest into a level- $p$ QAOA circuit having $2p$ variational parameters, which can be optimized by classical optimizers. This level- $p$ QAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately in $p$ consecutive rounds. More explicitly, we first encode the optimal solution of the ML detection problem into the ground state of a problem Hamiltonian. Using the quantum adiabatic evolution technique, we provide both analytical and numerical results for characterizing the evolution of the eigenvalues of the quantum system used for ML detection. Then, for level-1 QAOA circuits, we derive the analytical expressions of the expectation values of the QAOA and discuss the complexity of the QAOA based ML detector. Explicitly, we evaluate the computational complexity of the classical optimizer used and the storage requirement of simulating the QAOA. Finally, we evaluate the bit error rate (BER) of the QAOA based ML detector and compare it both to the classical ML detector and to the classical minimum mean squared error (MMSE) detector, demonstrating that the QAOA based ML detector is capable of approaching the performance of the classical ML detector. [ABSTRACT FROM AUTHOR]

We propose an algorithm to generate inner and outer polyhedral approximations to the upper image of a bounded convex vector optimization problem. It is an outer approximation algorithm and is based on solving norm-minimizing scalarizations. Unlike Pascoletti–Serafini scalarization used in the literature for similar purposes, it does not involve a direction parameter. Therefore, the algorithm is free of direction-biasedness. We also propose a modification of the algorithm by introducing a suitable compact subset of the upper image, which helps in proving for the first time the finiteness of an algorithm for convex vector optimization. The computational performance of the algorithms is illustrated using some of the benchmark test problems, which shows promising results in comparison to a similar algorithm that is based on Pascoletti–Serafini scalarization. [ABSTRACT FROM AUTHOR]

Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA's performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified. [ABSTRACT FROM AUTHOR]

A displacement aggregation strategy is proposed for the curvature pairs stored in a limited-memory BFGS (a.k.a. L-BFGS) method such that the resulting (inverse) Hessian approximations are equal to those that would be derived from a full-memory BFGS method. This means that, if a sufficiently large number of pairs are stored, then an optimization algorithm employing the limited-memory method can achieve the same theoretical convergence properties as when full-memory (inverse) Hessian approximations are stored and employed, such as a local superlinear rate of convergence under assumptions that are common for attaining such guarantees. To the best of our knowledge, this is the first work in which a local superlinear convergence rate guarantee is offered by a quasi-Newton scheme that does not either store all curvature pairs throughout the entire run of the optimization algorithm or store an explicit (inverse) Hessian approximation. Numerical results are presented to show that displacement aggregation within an adaptive L-BFGS scheme can lead to better performance than standard L-BFGS. [ABSTRACT FROM AUTHOR]

The manta ray foraging optimization algorithm (MRFO) is one of the promised meta-heuristic optimization algorithms. However, it can stick to a local minimum, consuming iterations without reaching the optimum solution. So, this paper proposes a hybridization between MRFO, and the genetic algorithm (GA) based on a pseudo parameter; where the GA can help MRFO to escape from falling into the local minimum. It is called a pseudo genetic algorithm with manta-ray foraging optimization (PGA-MRFO). The proposed algorithm is not a classical hybridization between MRFO and GA, wherein the classical hybridization consumes time in the search process as each algorithm is applied to all system variables. In addition, the classical hybridization results in an extended search algorithm, especially in systems with many variables. The PGA-MRFO hybridizes the pseudo-parameter-based GA and the MRFO algorithm to produce a more efficient algorithm that combines the advantages of both algorithms without getting stuck in a local minimum or taking a long time in the calculations. The pseudo parameter enables the GA to be applied to a specific number of variables and not to all system variables leading to reduce the computation time and burden. Also, the proposed algorithm used an approximation for the gradient of the objective function, which leads to dispensing derivatives calculations. Besides, PGA-MRFO depends on the pseudo inverse of non-square matrices, which saves calculations time; where the dependence on the pseudo inverse gives the algorithm more flexibility to deal with square and non-square systems. The proposed algorithm will be tested on the test functions that the main MRFO failed to find their optimum solution to prove its capability and efficiency. In addition, it will be applied to solve the unit commitment (UC) problem as one of the vital power system problems to show the validity of the proposed algorithm in practical applications. Finally, several analyses will be applied to the proposed algorithm to illustrate its effectiveness and reliability. [ABSTRACT FROM AUTHOR]

For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to compute an approximation of the nondominated set. A common technique for this approach is to generate a polyhedron which contains the nondominated set. However, often these approximations are used for further evaluations. For those applications a polyhedron is a structure that is not easy to handle. In this paper, we introduce an approximation with a simpler structure respecting the natural ordering. In particular, we compute a box-coverage of the nondominated set. To do so, we use an approach that, in general, allows us to update not only one but several boxes whenever a new nondominated point is found. The algorithm is guaranteed to stop with a finite number of boxes, each being sufficiently thin. [ABSTRACT FROM AUTHOR]

Existing wideband beampattern synthesis methods usually require multiple beamformers, each corresponding to one frequency bin, which results in excessive resource consumption in engineering practice. To alleviate the resource consumption of wideband array beamforming, we propose a novel time-domain wideband digital beamformer that can control the beam shape over the whole bandwidth for interference mitigation by using only one set of amplitude–phase weights and integer time delay filters. To tackle the resultant optimization problem, two effective algorithms are introduced, and both can solve the problem within polynomial time. One is an alternating optimization algorithm that decomposes the original problem into multiple tractable subproblems iteratively. The other is the convex approximation algorithm that transforms the original problem into a series of second-order cone programming problems iteratively. The two algorithms exhibit their respective advantages in terms of convergence and computational complexity. Extensive numerical examples are presented to evaluate the proposed time-domain wideband beamforming strategy, highlighting that it can form a deep notch in any interested spatial–spectral region to suppress the strong interferences. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint. The input is a set I of items, each has a non-negative weight, and a set of bins of arbitrary capacities. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a packing of a subset of items A ⊆ I in the bins such that f (A) is maximized. Our main result is an almost optimal polynomial time (1 − e − 1 − ε) -approximation algorithm for the problem, for any ε > 0. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints. [ABSTRACT FROM AUTHOR]

Non-orthogonal multiple access (NOMA) and backscatter communication are two emerging technologies for low-power communication. In this paper, we consider a NOMA backscatter system, where signals from two backscatter devices are multiplexed on a frequency resource block using NOMA in each time slot. Our objective is to maximize the average energy efficiency by optimizing backscatter device pairing, reflection coefficients of backscatter devices, and the transmit power of the reader. We formulate the average energy efficiency maximization problem subject to the minimum circuit power and the minimum data rate requirements of the backscatter devices, and the transmit power constraint of the reader. The formulated problem is nonconvex. To obtain a suboptimal solution for this problem, we use alternating optimization technique and decompose the problem into two subproblems. The subproblems are solved by using fractional programming, Dinkelbach’s algorithm, and successive convex approximation method. Simulation results show that our proposed algorithm converges quickly to a suboptimal solution. Our proposed algorithm outperforms several baseline algorithms, including the genetic algorithm, fixed device pairing scheme, conventional device pairing scheme, maximum transmit power allocation scheme, and random reflection coefficient selection scheme, in terms of the average energy efficiency. The optimality gap of our proposed algorithm is investigated by comparing with the optimal scheme, in which the optimal device pairing is obtained based on exhaustive search. [ABSTRACT FROM AUTHOR]

Quantum state tomography is a process for estimating an unknown quantum state; which is innately probabilistic. The exponential growth of unknown parameters to be estimated is a fundamental difficulty in realizing quantum state tomography for higher dimensions. Iterative optimization algorithms like self-guided quantum tomography have been effective in robust and accurate ascertaining a quantum state even with exponential growth in Hilbert space. We propose a faster convergent simultaneous perturbation stochastic approximation algorithm which is more practical in a resource-deprived situation for determining the underlying quantum states by incorporating the Barzilai–Borwein two-point step size gradient method with minimal loss of accuracy. [ABSTRACT FROM AUTHOR]

We consider stochastic algorithms derived from methods for solving deterministic optimization problems, especially comparison-based algorithms derived from stochastic approximation algorithms with a constant step-size. We develop a methodology for proving geometric convergence of the parameter sequence { θ n } n ⩾ 0 of such algorithms. We employ the ordinary differential equation (ODE) method, which relates a stochastic algorithm to its mean ODE, along with a Lyapunov-like function Ψ such that the geometric convergence of Ψ (θ n) implies – in the case of an optimization algorithm – the geometric convergence of the expected distance between the optimum and the search point generated by the algorithm. We provide two sufficient conditions for Ψ (θ n) to decrease at a geometric rate: Ψ should decrease "exponentially" along the solution to the mean ODE, and the deviation between the stochastic algorithm and the ODE solution (measured by Ψ) should be bounded by Ψ (θ n) times a constant. We also provide practical conditions under which the two sufficient conditions may be verified easily without knowing the solution of the mean ODE. Our results are any-time bounds on Ψ (θ n) , so we can deduce not only the asymptotic upper bound on the convergence rate, but also the first hitting time of the algorithm. The main results are applied to a comparison-based stochastic algorithm with a constant step-size for optimization on continuous domains. [ABSTRACT FROM AUTHOR]

We present a simple deterministic distributed (2 + ε)-approximation algorithm for minimum-weight vertex cover, which completes in O(logΔ/ε log logΔ) rounds, where Δ is the maximum degree in the graph, for any ε > 0 that is at most O(1). For a constant Δ, this implies a constant approximation in O(logΔ/log logΔ) rounds, which contradicts the lower bound of [KMW10]. [ABSTRACT FROM AUTHOR]

We suggest a new optimization technique for minimizing the sum $\sum _{i=1}^n g_i(x)$ ∑ i = 1 n g i (x) of $n$ n non-convex real functions that satisfy a property that we call piecewise log-Lipschitz. This is by forging links between techniques in computational geometry, combinatorics and convex optimization. As an example application, we provide the first constant-factor approximation algorithms whose running-times are polynomial in $n$ n for the fundamental problem of Points-to-Lines alignment: Given $n$ n points $p_1,\ldots,p_n$ p 1 ,... , p n and $n$ n lines $\ell _1,\ldots,\ell _n$ ℓ 1 ,... , ℓ n on the plane and $z>0$ z > 0 , compute the matching $\pi :[n]\to [n]$ π : [ n ] → [ n ] and alignment (rotation matrix $R$ R and translation vector $t$ t ) that minimize the sum of euclidean distances $\sum _{i=1}^n \mathrm{dist}(Rp_i-t,\ell _{\pi (i)})^z$ ∑ i = 1 n dist (R p i - t , ℓ π (i)) z between each point to its corresponding line. This problem is non-trivial even if $z=1$ z = 1 and the matching $\pi$ π is given. If $\pi$ π is given, our algorithms run in $O(n^3)$ O (n 3) time, and even near-linear in $n$ n using core-sets that support: streaming, dynamic, and distributed parallel computations in poly-logarithmic update time. Generalizations for handling e.g., outliers or pseudo-distances such as $M$ M -estimators for the problem are also provided. Experimental results and open source code show that our algorithms improve existing heuristics also in practice. A companion demonstration video in the context of Augmented Reality shows how such algorithms may be used in real-time systems. [ABSTRACT FROM AUTHOR]

Recent research has revealed new and unexpected applications of network control science within biomedicine, pharmacology, and medical therapeutics. These new insights and new applications generated in turn a rediscovery of some old, unresolved algorithmic problems. One of these problems is the Structural Target Control optimization problem, known in previous literature also as Structural Output Controllability problem, which is defined as follows. Given a directed network and a target subset of nodes, the task is to select a small (or the smallest) set of nodes from which the target can be independently controlled, i.e., there exists a set of paths from the selected set of nodes (called driver nodes) to the target nodes such that no two paths intersect at the same distance from their targets. Recently, Structural Target Control optimization problem has been shown to be NP-hard, and several heuristic algorithms were introduced and analyzed, both on randomly generated networks, and on biomedical ones. In this paper, we show that the Structural Target Controllability problem is fixed parameter tractable when parameterized by the number of target nodes. We also prove that the problem is hard to approximate at a factor better than O(log n). Taking into consideration the real case formulations of this problem we identify two more parameters which are naturally constrained by smaller bounds: the maximal length of a controlling path and the size of the set of nodes from which the control can start. With these new parameters we provide an approximation algorithm which is of exponential complexity in the size of the set of nodes from which the control can start and polynomial in all the other parameters. [ABSTRACT FROM AUTHOR]

The quantum approximate optimization algorithm (QAOA) has been put forth as a method for near-term quantum computers to solve optimization problems. However, assessments of QAOA performance have mostly focused on small structured problem instances while performance on more general instances is less clear. Here, we numerically simulate QAOA pure state dynamics for every instance of MaxCut on non-isomorphic unweighted graphs with nine or fewer vertices with depth parameters p ≤ 3 . We find the approximation ratios and optimized circuit parameters concentrate across graphs of a given size and empirically show increases in concentration as graph size increases. The parameter concentration leads to two median-angle heuristics that overcome difficulties in QAOA parameter optimization and obtain mean approximation ratios within 3% and 0.2% of the optimal. We also analyze the probability to measure an optimal solution and find increasing variations between graphs as depth increases, in stark contrast to the approximation ratios which concentrate as depth increases. The resulting benchmark data set gives empirical bounds for on-going experimental realizations and lays groundwork for theoretical extensions to greater problem sizes and depths where QAOA may prove important for practically relevant problems. [ABSTRACT FROM AUTHOR]

An important characteristic of a fractal signal is that its graph is not smooth in any small interval. This indicates the difficulty of the approximation of fractal signals, because traditional approximation methods normally require some certain smoothness of the approximated function. However, recent studies have shown that fractal functions that satisfy the Hölder condition can be linearly changed in the fractal dimension of their graphs by the fractional calculus, which implies that we can use the fractional calculus to make graphs of fractal signals smoother, and then approximate these fractal signals. This paper first gives our research background and related theories of fractals and the fractional calculus, and then introduces the main research content, including the following aspects: (1) Proposing a fractal signal approximation algorithm, the R-L algorithm, explaining and deriving how to implement this algorithm. (2) Aiming at a specific fractal signal, carrying out an approximation experiment, and confirming the R-L algorithm is better than a direct approximation. (3) According to the experimental process and conclusions, introducing our future work, such as further optimization of the R-L algorithm, and showing the R-L algorithm may have the predictive capability outside the sampling interval. The R-L algorithm can effectively modify the smoothness of graphs of the fractal signal, so that more types of approximation algorithms can be selected with a better approximation effect. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular, we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques toward predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize. [ABSTRACT FROM AUTHOR]

Algorithms for approximating the nondominated set of multiobjective optimization problems are reviewed. The approaches are categorized into general methods that are applicable under mild assumptions and, thus, to a wide range of problems, and into algorithms that are specifically tailored to structured problems. All in all, this survey covers 52 articles published within the last 41 years, that is, between 1979 and 2020. Summary of Contribution: In many problems in operations research, several conflicting objective functions have to be optimized simultaneously, and one is interested in finding Pareto optimal solutions. Because of the high complexity of finding Pareto optimal solutions and their usually very large number, however, the exact solution of such multiobjective problems is often very difficult, which motivates the study of approximation algorithms for multiobjective optimization problems. This research area uses techniques and methods from algorithmics and computing in order to efficiently determine approximate solutions to many well-known multiobjective problems from operations research. Even though approximation algorithms for multiobjective optimization problems have been investigated for more than 40 years and more than 50 research articles have been published on this topic, this paper provides the first survey of this important area at the intersection of computing and operations research. [ABSTRACT FROM AUTHOR]

Unsourced random-access (U-RA) is a type of grant-free random access with a virtually unlimited number of users, of which only a certain number $K_{a}$ are active on the same time slot. Users employ exactly the same codebook, and the task of the receiver is to decode the list of transmitted messages. We present a concatenated coding construction for U-RA on the AWGN channel, in which a sparse regression code (SPARC) is used as an inner code to create an effective outer OR-channel. Then an outer code is used to resolve the multiple-access interference in the OR-MAC. We propose a modified version of the approximate message passing (AMP) algorithm as an inner decoder and give a precise asymptotic analysis of the error probabilities of the AMP decoder and of a hypothetical optimal inner MAP decoder. This analysis shows that the concatenated construction under optimal decoding can achieve a vanishing per-user error probability in the limit of large blocklength and a large number of active users at sum-rates up to the symmetric Shannon capacity, i.e. as long as $K_{a}R < 0.5\log _{2}(1+K_{a} { \mathsf {SNR}})$. This extends previous point-to-point optimality results about SPARCs to the unsourced multiuser scenario. Furthermore, we give an optimization algorithm to find the power allocation for the inner SPARC code that minimizes the ${\mathsf {SNR}}$ required to achieve a given target per-user error probability with the AMP decoder. [ABSTRACT FROM AUTHOR]

The implicit frequency dependence of linear systems arising from the acoustic boundary element method necessitates an efficient treatment for problems in a frequency range. Instead of solving the linear systems independently at each frequency point, this paper is concerned with solving them simultaneously at multiple frequency points within a single iteration scheme. The proposed concept is based on truncation of the frequency range solution and is incorporated into two well-known iterative solvers - BiCGstab and GMRes. The proposed method is applied to two acoustic interior problems as well as to an exterior problem in order to assess the underlying approximations and to study the convergence behavior. While this paper provides the proof of concept, its application to large-scale acoustic problems necessitates efficient preconditioning for multi-frequency systems, which are yet to be developed. [ABSTRACT FROM AUTHOR]

Optimisation of automatic tool changer (ATC) indexing problem, where cutting tools are allocated to the stations on a turret magazine of a CNC machine, is one of the challenging problems in machining. The aim of the problem is to minimise the total indexing time of ATC. This problem becomes even more challenging if duplication of cutting tools is allowed and a bidirectional ATC is used. The problem has a unique feature which has not been stressed yet by other researchers, that is, although ATC indexing (master problem) is the main optimisation problem, objective function evaluation of this problem is a standalone optimisation problem (sub problem) indeed. Although an approximation algorithm does not guarantee optimality for the master problem, the subproblem must be solved optimally; otherwise, deficiencies arising from ill-defined objective function might be encountered. Considering this interesting future, a novel methodology, which employs a shortest path algorithm, is developed. Thus, the subproblem of this complicated problem can be optimally solved. Moreover, two metaheuristics, based on threshold accepting and descent first improvement greedy methodologies, are proposed for generating efficient solutions. Finally, several benchmarking instances are generated and solved to test the proposed algorithms. [ABSTRACT FROM AUTHOR]

We consider a distributed stochastic optimization problem in networks with finite number of nodes. Each node adjusts its action to optimize the global utility of the network, which is defined as the sum of local utilities of all nodes. While Gradient descent method is a common technique to solve such optimization problem, the computation of the gradient may require much information exchange. In this paper, we consider that each node can only have a noisy numerical observation of its local utility, of which the closed-form expression is not available. This assumption is quite realistic, especially when the system is either too complex or constantly changing. Nodes may exchange partially the observation of their local utilities to estimate the global utility at each timeslot. We propose a distributed algorithm based on stochastic perturbation, under the assumption that each node has only part of the local utilities of the other nodes. We use stochastic approximation tools to prove that our algorithm converges almost surely to the optimum, given that the objective function is smooth and strictly concave. The convergence rate is also derived, under the additional assumption of strongly concave objective function. It is shown that the convergence rate scales as O (K−0.5) after a sufficient number of iterations K > K0, which is the optimal rate order in terms of K for our problem. Although the proposed algorithm can be applied to general optimization problems, we perform simulations for a typical power control problem in wireless networks and present numerical results to corroborate our claims. [ABSTRACT FROM AUTHOR]

In this work, we consider a logarithmic nonlinear viscoelastic wave equation with a delay term in a bounded domain. We obtain the local existence of the solution by using the Faedo-Galerkin approximation. Then, under suitable conditions, we prove the blow up of solutions in finite time. [ABSTRACT FROM AUTHOR]

We revisit the problem of online linear optimization in the case where the set of feasible actions is accessible through an approximated linear optimization oracle with a factor α multiplicative approximation guarantee. This setting in particular is interesting because it captures natural online extensions of well-studied offline linear optimization problems that are NP-hard yet admit efficient approximation algorithms. The goal here is to minimize the α-regret, which is the natural extension to this setting of the standard regret in online learning. We present new algorithms with significantly improved oracle complexity for both the full-information and bandit variants of the problem. Mainly, for both variants, we present α-regret bounds of O (T − 1 / 3 ) , were T is the number of prediction rounds, using only O (l o g T) calls to the approximation oracle per iteration, on average. These are the first results to obtain both the average oracle complexity of O (l o g T) (or even polylogarithmic in T) and α -regret bound O (T − c ) for a constant c > 0 for both variants. [ABSTRACT FROM AUTHOR]

The emergence of big data has caused a dramatic shift in the operating regime for optimization algorithms. The performance bottleneck, which used to be computations, is now often communications. Several gradient compression techniques have been proposed to reduce the communication load at the price of a loss in solution accuracy. Recently, it has been shown how compression errors can be compensated for in the optimization algorithm to improve the solution accuracy. Even though convergence guarantees for error-compensated algorithms have been established, there is very limited theoretical support for quantifying the observed improvements in solution accuracy. In this paper, we show that Hessian-aided error compensation, unlike other existing schemes, avoids accumulation of compression errors on quadratic problems. We also present strong convergence guarantees of Hessian-based error compensation for stochastic gradient descent. Our numerical experiments highlight the benefits of Hessian-based error compensation, and demonstrate that similar convergence improvements are attained when only a diagonal Hessian approximation is used. [ABSTRACT FROM AUTHOR]

This paper considers the networked system optimization problem by cooperatively finding an approximately optimal solution to the overall network convex cost function, which is the sum of the individual cost functions of nodes (agents) in a networked system. A new distributed gradient descent algorithm is proposed based on the distributed estimation of the sum of gradients of individual cost functions using a consensus-type coordination algorithm. The proposed algorithm can address unknown directed communication topologies and only requires limited communications and information exchanges among nodes in the networked system. Under the assumption that the communication graph is strongly connected, the convergence of the proposed algorithm is rigorously analyzed. Simulation examples are presented to demonstrate the applicability and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base relations. Post's lattice gives a complete classification of all Boolean relational clones, and this has been used to classify the computational difficulty of CSPs. Motivated by a desire to understand the computational complexity of (weighted) counting CSPs, we develop an analogous notion of functional clones and study the landscape of these clones. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In the conservative case (where all nonnegative unary functions are available), we show that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard to approximate as any problem in #P. Furthermore, we show that any nontrivial functional clone (in a sense that will be made precise) contains the binary function "implies". As a consequence, in the conservative case, all nontrivial counting CSPs are as hard to approximate as #BIS, the problem of counting independent sets in a bipartite graph. Given the complexity-theoretic results, it is natural to ask whether the "implies" clone is equivalent to the clone of lsm functions. We use the Möbius transform and the Fourier transform to show that these clones coincide precisely up to arity 3. It is an intriguing open question whether the lsm clone is finitely generated. Finally, we investigate functional clones in which only restricted classes of unary functions are available. [ABSTRACT FROM AUTHOR]

Optimization underpins many of the challenges that science and technology face on a daily basis. Recent years have witnessed a major shift from traditional optimization paradigms grounded on batch algorithms for medium-scale problems to challenging dynamic, time-varying, and even huge-size settings. This is driven by technological transformations that converted infrastructural and social platforms into complex and dynamic networked systems with even pervasive sensing and computing capabilities. This article reviews a broad class of state-of-the-art algorithms for time-varying optimization, with an eye to performing both algorithmic development and performance analysis. It offers a comprehensive overview of available tools and methods and unveils open challenges in application domains of broad range of interest. The real-world examples presented include smart power systems, robotics, machine learning, and data analytics, highlighting domain-specific issues and solutions. The ultimate goal is to exemplify wide engineering relevance of analytical tools and pertinent theoretical foundations. [ABSTRACT FROM AUTHOR]

In this article, a new hypervolume-based evolutionary multiobjective optimization algorithm (EMOA), namely, R2HCA-EMOA (R2-based hypervolume contribution approximation EMOA), is proposed for many-objective optimization. The core idea of the algorithm is to use an R2 indicator variant to approximate the hypervolume contribution. The basic framework of the proposed algorithm is the same as SMS-EMOA. In order to make the algorithm computationally efficient, a utility tensor structure is introduced for the calculation of the R2 indicator variant. Moreover, a normalization mechanism is incorporated into R2HCA-EMOA to enhance the performance of the algorithm. Through experimental studies, R2HCA-EMOA is compared with three hypervolume-based EMOAs and several other state-of-the-art EMOAs on 5-, 10-, and 15-objective DTLZ, WFG problems, and their minus versions. Our results show that R2HCA-EMOA is more efficient than the other hypervolume-based EMOAs, and is superior to all the compared state-of-the-art EMOAs. [ABSTRACT FROM AUTHOR]

A common approach to clustering data is to view data objects as points in a metric space, and then to optimize a natural distance-based objective such as the k-median, k-means, or min-sum score. For applications such as clustering proteins by function or clustering images by subject, the implicit hope in taking this approach is that the optimal solution for the chosen objective will closely match the desired "target" clustering (e.g., a correct clustering of proteins by function or of images by who is in them). However, most distance-based objectives, including those mentioned here, are NP-hard to optimize. So, this assumption by itself is not sufficient, assuming P ≠ NP, to achieve clusterings of low-error via polynomial time algorithms. In this article, we show that we can bypass this barrier if we slightly extend this assumption to ask that for some small constant c, not only the optimal solution, but also all c-approximations to the optimal solution, differ from the target on at most some ∈ fraction of points--we call this (c, ∈)-approximation-stability. We show that under this condition, it is possible to efficiently obtain low-error clusterings even if the property holds only for values c for which the objective is known to be NP-hard to approximate. Specifically, for any constant c > 1, (c, ∈)-approximation-stability of k-median or k-means objectives can be used to efficiently produce a clustering of error O(∈) with respect to the target clustering, as can stability of the min-sum objective if the target clusters are sufficiently large. Thus, we can perform nearly as well in terms of agreement with the target clustering as if we could approximate these objectives to this NP-hard value. [ABSTRACT FROM AUTHOR]

We investigate variants of Lloyd's heuristic for clustering high-dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify a clusterability criterion for data sets.We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for being faster in practice than currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration. [ABSTRACT FROM AUTHOR]

We present a 7 4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any given MAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7 4 approximation algorithm for a well-structured MAP instance. The algorithm starts with a min-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by Vempala and Vetta for the (unweighted) min-size 2-ECSS problem (in: Jansen and Khuller (eds.) Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Proceedings, LNCS 1913, pp.262–273, Springer, Berlin, 2000). [ABSTRACT FROM AUTHOR]

Summary: Analysis of higher‐order gas turbine plant in real time would be tedious and expensive. In order to overcome this complexity, reduced‐order model for 5001M heavy‐duty gas turbine rated 18.2 MW has been obtained by Routh approximation, clustering technique, modified pole clustering, eigen permutation, Mihailov criterion, and Padé approximation algorithms. The step responses are obtained using MATLAB/Simulink and compared based on time domain specifications and performance index criteria. It indicates that the mixed method, namely, Routh approximation–Padé approximation algorithm–based reduced‐order model, retains the original characteristics. Further, particle swarm optimization (PSO) algorithm has also been applied to develop an optimal reduced‐order model. Based on the dynamic response against the load disturbance and set point variations, PSO‐based reduced‐order model has been identified as an optimal reduced‐order model for heavy‐duty gas turbine. The reduced‐order model proposed in this paper will be suitable for analyzing the dynamic behavior of heavy‐duty gas turbine plants in real‐time environment. [ABSTRACT FROM AUTHOR]

Mesh segmentation is a process of partitioning a mesh model into meaningful parts — a fundamental problem in various disciplines. This paper introduces a novel mesh segmentation method inspired by sparsity pursuit. Based on the local geometric and topological information of a given mesh, we build a Laplacian matrix whose Fiedler vector is used to characterize the uniformity among elements of the same segment. By analyzing the Fiedler vector, we reformulate the mesh segmentation problem as a $\ell _0$ ℓ 0 gradient minimization problem. To solve this problem efficiently, we adopt a coarse-to-fine strategy. A fast heuristic algorithm is first devised to find a rational coarse segmentation, and then an optimization algorithm based on the alternating direction method of multiplier (ADMM) is proposed to refine the segment boundaries within their local regions. To extract the inherent hierarchical structure of the given mesh, our method performs segmentation in a recursive way. Experimental results demonstrate that the presented method outperforms the state-of-the-art segmentation methods when evaluated on the Princeton Segmentation Benchmark, the LIFL/LIRIS Segmentation Benchmark and a number of other complex meshes. [ABSTRACT FROM AUTHOR]