Recent zbMATH articles in MSC 90Chttps://www.zbmath.org/atom/cc/90C2021-11-25T18:46:10.358925ZWerkzeugAlgebraic combinatorics. Translated from the Japanesehttps://www.zbmath.org/1472.050022021-11-25T18:46:10.358925Z"Bannai, Eiichi"https://www.zbmath.org/authors/?q=ai:bannai.eiichi"Bannai, Etsuko"https://www.zbmath.org/authors/?q=ai:bannai.etsuko"Ito, Tatsuro"https://www.zbmath.org/authors/?q=ai:ito.tatsuro"Tanaka, Rie"https://www.zbmath.org/authors/?q=ai:tanaka.rieThis book is the English translation of the book Introduction to Algebraic Combinatorics, which was published by Kyoritsu Shuppan in 2016 and written by the first three authors in Japanese. Later, the fourth author joined the team and translated the book in its current form in English. Bannai and Ito describe algebraic combinatorics as ``a group theory without groups'' or ``a character theoretical study of combinatorial objects''. The aim of this book is to ``pursue the study of combinatorics as an extension or a generalization of the study of finite permutation groups''. The early chapters of the book provides an accessible introduction to the subject for undergraduates and interested readers. The later chapters are suited for researchers in combinatorics and broader areas.
Chapter 1 is an introduction to classical combinatorics with selected subjects of study, such as graph theory and coding theory. Chapter 2 is an introduction to association schemes. Chapter 3 and 4 present codes and designs in connection to association schemes. Chapter 5 is on algebraic combinatorics on spheres. The book ends with Chapter 6 covering \(P\) and \(Q\)-polynomial schemes.A branch-and-price algorithm for the minimum sum coloring problemhttps://www.zbmath.org/1472.050492021-11-25T18:46:10.358925Z"Delle Donne, Diego"https://www.zbmath.org/authors/?q=ai:donne.diego-delle"Furini, Fabio"https://www.zbmath.org/authors/?q=ai:furini.fabio"Malaguti, Enrico"https://www.zbmath.org/authors/?q=ai:malaguti.enrico"Wolfler Calvo, Roberto"https://www.zbmath.org/authors/?q=ai:wolfler-calvo.robertoSummary: A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (ii) running times and (iii) exit gaps obtained when optimality is not achieved. For the instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds.A method for enumerating pairwise compatibility graphs with a given number of verticeshttps://www.zbmath.org/1472.050682021-11-25T18:46:10.358925Z"Azam, Naveed Ahmed"https://www.zbmath.org/authors/?q=ai:azam.naveed-ahmed"Shurbevski, Aleksandar"https://www.zbmath.org/authors/?q=ai:shurbevski.aleksandar"Nagamochi, Hiroshi"https://www.zbmath.org/authors/?q=ai:nagamochi.hiroshiSummary: \textit{N. A. Azam} et al. [``Enumerating all pairwise compatibility graphs with a given number of vertices based on linear programming'', in: Proceedings of 2nd International Workshop on Enumeration Problems and Applications, WEPA, Pisa, Italy. 5--8 (2018)] proposed a method to enumerate all pairwise compatibility graphs (PCGs) with a given number \(n\) of vertices. For a tuple \(( G , T , \sigma , \lambda )\) of a graph \(G\) with \(n\) vertices and a tree \(T\) with \(n\) leaves, a bijection \(\sigma\) between the vertices in \(G\) and the leaves in \(T\), and a bi-partition \(\lambda\) of the set of non-adjacent vertex pairs in \(G\), they formulated two linear programs, LP\(( G , T , \sigma , \lambda )\) and DLP\(( G , T , \sigma , \lambda )\) such that: exactly one of them is feasible; and \(G\) is a PCG if and only if LP\(( G , T , \sigma , \lambda )\) is feasible for some tuple \(( G , T , \sigma , \lambda )\). To reduce the number of graphs \(G\) with \(n\) vertices (resp., tuples) for which the LPs are solved, they excluded PCGs by heuristically generating PCGs (resp., some tuples that contain a sub-tuple \(( G^\prime , T^\prime , \sigma^\prime , \lambda^\prime )\) for \(n = 4\) whose LP\(( G^\prime , T^\prime , \sigma^\prime , \lambda^\prime )\) is infeasible). This paper proposes two improvements in the method: derive a sufficient condition for a graph to be a PCG for a given tree in order to exclude more PCGs; and characterize all sub-tuples \(( G^\prime , T^\prime , \sigma^\prime , \lambda^\prime )\) for \(n = 4\) for which LP\(( G^\prime , T^\prime , \sigma^\prime , \lambda^\prime )\) is infeasible, and enumerate tuples that contain no such sub-tuples by a branch-and-bound algorithm. Experimental results show that our method more efficiently enumerated all PCGs for \(n = 8\).Compact cactus representations of all non-trivial min-cutshttps://www.zbmath.org/1472.050852021-11-25T18:46:10.358925Z"Lo, On-Hei S."https://www.zbmath.org/authors/?q=ai:lo.on-hei-solomon"Schmidt, Jens M."https://www.zbmath.org/authors/?q=ai:schmidt.jens-m"Thorup, Mikkel"https://www.zbmath.org/authors/?q=ai:thorup.mikkelSummary: Recently, \textit{K.-I. Kawarabayashi} and \textit{M. Thorup} [J. ACM 66, No. 1, Article No. 4, 50 p. (2019; Zbl 1426.68217)] presented the first deterministic edge-connectivity recognition algorithm in near-linear time. A crucial step in their algorithm uses the existence of vertex subsets of a simple graph \(G\) on \(n\) vertices whose contractions leave a multigraph with \(\widetilde{O} ( n / \delta )\) vertices and \(\widetilde{O} ( n )\) edges that preserves all non-trivial min-cuts of \(G\), where \(\delta\) is the minimum degree of \(G\) and \(\widetilde{O}\) hides logarithmic factors.
We present a simple argument that improves this contraction-based sparsifier by eliminating the poly-logarithmic factors, that is, we show a contraction-based sparsification that leaves \(O ( n / \delta )\) vertices and \(O ( n )\) edges, preserves all non-trivial min-cuts and can be computed in near-linear time \(\widetilde{O} ( m )\), where \(m\) is the number of edges of \(G\). We also obtain that every simple graph has \(O ( ( n / \delta )^2 )\) non-trivial min-cuts.
Our approach allows to represent all non-trivial min-cuts of a graph by a cactus representation, whose cactus graph has \(O ( n / \delta )\) vertices. Moreover, this cactus representation can be derived directly from the standard cactus representation of all min-cuts in linear time. We apply this compact structure to show that all min-cuts can be explicitly listed in \(\widetilde{O} ( m ) + O ( n^2 / \delta )\) time for every simple graph, which improves the previous best time bound \(O ( n m )\) given by \textit{D. Gusfield} and \textit{D. Naor} [Algorithmica 10, No. 1, 64--89 (1993; Zbl 0781.90087)].Lower bound for the cost of connecting tree with given vertex degree sequencehttps://www.zbmath.org/1472.051372021-11-25T18:46:10.358925Z"Goubko, Mikhail"https://www.zbmath.org/authors/?q=ai:goubko.mikhail-v"Kuznetsov, Alexander"https://www.zbmath.org/authors/?q=ai:kuznetsov.alexander-i|kuznetsov.alexander-gennadevich|kuznetsov.aleksandr-vladimirovich|kuznetsov.alexander-g|kuznetsov.aleksandr-petrovich|kuznetsov.alexander-m|kuznetsov.alexander-aSummary: The optimal connecting network problem generalizes many models of structure optimization known from the literature, including communication and transport network topology design, graph cut and graph clustering, etc. For the case of connecting trees with the given sequence of vertex degrees the cost of the optimal tree is shown to be bounded from below by the solution of a semidefinite optimization program with bilinear matrix inequality constraints, which is reduced to the solution of a series of convex programs with linear matrix inequality constraints. The proposed lower-bound estimate is used to construct several heuristic algorithms and to evaluate their quality on a variety of generated and real-life datasets.The set of separable states has no finite semidefinite representation except in dimension \(3\times 2\)https://www.zbmath.org/1472.140662021-11-25T18:46:10.358925Z"Fawzi, Hamza"https://www.zbmath.org/authors/?q=ai:fawzi.hamzaGiven integers \(n \ge m,\) let \(\mathrm{Sep}(n, m)\) be the set of {\em separable states} on the Hilbert space \(\mathbb{C}^n \otimes \mathbb{C}^m,\) i.e., \[\mathrm{Sep}(n, m) := \mathbf{conv}\{x x^\dagger \otimes y y^\dagger \ : \ x \in \mathbb{C}^n, |x| = 1, y \in \mathbb{C}^m, |y| = 1\}.\] Here \(x^\dagger\) indicates conjugate transpose, \(|x|^2 := x^\dagger x\) and \(\mathbf{conv}\) denotes the convex hull.
We say that a convex set \(C \subset \mathbb{R}^d\) has a {\em semidefinite representation} (of size \(r\)) if it can be expressed as \(C = \pi(S),\) where \(\pi \colon \mathbb{R}^D \to \mathbb{R}^d\) is a linear map and \(S \subset \mathbb{R}^D\) is a convex set defined using a linear matrix inequality \[S = \{w \in \mathbb{R}^D \ : \ M_0 + w_1M_1 + \cdots + w_DM_D \succeq 0\}\] where \(M_0, \ldots, M_D\) are Hermitian matrices of size \(r \times r.\)
It is known, from the earlier work of [\textit{S. L. Woronowicz}, Rep. Math. Phys. 10, 165--183 (1976; Zbl 0347.46063)] that for \(n + m \le 5,\) the set \(\mathrm{Sep}(n, m)\) is just the set of states which have a positive partial transpose, and hence it has a semidefinite representation.
In the paper under review, the author shows that for \(n + m > 5,\) the set \(\mathrm{Sep}(n, m)\) has no semidefinite representation, and so this provides a new counterexample to the Helton-Nie conjecture [\textit{J. W. Helton} and \textit{J. Nie}, SIAM J. Optim. 20, No. 2, 759--791 (2009; Zbl 1190.14058)], which was recently disproved by \textit{C. Scheiderer} [SIAM J. Appl. Algebra Geom. 2, No. 1, 26--44 (2018; Zbl 1391.90462)].
The paper is very clear, well written and quite interesting.``Controlled'' versions of the Collatz-Wielandt and Donsker-Varadhan formulaehttps://www.zbmath.org/1472.150092021-11-25T18:46:10.358925Z"Arapostathis, Aristotle"https://www.zbmath.org/authors/?q=ai:arapostathis.aristotle"Borkar, Vivek S."https://www.zbmath.org/authors/?q=ai:borkar.vivek-shripadSummary: This is an overview of the work of the authors and their collaborators on the characterization of risk-sensitive costs and rewards in terms of an abstract Collatz-Wielandt formula and in case of rewards, also a controlled version of the Donsker-Varadhan formula. For the finite state and action case, this leads to useful linear and dynamic programming formulations for the reward maximization problem in the reducible case.
For the entire collection see [Zbl 1468.60003].Minimum wave speeds in monostable reaction-diffusion equations: sharp bounds by polynomial optimizationhttps://www.zbmath.org/1472.352192021-11-25T18:46:10.358925Z"Bramburger, Jason J."https://www.zbmath.org/authors/?q=ai:bramburger.jason-j"Goluskin, David"https://www.zbmath.org/authors/?q=ai:goluskin.davidSummary: Many monostable reaction-diffusion equations admit one-dimensional travelling waves if and only if the wave speed is sufficiently high. The values of these minimum wave speeds are not known exactly, except in a few simple cases. We present methods for finding upper and lower bounds on minimum wave speed. They rely on constructing trapping boundaries for dynamical systems whose heteroclinic connections correspond to the travelling waves. Simple versions of this approach can be carried out analytically but often give overly conservative bounds on minimum wave speed. When the reaction-diffusion equations being studied have polynomial nonlinearities, our approach can be implemented computationally using polynomial optimization. For scalar reaction-diffusion equations, we present a general method and then apply it to examples from the literature where minimum wave speeds were unknown. The extension of our approach to multi-component reaction-diffusion systems is then illustrated using a cubic autocatalysis model from the literature. In all three examples and with many different parameter values, polynomial optimization computations give upper and lower bounds that are within 0.1\% of each other and thus nearly sharp. Upper bounds are derived analytically as well for the scalar reaction-diffusion equations.Computing multiple solutions of topology optimization problemshttps://www.zbmath.org/1472.353082021-11-25T18:46:10.358925Z"Papadopoulos, Ioannis P. A."https://www.zbmath.org/authors/?q=ai:papadopoulos.ioannis-p-a"Farrell, Patrick E."https://www.zbmath.org/authors/?q=ai:farrell.patrick-e"Surowiec, Thomas M."https://www.zbmath.org/authors/?q=ai:surowiec.thomasNon-convex \(\ell_p\) regularization for sparse reconstruction of electrical impedance tomographyhttps://www.zbmath.org/1472.353692021-11-25T18:46:10.358925Z"Wang, Jing"https://www.zbmath.org/authors/?q=ai:wang.jing|wang.jing.13|wang.jing.1|wang.jing.11|wang.jing.14|wang.jing.2|wang.jing.3|wang.jing.6|wang.jing.17|wang.jing.16|wang.jing.5|wang.jing.15Summary: This work is to investigate the image reconstruction of electrical impedance tomography from the electrical measurements made on an object's surface. An \(\ell_p\)-norm \((0<p<1)\) sparsity-promoting regularization is considered to deal with the fully non-linear electrical impedance tomography problem, and a novel type of smoothing gradient-type iteration scheme is introduced. To avoid the difficulty in calculating its gradient in the optimization process, a smoothing Huber potential function is utilized to approximate the \(\ell_p\)-norm penalty. We then propose the smoothing algorithm in the general frame and establish that any accumulation point of the generated iteration sequence is a first-order stationary point of the original problem. Furthermore, one iteration scheme based on the homotopy perturbation technology is derived to find the minimizers of the Huberized approximated objective function. Numerical experiments show that non-convex \(\ell_p\)-norm sparsity-promoting regularization improves the spatial resolution and is more robust with respect to noise, in comparison with \(\ell_p\)-norm regularization.A degenerate Kirchhoff-type inclusion problem with nonlocal operatorhttps://www.zbmath.org/1472.354392021-11-25T18:46:10.358925Z"Motreanu, Dumitru"https://www.zbmath.org/authors/?q=ai:motreanu.dumitruSummary: The chapter focuses on a Kirchhoff-type elliptic inclusion problem driven by a generalized nonlocal fractional p-Laplacian whose nonlocal term vanishes at finitely many points and for which the multivalued term is in the form of the generalized gradient of a locally Lipschitz function. The corresponding elliptic equation has been treated in (Liu et al., Existence of solutions to Kirchhoff-type problem with vanishing nonlocal term and fractional \(p\)-Laplacian). Multiple nontrivial solutions are obtained by applying the nonsmooth critical point theory combined with truncation techniques.
For the entire collection see [Zbl 1470.49002].Solution analysis for a class of set-inclusive generalized equations: a convex analysis approachhttps://www.zbmath.org/1472.460772021-11-25T18:46:10.358925Z"Uderzo, Amos"https://www.zbmath.org/authors/?q=ai:uderzo.amosSummary: In the present paper, classical tools of convex analysis are used to study the solution set to a certain class of set-inclusive generalized equations. A condition for the solution existence and for global error bounds is established, in the case the set-valued term appearing in the generalized equation is concave. A functional characterization of the contingent (a.k.a. Bouligand tangent) cone to the solution set is provided via directional derivatives. Specializations of these results are also considered when outer prederivatives can be employed as approximations of set-valued mappings.\(\mathcal{J} \mathcal{H}\)-operator pairs with application to functional equations arising in dynamic programminghttps://www.zbmath.org/1472.470472021-11-25T18:46:10.358925Z"Razani, A."https://www.zbmath.org/authors/?q=ai:razani.abdolrahman"Moeini, B."https://www.zbmath.org/authors/?q=ai:moeini.bahmanSummary: Some common fixed point theorems for \(\mathcal{J} \mathcal{H}\)-operator pairs are proved. As an application, the existence and uniqueness of the common solution for systems of functional equations arising in dynamic programming are discussed. Also, an example to validate all the conditions of the main result is presented.Weak and strong convergence theorems for equilibrium problems and countable strict pseudocontraction mappings in Hilbert spacehttps://www.zbmath.org/1472.470802021-11-25T18:46:10.358925Z"Ram, Tirth"https://www.zbmath.org/authors/?q=ai:ram.tirthSummary: In this paper, we intend to introduce two iterative sequence for finding a common element of the set of solutions of an equilibrium problem and the set of fixed points of a countable family of strict pseudocontractions in Hilbert space. Then we study the weak and strong convergence of the sequences.An invitation to the study of a uniqueness problemhttps://www.zbmath.org/1472.490022021-11-25T18:46:10.358925Z"Ricceri, Biagio"https://www.zbmath.org/authors/?q=ai:ricceri.biagioSummary: In this very short chapter, we provide a strong motivation for the study of the following problem: given a real normed space \(E\), a closed, convex, unbounded set \(X \subseteq E\), and a function \(f : X \rightarrow X\), find suitable conditions under which, for each \(y \in X\), the function
\[ x\to \|x-f(x)\|-\|y-f(x)\|\]
has at most one global minimum in \(X\).
For the entire collection see [Zbl 1470.49002].Existence results for strong mixed vector equilibrium problem for multivalued mappingshttps://www.zbmath.org/1472.490102021-11-25T18:46:10.358925Z"Kılıçman, Adem"https://www.zbmath.org/authors/?q=ai:kilicman.adem"Ahmad, Rais"https://www.zbmath.org/authors/?q=ai:ahmad.rais"Rahaman, Mijanur"https://www.zbmath.org/authors/?q=ai:rahaman.mijanurSummary: We consider a strong mixed vector equilibrium problem in topological vector spaces. Using generalized Fan-Browder fixed point theorem (Takahashi 1976) and generalized pseudomonotonicity for multivalued mappings, we provide some existence results for strong mixed vector equilibrium problem without using KKM-Fan theorem. The results in this paper generalize, improve, extend, and unify some existence results in the literature. Some special cases are discussed and an example is constructed.Error analysis through energy minimization and stability properties of exponential integratorshttps://www.zbmath.org/1472.490112021-11-25T18:46:10.358925Z"Kosmas, Odysseas"https://www.zbmath.org/authors/?q=ai:kosmas.odysseas"Vlachos, Dimitrios"https://www.zbmath.org/authors/?q=ai:vlachos.dimitriosSummary: In this article, the stability property and the error analysis of higher-order exponential variational integration are examined and discussed. Toward this purpose, at first we recall the derivation of these integrators and then address the eigenvalue problem of the amplification matrix for advantageous choices of the number of intermediate points employed. Obviously, the latter determines the order of the numerical accuracy of the method. Following a linear stability analysis process we show that the methods with at least one intermediate point are unconditionally stable. Finally, we explore the behavior of the energy errors of the presented schemes in prominent numerical examples and point out their excellent efficiency in long term integration.
For the entire collection see [Zbl 1470.49002].Existence theorems and regularization methods for non-coercive vector variational and vector quasi-variational inequalitieshttps://www.zbmath.org/1472.490152021-11-25T18:46:10.358925Z"Khan, Akhtar A."https://www.zbmath.org/authors/?q=ai:khan.akhtar-ali"Hebestreit, Niklas"https://www.zbmath.org/authors/?q=ai:hebestreit.niklas"Köbis, Elisabeth"https://www.zbmath.org/authors/?q=ai:kobis.elisabeth"Tammer, Christiane"https://www.zbmath.org/authors/?q=ai:tammer.christianeSummary: In this paper, we present a novel existence result for vector variational inequalities with respect to a fixed ordering cone. Since these problems are ill-posed in general, we further propose a regularization technique for non-coercive problems which allows to derive existence statements even when the common coercivity conditions in the literature do not hold. For this purpose, we replace our original problem by a family of well-behaving problems and study their relationships. In order to justify our abstract framework we apply our results to generalized vector variational inequalities and multi-objective optimization problems. We further consider vector quasi-variational inequalities and prove existence of solutions using a regularization approach and a fixed-point theorem for single-valued mappings.Split generalized vector variational inequalities for set-valued mappings and applications to social utility optimizations with uncertaintyhttps://www.zbmath.org/1472.490172021-11-25T18:46:10.358925Z"Li, Jinlu"https://www.zbmath.org/authors/?q=ai:li.jinlu"Stone, Glenn"https://www.zbmath.org/authors/?q=ai:stone.glenn-davisSummary: In this paper, we use the power, upward power and the downward power preorders on the power sets of topological vector spaces to define the split generalized vector variational inequality problems for set-valued mappings on topological vector spaces. By using the Fan-KKM theorem, we prove an existence theorem for solutions to some split generalized vector variational inequality problems for set-valued mappings on topological vector spaces. Consequently, we prove the solvability of some generalized vector variational inequality problems for set-valued mappings. As applications, we study the existence of efficient pair of initial social activity profiles for some split generalized social utility optimization problems.Solvability of ordered equilibrium problems on partially ordered spaceshttps://www.zbmath.org/1472.490182021-11-25T18:46:10.358925Z"Li, Jinlu"https://www.zbmath.org/authors/?q=ai:li.jinlu"Wen, Ching-Feng"https://www.zbmath.org/authors/?q=ai:wen.chingfengSummary: The concept of ordered equilibrium problems on partially ordered sets extends the concept of vector equilibrium problems on topological vector spaces, while the latter is a natural extension of equilibrium problems on topological vector spaces. In this paper, for generalizing the semicontinuity and concavity of real valued functions, we introduce the concepts of ordered semicontinuity and ordered concavity for mappings that take values in partially ordered spaces. We prove some existence theorems for solutions of some ordered equilibrium problems by using the Fan-KKM theorem. Then we apply this theorem to show the solvability of some vector equilibrium problems and some ordinary equilibrium problems.Nonemptiness and compactness of solution sets to weakly homogeneous generalized variational inequalitieshttps://www.zbmath.org/1472.490242021-11-25T18:46:10.358925Z"Zheng, Meng-Meng"https://www.zbmath.org/authors/?q=ai:zheng.mengmeng"Huang, Zheng-Hai"https://www.zbmath.org/authors/?q=ai:huang.zheng-hai"Bai, Xue-Li"https://www.zbmath.org/authors/?q=ai:bai.xueliSummary: In this paper, we deal with the weakly homogeneous generalized variational inequality, which provides a unified setting for several special variational inequalities and complementarity problems studied in recent years. By exploiting weakly homogeneous structures of involved map pairs and using degree theory, we establish a result which demonstrates the connection between weakly homogeneous generalized variational inequalities and weakly homogeneous generalized complementarity problems. Subsequently, we obtain a result on the nonemptiness and compactness of solution sets to weakly homogeneous generalized variational inequalities by utilizing Harker-Pang-type condition, which can lead to a Hartman-Stampacchia-type existence theorem. Last, we give several copositivity results for weakly homogeneous generalized variational inequalities, which can reduce to some existing ones.The Tikhonov regularization for vector equilibrium problemshttps://www.zbmath.org/1472.490252021-11-25T18:46:10.358925Z"Anh, Lam Quoc"https://www.zbmath.org/authors/?q=ai:anh.lam-quoc"Duy, Tran Quoc"https://www.zbmath.org/authors/?q=ai:duy.tran-quoc"Muu, Le Dung"https://www.zbmath.org/authors/?q=ai:muu.le-dung"Tri, Truong Van"https://www.zbmath.org/authors/?q=ai:tri.truong-vanAuthors' abstract: We consider vector equilibrium problems in real Banach spaces and study their regularized problems. Based on cone continuity and generalized convexity properties of vector-valued mappings, we propose general conditions that guarantee existence of solutions to such problems in cases of monotonicity and nonmonotonicity. First, our study indicates that every Tikhonov trajectory converges to a solution to the original problem. Then, we establish the equivalence between the problem solvability and the boundedness of any Tikhonov trajectory. Finally, the convergence of the Tikhonov trajectory to the least-norm solution of the original problem is discussed.A Lagrange multiplier method for semilinear elliptic state constrained optimal control problemshttps://www.zbmath.org/1472.490272021-11-25T18:46:10.358925Z"Karl, Veronika"https://www.zbmath.org/authors/?q=ai:karl.veronika"Neitzel, Ira"https://www.zbmath.org/authors/?q=ai:neitzel.ira"Wachsmuth, Daniel"https://www.zbmath.org/authors/?q=ai:wachsmuth.danielAuthors' abstract: In this paper we apply an augmented Lagrange method to a class of semilinear elliptic optimal control problems with pointwise state constraints. We show strong convergence of subsequences of the primal variables to a local solution of the original problem as well as weak convergence of the adjoint states and weak-star convergence of the multipliers associated to the state constraint. Moreover, we show existence of stationary points in arbitrary small neighborhoods of local solutions of the original problem. Additionally, various numerical results are presented.A predictor-corrector method for solving equilibrium problemshttps://www.zbmath.org/1472.490282021-11-25T18:46:10.358925Z"Bao, Zong-Ke"https://www.zbmath.org/authors/?q=ai:bao.zong-ke"Huang, Ming"https://www.zbmath.org/authors/?q=ai:huang.ming"Xia, Xi-Qiang"https://www.zbmath.org/authors/?q=ai:xia.xiqiangSummary: We suggest and analyze a predictor-corrector method for solving nonsmooth convex equilibrium problems based on the auxiliary problem principle. In the main algorithm each stage of computation requires two proximal steps. One step serves to predict the next point; the other helps to correct the new prediction. At the same time, we present convergence analysis under perfect foresight and imperfect one. In particular, we introduce a stopping criterion which gives rise to \(\Delta\)-stationary points. Moreover, we apply this algorithm for solving the particular case: variational inequalities.Erratum to: ``Optimality conditions for nonsmooth interval-valued and multiobjective semi-infinite programming''https://www.zbmath.org/1472.490302021-11-25T18:46:10.358925Z"Jennane, Mohsine"https://www.zbmath.org/authors/?q=ai:jennane.mohsine"Kalmoun, El Mostafa"https://www.zbmath.org/authors/?q=ai:kalmoun.el-mostafa"Lafhim, Lahoussine"https://www.zbmath.org/authors/?q=ai:lafhim.lahoussineSummary: This note corrects an error in our paper [ibid. 55, No. 1, 1--11 (2021; Zbl 1468.49016)] as we should drop the expression ``\textit{with at least one strict inequality}'' in the definition of interval order in Section 2. Instead of proposing this short amendment, \textit{N. A. Gadhi} and \textit{A. Ichatouhane} [ibid. 55, No. 1, 13--22 (2021; Zbl 1468.49014)] gave a proposition that requires an additional condition on the constraint functions. However, we claim that all the results of our paper are correct once the modification above is done.On nonsmooth semi-infinite minimax programming problem with \((\Phi, \rho)\)-invexityhttps://www.zbmath.org/1472.490312021-11-25T18:46:10.358925Z"Liu, X. L."https://www.zbmath.org/authors/?q=ai:liu.xiaoling"Lai, G. M."https://www.zbmath.org/authors/?q=ai:lai.guoming"Xu, C. Q."https://www.zbmath.org/authors/?q=ai:xu.chuanqing"Yuan, D. H."https://www.zbmath.org/authors/?q=ai:yuan.dehuiSummary: We are interested in a nonsmooth minimax programming Problem (SIP). Firstly, we establish the necessary optimality conditions theorems for Problem (SIP) when using the well-known Caratheodory's theorem. Under the Lipschitz \((\Phi, \rho)\)-invexity assumptions, we derive the sufficiency of the necessary optimality conditions for the same problem. We also formulate dual and establish weak, strong, and strict converse duality theorems for Problem (SIP) and its dual. These results extend several known results to a wider class of problems.On continuous codifferentiability of quasidifferentiable functionshttps://www.zbmath.org/1472.490322021-11-25T18:46:10.358925Z"Prudnikov, Igor M."https://www.zbmath.org/authors/?q=ai:prudnikov.igor-mSummary: The author studied codifferentiable functions introduced by Professor V. F. Demyanov and a method for calculating their subdifferentials and codifferentials. The proven theorems give the rules for calculating the subdifferentials. It was shown that the subdifferential of the first order, introduced by the author, coincides with the Demyanov's difference applied to the subdifferential and superdifferential of a Lipschitz quasidifferentiable function. The author proved that any quasidifferentiable function is continuously codifferentiable under the condition of upper semicontinuity for the subdifferential and superdifferential mappings. The author suggested constructing a continuous extension for the subdifferential of the first order and introduced \(\alpha \) -optimal points.Approximate solutions in nonsmooth robust optimization with locally Lipschitz constraintshttps://www.zbmath.org/1472.490332021-11-25T18:46:10.358925Z"Shitkovskaya, Tatiana"https://www.zbmath.org/authors/?q=ai:shitkovskaya.tatiana"Hong, Zhe"https://www.zbmath.org/authors/?q=ai:hong.zhe"Jiao, Liguo"https://www.zbmath.org/authors/?q=ai:jiao.liguo"Kim, Do Sang"https://www.zbmath.org/authors/?q=ai:kim.do-sangSummary: In this paper, we consider a robust optimization problem with locally Lipschitz constraints, and study some characterizations of a so-called quasi \(\epsilon\)-solution in this setting. In other words, a necessary optimality condition for a quasi \(\epsilon\)-solution to the mentioned problem is established under some suitable robust constraint qualification; sufficient optimality conditions are also provided with the help of generalized convexity. The optimality conditions are presented in terms of multipliers and limiting subdifferentials of the related functions. Moreover, a simple example is provided to illustrate necessary optimality conditions. Finally, approximate duality relationships are discussed after a Wolfe type dual model (in approximate form) is formulated.Generalized error bound for conic inequality in \(\mathfrak{C}^2\) type Banach spaceshttps://www.zbmath.org/1472.490342021-11-25T18:46:10.358925Z"Zhu, Jiangxing"https://www.zbmath.org/authors/?q=ai:zhu.jiangxing"Hu, Chunhai"https://www.zbmath.org/authors/?q=ai:hu.chunhai"Ouyang, Wei"https://www.zbmath.org/authors/?q=ai:ouyang.weiSummary: In this paper, we consider generalized error bound issues for conic inequalities in \(\mathfrak{C}^2\) type Banach spaces. Using the techniques of variational analysis and in terms of proximal subdifferentials of vector-valued functions, we provide sufficient conditions for the existence of a generalized error bound for a conic inequality. In particular, our results improve and extend some existing results.Ekeland type variational principle for set-valued maps in quasi-metric spaces with applicationshttps://www.zbmath.org/1472.490352021-11-25T18:46:10.358925Z"Ansari, Qamrul Hasan"https://www.zbmath.org/authors/?q=ai:ansari.qamrul-hasan"Sharma, Pradeep Kumar"https://www.zbmath.org/authors/?q=ai:sharma.pradeep-kumarSummary: In this paper, we derive a fixed point theorem, minimal element theorems and Ekeland type variational principle for set-valued maps with generalized variable set relations in quasi-metric spaces. These generalized variable set relations are the generalizations of set relations with constant ordering cone, and form the modern approach to compare sets in set-valued optimization with respect to variable domination structures under some appropriate assumptions. At the end, we give application of these variational principles to the capability theory of well-beings via variational rationality.Generalized sequential differential calculus for expected-integral functionalshttps://www.zbmath.org/1472.490362021-11-25T18:46:10.358925Z"Mordukhovich, Boris S."https://www.zbmath.org/authors/?q=ai:mordukhovich.boris-s"Pérez-Aros, Pedro"https://www.zbmath.org/authors/?q=ai:perez-aros.pedroIntegral functionals depending on a parameter of the type
\[
E(x, y) :=\int_T \varphi_t (x,y(t)) \mu (dt)
\]
are considered, where \(x\in \mathbb{R}^n\) and \(y\in L^1(T;\mathbb{R}^m)\), with \(T\) a measure space. The main assumptions on \(\varphi\) are a bound from below and convexity with respect to \(y\). The point of the paper is representing elements of the subdifferential of \(E\) at \((\bar x,\bar y)\) as a limit of integrals involving the subdifferential of \(\varphi\) at suitable nearby points. In particular, the point \(\bar x\) needs to be approximated by an \(L^p\) function in a suitable way.Applying twice a minimax theoremhttps://www.zbmath.org/1472.490382021-11-25T18:46:10.358925Z"Ricceri, Biagio"https://www.zbmath.org/authors/?q=ai:ricceri.biagioSummary: Here is one of the results obtained in this paper: Let \(X\), \(Y\) be two convex sets each in a real vector space, let \(J:X\times Y\to\mathbb{R}\) be convex and without global minima in \(X\) and concave in \(Y\), and let \(\Phi:X\to\mathbb{R}\) be strictly convex. Also, assume that, for some topology on \(X\), \(\Phi\) is lower semicontinuous and, for each \(y\in Y\) and \(\lambda>0\), \(J(\cdot,y)\) is lower semicontinuous and \(J(\cdot,y)+\lambda\Phi(\cdot)\) is inf-compact.
Then, for each \(r\in]\inf_X\Phi,\sup_X\Phi[\) and for each closed set \(S\subseteq X\) satisfying
\[
\Phi^{-1}(r)\subseteq S\subseteq\Phi^{-1}(]-\infty,r]),
\]
one has
\[
\sup\limits_Y\inf\limits_S J=\inf\limits_S\sup\limits_Y J.
\]A projected primal-dual gradient optimal control method for deep reinforcement learninghttps://www.zbmath.org/1472.490422021-11-25T18:46:10.358925Z"Gottschalk, Simon"https://www.zbmath.org/authors/?q=ai:gottschalk.simon"Burger, Michael"https://www.zbmath.org/authors/?q=ai:burger.michael"Gerdts, Matthias"https://www.zbmath.org/authors/?q=ai:gerdts.matthiasSummary: In this contribution, we start with a policy-based Reinforcement Learning ansatz using neural networks. The underlying Markov Decision Process consists of a transition probability representing the dynamical system and a policy realized by a neural network mapping the current state to parameters of a distribution. Therefrom, the next control can be sampled. In this setting, the neural network is replaced by an ODE, which is based on a recently discussed interpretation of neural networks. The resulting infinite optimization problem is transformed into an optimization problem similar to the well-known optimal control problems. Afterwards, the necessary optimality conditions are established and from this a new numerical algorithm is derived. The operating principle is shown with two examples. It is applied to a simple example, where a moving point is steered through an obstacle course to a desired end position in a 2D plane. The second example shows the applicability to more complex problems. There, the aim is to control the finger tip of a human arm model with five degrees of freedom and 29 Hill's muscle models to a desired end position.On sensitivity of vector equilibria by means of the diagonal subdifferential operatorhttps://www.zbmath.org/1472.490512021-11-25T18:46:10.358925Z"Al-Homidan, Suliman"https://www.zbmath.org/authors/?q=ai:al-homidan.suliman-s"Ansari, Qamrul Hasan"https://www.zbmath.org/authors/?q=ai:ansari.qamrul-hasan"Kassay, Gabor"https://www.zbmath.org/authors/?q=ai:kassay.gaborSummary: Based on the concept of subdifferential of a convex vector function, we define the so-called diagonal subdifferential operator for vector-valued bifunctions depending on a parameter and show its sensitivity with respect to the parameter. As a byproduct, we obtain Lipschitz continuity results of the solution map for parametric strong vector equilibrium problems.Painlevé-Kuratowski stability of the approximate solution sets for set-valued vector equilibrium problemshttps://www.zbmath.org/1472.490532021-11-25T18:46:10.358925Z"Peng, Zai Yun"https://www.zbmath.org/authors/?q=ai:peng.zaiyun"Zhao, Yong"https://www.zbmath.org/authors/?q=ai:zhao.yong"Yang, Xin Min"https://www.zbmath.org/authors/?q=ai:yang.xinminSummary: The aim of this paper is to study the stability aspects of approximate solution sets of perturbed vector equilibrium problems in Hausdorff topological vector spaces. Using a scalarization method, we establish a sufficient condition for Painlevé-Kuratowski convergence of \(\epsilon\)-approximate solutions set to set-valued vector equilibrium problems, where the sequence of mappings converge in the sense of \(\Gamma_C\). These results extend and improve some results in the literature. Some examples are given to illustrate the results.On a class of efficient higher order Newton-like methodshttps://www.zbmath.org/1472.490562021-11-25T18:46:10.358925Z"Sharma, Janak Raj"https://www.zbmath.org/authors/?q=ai:sharma.janak-raj"Kumar, Deepak"https://www.zbmath.org/authors/?q=ai:kumar.deepakSummary: Based on a two-step Newton-like scheme, we propose a three-step scheme of convergence order \(p+2 (p \geq 3)\) for solving systems of nonlinear equations. Furthermore, on the basis of this scheme a generalized \(k+2\)-step scheme with increasing convergence order \(p+2k\) is presented. Local convergence analysis including radius of convergence and uniqueness results of the methods is presented. Computational efficiency in the general form is discussed. Theoretical results are verified through numerical experimentation. Finally, the performance is demonstrated by the application of the methods on some nonlinear systems of equations.An iterative method for optimal control of bilateral free boundaries problemhttps://www.zbmath.org/1472.490592021-11-25T18:46:10.358925Z"El Yazidi, Youness"https://www.zbmath.org/authors/?q=ai:el-yazidi.youness"Ellabib, Abdellatif"https://www.zbmath.org/authors/?q=ai:ellabib.abdellatifSummary: In this paper, a bilateral free boundaries problem is considered. This kind of inverse problems appears in the theory of semiconductors and multi-phase problems. Using a shape functional and some regularization terms, an optimal control problem is formulated. In addition, we prove its solution existence. The first optimality conditions and the shape gradient are computed. With the finite element method, we write the discrete version of the optimal control problem. To design our proposed scheme, we based on the conjugate gradient, where we use the genetic algorithm to find the best initial guess for the gradient method. At each mesh regeneration, we perform a mesh refinement in order to avoid any domain singularities. Some numerical examples are shown to demonstrate the validity of the theoretical results and to prove the robustness and efficiency of the proposed scheme, especially to identify free boundaries with jump points.Asymptotic analysis and topological derivative for 3D quasi-linear magnetostaticshttps://www.zbmath.org/1472.490612021-11-25T18:46:10.358925Z"Gangl, Peter"https://www.zbmath.org/authors/?q=ai:gangl.peter"Sturm, Kevin"https://www.zbmath.org/authors/?q=ai:sturm.kevinSummary: In this paper we study the asymptotic behaviour of the quasilinear curl-curl equation of 3D magnetostatics with respect to a singular perturbation of the differential operator and prove the existence of the topological derivative using a Lagrangian approach. We follow the strategy proposed in [\textit{P. Gangl} and \textit{K. Sturm}, ESAIM, Control Optim. Calc. Var. 26, Paper No. 106, 20 p. (2020; Zbl 1459.49027)] where a systematic and concise way for the derivation of topological derivatives for quasi-linear elliptic problems in \(H^1\) is introduced. In order to prove the asymptotics for the state equation we make use of an appropriate Helmholtz decomposition. The evaluation of the topological derivative at any spatial point requires the solution of a nonlinear transmission problem. We discuss an efficient way for the numerical evaluation of the topological derivative in the whole design domain using precomputation in an offline stage. This allows us to use the topological derivative for the design optimization of an electrical machine.Optimal control of Earth pressure balance of shield tunneling machine based on dual-heuristic dynamic programminghttps://www.zbmath.org/1472.490692021-11-25T18:46:10.358925Z"Liu, Xuanyu"https://www.zbmath.org/authors/?q=ai:liu.xuanyu"Xu, Sheng"https://www.zbmath.org/authors/?q=ai:xu.sheng"Shao, Cheng"https://www.zbmath.org/authors/?q=ai:shao.chengSummary: Earth pressure balance (EPB) shield tunneling machine has been widely used in underground construction. To avoid the catastrophic accidents caused by earth pressure imbalance, the earth pressure on excavation face must be controlled balance to that in chamber. To solve this problem better, a multi-variable data-driven optimal control method for shield machine based on dual-heuristic programming (DHP) is proposed. The DHP controller is constructed with action network, model network, and critic network based on back-propagation neural networks (BPNNs). Following Bellman's principle of optimality, a cost function of DHP controller for the chamber's earth pressure is presented, which simplifies a multi-level optimization to a single-level optimization. To minimize the cost function, the action network utilizes the critic network's error to achieve multi-variable optimization, and the optimal control parameters for the tunneling process are obtained at last. The simulation results show that the method can effectively control the earth pressure balance. Even in case of disturbance, the system has strong anti-interference ability and the control process is also quicker and steadier.Penumbras and separation of convex setshttps://www.zbmath.org/1472.520072021-11-25T18:46:10.358925Z"Soltan, Valeriu"https://www.zbmath.org/authors/?q=ai:soltan.valeriuThe penumbra \(P(K_1,K_2)\) of two convex \(K_1\) and \(K_2\) in \(\mathbb{R}^n\) is the set of all points of the form \(x_1+\alpha(x_2-x_1)\) with \(x_1\in K_1\), \(x_2\in K_2\) and \(\alpha\ge 0\). In other words, \(P(K_1, K_2)\) can be described as \(K_1+\mathrm{cone}(K_2 -K_1)\), where \(\mathrm{cone}\) is the conic hull operation (this is mentioned in Theorem 10).
The paper contains 13 theorems on intrinsic convex-geometric properties of penumbras. In particular, Theorems 1 and 2 are about properties related to common convex-geometric operations and functionals, including affine hull, relative interior, closure and the Hausdorff distance; Theorem 3 characterizes different versions of separation of \(K_1\) and \(K_2\) via separation of the respective penumbras \(P(K_1,K_2)\) and \(P(K_2,K_1)\); Theorem 4 deals with supporting hyperplanes of the topological closure of a penumbra and Theorem 5 describes the closure \(P(K_1,K_2)\) in terms of half-spaces that separate \(K_1\) from \(K_2\).Extending the realm of Horvath spaceshttps://www.zbmath.org/1472.540112021-11-25T18:46:10.358925Z"Park, Sehie"https://www.zbmath.org/authors/?q=ai:park.sehieSummary: A KKM space is an abstract convex space satisfying the abstract form of the KKM theorem and its open-valued version. In this article we introduce a typical subclass of KKM spaces called the Horvath spaces including \(c\)-spaces due to Horvath. We show that hyperbolic metric spaces, metric spaces with continuous midpoints, metric spaces with global nonpositive curvature (NPC) and convex hull finite property (CHFP), certain Riemannian manifolds, and \(\mathbb{B}\)-spaces are relatively new examples of Horvath spaces. Many of their properties are introduced by following our previous works [the author, Nonlinear Anal., Theory Methods Appl., Ser. A, Theory Methods 69, No. 12, 4352--4364 (2008; Zbl 1163.47044); Nonlinear Anal., Theory Methods Appl., Ser. A, Theory Methods 73, No. 4, 1028--1042 (2010; Zbl 1214.47042)].Gaussian process optimization with failures: classification and convergence proofhttps://www.zbmath.org/1472.600622021-11-25T18:46:10.358925Z"Bachoc, François"https://www.zbmath.org/authors/?q=ai:bachoc.francois"Helbert, Céline"https://www.zbmath.org/authors/?q=ai:helbert.celine"Picheny, Victor"https://www.zbmath.org/authors/?q=ai:picheny.victorSummary: We consider the optimization of a computer model where each simulation either fails or returns a valid output performance. We first propose a new joint Gaussian process model for classification of the inputs (computation failure or success) and for regression of the performance function. We provide results that allow for a computationally efficient maximum likelihood estimation of the covariance parameters, with a stochastic approximation of the likelihood gradient. We then extend the classical improvement criterion to our setting of joint classification and regression. We provide an efficient computation procedure for the extended criterion and its gradient. We prove the almost sure convergence of the global optimization algorithm following from this extended criterion. We also study the practical performances of this algorithm, both on simulated data and on a real computer model in the context of automotive fan design.Phase retrieval of low-rank matrices by anchored regressionhttps://www.zbmath.org/1472.620772021-11-25T18:46:10.358925Z"Lee, Kiryung"https://www.zbmath.org/authors/?q=ai:lee.kiryung"Bahmani, Sohail"https://www.zbmath.org/authors/?q=ai:bahmani.sohail"Eldar, Yonina C."https://www.zbmath.org/authors/?q=ai:eldar.yonina-c"Romberg, Justin"https://www.zbmath.org/authors/?q=ai:romberg.justin-kSummary: We study the low-rank phase retrieval problem, where our goal is to recover a \(d_1\times d_2\) low-rank matrix from a series of phaseless linear measurements. This is a fourth-order inverse problem, as we are trying to recover factors of a matrix that have been observed, indirectly, through some quadratic measurements. We propose a solution to this problem using the recently introduced technique of anchored regression. This approach uses two different types of convex relaxations: we replace the quadratic equality constraints for the phaseless measurements by a search over a polytope and enforce the rank constraint through nuclear norm regularization. The result is a convex program in the space of \(d_1 \times d_2\) matrices. We analyze two specific scenarios. In the first, the target matrix is rank-\(1\), and the observations are structured to correspond to a phaseless blind deconvolution. In the second, the target matrix has general rank, and we observe the magnitudes of the inner products against a series of independent Gaussian random matrices. In each of these problems, we show that anchored regression returns an accurate estimate from a near-optimal number of measurements given that we have access to an anchor matrix of sufficient quality. We also show how to create such an anchor in the phaseless blind deconvolution problem from an optimal number of measurements and present a partial result in this direction for the general rank problem.Joint outlier detection and variable selection using discrete optimizationhttps://www.zbmath.org/1472.621102021-11-25T18:46:10.358925Z"Jammal, Mahdi"https://www.zbmath.org/authors/?q=ai:jammal.mahdi"Canu, Stephane"https://www.zbmath.org/authors/?q=ai:canu.stephane"Abdallah, Maher"https://www.zbmath.org/authors/?q=ai:abdallah.maherSummary: In regression, the quality of estimators is known to be very sensitive to the presence of spurious variables and outliers. Unfortunately, this is a frequent situation when dealing with real data. To handle outlier proneness and achieve variable selection, we propose a robust method performing the outright rejection of discordant observations together with the selection of relevant variables. A natural way to define the corresponding optimization problem is to use the \(\ell_0\) norm and recast it as a mixed integer optimization problem. To retrieve this global solution more efficiently, we suggest the use of additional constraints as well as a clever initialization. To this end, an efficient and scalable non-convex proximal alternate algorithm is introduced. An empirical comparison between the \(\ell_0\) norm approach and its \(\ell_1\) relaxation is presented as well. Results on both synthetic and real data sets provided that the mixed integer programming approach and its discrete first order warm start provide high quality solutions.An effective procedure for feature subset selection in logistic regression based on information criteriahttps://www.zbmath.org/1472.621202021-11-25T18:46:10.358925Z"Civitelli, Enrico"https://www.zbmath.org/authors/?q=ai:civitelli.enrico"Lapucci, Matteo"https://www.zbmath.org/authors/?q=ai:lapucci.matteo"Schoen, Fabio"https://www.zbmath.org/authors/?q=ai:schoen.fabio"Sortino, Alessio"https://www.zbmath.org/authors/?q=ai:sortino.alessioSummary: In this paper, the problem of best subset selection in logistic regression is addressed. In particular, we take into account formulations of the problem resulting from the adoption of information criteria, such as AIC or BIC, as goodness-of-fit measures. There exist various methods to tackle this problem. Heuristic methods are computationally cheap, but are usually only able to find low quality solutions. Methods based on local optimization suffer from similar limitations as heuristic ones. On the other hand, methods based on mixed integer reformulations of the problem are much more effective, at the cost of higher computational requirements, that become unsustainable when the problem size grows. We thus propose a new approach, which combines mixed-integer programming and decomposition techniques in order to overcome the aforementioned scalability issues. We provide a theoretical characterization of the proposed algorithm properties. The results of a vast numerical experiment, performed on widely available datasets, show that the proposed method achieves the goal of outperforming state-of-the-art techniques.A-EMCS for PHEV based on real-time driving cycle prediction and personalized travel characteristicshttps://www.zbmath.org/1472.621702021-11-25T18:46:10.358925Z"Yu, Yuanbin"https://www.zbmath.org/authors/?q=ai:yu.yuanbin"Jiang, Junyu"https://www.zbmath.org/authors/?q=ai:jiang.junyu"Wang, Pengyu"https://www.zbmath.org/authors/?q=ai:wang.pengyu"Li, Jinke"https://www.zbmath.org/authors/?q=ai:li.jinkeSummary: Energy management plays an important role in improving the fuel economy of plug-in hybrid electric vehicles (PHEV). Therefore, this paper proposes an improved adaptive equivalent consumption minimization strategy (A-ECMS) based on long-term target driving cycle recognition and short-term vehicle speed prediction, and adapt it to personalized travel characteristics. Two main contributions have been made to distinguish our work from exiting research. Firstly, online long-term driving cycle recognition and short-term speed prediction are considered simultaneously to adjust the equivalent factor (EF). Secondly, the dynamic programming (DP) algorithm is applied to the offline energy optimization process of A-ECMS based on typical driving cycles constructed according to personalized travel characteristics. The improved A-ECMS can optimize EF based on mileage, SOC, long-term driving cycle and real-time vehicle speed. In the offline part, typical driving cycles of a specific driver is constructed by analyzing personalized travel characteristics in the historical driving data, and optimal SOC consumption under each typical driving cycle is optimized by DP. In the online part, the SOC reference trajectory is obtained by recognizing the target driving cycle from Intelligent Traffic System, and short-term vehicle speed is predicted by Nonlinear Auto-Regressive (NAR) neural network which both adjust EF together. Simulation results show that compared with CD-CS, the fuel consumption of A-ECMS proposed in the paper is reduced by 8.7\%.On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problemshttps://www.zbmath.org/1472.650402021-11-25T18:46:10.358925Z"Liu, Yong"https://www.zbmath.org/authors/?q=ai:liu.yong.2|liu.yong.4|liu.yong.3|liu.yong.5|liu.yong.1"Jiang, Xiang-Long"https://www.zbmath.org/authors/?q=ai:jiang.xianglong"Gu, Chuan-Qing"https://www.zbmath.org/authors/?q=ai:gu.chuanqingSummary: The block Gauss-Seidel algorithm can significantly outperform the simple randomized Gauss-Seidel algorithm for solving overdetermined least-squares problems since it moves a large block of columns rather than a single column into working memory. Here, with the help of the maximum residual rule, we construct a two-step Gauss-Seidel (2SGS) algorithm, which selects two different columns simultaneously at each iteration. As a natural extension of the 2SGS algorithm, we further propose a multi-step Gauss-Seidel algorithm, that is, the maximum residual block Gauss-Seidel (MRBGS) algorithm for solving overdetermined least-squares problems. We prove that these two different algorithms converge to the unique solution of the overdetermined least-squares problem when its coefficient matrix is of full column rank. Numerical experiments on Gaussian models as well as on 2D image reconstruction problems, show that 2SGS is more effective than the greedy randomized Gauss-Seidel algorithm, and MRBGS apparently outperforms both the greedy and randomized block Gauss-Seidel algorithms in terms of numerical performance.Nonconvex optimization for robust tensor completion from grossly sparse observationshttps://www.zbmath.org/1472.650562021-11-25T18:46:10.358925Z"Zhao, Xueying"https://www.zbmath.org/authors/?q=ai:zhao.xueying"Bai, Minru"https://www.zbmath.org/authors/?q=ai:bai.minru"Ng, Michael K."https://www.zbmath.org/authors/?q=ai:ng.michael-kSummary: In this paper, we consider the robust tensor completion problem for recovering a low-rank tensor from limited samples and sparsely corrupted observations, especially by impulse noise. A convex relaxation of this problem is to minimize a weighted combination of tubal nuclear norm and the \(\ell_1\)-norm data fidelity term. However, the \(\ell_1\)-norm may yield biased estimators and fail to achieve the best estimation performance. To overcome this disadvantage, we propose and develop a nonconvex model, which minimizes a weighted combination of tubal nuclear norm, the \(\ell_1\)-norm data fidelity term, and a concave smooth correction term. Further, we present a Gauss-Seidel difference of convex functions algorithm (GS-DCA) to solve the resulting optimization model by using a linearization technique. We prove that the iteration sequence generated by GS-DCA converges to the critical point of the proposed model. Furthermore, we propose an extrapolation technique of GS-DCA to improve the performance of the GS-DCA. Numerical experiments for color images, hyperspectral images, magnetic resonance imaging images and videos demonstrate that the effectiveness of the proposed method.Newton's method for M-tensor equationshttps://www.zbmath.org/1472.650592021-11-25T18:46:10.358925Z"Li, Dong-Hui"https://www.zbmath.org/authors/?q=ai:li.donghui|li.dong-hui"Xu, Jie-Feng"https://www.zbmath.org/authors/?q=ai:xu.jiefeng"Guan, Hong-Bo"https://www.zbmath.org/authors/?q=ai:guan.hongboSummary: We are concerned with the tensor equations whose coefficient tensors are M-tensors. We first propose a Newton method for solving the equation with a positive constant term and establish its global and quadratic convergence. Then we extend the method to solve the equation with a nonnegative constant term and establish its convergence. At last, we do numerical experiments to test the proposed methods. The results show that the proposed methods are quite efficient.Convergence theorem for system of pseudomonotone equilibrium and split common fixed point problems in Hilbert spaceshttps://www.zbmath.org/1472.650632021-11-25T18:46:10.358925Z"Jolaoso, Lateef Olakunle"https://www.zbmath.org/authors/?q=ai:jolaoso.lateef-olakunle"Lukumon, Gafari Abiodun"https://www.zbmath.org/authors/?q=ai:lukumon.gafari-abiodun"Aphane, Maggie"https://www.zbmath.org/authors/?q=ai:aphane.maggieSummary: We consider a system of pseudomonotone equilibrium problem and split common fixed point problem in the framework of real Hilbert spaces. We propose a modified extragradient method with line searching technique for approximating a common element in the sets of solutions of the two nonlinear problems. The convergence result is proved without prior knowledge of the Lipschitz-like constants of the equilibrium bifunctions and the norm of the bounded linear operator of the split common fixed point problem. We further provide some application and numerical example to show the importance of the obtained results in the paper.Strong convergence of self-adaptive inertial algorithms for solving split variational inclusion problems with applicationshttps://www.zbmath.org/1472.650642021-11-25T18:46:10.358925Z"Tan, Bing"https://www.zbmath.org/authors/?q=ai:tan.bing.1"Qin, Xiaolong"https://www.zbmath.org/authors/?q=ai:qin.xiaolong"Yao, Jen-Chih"https://www.zbmath.org/authors/?q=ai:yao.jen-chihSummary: In this paper, four self-adaptive iterative algorithms with inertial effects are introduced to solve a split variational inclusion problem in real Hilbert spaces. One of the advantages of the suggested algorithms is that they can work without knowing the prior information of the operator norm. Strong convergence theorems of these algorithms are established under mild and standard assumptions. As applications, the split feasibility problem and the split minimization problem in real Hilbert spaces are studied. Finally, several preliminary numerical experiments as well as an example in the field of compressed sensing are proposed to support the advantages and efficiency of the suggested methods over some existing ones.Alternating conditional gradient method for convex feasibility problemshttps://www.zbmath.org/1472.650682021-11-25T18:46:10.358925Z"Díaz Millán, R."https://www.zbmath.org/authors/?q=ai:diaz-millan.r"Ferreira, O. P."https://www.zbmath.org/authors/?q=ai:ferreira.orizon-pereira"Prudente, L. F."https://www.zbmath.org/authors/?q=ai:prudente.leandro-fSummary: The classical convex feasibility problem in a finite dimensional Euclidean space consists of finding a point in the intersection of two convex sets. In the present paper we are interested in two particular instances of this problem. First, we assume to know how to compute an exact projection onto one of the sets involved and the other set is compact such that the conditional gradient (CondG) method can be used for computing efficiently an inexact projection on it. Second, we assume that both sets involved are compact such that the CondG method can be used for computing efficiently inexact projections on them. We combine alternating projection method with CondG method to design a new method, which can be seen as an inexact feasible version of alternate projection method. The proposed method generates two different sequences belonging to each involved set, which converge to a point in the intersection of them whenever it is not empty. If the intersection is empty, then the sequences converge to points in the respective sets whose distance between them is equal to the distance between the sets in consideration. Numerical experiments are provided to illustrate the practical behavior of the method.Inexact stochastic subgradient projection method for stochastic equilibrium problems with nonmonotone bifunctions: application to expected risk minimization in machine learninghttps://www.zbmath.org/1472.650692021-11-25T18:46:10.358925Z"Iiduka, Hideaki"https://www.zbmath.org/authors/?q=ai:iiduka.hideakiSummary: This paper discusses a stochastic equilibrium problem for which the function is in the form of the expectation of nonmonotone bifunctions and the constraint set is closed and convex. This problem includes various applications such as stochastic variational inequalities, stochastic Nash equilibrium problems, and nonconvex stochastic optimization problems. For solving this stochastic equilibrium problem, we propose an inexact stochastic subgradient projection method. The proposed method sets a random realization of the bifunction and then updates its approximation by using both its stochastic subgradient and the projection onto the constraint set. The main contribution of this paper is to present a convergence analysis showing that, under certain assumptions, any accumulation point of the sequence generated by the proposed method using a constant step size almost surely belongs to the solution set of the stochastic equilibrium problem. A convergence rate analysis of the method is also provided to illustrate the method's efficiency. Another contribution of this paper is to show that a machine learning algorithm based on the proposed method achieves the expected risk minimization for a class of least absolute selection and shrinkage operator (lasso) problems in statistical learning with sparsity. Numerical comparisons of the proposed machine learning algorithm with existing machine learning algorithms for the expected risk minimization using LIBSVM datasets demonstrate the effectiveness and superior classification accuracy of the proposed algorithm.Efficient nonnegative matrix factorization by DC programming and DCAhttps://www.zbmath.org/1472.650702021-11-25T18:46:10.358925Z"Le Thi, Hoai An"https://www.zbmath.org/authors/?q=ai:le-thi-hoai-an."Vo, Xuan Thanh"https://www.zbmath.org/authors/?q=ai:vo.xuan-thanh"Dinh, Tao Pham"https://www.zbmath.org/authors/?q=ai:pham-dinh-tao.Summary: In this letter, we consider the nonnegative matrix factorization (NMF) problem and several NMF variants. Two approaches based on DC (difference of convex functions) programming and DCA (DC algorithm) are developed. The first approach follows the alternating framework that requires solving, at each iteration, two nonnegativity-constrained least squares subproblems for which DCA-based schemes are investigated. The convergence property of the proposed algorithm is carefully studied. We show that with suitable DC decompositions, our algorithm generates most of the standard methods for the NMF problem. The second approach directly applies DCA on the whole NMF problem. Two algorithms -- one computing all variables and one deploying a variable selection strategy -- are proposed. The proposed methods are then adapted to solve various NMF variants, including the nonnegative factorization, the smooth regularization NMF, the sparse regularization NMF, the multilayer NMF, the convex/convex-hull NMF, and the symmetric NMF. We also show that our algorithms include several existing methods for these NMF variants as special versions. The efficiency of the proposed approaches is empirically demonstrated on both real-world and synthetic data sets. It turns out that our algorithms compete favorably with five state-of-the-art alternating nonnegative least squares algorithms.Sufficient descent Riemannian conjugate gradient methodshttps://www.zbmath.org/1472.650722021-11-25T18:46:10.358925Z"Sakai, Hiroyuki"https://www.zbmath.org/authors/?q=ai:sakai.hiroyuki"Iiduka, Hideaki"https://www.zbmath.org/authors/?q=ai:iiduka.hideakiSummary: This paper considers sufficient descent Riemannian conjugate gradient methods with line search algorithms. We propose two kinds of sufficient descent nonlinear conjugate gradient method and prove that these methods satisfy the sufficient descent condition on Riemannian manifolds. One is a hybrid method combining a Fletcher-Reeves-type method with a Polak-Ribière-Polyak-type method, and the other is a Hager-Zhang-type method, both of which are generalizations of those used in Euclidean space. Moreover, we prove that the hybrid method has a global convergence property under the strong Wolfe conditions and the Hager-Zhang-type method has the sufficient descent property regardless of whether a line search is used or not. Further, we review two kinds of line search algorithm on Riemannian manifolds and numerically compare our generalized methods by solving several Riemannian optimization problems. The results show that the performance of the proposed hybrid methods greatly depends on the type of line search used. Meanwhile, the Hager-Zhang-type method has the fast convergence property regardless of the type of line search used.Improved conjugate gradient method for nonlinear system of equationshttps://www.zbmath.org/1472.650732021-11-25T18:46:10.358925Z"Waziri, Mohammed Yusuf"https://www.zbmath.org/authors/?q=ai:waziri.mohammed-yusuf"Yusuf, Aliyu"https://www.zbmath.org/authors/?q=ai:yusuf.aliyu"Abubakar, Auwal Bala"https://www.zbmath.org/authors/?q=ai:bala-abubakar.auwalSummary: In this paper, we propose a hybrid conjugate gradient (CG) method based on the approach of convex combination of Fletcher-Reeves (FR) and Polak-Ribière-Polyak (PRP) parameters, and Quasi-Newton's update. This is made possible by using self-scaling memory-less Broyden's update together with a hybrid direction consisting of two CG parameters. However, an important property of the new algorithm is that, it generates a descent search direction via non-monotone type line search. The global convergence of the algorithm is established under appropriate conditions. Finally, numerical experiments on some benchmark test problems, demonstrate the effectiveness of the proposed algorithm over some existing alternatives.Data-driven algorithm selection and tuning in optimization and signal processinghttps://www.zbmath.org/1472.650742021-11-25T18:46:10.358925Z"De Loera, Jesús A."https://www.zbmath.org/authors/?q=ai:de-loera.jesus-a"Haddock, Jamie"https://www.zbmath.org/authors/?q=ai:haddock.jamie"Ma, Anna"https://www.zbmath.org/authors/?q=ai:ma.anna"Needell, Deanna"https://www.zbmath.org/authors/?q=ai:needell.deannaSummary: Machine learning algorithms typically rely on optimization subroutines and are well known to provide very effective outcomes for many types of problems. Here, we flip the reliance and ask the reverse question: can machine learning algorithms lead to more effective outcomes for optimization problems? Our goal is to train machine learning methods to automatically improve the performance of optimization and signal processing algorithms. As a proof of concept, we use our approach to improve two popular data processing subroutines in data science: stochastic gradient descent and greedy methods in compressed sensing. We provide experimental results that demonstrate the answer is ``yes'', machine learning algorithms do lead to more effective outcomes for optimization problems, and show the future potential for this research direction. In addition to our experimental work, we prove relevant \textit{Probably Approximately Correct} (PAC) learning theorems for our problems of interest. More precisely, we show that there exists a learning algorithm that, with high probability, will select the algorithm that optimizes the average performance on an input set of problem instances with a given distribution.Convergence of the forward-backward method for split null-point problems beyond cocoercivenesshttps://www.zbmath.org/1472.650752021-11-25T18:46:10.358925Z"Moudafi, Abdellatif"https://www.zbmath.org/authors/?q=ai:moudafi.abdellatif"Shehu, Yekini"https://www.zbmath.org/authors/?q=ai:shehu.yekiniSummary: The forward-backward algorithm is one of the most attractive algorithm for finding zeroes of the sum of two maximal monotone operators, with one being single-valued. However, it requires the single-valued part to be co-coercive, thus precluding its use in many applications. The aim of this paper is to present and investigate the asymptotic behavior of a forward-backward algorithm with Bregman distances for solving constrained split null-point problems beyond co-coerciveness of its single-valued part. Special attention is given to constrained composite minimization and we illustrate the potential of this approach by answering a question by \textit{H.-K. Xu} [Linear Nonlinear Anal. 4, No. 1, 135--144 (2018; Zbl 1458.94147)] on the non applicability of the proximal gradient algorithm when the \(l_p\)-norm is used to measure the errors in signal processing.An iterative algorithm for solving variational inequality, generalized mixed equilibrium, convex minimization and zeros problems for a class of nonexpansive-type mappingshttps://www.zbmath.org/1472.650772021-11-25T18:46:10.358925Z"Alakoya, Timilehin Opeyemi"https://www.zbmath.org/authors/?q=ai:alakoya.timilehin-opeyemi"Taiwo, Adeolu"https://www.zbmath.org/authors/?q=ai:taiwo.adeolu"Mewomo, Oluwatosin Temitope"https://www.zbmath.org/authors/?q=ai:mewomo.oluwatosin-temitope"Cho, Yeol Je"https://www.zbmath.org/authors/?q=ai:cho.yeol-jeSummary: In this paper, we study a classical monotone and Lipschitz continuous variational inequality and fixed point problems defined on a level set of a convex function in the framework of Hilbert spaces. First, we introduce a new iterative scheme which combines the inertial subgradient extragradient method with viscosity technique and with self-adaptive stepsize. Unlike in many existing subgradient extragradient techniques in literature, the two projections of our proposed algorithm are made onto some half-spaces. Furthermore, we prove a strong convergence theorem for approximating a common solution of the variational inequality and fixed point of an infinite family of nonexpansive mappings under some mild conditions. The main advantages of our method are: the self-adaptive stepsize which avoids the need to know a priori the Lipschitz constant of the associated monotone operator, the two projections made onto some half-spaces, the strong convergence and the inertial technique employed which accelerates convergence rate of the algorithm. Second, we apply our theorem to solve generalised mixed equilibrium problem, zero point problems and convex minimization problem. Finally, we present some numerical examples to demonstrate the efficiency of our algorithm in comparison with other existing methods in literature. Our results improve and extend several existing works in the current literature in this direction.Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalitieshttps://www.zbmath.org/1472.650782021-11-25T18:46:10.358925Z"Yang, Zhen-Ping"https://www.zbmath.org/authors/?q=ai:yang.zhenping"Lin, Gui-Hua"https://www.zbmath.org/authors/?q=ai:lin.guihuaSummary: In the study of stochastic variational inequalities, the extragradient algorithms attract much attention. However, such schemes require two evaluations of the expected mapping at each iteration in general. In this paper, we present several variance-based single-call proximal extragradient algorithms for solving a class of stochastic mixed variational inequalities by aiming at alleviating the cost of an extragradient step. One salient feature of the proposed algorithms is that they require only one evaluation of the expected mapping at each iteration, and hence, the computation load may be significantly reduced. We show that the proposed algorithms can achieve sublinear ergodic convergence rate in terms of the restricted merit function. Furthermore, under the strongly Minty variational inequality condition, we derive some results related to convergence rate of the distance between iterates and solutions, the iteration and oracle complexities for the proposed algorithms when the sample size increases at a geometric or polynomial rate. Numerical experiments indicate that the proposed algorithms are quite competitive with some existing algorithms.Affine invariant interacting Langevin dynamics for Bayesian inferencehttps://www.zbmath.org/1472.651182021-11-25T18:46:10.358925Z"Garbuno-Inigo, Alfredo"https://www.zbmath.org/authors/?q=ai:garbuno-inigo.alfredo"Nüsken, Nikolas"https://www.zbmath.org/authors/?q=ai:nusken.nikolas"Reich, Sebastian"https://www.zbmath.org/authors/?q=ai:reich.sebastianThis paper proposes a computational method for generating samples from a given high-dimensional target distribution of the form \[ \pi(u) = \frac1Z \exp(-\Phi(u)) \] where \(\Phi\) is a suitable potential and \(Z\) is a normalization constant; this is a fundamental task in, e.g., Bayesian inverse problems. As an alternative to the widely known (Markov chain) Monte Carlo methods, the proposed method is based on Langevin dynamics under which the target distribution is invariant. Specifically, they propose a stochastic process of \(N\) interacting particles given by \[ d u^{(i)}_t = -C(U_t) \nabla_{u^{(i)}}\Phi(u^{(i)}_t)dt + \frac{D+1}{N}(u^{(i)}_t - m(U_t))dt + \sqrt2 C^{1/2}(U_t)dW_t^{(i)}, \] where \(u^{(i)}_t\in\mathbb{R}^D\) denotes position of the \(i\)th particle at time \(t\) (which are all collected into the vector \(U_t\)), \(C(U_t)\) is the empirical covariance matrix, \(m(U_t)\) is the empirical mean, and \(C^{1/2}(U_t)\) is a generalized square root than can be directly computed using the deviations of the particles from the empirical mean. The second term here is a correction term that guarantees for \(N>D+1\) (under suitable assumptions on the potential and the initial ensemble) that these dynamics are invariant under affine transformations, which prevents inefficient sampling if the empirical covariance matrix is a poor approximation of the target covariance measure in Bayesian inverse problems with Gaussian posteriors.
They also provide a gradient-free variant that replaces \(\nabla_{u^{(i)}}\Phi(u^{(i)}_t)\) by an approximation that is exact for Bayesian inverse problems with affine forward operators and is related to classical Ensemble Kalman-Bucy Filter as well as to the more recent Ensemble Kalman inversion.
The performance of this method is illustrated for the typical model problem of Darcy flow inversion.Agent-based optimizationhttps://www.zbmath.org/1472.680072021-11-25T18:46:10.358925Z"Czarnowski, Ireneusz"https://www.zbmath.org/authors/?q=ai:czarnowski.ireneusz"Jȩdrzejowicz, Piotr"https://www.zbmath.org/authors/?q=ai:jedrzejowicz.piotr"Kacprzyk, Janusz"https://www.zbmath.org/authors/?q=ai:kacprzyk.januszPublisher's description: This volume presents a collection of original research works by leading specialists focusing on novel and promising approaches in which the multi-agent system paradigm is used to support, enhance or replace traditional approaches to solving difficult optimization problems. The editors have invited several well-known specialists to present their solutions, tools, and models falling under the common denominator of the agent-based optimization. The book consists of eight chapters covering examples of application of the multi-agent paradigm and respective customized tools to solve difficult optimization problems arising in different areas such as machine learning, scheduling, transportation and, more generally, distributed and cooperative problem solving.
The articles of this volume will be reviewed individually.Corrigendum to: ``On the complexity of finding first-order critical points in constrained nonlinear optimization''https://www.zbmath.org/1472.680662021-11-25T18:46:10.358925Z"Cartis, C."https://www.zbmath.org/authors/?q=ai:cartis.coralia"Gould, N. I. M."https://www.zbmath.org/authors/?q=ai:gould.nicholas-ian-mark|gould.nick-i-m"Toint, Ph. L."https://www.zbmath.org/authors/?q=ai:toint.philippe-lSummary: In a recent paper [the authors, ibid. 144, No. 1--2 (A), 93--106 (2014; Zbl 1301.68154)], the evaluation complexity of an algorithm to find an approximate first-order critical point for the general smooth constrained optimization problem was examined. Unfortunately, the proof of Lemma 3.5 in that paper uses a result from an earlier paper in an incorrect way, and indeed the result of the lemma is false. The purpose of this corrigendum is to provide a modification of the previous analysis that allows us to restore the complexity bound for a different, scaled measure of first-order criticality.Minimizing the maximum moving cost of interval coveragehttps://www.zbmath.org/1472.681082021-11-25T18:46:10.358925Z"Wang, Haitao"https://www.zbmath.org/authors/?q=ai:wang.haitao"Zhang, Xiao"https://www.zbmath.org/authors/?q=ai:zhang.xiaoSummary: In this paper, we study an interval coverage problem. We are given \(n\) intervals of the same length on a line \(L\) and a line segment \(B\) on \(L\). Each interval has a nonnegative weight. The goal is to move the intervals along \(L\) such that every point of \(B\) is covered by at least one interval and the maximum moving cost of all intervals is minimized, where the moving cost of each interval is its moving distance times its weight. Algorithms for the ``unweighted'' version of this problem have been given before. In this paper, we present a first-known algorithm for this weighted version and our algorithm runs in \(O(n^2\log n\log \log n)\) time. The problem has applications in mobile sensor barrier coverage.
For the entire collection see [Zbl 1326.68015].The network-untangling problem: from interactions to activity timelineshttps://www.zbmath.org/1472.681202021-11-25T18:46:10.358925Z"Rozenshtein, Polina"https://www.zbmath.org/authors/?q=ai:rozenshtein.polina"Tatti, Nikolaj"https://www.zbmath.org/authors/?q=ai:tatti.nikolaj"Gionis, Aristides"https://www.zbmath.org/authors/?q=ai:gionis.aristidesSummary: In this paper we study a problem of determining when entities are active based on their interactions with each other. We consider a set of entities \(V\) and a sequence of time-stamped edges \(E\) among the entities. Each edge \((u,v,t)\in E\) denotes an interaction between entities \(u\) and \(v\) at time \(t\). We assume an activity model where each entity is active during at most \(k\) time intervals. An interaction \((u, v, t)\) can be \textit{explained} if at least one of \(u\) or \(v\) are active at time \(t\). Our goal is to reconstruct the \textit{activity intervals} for all entities in the network, so as to explain the observed interactions. This problem, the \textit{network-untangling problem}, can be applied to discover event timelines from complex entity interactions. We provide two formulations of the network-untangling problem: (i) minimizing the total interval length over all entities (sum version), and (ii) minimizing the maximum interval length (max version). We study separately the two problems for \(k=1\) and \(k>1\) activity intervals per entity. For the case \(k=1\), we show that the sum problem is \textbf{NP}-hard, while the max problem can be solved optimally in linear time. For the sum problem we provide efficient algorithms motivated by realistic assumptions. For the case of \(k>1\), we show that both formulations are inapproximable. However, we propose efficient algorithms based on alternative optimization. We complement our study with an evaluation on synthetic and real-world datasets, which demonstrates the validity of our concepts and the good performance of our algorithms.Waypoint routing on bounded treewidth graphshttps://www.zbmath.org/1472.681212021-11-25T18:46:10.358925Z"Schierreich, Šimon"https://www.zbmath.org/authors/?q=ai:schierreich.simon"Suchý, Ondřej"https://www.zbmath.org/authors/?q=ai:suchy.ondrejSummary: In the \textsc{Waypoint Routing Problem} one is given an undirected capacitated and weighted graph \(G\), a source-destination pair \(s,t\in V(G)\) and a set \(W\subseteq V(G)\), of \textit{waypoints}. The task is to find a walk which starts at the source vertex \(s\), visits, in any order, all waypoints, ends at the destination vertex \(t\), respects edge capacities, that is, traverses each edge at most as many times as is its capacity, and minimizes the cost computed as the sum of costs of traversed edges with multiplicities. We study the problem for graphs of bounded treewidth and present a new algorithm for the problem working in \(2^{\mathcal{O}(\mathrm{tw})}\cdot n\) time, significantly improving upon the previously known algorithms. We also show that this running time is optimal for the problem under Exponential Time Hypothesis.On a generalization of Nemhauser and Trotter's local optimization theoremhttps://www.zbmath.org/1472.681242021-11-25T18:46:10.358925Z"Xiao, Mingyu"https://www.zbmath.org/authors/?q=ai:xiao.mingyuSummary: The Nemhauser and Trotter's theorem applies to the famous \textsc{Vertex Cover} problem and can obtain a 2-approximation solution and a problem kernel of 2\(k\) vertices. This theorem is a famous theorem in combinatorial optimization and has been extensively studied. One way to generalize this theorem is to extend the result to the \textsc{Bounded-Degree Vertex Deletion} problem. For a fixed integer \(d\geq 0\), \textsc{Bounded-Degree Vertex Deletion} asks to delete at most \(k\) vertices of the input graph to make the maximum degree of the remaining graph at most \(d\). \textsc{Vertex Cover} is a special case that \(d=0\). Fellows, Guo, Moser and Niedermeier proved a generalized theorem that implies an \(O(k)\)-vertex kernel for \textsc{Bounded-Degree Vertex Deletion} for \(d=0\) and 1, and for any \(\varepsilon >0\), an \(O(k^{1+\varepsilon})\)-vertex kernel for each \(d\geq 2\). In fact, it is still left as an open problem whether \textsc{Bounded-Degree Vertex Deletion} parameterized by \(k\) admits a linear-vertex
kernel for each \(d\geq 3\). In this paper, we refine the generalized Nemhauser and Trotter's theorem. Our result implies a linear-vertex kernel for \textsc{Bounded-Degree Vertex Deletion} parameterized by \(k\) for each \(d\geq 0\).
For the entire collection see [Zbl 1326.68015].A simple label switching algorithm for semisupervised structural SVMshttps://www.zbmath.org/1472.681302021-11-25T18:46:10.358925Z"Balamurugan, Palaniappan"https://www.zbmath.org/authors/?q=ai:balamurugan.palaniappan"Shevade, Shirish"https://www.zbmath.org/authors/?q=ai:shevade.shirish-krishnaj"Sundararajan, S."https://www.zbmath.org/authors/?q=ai:sundararajan.sSummary: In structured output learning, obtaining labeled data for real-world applications is usually costly, while unlabeled examples are available in abundance. Semisupervised structured classification deals with a small number of labeled examples and a large number of unlabeled structured data. In this work, we consider semisupervised structural support vector machines with domain constraints. The optimization problem, which in general is not convex, contains the loss terms associated with the labeled and unlabeled examples, along with the domain constraints. We propose a simple optimization approach that alternates between solving a supervised learning problem and a constraint matching problem. Solving the constraint matching problem is difficult for structured prediction, and we propose an efficient and effective label switching method to solve it. The alternating optimization is carried out within a deterministic annealing framework, which helps in effective constraint matching and avoiding poor
local minima, which are not very useful. The algorithm is simple and easy to implement. Further, it is suitable for any structured output learning problem where exact inference is available. Experiments on benchmark sequence labeling data sets and a natural language parsing data set show that the proposed approach, though simple, achieves comparable generalization performance.Learning data manifolds with a cutting plane methodhttps://www.zbmath.org/1472.681322021-11-25T18:46:10.358925Z"Chung, Sueyeon"https://www.zbmath.org/authors/?q=ai:chung.sueyeon"Cohen, Uri"https://www.zbmath.org/authors/?q=ai:cohen.uri"Sompolinsky, Haim"https://www.zbmath.org/authors/?q=ai:sompolinsky.haim"Lee, Daniel D."https://www.zbmath.org/authors/?q=ai:lee.daniel-dSummary: We consider the problem of classifying data manifolds where each manifold represents invariances that are parameterized by continuous degrees of freedom. Conventional data augmentation methods rely on sampling large numbers of training examples from these manifolds. Instead, we propose an iterative algorithm, \(M_{CP}\), based on a cutting plane approach that efficiently solves a quadratic semi-infinite programming problem to find the maximum margin solution. We provide a proof of convergence as well as a polynomial bound on the number of iterations required for a desired tolerance in the objective function. The efficiency and performance of \(M_{CP}\) are demonstrated in high-dimensional simulations and on image manifolds generated from the ImageNet data set. Our results indicate that \(M_{CP}\) is able to rapidly learn good classifiers and shows superior generalization performance compared with conventional maximum margin methods using data augmentation methods.A fast algorithm for learning overcomplete dictionary for sparse representation based on proximal operatorshttps://www.zbmath.org/1472.681472021-11-25T18:46:10.358925Z"Li, Zhenni"https://www.zbmath.org/authors/?q=ai:li.zhenni"Ding, Shuxue"https://www.zbmath.org/authors/?q=ai:ding.shuxue"Li, Yujie"https://www.zbmath.org/authors/?q=ai:li.yujieSummary: We present a fast, efficient algorithm for learning an overcomplete dictionary for sparse representation of signals. The whole problem is considered as a minimization of the approximation error function with a coherence penalty for the dictionary atoms and with the sparsity regularization of the coefficient matrix. Because the problem is nonconvex and nonsmooth, this minimization problem cannot be solved efficiently by an ordinary optimization method. We propose a decomposition scheme and an alternating optimization that can turn the problem into a set of minimizations of piecewise quadratic and univariate subproblems, each of which is a single variable vector problem, of either one dictionary atom or one coefficient vector. Although the subproblems are still nonsmooth, remarkably they become much simpler so that we can find a closed-form solution by introducing a proximal operator. This leads to an efficient algorithm for sparse representation. To our knowledge, applying the proximal operator to the problem with an incoherence term and obtaining the optimal dictionary atoms in closed form with a proximal operator technique have not previously been studied. The main advantages of the proposed algorithm are that, as suggested by our analysis and simulation study, it has lower computational complexity and a higher convergence rate than state-of-the-art algorithms. In addition, for real applications, it shows good performance and significant reductions in computational time.An online policy gradient algorithm for Markov decision processes with continuous states and actionshttps://www.zbmath.org/1472.681492021-11-25T18:46:10.358925Z"Ma, Yao"https://www.zbmath.org/authors/?q=ai:ma.yao"Zhao, Tingting"https://www.zbmath.org/authors/?q=ai:zhao.tingting"Hatano, Kohei"https://www.zbmath.org/authors/?q=ai:hatano.kohei"Sugiyama, Masashi"https://www.zbmath.org/authors/?q=ai:sugiyama.masashiSummary: We consider the learning problem under an online Markov decision process (MDP) aimed at learning the time-dependent decision-making policy of an agent that minimizes the regret -- the difference from the best fixed policy. The difficulty of online MDP learning is that the reward function changes over time. In this letter, we show that a simple online policy gradient algorithm achieves regret \(O(\sqrt{T})\) for \(T\) steps under a certain concavity assumption and \(O(\log T)\) under a strong concavity assumption. To the best of our knowledge, this is the first work to present an online MDP algorithm that can handle continuous state, action, and parameter spaces with guarantee. We also illustrate the behavior of the proposed online policy gradient method through experiments.Why does large batch training result in poor generalization? A comprehensive explanation and a better strategy from the viewpoint of stochastic optimizationhttps://www.zbmath.org/1472.681592021-11-25T18:46:10.358925Z"Takase, Tomoumi"https://www.zbmath.org/authors/?q=ai:takase.tomoumi"Oyama, Satoshi"https://www.zbmath.org/authors/?q=ai:oyama.satoshi"Kurihara, Masahito"https://www.zbmath.org/authors/?q=ai:kurihara.masahitoSummary: We present a comprehensive framework of search methods, such as simulated annealing and batch training, for solving nonconvex optimization problems. These methods search a wider range by gradually decreasing the randomness added to the standard gradient descent method. The formulation that we define on the basis of this framework can be directly applied to neural network training. This produces an effective approach that gradually increases batch size during training. We also explain why large batch training degrades generalization performance, which previous studies have not clarified.Subsampled Hessian Newton methods for supervised learninghttps://www.zbmath.org/1472.681622021-11-25T18:46:10.358925Z"Wang, Chien-Chih"https://www.zbmath.org/authors/?q=ai:wang.chien-chih"Huang, Chun-Heng"https://www.zbmath.org/authors/?q=ai:huang.chun-heng"Lin, Chih-Jen"https://www.zbmath.org/authors/?q=ai:lin.chih-jenSummary: Newton methods can be applied in many supervised learning approaches. However, for large-scale data, the use of the whole Hessian matrix can be time-consuming. Recently, subsampled Newton methods have been proposed to reduce the computational time by using only a subset of data for calculating an approximation of the Hessian matrix. Unfortunately, we find that in some situations, the running speed is worse than the standard Newton method because cheaper but less accurate search directions are used. In this work, we propose some novel techniques to improve the existing subsampled Hessian Newton method. The main idea is to solve a two-dimensional subproblem per iteration to adjust the search direction to better minimize the second-order approximation of the function value. We prove the theoretical convergence of the proposed method. Experiments on logistic regression, linear SVM, maximum entropy, and deep networks indicate that our techniques significantly reduce the running time of the subsampled Hessian Newton method. The resulting algorithm becomes a compelling alternative to the standard Newton method for large-scale data classification.Distributed Newton methods for deep neural networkshttps://www.zbmath.org/1472.681762021-11-25T18:46:10.358925Z"Wang, Chien-Chih"https://www.zbmath.org/authors/?q=ai:wang.chien-chih"Tan, Kent Loong"https://www.zbmath.org/authors/?q=ai:tan.kent-loong"Chen, Chun-Ting"https://www.zbmath.org/authors/?q=ai:chen.chun-ting"Lin, Yu-Hsiang"https://www.zbmath.org/authors/?q=ai:lin.yu-hsiang"Keerthi, S. Sathiya"https://www.zbmath.org/authors/?q=ai:keerthi.s-sathiya"Mahajan, Dhruv"https://www.zbmath.org/authors/?q=ai:mahajan.dhruv"Sundararajan, S."https://www.zbmath.org/authors/?q=ai:sundararajan.s"Lin, Chih-Jen"https://www.zbmath.org/authors/?q=ai:lin.chih-jenSummary: Deep learning involves a difficult nonconvex optimization problem with a large number of weights between any two adjacent layers of a deep structure. To handle large data sets or complicated networks, distributed training is needed, but the calculation of function, gradient, and Hessian is expensive. In particular, the communication and the synchronization cost may become a bottleneck. In this letter, we focus on situations where the model is distributedly stored and propose a novel distributed Newton method for training deep neural networks. By variable and feature-wise data partitions and some careful designs, we are able to explicitly use the Jacobian matrix for matrix-vector products in the Newton method. Some techniques are incorporated to reduce the running time as well as memory consumption. First, to reduce the communication cost, we propose a diagonalization method such that an approximate Newton direction can be obtained without communication between machines. Second, we consider subsampled Gauss-Newton matrices for reducing the running time as well as the communication cost. Third, to reduce the synchronization cost, we terminate the process of finding an approximate Newton direction even though some nodes have not finished their tasks. Details of some implementation issues in distributed environments are thoroughly investigated. Experiments demonstrate that the proposed method is effective for the distributed training of deep neural networks. Compared with stochastic gradient methods, it is more robust and may give better test accuracy.Why simheuristics? Benefits, limitations, and best practices when combining metaheuristics with simulationhttps://www.zbmath.org/1472.681812021-11-25T18:46:10.358925Z"Chica, Manuel"https://www.zbmath.org/authors/?q=ai:chica.manuel"Juan, Angel A."https://www.zbmath.org/authors/?q=ai:juan.angel-a"Bayliss, Christopher"https://www.zbmath.org/authors/?q=ai:bayliss.christopher"Cordón, Oscar"https://www.zbmath.org/authors/?q=ai:cordon.oscar"Kelton, W. David"https://www.zbmath.org/authors/?q=ai:kelton.w-davidSummary: Many decision-making processes in our society involve NP-hard optimization problems. The largescale, dynamism, and uncertainty of these problems constrain the potential use of stand-alone optimization methods. The same applies for isolated simulation models, which do not have the potential to find optimal solutions in a combinatorial environment. This paper discusses the utilization of modelling and solving approaches based on the integration of simulation with metaheuristics. These `simheuristic' algorithms, which constitute a natural extension of both metaheuristics and simulation techniques, should be used as a `first-resort' method when addressing large-scale and NP-hard optimization problems under uncertainty -- which is a frequent case in real-life applications. We outline the benefits and limitations of simheuristic algorithms, provide numerical experiments that validate our arguments, review some recent publications, and outline the best practices to consider during their design and implementation stages.The secretary problem with a choice functionhttps://www.zbmath.org/1472.682122021-11-25T18:46:10.358925Z"Kawase, Yasushi"https://www.zbmath.org/authors/?q=ai:kawase.yasushiSummary: In the classical secretary problem, a decision-maker is willing to hire the best secretary out of \(n\) applicants that arrive in a random order, and the goal is to maximize the probability of choosing the best applicant. In this paper, we introduce the secretary problem with a choice function. The choice function represents the preference of the decision-maker. In this problem, the decision-maker hires some applicants, and the goal is to maximize the probability of choosing the best set of applicants defined by the choice function. We see that the secretary problem with a path-independent choice function generalizes secretary version of the stable matching problem, the maximum weight bipartite matching problem, and the maximum weight base problem in a matroid. When the choice function is path-independent, we provide an algorithm that succeeds with probability at least \(1/e^k\) where \(k\) is the maximum size of the choice, and prove that this is the best possible. Moreover, for the non-path-independent case, we prove that the success probability goes to arbitrary small for any algorithm even if the maximum size of the choice is 2.
For the entire collection see [Zbl 1326.68015].Randomized minmax regret for combinatorial optimization under uncertaintyhttps://www.zbmath.org/1472.682132021-11-25T18:46:10.358925Z"Mastin, Andrew"https://www.zbmath.org/authors/?q=ai:mastin.andrew"Jaillet, Patrick"https://www.zbmath.org/authors/?q=ai:jaillet.patrick"Chin, Sang"https://www.zbmath.org/authors/?q=ai:chin.sangSummary: The minmax regret problem for combinatorial optimization under uncertainty can be viewed as a zero-sum game played between an optimizing player and an adversary, where the optimizing player selects a solution and the adversary selects costs with the intention of maximizing the regret of the player. The conventional minmax regret model considers only deterministic solutions/strategies, and minmax regret versions of most polynomial solvable problems are NP-hard. In this paper, we consider a randomized model where the optimizing player selects a probability distribution (corresponding to a mixed strategy) over solutions and the adversary selects costs with knowledge of the player's distribution, but not its realization. We show that under this randomized model, the minmax regret version of any polynomial solvable combinatorial problem becomes polynomial solvable. This holds true for both interval and discrete scenario representations of uncertainty. Using the randomized model, we show new proofs
of existing approximation algorithms for the deterministic model based on primal-dual approaches. We also determine integrality gaps of minmax regret formulations, giving tight bounds on the limits of performance gains from randomization. Finally, we prove that minmax regret problems are NP-hard under general convex uncertainty.
For the entire collection see [Zbl 1326.68015].On the minimum cost range assignment problemhttps://www.zbmath.org/1472.682142021-11-25T18:46:10.358925Z"Carmi, Paz"https://www.zbmath.org/authors/?q=ai:carmi.paz"Chaitman-Yerushalmi, Lilach"https://www.zbmath.org/authors/?q=ai:chaitman-yerushalmi.lilachSummary: We study the problem of assigning transmission ranges to radio stations placed in a \(d\)-dimensional (\(d\)-D) Euclidean space in order to achieve a strongly connected communication network with minimum total cost, where the cost of transmitting in range \(r\) is proportional to \(r^\alpha \). While this problem can be solved optimally in 1D, in higher dimensions it is known to be NP-hard for any \(\alpha \geq 1\).
For the 1D version of the problem and \(\alpha \geq 1\), we propose a new approach that achieves an exact \(O(n^2)\)-time algorithm. This improves the running time of the best known algorithm by a factor of \(n\). Moreover, we show that this new technique can be utilized for achieving a polynomial-time algorithm for finding the minimum cost range assignment in 1D whose induced communication graph is a \(t\)-spanner, for any \(t \geq 1\).
In higher dimensions, finding the optimal range assignment is NP-hard; however, it can be approximated within a constant factor. The best known
approximation ratio is for the case \(\alpha =1\), where the approximation ratio is 1.5. We show a new approximation algorithm that breaks the 1.5 ratio.
For the entire collection see [Zbl 1326.68015].A \(4+\epsilon\) approximation for \(k\)-connected subgraphshttps://www.zbmath.org/1472.682152021-11-25T18:46:10.358925Z"Nutov, Zeev"https://www.zbmath.org/authors/?q=ai:nutov.zeevSummary: We obtain approximation ratio \(4+\frac{2}{\ell}\approx 4+\frac{4\lg k}{\lg n-\lg k}\) for the (undirected) \(k\)-\textsc{Connected Subgraph} problem, where \(\ell=\lfloor\frac{\lg n-\lg k+1}{2\lg k+1} \rfloor\) is the largest integer such that \(2^{\ell-1}k^{2\ell+1}\leq n\). For large values of \(n\) this improves the ratio 6 of
\textit{J. Cheriyan} and \textit{L. A. Végh} [SIAM J. Comput. 43, No. 4, 1342--1362 (2014; Zbl 1303.05097)]
when \(n\geq k^3\) (the case \(\ell=1)\). Our result implies an fpt-approximation ratio \(4+\epsilon\) that matches (up to the ``\(+\epsilon\)'' term) the best known ratio 4 for \(k=6,7\) for both the general and the easier augmentation versions of the problem. Similar results are shown for the problem of covering an arbitrary symmetric crossing supermodular biset function.Approximation algorithms in the successive hitting set modelhttps://www.zbmath.org/1472.682162021-11-25T18:46:10.358925Z"Storandt, Sabine"https://www.zbmath.org/authors/?q=ai:storandt.sabineSummary: We introduce the successive Hitting Set model, where the set system is not given in advance but a set generator produces the sets that contain a specific element from the universe on demand. Despite incomplete knowledge about the set system, we show that several approximation algorithms for the conventional Hitting Set problem can be adopted to perform well in this model. We describe, and experimentally investigate, several scenarios where the new model is beneficial compared to the conventional one.
For the entire collection see [Zbl 1326.68015].All-around near-optimal solutions for the online bin packing problemhttps://www.zbmath.org/1472.682202021-11-25T18:46:10.358925Z"Kamali, Shahin"https://www.zbmath.org/authors/?q=ai:kamali.shahin"López-Ortiz, Alejandro"https://www.zbmath.org/authors/?q=ai:lopez-ortiz.alejandroSummary: In this paper, we present algorithms with optimal average-case and close-to-best known worst-case performance for the classic online bin packing problem. It has long been observed that known bin packing algorithms with optimal average-case performance are not optimal in the worst-case. In particular, First Fit and Best Fit have optimal asymptotic average-case ratio of 1 but a worst-case competitive ratio of 1.7. The competitive ratio can be improved to 1.691 using the Harmonic algorithm. Further variations of this algorithm can push down the competitive ratio to 1.588. However, these algorithms have poor performance on average; in particular, Harmonic algorithm has average-case ratio of 1.27. In this paper, first we introduce a simple algorithm which we term Harmonic Match. This algorithm performs as well as Best Fit on average, i.e., it has an average-case ratio of 1. Moreover, the competitive ratio of the algorithm is as good as Harmonic, i.e., it converges to 1.691 which is an improvement
over
Best Fit and First Fit. We also introduce a different algorithm, termed as Refined Harmonic Match, which achieves an improved competitive ratio of 1.636 while maintaining the good average-case performance of Harmonic Match and Best Fit. Our experimental evaluations show that our proposed algorithms have comparable average-case performance with Best Fit and First Fit, and this holds also for sequences that follow distributions other than the uniform distribution.
For the entire collection see [Zbl 1326.68015].An algorithm for the sequence alignment with gap penalty problem using multiway divide-and-conquer and matrix transpositionhttps://www.zbmath.org/1472.682272021-11-25T18:46:10.358925Z"Shubham"https://www.zbmath.org/authors/?q=ai:shubham.k"Prakash, Surya"https://www.zbmath.org/authors/?q=ai:prakash.surya"Ganapathi, Pramod"https://www.zbmath.org/authors/?q=ai:ganapathi.pramodSummary: We present a cache-efficient parallel algorithm for the sequence alignment with gap penalty problem for shared-memory machines using multiway divide-and-conquer and not-in-place matrix transposition.
Our \(r\)-way divide-and-conquer algorithm, for a fixed natural number \(r\geq 2\), performs \(\Theta(n^3)\) work, achieves \(\Theta(n^{\log_r(2r-1)})\) span, and incurs \(\mathcal{O}\left(n^3/(BM)+(n^2/B)\log\sqrt{M}\right)\) serial cache misses for \(n>\gamma M\), and incurs \(\mathcal{O}\left((n^2/B)\log(n/\sqrt{M})\right)\) serial cache misses for \(\alpha\sqrt{M}<n\leq\gamma M\), where, \(M\) is the cache size, \(B\) is the cache line size, and \(\alpha\) and \(\gamma\) are constants.The benefit of recombination in noisy evolutionary searchhttps://www.zbmath.org/1472.682322021-11-25T18:46:10.358925Z"Friedrich, Tobias"https://www.zbmath.org/authors/?q=ai:friedrich.tobias"Kötzing, Timo"https://www.zbmath.org/authors/?q=ai:kotzing.timo"Krejca, Martin S."https://www.zbmath.org/authors/?q=ai:krejca.martin-s"Sutton, Andrew M."https://www.zbmath.org/authors/?q=ai:sutton.andrew-mSummary: Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper, we want to support this claim with mathematical rigor.
The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the \(( \mu +1) \)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm
which
does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.
For the entire collection see [Zbl 1326.68015].Generation of realistic saddle trajectories from captured horseback motionhttps://www.zbmath.org/1472.700092021-11-25T18:46:10.358925Z"Ziegler, Jakob"https://www.zbmath.org/authors/?q=ai:ziegler.jakob"Gattringer, Hubert"https://www.zbmath.org/authors/?q=ai:gattringer.hubert"Müller, Andreas"https://www.zbmath.org/authors/?q=ai:muller.andreas.2|muller.andreas|muller.andreas-christian|muller.andreas-h|muller.andreas.1Summary: Hippotherapy, riding a horse in the context of rehabilitation, is a medical treatment that successfully has been employed in various fields, e.g. for improving locomotion performance of patients with movement disorders. Robotic systems enable the application of hippotherapy in clinical environments with additional benefits, like adjustable speed and high repeatability. Fundamental for a therapy outcome equivalent to classical hippotherapy is that the trajectory of the robotic system is as realistic as possible. This paper introduces a method for the synthesis of horseback motions using motion capture data of various horse gaits. Based on complete gait cycles, an analytical, time-continuous and periodic motion description is constructed. Measured 3D marker positions are reconstructed with a mean error not exceeding 8.6 mm. If the motion capture data of several gait cycles are considered, a more generalized trajectory is generated. An adjustable time dilatation parameter enables the adaptation of the generated motion according to the physical abilities of the patient or the capabilities of the robotic system. This method allows for motion synthesis with arbitrary time span and time resolution, generating realistic trajectories effectively applicable to robotic systems for riding simulation in general and robotic hippotherapy in particular.Robust optimal solution for a smart rigid-flexible system control during multimode operational mission via actuators in combinationhttps://www.zbmath.org/1472.700182021-11-25T18:46:10.358925Z"Azimi, Milad"https://www.zbmath.org/authors/?q=ai:azimi.milad"Moradi, Samad"https://www.zbmath.org/authors/?q=ai:moradi.samadSummary: This paper is aimed at developing several control scenarios for vibration suppression of a flexible microsatellite as a multibody system with nonlinear fully coupled dynamics in different but interconnected in-orbit mission phases. The design approach is to exploit different actuators in a single and hybrid configuration with an optimal switching mechanism to achieve a desirable maneuvering performance by means of agility and accuracy. In this regard, a genetic algorithm (GA)-particle swarm optimization (PSO) based nonsingular terminal sliding mode control (GP-NSTSMC) and extended Lyapunov-based controller design (LD) are developed to cope with the limitations of bounded uncertainty and external disturbances. Great features of the GP-NSTSMC are its gains which are selected based on two major criteria, system energy and maneuver time, and for LD we consider the piezoelectric (PZT) and reaction wheel (RW) performance in the form of mechanical and electrical energies in the structure of the control algorithm. Despite the capabilities of these algorithms, they still excite high-frequency flexible modes. Accordingly, by applying feedback voltages to the PZTs, the extra vibration is actively damped, where the strain rate feedback (SRF) method is set to determine the control voltages. Furthermore, to satisfy one of the mission's requirements, which is solar panels deployment, a classical Levenberg-Marquardt (CLM) technique for online mass property identification along with an effective fault detection scenario is employed. A comparative assessment of the proposed hybrid actuator/controllers is presented to clarify the technical aspects of this multimode scenario for further investigations and practical real-time space missions.Equivalent formulations for economic lot-sizing problem with remanufacturing and joint setupshttps://www.zbmath.org/1472.900052021-11-25T18:46:10.358925Z"Ali, Sharifah Aishah Syed"https://www.zbmath.org/authors/?q=ai:ali.sharifah-aishah-syed"Supian, Latifah Sarah"https://www.zbmath.org/authors/?q=ai:supian.latifah-sarah"Shafie, Shafie"https://www.zbmath.org/authors/?q=ai:shafie.shafieSummary: In this paper, we investigate the economic lot-sizing problem with the remanufacturing and joint setups case (ELSRj), where remanufacturing and manufacturing processes share the same production line. This problem is modeled as a Mixed Integer Programming (MIP) formulation and is classified as an NP-hard problem. In order to strengthen this basic ELSRj model formulation, an extended reformulation, namely a shortest path (SP) reformulation and also \((l,S,WW)\) inequalities are proposed for this problem. Then, these formulations are compared with another existing extended reformulation which is a facility location (FL) reformulation. The findings show that all proposed and existing formulations are proven to be theoretically equivalent. A computational analysis of average percentage of duality gap is then presented, which demonstrates the equivalence and the effectiveness of the proposed and existing formulations. These formulations outperform the basic formulation for all data instances tested.Modelling and analysis of healthcare inventory management systemshttps://www.zbmath.org/1472.900102021-11-25T18:46:10.358925Z"Saha, Esha"https://www.zbmath.org/authors/?q=ai:saha.esha"Ray, Pradip Kumar"https://www.zbmath.org/authors/?q=ai:ray.pradip-kumarSummary: The core competency of the healthcare system is to provide treatment and care to the patient. The prime focus has always been towards appointing specialized physicians, well-trained nurses and medical staffs, well-established infrastructure with advanced medical equipment, and good quality pharmacy items. But, of late, the focus is driven towards management side of healthcare systems which include proper capacity planning, optimal resource allocation, and utilization, effective and efficient inventory management, accurate demand forecasting, proper scheduling, etc. and may be dealt with a number of operations research tools and techniques. In this paper, a Markov decision process inventory model is developed for a hospital pharmacy considering the information of bed occupancy in the hospital. One of the major findings of this research is the significant reduction in the inventory level and total inventory cost of pharmacy items when the demand for the items is considered to be correlated with the number of beds of each type occupied by the patients in the healthcare system. It is observed that around 53.8\% of inventory cost is reduced when the bed occupancy state is acute care, 63.9\% when it is rehabilitative care, and 55.4\% when long-term care. This may help and support the healthcare managers in better functioning of the overall healthcare system.A simheuristic algorithm for time-dependent waste collection management with stochastic travel timeshttps://www.zbmath.org/1472.900132021-11-25T18:46:10.358925Z"Gruler, Aljoscha"https://www.zbmath.org/authors/?q=ai:gruler.aljoscha"Perez-Navarro, Antoni"https://www.zbmath.org/authors/?q=ai:perez-navarro.antoni"Calvet, Laura"https://www.zbmath.org/authors/?q=ai:calvet.laura"Juan, Angel A."https://www.zbmath.org/authors/?q=ai:juan.angel-aSummary: A major operational task in city logistics is related to waste collection. Due to large problem sizes and numerous constraints, the optimization of real-life waste collection problems on a daily basis requires the use of metaheuristic solving frameworks to generate near-optimal collection routes in low computation times. This paper presents a simheuristic algorithm for the time-dependent waste collection problem with stochastic travel times. By combining Monte Carlo simulation with a biased randomized iterated local search metaheuristic, time-varying and stochastic travel speeds between different network nodes are accounted for. The algorithm is tested using real instances in a medium-sized city in Spain.The continuous pollution routing problemhttps://www.zbmath.org/1472.900172021-11-25T18:46:10.358925Z"Xiao, Yiyong"https://www.zbmath.org/authors/?q=ai:xiao.yiyong"Zuo, Xiaorong"https://www.zbmath.org/authors/?q=ai:zuo.xiaorong"Huang, Jiaoying"https://www.zbmath.org/authors/?q=ai:huang.jiaoying"Konak, Abdullah"https://www.zbmath.org/authors/?q=ai:konak.abdullah"Xu, Yuchun"https://www.zbmath.org/authors/?q=ai:xu.yuchunSummary: In this paper, we presented an \(\varepsilon \)-accurate approach to conduct a continuous optimization on the pollution routing problem (PRP). First, we developed an \(\varepsilon \)-accurate inner polyhedral approximation method for the nonlinear relation between the travel time and travel speed. The approximation error was controlled within the limit of a given parameter \(\varepsilon \), which could be as low as 0.01\% in our experiments. Second, we developed two \(\varepsilon \)-accurate methods for the nonlinear fuel consumption rate (FCR) function of a fossil fuel-powered vehicle while ensuring the approximation error to be within the same parameter \(\varepsilon \). Based on these linearization methods, we proposed an \(\varepsilon \)-accurate mathematical linear programming model for the continuous PRP (\( \varepsilon \)-CPRP for short), in which decision variables such as driving speeds, travel times, arrival/departure/waiting times, vehicle loads, and FCRs were all optimized concurrently on their continuous domains. A theoretical analysis is provided to confirm that the solutions of \(\varepsilon \)-CPRP are feasible and controlled within the predefined limit. The proposed \(\varepsilon \)-CPRP model is rigorously tested on well-known benchmark PRP instances in the literature, and has solved PRP instances optimally with up to 25 customers within reasonable CPU times. New optimal solutions of many PRP instances were reported for the first time in the experiments.Exploiting partial convexity of pump characteristics in water network designhttps://www.zbmath.org/1472.900222021-11-25T18:46:10.358925Z"Pfetsch, Marc E."https://www.zbmath.org/authors/?q=ai:pfetsch.marc-e"Schmitt, Andreas"https://www.zbmath.org/authors/?q=ai:schmitt.andreas.2|schmitt.andreasSummary: The design of water networks consists of selecting pipe connections and pumps to ensure a given water demand to minimize investment and operating costs. Of particular importance is the modeling of variable speed pumps, which are usually represented by degree two and three polynomials approximating the characteristic diagrams. In total, this yields complex mixed-integer (non-convex) nonlinear programs.
This work investigates a reformulation of these characteristic diagrams, eliminating rotating speed variables and determining power usage in terms of volume flow and pressure increase. We characterize when this formulation is convex in the pressure variables. This structural observation is applied to design the water network of a high-rise building in which the piping is tree-shaped. For these problems, the volume flow can only attain finitely many values. We branch on these flow values, eliminating the non-convexities of the characteristic diagrams. Then we apply perspective cuts to strengthen the formulation. Numerical results demonstrate the advantage of the proposed approach.
For the entire collection see [Zbl 1468.90005].Optimal road maintenance investment in traffic networks with random demandshttps://www.zbmath.org/1472.900262021-11-25T18:46:10.358925Z"Passacantando, Mauro"https://www.zbmath.org/authors/?q=ai:passacantando.mauro"Raciti, Fabio"https://www.zbmath.org/authors/?q=ai:raciti.fabioSummary: The paper deals with a traffic network with random demands in which some of the roads need maintenance jobs. Due to budget constraints, a central authority has to choose which of them are to be maintained in order to decrease as much as possible the average total travel time spent by all the users, assuming that the network flows are distributed according to the Wardrop equilibrium principle. This optimal road maintenance problem is modeled as an integer nonlinear program, where the objective function evaluation is based on the solution of a stochastic variational inequality. We propose a regularization and approximation procedure for its computation and prove its convergence. Finally, the results of preliminary numerical experiments on some test networks are reported.A problem of scheduling operations at a locomotive maintenance depothttps://www.zbmath.org/1472.900322021-11-25T18:46:10.358925Z"Lazarev, A. A."https://www.zbmath.org/authors/?q=ai:lazarev.alexander-a"Musatova, E. G."https://www.zbmath.org/authors/?q=ai:musatova.e-g"Grishin, E. M."https://www.zbmath.org/authors/?q=ai:grishin.e-m"Tarasov, G. V."https://www.zbmath.org/authors/?q=ai:tarasov.g-v"Galakhov, S. A."https://www.zbmath.org/authors/?q=ai:galakhov.s-a"Pravdivets, N. A."https://www.zbmath.org/authors/?q=ai:pravdivets.n-aSummary: In this article, we consider the problem of planning maintenance operations at a locomotive maintenance depot. There are three types of tracks at the depot: buffer tracks, access tracks and service tracks. A depot consists of up to one buffer track and a number of access tracks, each of them ending with one service track. Each of these tracks has a limited capacity measured in locomotive sections. We present a constraint programming model and a greedy algorithm for solving the problem of planning maintenance operations. Using lifelike data based on the operation of several locomotive maintenance depots in Eastern polygon of Russian Railways, we carry out numerical experiments to compare the presented approaches.
For the entire collection see [Zbl 1460.90005].A stochastic programming model for service scheduling with uncertain demand: an application in open-access clinic schedulinghttps://www.zbmath.org/1472.900372021-11-25T18:46:10.358925Z"Fu, Yu"https://www.zbmath.org/authors/?q=ai:fu.yu"Banerjee, Amarnath"https://www.zbmath.org/authors/?q=ai:banerjee.amarnathSummary: This paper addressed a scheduling problem which handles urgent tasks along with existing schedules. The uncertainties in this problem come from random process of existing schedules and unknown upcoming urgent tasks. To deal with the uncertainties, this paper proposes a stochastic integer programming (SIP) based aggregated online scheduling method. The method is illustrated through a study case from the outpatient clinic block-wise scheduling system which is under a hybrid scheduling policy combining regular far-in-advance policy and the open-access policy. The COVID-19 pandemic brings more challenges for the healthcare system including the fluctuations of service time and increasing urgent requests which this paper is designed for. The schedule framework designed in the method is comprehensive to accommodate various uncertainties in the healthcare service system, such as: no-shows, cancellations and punctuality of patients as well as preference of patients over time slots and physicians.Bite-sized operations managementhttps://www.zbmath.org/1472.900422021-11-25T18:46:10.358925Z"Daskin, Mark S."https://www.zbmath.org/authors/?q=ai:daskin.mark-sPublisher's description: This text is an introduction to Operations Management. Three themes are woven throughout the book: optimization or trying to do the best we can, managing tradeoffs between conflicting objectives, and dealing with uncertainty. After a brief introduction, the text reviews the fundamentals of probability including commonly used discrete and continuous distributions and functions of a random variable. The next major section, beginning in Chapter 7, examines optimization. The key fundamentals of optimization -- inputs, decision variables, objective(s), and constraints -- are introduced. Optimization is applied to linear regression, basic inventory modeling, and the newsvendor problem, which incorporates uncertain demand. Linear programming is then introduced. We show that the newsvendor problem can be cast as a network flow linear programming problem. Linear programming is then applied to the problem of redistributing empty rental vehicles (e.g., bicycles) at the end of a day and the problem of assigning students to seminars. Several chapters deal with location models as examples of both simple optimization problems and integer programming problems. The next major section focuses on queueing theory including single-and multi-server queues. This section also introduces a numerical method for solving for key performance metrics for a common class of queueing problems as well as simulation modeling. Finally, the text ends with a discussion of decision theory that again integrates notions of optimization, tradeoffs, and uncertainty analysis. The text is designed for anyone with a modest mathematical background. As such, it should be readily accessible to engineering students, economics, statistics, and mathematics majors, as well as many business students.Capacitated price bundling for markets with discrete customer segments and stochastic willingness to pay: abasic decision modelhttps://www.zbmath.org/1472.900432021-11-25T18:46:10.358925Z"Gössinger, Ralf"https://www.zbmath.org/authors/?q=ai:gossinger.ralf"Wand, Jacqueline"https://www.zbmath.org/authors/?q=ai:wand.jacquelineSummary: Current literature on price bundling focuses on the situation with limited capacity. This paper extends this research by considering multiple discrete customer segments each with individual size and buying behavior represented by distributed willingness to pay and max-surplus rule. We develop a stochastic non-linear programming model that can be solved by standard NLP optimization software. Aiming to examine the model behavior, we conduct a full-factorial numerical study and analyze the impact of capacity limitations and number of customer segments on optimal solutions.
For the entire collection see [Zbl 1468.90005].Hesitant fuzzy multi-attribute decision-making method based on signed correlation and prioritization relationshiphttps://www.zbmath.org/1472.900442021-11-25T18:46:10.358925Z"Liu, Ruobing"https://www.zbmath.org/authors/?q=ai:liu.ruobing"Ruan, Chuan-Yang"https://www.zbmath.org/authors/?q=ai:ruan.chuanyang"Li, Deng-Feng"https://www.zbmath.org/authors/?q=ai:li.dengfeng|li.dengfeng.1"Xu, Hui"https://www.zbmath.org/authors/?q=ai:xu.huiSummary: To solve the excessive subjectivity problem caused by artificially added elements in hesitant fuzzy elements, we propose a hesitant fuzzy decision-making method based on signed correlation that considers attribute priority. In order to consider the variance of the elements and the number of elements, we propose the hesitation degree of hesitant fuzzy set, and on this basis, hesitant fuzzy signed correlation measurement is defined. These are then applied to the multi-attribute decision-making problem in multi-sensor electronic reconnaissance. Comparative analyses are made via simulation to test the rationality and validity of the proposed method.On a maximum eigenvalue of third-order pairwise comparison matrix in analytic hierarchy process and convergence of Newton's methodhttps://www.zbmath.org/1472.900462021-11-25T18:46:10.358925Z"Shiraishi, Shunsuke"https://www.zbmath.org/authors/?q=ai:shiraishi.shunsuke"Obata, Tsuneshi"https://www.zbmath.org/authors/?q=ai:obata.tsuneshiSummary: Nowadays, the analytic hierarchy process is an established method of multiple criteria decision making in the field of Operations Research. Pairwise comparison matrix plays a crucial role in the analytic hierarchy process. The principal (maximum magnitude) eigenvalue of the pairwise comparison matrix can be utilized for measuring the consistency of the decision maker's judgment. The simple transformation of the maximum magnitude eigenvalue is known to be Saaty's consistency index. In this short note, we shed light on the characteristic polynomial of a pairwise comparison matrix of third order. We will show that the only real-number root of the characteristic equation is the maximum magnitude eigenvalue of the third-order pairwise comparison matrix. The unique real-number root appears in the area where it is greater than 3, which is equal to the order of the matrix. By applying usual Newton's method to the characteristic polynomial of the third-order pairwise comparison matrix, we see that the sequence generated from the initial value of 3 always converges to the maximum magnitude eigenvalue.A kind of affective computing MAGDM method with its applicationshttps://www.zbmath.org/1472.900472021-11-25T18:46:10.358925Z"Su, Chong"https://www.zbmath.org/authors/?q=ai:su.chong"Chen, Jie"https://www.zbmath.org/authors/?q=ai:chen.jie.6|chen.jie|chen.jie.3|chen.jie.5|chen.jie.4|chen.jie.1|chen.jie.7|chen.jie.8|chen.jie.10|chen.jie.2|chen.jie.9Summary: Traditional multi-attribute group decision-making (MAGDM) methods always focus on obtaining the alternatives' ranking order based on the gatherer group experts' preferences, which suffers difficulties in dealing with MAGDM with new input alternatives automatically. In regard to this problem, a new affective computing model that combines human personalities, PAD (pleasure-arousal-dominance) emotional space states and affective states is established, quantitatively describing emotional transitions impacted by persistent external stimuli and presenting a mapping approach from affective states to subjective expected values of decision results. Then, we propose the definition of decision parameters in MAGDM along with the decision parameters identification algorithms. Finally, an improved MAGDM model based on affective computing is used to study the influence between decision parameters and decision results, effectively helping computer do group decision-making automatically. Two numerical cases are employed to verify the merits of the proposed MAGDM methods over traditional MAGDM approaches, giving rise to satisfied results and showing validity of the contribution.An integer programming formulation of capacitated facility location problemhttps://www.zbmath.org/1472.900492021-11-25T18:46:10.358925Z"Alenezy, Eiman Jadaan"https://www.zbmath.org/authors/?q=ai:alenezy.eiman-jadaanSummary: We study the three approximation algorithms developed for solving Uncapacitated Facility Location Problem (UCFLP). These are: the algorithms based on linear programming rounding, the primal-dual algorithm of \textit{K. Jain} and \textit{V. V. Vazirani} [J. ACM 48, No. 2, 274--296 (2001; Zbl 1138.90417)], and the algorithms based on dual-fitting. They give the reader an insight into the main approach to solve the Facility Location Problem (FLP).Multi-period service territory designhttps://www.zbmath.org/1472.900512021-11-25T18:46:10.358925Z"Bender, Matthias"https://www.zbmath.org/authors/?q=ai:bender.matthias"Kalcsics, Jörg"https://www.zbmath.org/authors/?q=ai:kalcsics.jorgSummary: In service districting, a given set of customers has to be assigned to the individual members of the service workforce such that each customer has a unique representative, each service provider faces an equitable workload and travel time, and service districts are compact and contiguous. One important, but rarely addressed feature of many service districting applications is that customers require service with different frequencies. As a result, planners not only have to design the service districts, but also schedule visits to customers within the planning horizon such that the workload for each service provider is the same across all periods and the set of all customers visited in the same time period is as compact as possible. We present a mixed-integer linear programming formulation for the problem. As it turns out, only very small data sets can be solved to optimality within a reasonable amount of time. One of the reasons for that appears to be the high level of symmetry between solutions. We first characterize these symmetries and propose ideas to try to eliminate them in the formulation. Afterwards, we focus on the scheduling component of the problem and present a location-allocation based heuristic for determining visiting schedules for the service providers for fixed districts. In addition, we propose a branch-and-price algorithm to solve larger data sets to proven optimality. One of the novel features of the algorithm is a symmetry-reduced branching scheme that results in a significant speed-up.
For the entire collection see [Zbl 1469.90005].Bounding procedures and exact solutions for a class of territory design problemshttps://www.zbmath.org/1472.900522021-11-25T18:46:10.358925Z"Díaz, Juan A."https://www.zbmath.org/authors/?q=ai:diaz.juan-a"Luna, Dolores E."https://www.zbmath.org/authors/?q=ai:luna.dolores-e"Sandoval, María G."https://www.zbmath.org/authors/?q=ai:sandoval.maria-gSummary: In this chapter, we present and evaluate exact methods and lower and upper bounding procedures for a class of territory design problems. Most territory design problems, as the one studied in this chapter, consider requirements of compactness, contiguity, and balance with respect to one or more activity measures, for example, number of customers and sales volume in the case of commercial territories, voting potential equality in the case of political territories, workload balance when designing service territories, etc. To obtain solutions with compact territories, a minisum objective function equivalent to the objective function of the \(p\)-median problem is used. The exact solution methods presented here use different relaxations of integer linear programming formulations of the problem. Additionally, two methodologies to obtain upper bounds (feasible solutions) are presented. The first one uses the relaxation of an integer quadratic programming formulation. The second methodology obtains feasible solutions using a primal heuristic within the framework of a subgradient optimization algorithm to solve a Lagrangian dual that also provides lower bounds for the optimal solution. Instances obtained from the literature are used to evaluate and compare the different methodologies presented.
For the entire collection see [Zbl 1469.90005].Designing ambulance service districts under uncertaintyhttps://www.zbmath.org/1472.900532021-11-25T18:46:10.358925Z"Enayati, Shakiba"https://www.zbmath.org/authors/?q=ai:enayati.shakiba"Özaltın, Osman Y."https://www.zbmath.org/authors/?q=ai:ozaltin.osman-y"Mayorga, Maria E."https://www.zbmath.org/authors/?q=ai:mayorga.maria-eSummary: For ambulances, quick response to a medical emergency is critical. Limiting response area for each ambulance may lead to shorter response times to emergency scenes and more evenly distributed workload for ambulances. We propose a two-stage stochastic mixed-integer programming model to address the service district design problem under uncertainty. The proposed model recommends how to locate ambulances to the waiting sites in the service area, and how to assign a set of demand zones to each ambulance at different backup levels. Our proposed Stochastic Service District Design (SSDD) model enables quick response times by jointly addressing the location and dispatching policies in a stochastic and dynamic environment. Each backup level is associated with a given response time threshold. The objective function is to maximize the expected number of covered calls while restricting the workload of each ambulance. The proposed model can be optimized offline as is commonly done for ``patrol-beats'' used in policing models. We evaluate the implementation of the proposed model via a discrete-event simulation, and compare the model with two baseline policies. Our computational results show a significant improvement in mean response time, reduction of 2 min, and statistically lower average workload of ambulances, of 4\% on average, when the proposed model is fully implemented.
For the entire collection see [Zbl 1469.90005].Territory design for sales force sizinghttps://www.zbmath.org/1472.900562021-11-25T18:46:10.358925Z"Moya-García, Juan G."https://www.zbmath.org/authors/?q=ai:moya-garcia.juan-g"Salazar-Aguilar, M. Angélica"https://www.zbmath.org/authors/?q=ai:angelica-salazar-aguilar.m|salazar-aguilar.maria-angelicaSummary: In sales territory design applications, a sales force team is in charge of performing recurring visits to the customers and typically, each territory is assigned to a sales representative with the aim to establish long-term personal relationship with the customers. At the strategic level, the decision maker must partition the set of customer in sales territories and at the tactical level, the daily routes (schedule of visits) of the sales representatives must be planned. Balanced sales territories allow better customer coverage and balanced workload. Additionally, efficient routes allow to perform more visits and to reduce the travel time. In this work, we focus in an application of territory design for determining the size of the sales force in a Mexican company. We also describe a simple heuristic for this problem and analyze its performance in two real cases from the company. Computational results show that the proposed heuristic produces high-quality solutions within a low computation time.
For the entire collection see [Zbl 1469.90005].Research trends in optimization of districting systemshttps://www.zbmath.org/1472.900582021-11-25T18:46:10.358925Z"Ríos-Mercado, Roger Z."https://www.zbmath.org/authors/?q=ai:rios-mercado.roger-zSummary: The intent of this book is to present recent developments and insights on optimal territory design problems. In the literature, territory design can also be referred as districting or zone design. In particular emphasis is given to modeling aspects, theory, and algorithmic development of recent complex developments on districting and territory design by leading experts in the field. The book includes some literature surveys on particular areas of districting such as police patrolling, health care districting, and computational geometry methods, and successful case studies in political and sales force deployment districting.
For the entire collection see [Zbl 1469.90005].Optimization of usable leftover cutting stock problems using fuzzy approachhttps://www.zbmath.org/1472.900612021-11-25T18:46:10.358925Z"Bressan, Glaucia Maria"https://www.zbmath.org/authors/?q=ai:bressan.glaucia-maria"de Souza Sobrinho, Monique Gabrielle"https://www.zbmath.org/authors/?q=ai:de-souza-sobrinho.monique-gabrielle"Agulhari, Christiano Marcos"https://www.zbmath.org/authors/?q=ai:agulhari.christiano-marcosSummary: The objectives of this paper are to analyze different linear optimization models for the one-dimensional cutting stock problem and, by using a fuzzy classification approach, determine the reutilization of the leftovers from the cutting process. The optimal solutions of the proposed linear models are obtained from simplex method. The fuzzy classification system is a collaborative decision-making tool, which analyzes uncertain parameters in the manufacturing process in order to determine, according to the given objective, the most appropriate cutting pattern, also classifying the results provided by different linear optimization models. The comparison of the results allows to infer the most appropriate model to use according to the specifications of the problem to be solved. Results are obtained from a case study, in a packaging company, located in the state of Paraná, Brazil, which aims to select the best cutting pattern for two different scenarios: one with concentration of leftovers on standardized objects, and the other on non-standardized objects.Merging decision-making units with interval datahttps://www.zbmath.org/1472.900622021-11-25T18:46:10.358925Z"Ghobadi, Saeid"https://www.zbmath.org/authors/?q=ai:ghobadi.saeidSummary: This paper deals with the problem of merging units with interval data. There are two important problems in the merging units. Estimation of the inherited inputs/outputs of the merged unit from merging units is the first problem while the identification of the least and most achievable efficiency targets from the merged unit is the second one. In the imprecise or ambiguous data framework, the inverse DEA concept and linear programming models could be employed to solve the first and second problem, respectively. To identify the required inputs/outputs from merging units, the merged entity is enabled by the proposed method. This provides a predefined efficiency goal. The best and worst attainable efficiency could be determined through the presented models. The developed merging theory is evaluated through a banking sector application.Erratum to: ``Improved complexity analysis of full Nesterov-Todd step feasible interior-point method for symmetric optimization''https://www.zbmath.org/1472.900632021-11-25T18:46:10.358925Z"Wang, G. Q."https://www.zbmath.org/authors/?q=ai:wang.guoqiang"Kong, L. C."https://www.zbmath.org/authors/?q=ai:kong.lingchen"Tao, J. Y."https://www.zbmath.org/authors/?q=ai:tao.jiyuan"Lesaja, G."https://www.zbmath.org/authors/?q=ai:lesaja.goranFrom the text: We correct a typo in our paper [ibid. 166, No. 2, 588--604 (2015; Zbl 1336.90059), Corollary 3.1] and an error in the proof of [loc. cit., Lemma 2.3].A new CG algorithm based on a scaled memoryless BFGS update with adaptive search strategy, and its application to large-scale unconstrained optimization problemshttps://www.zbmath.org/1472.900642021-11-25T18:46:10.358925Z"Li, Xiangli"https://www.zbmath.org/authors/?q=ai:li.xiangli"Zhao, Wenjuan"https://www.zbmath.org/authors/?q=ai:zhao.wenjuan"Dong, Xiaoliang"https://www.zbmath.org/authors/?q=ai:dong.xiaoliangSummary: Conjugate gradient method is an effective method for solving large-scale unconstrained optimization problems. This paper proposes a new conjugate gradient algorithm based on the self-scaling memoryless BFGS update, which uses the Wolfe line search. The descent and global convergence of the method are given under mild conditions. Numerical experiments show that our new conjugate gradient method is effective.An algorithm for the anchor points of the PPS of the FRH modelshttps://www.zbmath.org/1472.900652021-11-25T18:46:10.358925Z"Akbarian, Dariush"https://www.zbmath.org/authors/?q=ai:akbarian.dariushSummary: In this paper we deal with a variant of non-convex data envelopment analysis, called free replication hull model and try to obtain their anchor points. This paper uses a variant of super-efficiency model to characterize all extreme efficient decision making units and anchor points of the free replication hull models. A necessary and sufficient conditions for a decision making unit to be anchor point of the production possibility set of the free replication hull models are stated and proved. Since the set of anchor points is a subset of the set of extreme units, a definition of extreme units and a new method for obtaining these units in non-convex technologies are given. To illustrate the applicability of the proposed model, some numerical examples are finally provided.Data envelopment analysis with fuzzy complex numbers with an empirical case on power plants of Iranhttps://www.zbmath.org/1472.900662021-11-25T18:46:10.358925Z"Esfandiari, Mahmood"https://www.zbmath.org/authors/?q=ai:esfandiari.mahmood"Saati, Saber"https://www.zbmath.org/authors/?q=ai:saati.saberSummary: Using Data Envelopment Analysis (DEA) in complex environment is an idea that has recently presented for measuring the relative efficiencies of a set of Decision Making Units (DMUs) with complex inputs and outputs. The values of the input and output data in real-world problems appear sometimes as fuzzy complex number. For dealing with these types of data in DEA, we need to design a new model. This paper proposes a DEA model with triangular fuzzy complex numbers and solve it by using the concept of the data size and the \(\alpha \)-level approach. This method transforms DEA model with fuzzy complex data to a linear programing problem with crisp data. In the following, a ranking model is also developed using the above approach to rank the efficient DMUs. The proposed method is presented for the first time by the authors and there is no similar method. Finally, we present a case study in the generators of the steam power plants to demonstrate the applicability of the proposed methods in the power industry.Recommending investment opportunities given congestion by adaptive network data envelopment analysis model: assessing sustainability of supply chainshttps://www.zbmath.org/1472.900672021-11-25T18:46:10.358925Z"Hajaji, Hossein"https://www.zbmath.org/authors/?q=ai:hajaji.hossein"Yousefi, Sara"https://www.zbmath.org/authors/?q=ai:yousefi.sara"Saen, Reza Farzipoor"https://www.zbmath.org/authors/?q=ai:saen.reza-farzipoor"Hassanzadeh, Amir"https://www.zbmath.org/authors/?q=ai:hassanzadeh.amirSummary: Nowadays, forward-thinking companies move beyond conventional structures of organizations and consider all parties of the supply chain. The objective of this paper is to present an adaptive network data envelopment analysis (DEA) model to evaluate overall and divisional efficiency of sustainable supply chains in the presence of desirable and undesirable outputs. Our adaptive network DEA model can assess overall and divisional efficiency of supply chains given managerial and natural disposability. Also, it suggests new investment opportunity given congestion type. A case study is presented.Solving optimization problems with MATLABhttps://www.zbmath.org/1472.900682021-11-25T18:46:10.358925Z"Xue, Dingyü"https://www.zbmath.org/authors/?q=ai:xue.dingyuThe book is meant for readers who have learnt optimization methods in mathematics courses and want to revisit them with computer tools to verify the solutions of large dimensional problems. Since Matlab includes some exquisite skills and general-purpose solvers, it remains unique from other existing software packages that are used for scientific computing. The author elaborately depicts in the whole book how to use and handle Matlab for obtaining the solutions for various types of nonlinear equations and optimization problems. The structure of the book is as follows. In the second chapter, the author attempts to find the solutions of polynomial and ordinary nonlinear equations with the help of existing nonlinear equation solvers provided in Matlab. Besides describing the symbolic computation method, the solution methods for matrix equations and pseudo-polynomial equations are also explored with high precision methods. In the next chapter, the author mainly focuses on the unconstrained optimization solvers provided in the Matlab optimization toolbox and also presents the efficiency of the global optimum solver by experimenting with several test functions. The author explicitly puts all the control options available in the optimization toolbox with their proper explanations. In contrast to Chapter 3, from Chapter 4 to Chapter 8, the Matlab-based solutions of constrained optimization problems are presented, which includes several variations of linear and nonlinear programming such as quadratic programming, mixed integer programming, multi-objective programming, dynamic programming, etc. In the last chapter, the book introduces some of the intelligent optimization algorithms including genetic algorithm, particle swarm optimization algorithm, simulated annealing algorithm, and also shows their execution technique through Matlab global optimization toolbox. Some comparisons between the intelligent methods and the conventional methods over several benchmark problems are also provided to assess and suitably conclude on the behavior of the evolutionary algorithms. In a nutshell, the effective explanations of the methods and their implementation in Matlab genuinely help the readers to establish a solid foundation and deep introspection for the application of Matlab in numerical computing.Design, analysis and performance evaluation of parallel algorithms for solving triangular linear systems on multicore platformshttps://www.zbmath.org/1472.900692021-11-25T18:46:10.358925Z"Belmabrouk, Mounira"https://www.zbmath.org/authors/?q=ai:belmabrouk.mounira"Marrakchi, Mounir"https://www.zbmath.org/authors/?q=ai:marrakchi.mounirSummary: In this paper, we focus on the schedulings of 2-steps graph with constant task cost obtained when parallelizing algorithm solving a triangular linear system. We present three scheduling approaches having the same least theoretical execution time. The first is designed through solving a 0-1 integer problem by Mixed Integer Programming (MIP), the second is based on the Critical Path Algorithm (CPA) and the third is a particular Column-Oriented Scheduling (COS). The MIP approach experiments were carried out and confirmed that the makespan values of the MIP scheduling coincide with those of the corresponding lower bound already reached. Experimental results of the last two approaches detailing both makespans and efficiencies are presented and show that their practical performances differ though they are theoretically identical. We compare also these results to those of the appropriate procedure into so-called PLASMA library (Parallel Linear Algebra for Scalable Multi-core Architectures).Integer and constraint programming approaches for providing optimality to the bandwidth multicoloring problemhttps://www.zbmath.org/1472.900702021-11-25T18:46:10.358925Z"Dias, Bruno"https://www.zbmath.org/authors/?q=ai:dias.bruno-h"de Freitas, Rosiane"https://www.zbmath.org/authors/?q=ai:de-freitas.rosiane"Maculan, Nelson"https://www.zbmath.org/authors/?q=ai:maculan.nelson-f"Michelon, Philippe"https://www.zbmath.org/authors/?q=ai:michelon.philippe-yves-paulSummary: In this paper, constraint and integer programming techniques are applied to solving bandwidth coloring problems, in the sense of proving optimality or finding better feasible solutions for benchmark instances from the literature. The Bandwidth Coloring Problem (BCP) is a generalization of the classic vertex coloring problem (VCP), where, given a graph, its vertices must be colored such that not only adjacent ones do not share the same color, but also their colors must be separated by a minimum given value. BCP is further generalized to the Bandwidth Multicoloring Problem (BMCP), where each vertex can receive more than one different color, also subject to separation constraints. BMCP is used to model the Minimum Span Channel Assignment Problem (MS-CAP), which arises in the planning of telecommunication networks. Research on algorithmic strategies to solve these problems focus mainly on heuristic approaches and the performance of such methods is tested on artificial and real scenarios benchmarks, such as GEOM, Philadelphia and Helsinki sets. We achieve optimal solutions or provide better upper bounds for these well-known instances, We also compare the effects of multicoloring demands on the performance of each exact solution approach, based on empirical analysis.An outer approximation method for a class of minimax convex MINLP problemshttps://www.zbmath.org/1472.900712021-11-25T18:46:10.358925Z"Chen, Liang"https://www.zbmath.org/authors/?q=ai:chen.liang"Dai, Yu-Hong"https://www.zbmath.org/authors/?q=ai:dai.yu-hong"Wei, Zhou"https://www.zbmath.org/authors/?q=ai:wei.zhouSummary: In this paper, we mainly study a class of mixed-integer nonlinear program (MINLP) problems whose objective and constraint functions are the maximum of finite convex smooth functions. Such problems refer to the combination of two areas of MINLP and nonsmooth optimization. For solving these minimax convex MINLP problems, we consider an outer approximation method and use KKT optimality conditions and subgradients to reformulate MINLP as an equivalent mixed-integer linear program (MILP). Then we construct an outer approximation algorithm for solving a sequence of relaxed MILP problems so as to find the optimal solution of MINLP. The algorithm is proved to terminate after a finite number of steps. To illustrate the feasibility of the outer approximation method for such problems, several minimax convex MINLP examples are provided and calculated by this algorithm. All computational tests are implemented by MILP solvers of Matlab and BARON.A scenario-based optimization model for planning and redesigning the sale and after-sales services closed-loop supply chainhttps://www.zbmath.org/1472.900722021-11-25T18:46:10.358925Z"Esmaeili, Nazanin"https://www.zbmath.org/authors/?q=ai:esmaeili.nazanin"Teimoury, Ebrahim"https://www.zbmath.org/authors/?q=ai:teimoury.ebrahim"Pourmohammadi, Fahimeh"https://www.zbmath.org/authors/?q=ai:pourmohammadi.fahimehSummary: In today's competitive world, the quality of after-sales services plays a significant role in customer satisfaction and customer retention. Some after-sales activities require spare parts and owing to the importance of customer satisfaction, the needed spare parts must be supplied until the end of the warranty period. In this study, a mixed-integer linear optimization model is presented to redesign and plan the sale and after-sales services supply chain that addresses the challenges of supplying spare parts after the production is stopped due to demand reduction. Three different options are considered for supplying spare parts, including production/procurement of extra parts while the product is being produced, remanufacturing, and procurement of parts just in time they are needed. Considering the challenges of supplying spare parts for after-sales services based on the product's life cycle is one contribution of this paper. Also, this paper addresses the uncertainties associated with different parameters through Mulvey's scenario-based optimization approach. Applicability of the model is investigated using a numerical example from the literature. The results indicate that the production/procurement of extra parts and remanufacturing are preferred to the third option. Moreover, remanufacturing is recommended when the remanufacturing cost is less than 23\% of the production cost.Erratum to: ``An abstract model for branching and its application to mixed integer programming''https://www.zbmath.org/1472.900732021-11-25T18:46:10.358925Z"Le Bodic, Pierre"https://www.zbmath.org/authors/?q=ai:le-bodic.pierre"Nemhauser, George"https://www.zbmath.org/authors/?q=ai:nemhauser.george-lFrom the text: In the original version of the article [the authors, ibid. 166, No. 1-2 (A), 369--405 (2017; Zbl 1386.90087)], the format of Table 1 was incorrect. The original article has been revised to provide the correct table.Designing a clothing supply chain network considering pricing and demand sensitivity to discounts and advertisementhttps://www.zbmath.org/1472.900742021-11-25T18:46:10.358925Z"Paydar, Mohammad Mahdi"https://www.zbmath.org/authors/?q=ai:paydar.mohammad-mahdi"Olfati, Marjan"https://www.zbmath.org/authors/?q=ai:olfati.marjan"Triki, Chefi"https://www.zbmath.org/authors/?q=ai:triki.chefiSummary: These days, clothing companies are becoming more and more developed around the world. Due to the rapid development of these companies, designing an efficient clothing supply chain network can be highly beneficial, especially with the remarkable increase in demand and uncertainties in both supply and demand. In this study, a bi-objective stochastic mixed-integer linear programming model is proposed for designing the supply chain of the clothing industry. The first objective function maximizes total profit and the second one minimizes downside risk. In the presented network, the initial demand and price are uncertain and are incorporated into the model through a set of scenarios. To solve the bi-objective model, weighted normalized goal programming is applied. Besides, a real case study for the clothing industry in Iran is proposed to validate the presented model and developed method. The obtained results showed the validity and efficiency of the current study. Also, sensitivity analyses are conducted to evaluate the effect of several important parameters, such as discount and advertisement, on the supply chain. The results indicate that considering the optimal amount for discount parameter can conceivably enhance total profit by about 20\% compared to the time without this discount scheme. When the optimized parameter is taken into account for advertisement, 12\% is obtained as total profit.A mixed integer nonlinear multiperiod model for supply chain management of a company in the retail sectorhttps://www.zbmath.org/1472.900752021-11-25T18:46:10.358925Z"Teixeira, Ana"https://www.zbmath.org/authors/?q=ai:teixeira.ana"Silva, Eliana Costa E."https://www.zbmath.org/authors/?q=ai:silva.eliana-costa-e"Lopes, Cristina"https://www.zbmath.org/authors/?q=ai:lopes.cristina-videiraSummary: The fluctuations in the business environment and seasonal variations characteristic of food supply chains contribute greatly to the increasing complexity of the entire Supply Chain planning. In the present paper, quantitative models are applied to support the decision-making purchasing management department of a retail company. Specifically, a multiperiod mathematical model was developed with the aim of optimizing decision-making of the purchasing managers. The developed model consists of a multiperiod Mixed Integer Nonlinear Programming model, with the objective to minimize the ratio between how much is costing the company to move the products along the Supply Chain and the products' costs. It is discussed how to order the product, what is the most advantageous storage mode and whether it is preferable to order once or twice a week. Real instances, provided by a Portuguese retail company, regarding the demand for one year are tested for two scenarii, which are used currently by the company. The results show that the proposed model can reduce, on both scenarios, the ratio between operational costs and merchandise costs, for almost all products, and therefore it can be an important tool for supporting decision-making of the purchasing manager.Warehouse redesigning in a three-echelon supply chain network with consideration of routing under uncertainty: a light robust approachhttps://www.zbmath.org/1472.900762021-11-25T18:46:10.358925Z"Azadehranjbar, Zahra"https://www.zbmath.org/authors/?q=ai:azadehranjbar.zahra"Bozorgi-Amiri, Ali"https://www.zbmath.org/authors/?q=ai:bozorgi-amiri.ali"Zandi, Arash"https://www.zbmath.org/authors/?q=ai:zandi.arashSummary: This paper addresses the problem of redesigning a three-echelon supply chain network under uncertainty. Since one of the most realistic problems that supply chains are dealt with is routing of vehicles, routing constraints with a split delivery condition are considered in our proposed model. Also, the possibility of outsourcing is considered in order to satisfy demands that exceed the production capacity. Furthermore, in order to deal with the presence of uncertainty in the problem, a light robust approach is developed. The performance of the proposed model is illustrated using a simulation procedure. Sensitivity analysis on the proposed model is also presented in the paper. The results show that the proposed method has a better performance than Light Robust approach and can be used as a useful managerial tool in redesign problems.Sample out-of-sample inference based on Wasserstein distancehttps://www.zbmath.org/1472.900772021-11-25T18:46:10.358925Z"Blanchet, Jose"https://www.zbmath.org/authors/?q=ai:blanchet.jose-h"Kang, Yang"https://www.zbmath.org/authors/?q=ai:kang.yangSummary: We present a novel inference approach that we call sample out-of-sample inference. The approach can be used widely, ranging from semisupervised learning to stress testing, and it is fundamental in the application of data-driven distributionally robust optimization. Our method enables measuring the impact of plausible out-of-sample scenarios in a given performance measure of interest, such as a financial loss. The methodology is inspired by empirical likelihood (EL), but we optimize the empirical Wasserstein distance (instead of the empirical likelihood) induced by observations. From a methodological standpoint, our analysis of the asymptotic behavior of the induced Wasserstein-distance profile function shows dramatic qualitative differences relative to EL. For instance, in contrast to EL, which typically yields chi-squared weak convergence limits, our asymptotic distributions are often not chi-squared. Also, the rates of convergence that we obtain have some dependence on the dimension in a nontrivial way but remain controlled as the dimension increases.Robust Farkas-Minkowski constraint qualification for convex inequality system under data uncertaintyhttps://www.zbmath.org/1472.900782021-11-25T18:46:10.358925Z"Li, Xiao-Bing"https://www.zbmath.org/authors/?q=ai:li.xiaobing"Al-Homidan, Suliman"https://www.zbmath.org/authors/?q=ai:al-homidan.suliman-s"Ansari, Qamrul Hasan"https://www.zbmath.org/authors/?q=ai:ansari.qamrul-hasan"Yao, Jen-Chih"https://www.zbmath.org/authors/?q=ai:yao.jen-chihThe authors consider the nonempty assumed solution set \(S=\{x\in \mathbb{R}^n \mid g_i(x,u_i)\le 0\; \forall\,u_i\in \mathcal{U}_i,\, i\in \mathcal{I}=1,2,\dots k \}\) of a robust finite inequality system with compact convex uncertainty sets \(\mathcal{U}_i\) and convex-concave finite valued functions \(g_i:\mathbb{R}^n\times\mathbb{R}^m\rightarrow\mathbb{R}\), \(i\in \mathcal{I}\). They show (Th. 1) that the robust global error bound (RGEB) \(\alpha \inf_{y\in S}\|x-y\|\le \sum_{i\in \mathcal{I}}[\sup_{u_i\in \mathcal{U}_i}g_i(x,u_i)]_+\) on \(\mathbb{R}^n\) for some \(\alpha>0\) is sufficient for the validity of the robust Farkas-Minkowski constraint qualification (FMCQ) according to \(\mathrm{epi}\,\delta^*_S=\bigcup_{\lambda_i>0,\,\,u_i\in \mathcal{U}_i,\,i\in \mathcal{I}}\mathrm{epi}\,(\sum_{i\in \mathcal{I}}\lambda_ig_i(x,u_i))^*\). \(\mathrm{epi} f\) is the epigraph of an extended real-valued function \(f\) and \(\delta^*_S\) denotes the support functional of the convex set \(S\). Hence the union is a closed convex cone. Example 3.2 demonstrates that the concavity of \(g_i\) w.r.t. \(u_i\) is essential. Conditions (FMCQ) and (REGB) are equivalent for the special case of in \(x\) positively semidefinite quadratic forms \(g_i\) with coefficients \(u_i\) belonging to a scenario uncertainty set. In the last three rows of the proof of Th. 1, the subset sign should be replaced by the corresponding superset sign for getting equality.Branch-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertaintyhttps://www.zbmath.org/1472.900792021-11-25T18:46:10.358925Z"Pessoa, Artur Alves"https://www.zbmath.org/authors/?q=ai:pessoa.artur-alves"Poss, Michael"https://www.zbmath.org/authors/?q=ai:poss.michael"Sadykov, Ruslan"https://www.zbmath.org/authors/?q=ai:sadykov.ruslan"Vanderbeck, François"https://www.zbmath.org/authors/?q=ai:vanderbeck.francoisSummary: We examine the robust counterpart of the classical capacitated vehicle routing problem (CVRP). We consider two types of uncertainty sets for the customer demands: the classical budget polytope and a partitioned budget polytope. We show that using the set-partitioning formulation it is possible to reformulate our problem as a deterministic heterogeneous vehicle routing problem. Thus, many state-of-the-art techniques for exactly solving deterministic VRPs can be applied to the robust counterpart, and a modern branch-cut-and-price algorithm can be adapted to our setting by keeping the number of pricing subproblems strictly polynomial. More importantly, we introduce new techniques to significantly improve the efficiency of the algorithm. We present analytical conditions under which a pricing subproblem is infeasible. This result is general and can be applied to other combinatorial optimization problems with knapsack uncertainty. We also introduce robust capacity cuts that are provably stronger than the ones known in the literature. Finally, a fast-iterated local search algorithm is proposed to obtain heuristic solutions for the problem. Using our branch-cut-and-price algorithm incorporating existing and new techniques, we solve to optimality all but one of the open instances from the literature.
The e-companion is available at \url{https://doi.org/10.1287/opre.2020.2035}.Efficient algorithms for distributionally robust stochastic optimization with discrete scenario supporthttps://www.zbmath.org/1472.900802021-11-25T18:46:10.358925Z"Zhang, Zhe"https://www.zbmath.org/authors/?q=ai:zhang.zhe"Ahmed, Shabbir"https://www.zbmath.org/authors/?q=ai:ahmed.shabbir.1|ahmed.shabbir"Lan, Guanghui"https://www.zbmath.org/authors/?q=ai:lan.guanghuiQuadratic problems with two quadratic constraints: convex quadratic relaxation and strong Lagrangian dualityhttps://www.zbmath.org/1472.900812021-11-25T18:46:10.358925Z"Hamdi, Abdelouahed"https://www.zbmath.org/authors/?q=ai:hamdi.abdelouahed"Taati, Akram"https://www.zbmath.org/authors/?q=ai:taati.akram"Almaadeed, Temadher A."https://www.zbmath.org/authors/?q=ai:almaadeed.temadher-aSummary: In this paper, we study a nonconvex quadratic minimization problem with two quadratic constraints, one of which being convex. We introduce two convex quadratic relaxations (CQRs) and discuss cases, where the problem is equivalent to exactly one of the CQRs. Particularly, we show that the global optimal solution can be recovered from an optimal solution of the CQRs. Through this equivalence, we introduce new conditions under which the problem enjoys strong Lagrangian duality, generalizing the recent condition in the literature. Finally, under the new conditions, we present necessary and sufficient conditions for global optimality of the problem.Strong duality in minimizing a quadratic form subject to two homogeneous quadratic inequalities over the unit spherehttps://www.zbmath.org/1472.900822021-11-25T18:46:10.358925Z"Nguyen, Van-Bong"https://www.zbmath.org/authors/?q=ai:nguyen.van-bong"Nguyen, Thi Ngan"https://www.zbmath.org/authors/?q=ai:nguyen.thi-ngan"Sheu, Ruey-Lin"https://www.zbmath.org/authors/?q=ai:sheu.ruey-linThe authors study the strong duality for an optimization problem to minimize a homogeneous quadratic function subject to two homogeneous quadratic constraints over the unit sphere, called Problem (P) in this paper. When a feasible (P) fails to have a Slater point, they show that (P) always adopts the strong duality. When (P) has a Slater point, the authors propose a set of conditions, called ``Property J'', on an SDP relaxation of (P) and its conical dual. They show that (P) has the strong duality if and only if there exists at least one optimal solution to the SDP relaxation of (P) which fails Property J. The used techniques are based on various extensions of the \(S\)-lemma as well as the matrix rank-one decomposition procedure introduced by \textit{W. Ai} and \textit{S. Zhang} [SIAM J. Optim. 19, No. 4, 1735--1756 (2009; Zbl 1187.90290)]. Many nontrivial examples are constructed to help understand the mechanism.Symmetry adapted Gram spectrahedrahttps://www.zbmath.org/1472.900832021-11-25T18:46:10.358925Z"Heaton, Alexander"https://www.zbmath.org/authors/?q=ai:heaton.alexander"Hoşten, Serkan"https://www.zbmath.org/authors/?q=ai:hosten.serkan"Shankar, Isabelle"https://www.zbmath.org/authors/?q=ai:shankar.isabelleAn inexact augmented Lagrangian method for second-order cone programming with applicationshttps://www.zbmath.org/1472.900842021-11-25T18:46:10.358925Z"Liang, Ling"https://www.zbmath.org/authors/?q=ai:liang.ling"Sun, Defeng"https://www.zbmath.org/authors/?q=ai:sun.defeng"Toh, Kim-Chuan"https://www.zbmath.org/authors/?q=ai:toh.kimchuanCorrection to: ``A primal-dual interior point trust-region method for nonlinear semidefinite programming''https://www.zbmath.org/1472.900852021-11-25T18:46:10.358925Z"Yamashita, Hiroshi"https://www.zbmath.org/authors/?q=ai:yamashita.hiroshi"Yabe, Hiroshi"https://www.zbmath.org/authors/?q=ai:yabe.hiroshi"Harada, Kouhei"https://www.zbmath.org/authors/?q=ai:harada.kouheiCorrection to the authors' paper [ibid. 36, No. 2--3, 569--601 (2021; Zbl 1470.90067)].Metastability of the proximal point algorithm with multi-parametershttps://www.zbmath.org/1472.900862021-11-25T18:46:10.358925Z"Dinis, Bruno"https://www.zbmath.org/authors/?q=ai:dinis.bruno"Pinto, Pedro"https://www.zbmath.org/authors/?q=ai:pinto.pedro-cSummary: In this article we use techniques of proof mining to analyse a result, due to \textit{Y. Yao} and \textit{M. A. Noor} [J. Comput. Appl. Math. 217, No. 1, 46--55 (2008; Zbl 1147.65049)], concerning the strong convergence of a generalized proximal point algorithm which involves multiple parameters. Yao and Noor's result [loc. cit.] ensures the strong convergence of the algorithm to the nearest projection point onto the set of zeros of the operator. Our quantitative analysis, guided by \textit{F. Ferreira} and \textit{P. Oliva}'s [Ann. Pure Appl. Logic 135, No. 1--3, 73--112 (2005; Zbl 1095.03060)] bounded functional interpretation, provides a primitive recursive bound on the metastability for the convergence of the algorithm, in the sense of Terence Tao. Furthermore, we obtain quantitative information on the asymptotic regularity of the iteration. The results of this paper are made possible by an arithmetization of the lim sup.Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problemshttps://www.zbmath.org/1472.900872021-11-25T18:46:10.358925Z"Dvinskikh, Darina"https://www.zbmath.org/authors/?q=ai:dvinskikh.darina"Gasnikov, Alexander"https://www.zbmath.org/authors/?q=ai:gasnikov.alexander-vSummary: We introduce primal and dual stochastic gradient oracle methods for decentralized convex optimization problems. Both for primal and dual oracles, the proposed methods are optimal in terms of the number of communication steps. However, for all classes of the objective, the optimality in terms of the number of oracle calls per node takes place only up to a logarithmic factor and the notion of smoothness. By using mini-batching technique, we show that the proposed methods with stochastic oracle can be additionally parallelized at each node. The considered algorithms can be applied to many data science problems and inverse problems.Maximum entropy on the mean approach to solve generalized inverse problems with an application in computational thermodynamicshttps://www.zbmath.org/1472.900882021-11-25T18:46:10.358925Z"Gamboa, Fabrice"https://www.zbmath.org/authors/?q=ai:gamboa.fabrice"Guéneau, Christine"https://www.zbmath.org/authors/?q=ai:gueneau.christine"Klein, Thierry"https://www.zbmath.org/authors/?q=ai:klein.thierry-e"Lawrence, Eva"https://www.zbmath.org/authors/?q=ai:lawrence.evaSummary: In this paper, we study entropy maximisation problems in order to reconstruct functions or measures subject to very general integral constraints. Our work has a twofold purpose. We first make a global synthesis of entropy maximisation problems in the case of a single reconstruction (measure or function) from the convex analysis point of view, as well as in the framework of the embedding into the Maximum Entropy on the Mean (MEM) setting. We further propose an extension of the entropy methods for a multidimensional case.Proximal regularization for the saddle point gradient dynamicshttps://www.zbmath.org/1472.900892021-11-25T18:46:10.358925Z"Goldsztajn, Diego"https://www.zbmath.org/authors/?q=ai:goldsztajn.diego"Paganini, Fernando"https://www.zbmath.org/authors/?q=ai:paganini.fernandoEditorial remark: No review copy delivered.Convergence analysis of incremental and parallel line search subgradient methods in Hilbert spacehttps://www.zbmath.org/1472.900902021-11-25T18:46:10.358925Z"Hishinuma, Kazuhiro"https://www.zbmath.org/authors/?q=ai:hishinuma.kazuhiro"Iiduka, Hideaki"https://www.zbmath.org/authors/?q=ai:iiduka.hideakiSummary: There are many instances of optimization problems whose objective functional can be expressed as a sum of convex functionals, such as in learning with a support vector machine. Incremental and parallel subgradient methods are useful algorithms for solving them. In particular, modified algorithms for combining them with a line search overcome the disadvantage that choosing suitable step sizes for efficient convergence is diffucult. This paper performs convergence analyses of these modified algorithms in a real Hilbert space.The variational geometry, projection expression and decomposition associated with ellipsoidal coneshttps://www.zbmath.org/1472.900912021-11-25T18:46:10.358925Z"Lu, Yue"https://www.zbmath.org/authors/?q=ai:lu.yue"Chen, Jein-Shan"https://www.zbmath.org/authors/?q=ai:chen.jein-shanSummary: Non-symmetric cones have long been mysterious to optimization researchers because of no unified analysis technique to handle these cones. Nonetheless, by looking into symmetric cones and non-symmetric cones, it is still possible to find relations between these kinds of cones. This paper tries an attempt to this aspect and focuses on an important class of convex cones, the \textit{ellipsoidal} cone. There are two main reasons for it. The ellipsoidal cone not only includes the well known second-order cone, circular cone and elliptic cone as special cases, but also it can be converted to a second-order cone by a transformation and vice versa. With respect to the ellipsoidal cone, we characterize its dual cone, variational geometry, the projection mapping, and the decompositions. We believe these results may provide a fundamental approach on tackling with other unfamiliar non-symmetric cone optimization problems.Inexact descent methods with convex objective functions in Banach spaceshttps://www.zbmath.org/1472.900922021-11-25T18:46:10.358925Z"Reich, Simeon"https://www.zbmath.org/authors/?q=ai:reich.simeon"Zaslavski, Alexander J."https://www.zbmath.org/authors/?q=ai:zaslavski.alexander-jSummary: Given a Lipschitz and convex objective function on a Banach space, we revisit the class of regular vector fields introduced in our previous work on descent methods. We study the behavior of the values of the objective function for a certain inexact process generated by a regular vector field and show that the values of the objective function converge to its infimum.A discrete approximation of Blake and Zisserman energy in image denoising with optimal choice of regularization parametershttps://www.zbmath.org/1472.900932021-11-25T18:46:10.358925Z"Theljani, Anis"https://www.zbmath.org/authors/?q=ai:theljani.anis"Belhachmi, Zakaria"https://www.zbmath.org/authors/?q=ai:belhachmi.zakariaSummary: We introduce and study a multi-scale approximation of a nonlinear elliptic functional introduced by Blake and Zisserman (BZ) for solving image restoration problems. The functional is a fourth-order PDE variational model that aims to locate geometric features that are singularities of first kind and second kind in the image. The method consists in introducing a family of linear discrete energies approximating BZ functional in the sense of the \(\Gamma \)-convergence. These functionals are built from an adaptive finite element method that reflects how the corresponding high-order diffusion operators act on image restoration with preserving contours and corners. The initial nonlinear functional includes low-dimensional measures (Hausdorff) of the singular sets, whereas its linear discrete counterpart keep a simple structure of the underlying PDEs system easy to solve. The resulting approach allows us to capture that singularities of the image and its gradient better than the second-order methods. We perform the analysis of the proposed method in the framework of the \(\Gamma \)-convergence, and we derive a new algorithm to solve the minimization of the BZ functional. We consider and implement the algorithm and a variant based on the alternating direction method of multipliers (ADMM) to enhance the convergence. We give some numerical results in agreement with the theoretical analysis to show the performances of the method.Dual randomized coordinate descent method for solving a class of nonconvex problemshttps://www.zbmath.org/1472.900942021-11-25T18:46:10.358925Z"Beck, Amir"https://www.zbmath.org/authors/?q=ai:beck.amir"Teboulle, Marc"https://www.zbmath.org/authors/?q=ai:teboulle.marcA stochastic alternating direction method of multipliers for non-smooth and non-convex optimizationhttps://www.zbmath.org/1472.900952021-11-25T18:46:10.358925Z"Bian, Fengmiao"https://www.zbmath.org/authors/?q=ai:bian.fengmiao"Liang, Jingwei"https://www.zbmath.org/authors/?q=ai:liang.jingwei"Zhang, Xiaoqun"https://www.zbmath.org/authors/?q=ai:zhang.xiaoqunA system-optimization model for multiclass human migration with migration costs and regulations inspired by the Covid-19 pandemichttps://www.zbmath.org/1472.900962021-11-25T18:46:10.358925Z"Cappello, Giorgia"https://www.zbmath.org/authors/?q=ai:cappello.giorgia"Daniele, Patrizia"https://www.zbmath.org/authors/?q=ai:daniele.patrizia"Nagurney, Anna"https://www.zbmath.org/authors/?q=ai:nagurney.annaSummary: In the last several decades, the main causes of human migration have included: poverty, war and political strife, climate change, tsunamis, earthquakes, as well as economic and educational possibilities. In this paper, we present a system-optimized network model for multiple migration classes with migration costs and regulations inspired by the Covid-19 pandemic. We derive the variational inequality formulation associated with the system-optimization problem which consists of maximizing the total societal welfare. Lagrange analysis is also performed in order to obtain a precise evaluation of the multiclass human migration phenomenon. This work adds to the literature on system-optimization of human migration in the presence of regulations and with the explicit inclusion of migration costs.Extra-gradient linearized algorithms and Tseng's linearized algorithm for the split DC programminghttps://www.zbmath.org/1472.900972021-11-25T18:46:10.358925Z"Chuang, Chih-Sheng"https://www.zbmath.org/authors/?q=ai:chuang.chih-shengSummary: In this paper, we present extra-gradient linearized algorithm, Tseng's linearized algorithm, and several modified algorithms to study the split DC programming (the minimization problem for difference of convex functions), and establish convergence theorems for the proposed algorithms under suitable conditions. Final, we give numerical results for our main results.On some incremental algorithms for the minimum sum-of-squares clustering problem. I: Ordin and Bagirov's incremental algorithmhttps://www.zbmath.org/1472.900982021-11-25T18:46:10.358925Z"Cuong, Tran Hung"https://www.zbmath.org/authors/?q=ai:cuong.tran-hung"Yao, Jen-Chih"https://www.zbmath.org/authors/?q=ai:yao.jen-chih"Yen, Nguyen Dong"https://www.zbmath.org/authors/?q=ai:yen.nguyen-dongSummary: Solution methods for the minimum sum-of-squares clustering (MSSC) problem are analyzed and developed in this paper. Based on the DCA (difference-of-convex functions algorithms) in DC programming and recently established qualitative properties of the MSSC problem [the authors, Optimization 69, No. 9, 2131--2154 (2020; Zbl 1444.68155)], we suggest several improvements of the incremental algorithms of \textit{B. Ordin} and \textit{A. Bagirov} [J. Glob. Optim. 61, No. 2, 341--361 (2015; Zbl 1311.90111)] and of \textit{A. Bagirov} [``An incremental DC algorithm for the minimum sum-of-squares clustering'', Iranian J. Oper. Res. 5, 1--14 (2014)]. Properties of the new algorithms are obtained and preliminary numerical tests of those on real-world databases are shown. Finite convergence, convergence, and the rate of convergence of solution methods for the MSSC problem are presented for the first time in our paper. This Part I is devoted to the incremental heuristic clustering algorithm of Ordin and Bagirov and the modified version proposed herein.Erratum to: ``Increasing quasiconcave co-radiant functions with applications in mathematical economics''https://www.zbmath.org/1472.900992021-11-25T18:46:10.358925Z"Martínez-Legaz, Juan Enrique"https://www.zbmath.org/authors/?q=ai:martinez-legaz.juan-enriqueErratum to the author's paper with \textit{A. M. Rubinov} and \textit{S. Schaible} [ibid. 61, No. 2, 261--280 (2005; Zbl 1090.90142)].Optimality conditions for nonconvex constrained optimization problemshttps://www.zbmath.org/1472.901002021-11-25T18:46:10.358925Z"Mashkoorzadeh, F."https://www.zbmath.org/authors/?q=ai:mashkoorzadeh.feryal"Movahedian, N."https://www.zbmath.org/authors/?q=ai:movahedian.nooshin"Nobakhtian, S."https://www.zbmath.org/authors/?q=ai:nobakhtian.soghraThe authors consider nonconvex mathematical programming problems with a tangentially convex objective \(f:\mathbb{R}^n \rightarrow \mathbb{R}\cup \{\infty\}\) and tangentially convex and continuous inequality constraints \(g_i(x)\le 0\), \(i=1,2,\dots,m<\infty\), defining the feasible set \(S\). \(f\) is called tangentially convex at \(\bar x \in \mathrm{dom }f\) [\textit{C. Lemaréchal}, Optimization 17, 827--858 (1986; Zbl 0613.49017)] whenever the directional derivative \(f'(\bar x,v)\) of \(f\) exists and is finite for all directions \(v\in \mathbb{R}^n\) and the function \(v\mapsto f'(\bar x,v)\) is convex on \(\mathbb{R}^n\). The main role playes its tangential subdifferential \(\partial f(\bar x):=\partial f'(\bar x,0)\) already considered in [\textit{A. D. Ioffe} and \textit{V. M. Tikhomirov}, Theorie der Extremalprobleme. (Teorija ekstremal'nyh zadac.) (Russian). Nelineinyi analiz i ego prilozenija. Moskau: Verlag 'Nauka', Hauptredaktion für physikalisch-mathematische Literatur (1974; Zbl 0292.90042), Chap. 4.4; \textit{B. N. Pshenichnyj}, Sov. Math., Dokl. 10, 70--72 (1969; Zbl 0227.90062); translation from Dokl. Akad. Nauk SSSR 184, 285--287 (1969); Necessary conditions for an extremum. New York, NY: Marcel Dekker, Inc. (1971; Zbl 0212.23902)]. First the standard regularity conditions extended to tangential subdifferential notation are shown to satisfy similar relations to each other as known from the differential case. Non valid relations are verified by counter examples. If \(f\) is Lipschitzian near \(\bar x\), then necessary local optimality conditions are shown like KKT-rule under regularity and without regularity \(f^\prime(\bar x,v)\le 0\) on the tangent cone being locally sufficient in case of \(f^\prime(\bar x,v)> 0\) on the tangent cone. A KKT condition at \(\bar x\) is sufficient for global optimality under Slater's condition and pseudoconvexity of \(f\). All optimality conditions are illustrated by examples. A handicap for reading the paper are several misprints in definitions corrected in a just now published more general paper on DTC programming \url{https://doi.org/10.1007/s11750-021-00615-z}.Zero duality gap properties for DC composite optimization problemhttps://www.zbmath.org/1472.901012021-11-25T18:46:10.358925Z"Tian, Lliping"https://www.zbmath.org/authors/?q=ai:tian.lliping"Wang, Mengdan"https://www.zbmath.org/authors/?q=ai:wang.mengdan"Fang, Donghui"https://www.zbmath.org/authors/?q=ai:fang.donghuiSummary: In this paper, we present zero duality gap properties for DC composite optimization problem with conic constraints. By using the infimal convolution of conjugate functions, we give new constraint qualifications which completely characterize the zero and stable zero duality gap properties for DC composite conical programming problem in real locally convex Hausdorff topological vector spaces.Approximate 1-norm minimization and minimum-rank structured sparsity for various generalized inverses via local searchhttps://www.zbmath.org/1472.901022021-11-25T18:46:10.358925Z"Xu, Luze"https://www.zbmath.org/authors/?q=ai:xu.luze"Fampa, Marcia"https://www.zbmath.org/authors/?q=ai:fampa.marcia-helena-c"Lee, Jon"https://www.zbmath.org/authors/?q=ai:lee.jon"Ponte, Gabriel"https://www.zbmath.org/authors/?q=ai:ponte.gabrielAn extended proximal ADMM algorithm for three-block nonconvex optimization problemshttps://www.zbmath.org/1472.901032021-11-25T18:46:10.358925Z"Zhang, Chun"https://www.zbmath.org/authors/?q=ai:zhang.chun"Song, Yongzhong"https://www.zbmath.org/authors/?q=ai:song.yongzhong"Cai, Xingju"https://www.zbmath.org/authors/?q=ai:cai.xingju"Han, Deren"https://www.zbmath.org/authors/?q=ai:han.derenSummary: We propose a new proximal alternating direction method of multipliers (ADMM) for solving a class of three-block nonconvex optimization problems with linear constraints. The proposed method updates the third primal variable twice per iteration and introduces semidefinite proximal terms to the subproblems with the first two blocks. The method can be regarded as an extension of the method proposed in [\textit{D. Sun} et al., SIAM J. Optim. 25, No. 2, 882--915 (2015; Zbl 1328.90083)] which is specialized to the convex case with the third block of the objective function being quadratic. Based on the powerful Kurdyka-Łojasiewicz property, we prove that each bounded sequence generated by the proposed method converges to a critical point of the considered problem. Some numerical results are reported to indicate the effectiveness and superiority of the proposed method.Scalarizations and optimality of constrained set-valued optimization using improvement sets and image space analysishttps://www.zbmath.org/1472.901042021-11-25T18:46:10.358925Z"Zhou, Zhiang"https://www.zbmath.org/authors/?q=ai:zhou.zhiang"Chen, Wang"https://www.zbmath.org/authors/?q=ai:chen.wang"Yang, Xinmin"https://www.zbmath.org/authors/?q=ai:yang.xinminBy using improvement sets, some convexity and optimality concepts are generalized to set-valued optimization problems. Subsequently, some scalarization results are established in the sense of optimal solutions defined by the improvement set. Simultaneously, two kinds of separation functions are employed to derive some optimality conditions in the form of a separation between suitable sets in the image space, and saddle point conditions.Analysis of threat based algorithm using different performance measureshttps://www.zbmath.org/1472.901052021-11-25T18:46:10.358925Z"Ahmad, Iftikhar"https://www.zbmath.org/authors/?q=ai:ahmad.iftikhar"Pirron, Marcus"https://www.zbmath.org/authors/?q=ai:pirron.marcus"Schmidt, Günter"https://www.zbmath.org/authors/?q=ai:schmidt.gunterSummary: Since its introduction in 1985, competitive analysis is a widely used tool for the performance measurement of online algorithms. Despite its simplicity and popularity, competitive analysis has its own set of drawbacks which lead to the development of other performance measures. However, these measures were seldom applied to problems in other domains. Recently \textit{J. Boyar} et al. [Theor. Comput. Sci. 532, 2--13 (2014; Zbl 1359.68323)] studied the online search problem using various performance analysis measures for non-preemptive algorithms. We extend the work by considering preemptive \textit{threat-based} algorithms and evaluate it using competitive analysis, bijective analysis, average case and relative interval analysis. For competitive analysis, and average case analysis, our findings are in contrast with that of Boyar \textit{et al}., whereas for bijective and relative interval analysis our findings complement that of Boyar et al. [loc. cit.].Using multiflow formulations to solve the Steiner tree problem in graphshttps://www.zbmath.org/1472.901062021-11-25T18:46:10.358925Z"Bahiense, Laura"https://www.zbmath.org/authors/?q=ai:bahiense.laura"Besso, Arthur"https://www.zbmath.org/authors/?q=ai:besso.arthur"Tostas, Rogerio"https://www.zbmath.org/authors/?q=ai:tostas.rogerio"Maculan, Nelson"https://www.zbmath.org/authors/?q=ai:maculan.nelson-fSummary: We present three different mixed integer linear models with a polynomial number of variables and constraints for the Steiner tree problem in graphs. The linear relaxations of these models are compared to show that a good (strong) linear relaxation can be a good approximation for the problem. We present computational results for the STP OR-Library [\textit{J. E. Beasley}, Networks 14, 147--159 (1984; Zbl 0541.90034)] instances of type \(b, c, d\) and \(e\).Black-box combinatorial optimization using models with integer-valued minimahttps://www.zbmath.org/1472.901072021-11-25T18:46:10.358925Z"Bliek, Laurens"https://www.zbmath.org/authors/?q=ai:bliek.laurens"Verwer, Sicco"https://www.zbmath.org/authors/?q=ai:verwer.sicco"de Weerdt, Mathijs"https://www.zbmath.org/authors/?q=ai:de-weerdt.mathijs-mSummary: When a black-box optimization objective can only be evaluated with costly or noisy measurements, most standard optimization algorithms are unsuited to find the optimal solution. Specialized algorithms that deal with exactly this situation make use of surrogate models. These models are usually continuous and smooth, which is beneficial for continuous optimization problems, but not necessarily for combinatorial problems. However, by choosing the basis functions of the surrogate model in a certain way, we show that it can be guaranteed that the optimal solution of the surrogate model is integer. This approach outperforms random search, simulated annealing and a Bayesian optimization algorithm on the problem of finding robust routes for a noise-perturbed traveling salesman benchmark problem, with similar performance as another Bayesian optimization algorithm, and outperforms all compared algorithms on a convex binary optimization problem with a large number of variables.A reduction heuristic for the all-colors shortest path problemhttps://www.zbmath.org/1472.901082021-11-25T18:46:10.358925Z"Carrabs, Francesco"https://www.zbmath.org/authors/?q=ai:carrabs.francesco"Cerulli, Raffaele"https://www.zbmath.org/authors/?q=ai:cerulli.raffaele"Raiconi, Andrea"https://www.zbmath.org/authors/?q=ai:raiconi.andreaSummary: The All-Colors Shortest Path (ACSP) is a recently introduced NP-Hard optimization problem, in which a color is assigned to each vertex of an edge weighted graph, and the aim is to find the shortest path spanning all colors. The solution path can be not simple, that is it is possible to visit multiple times the same vertices if it is a convenient choice. The starting vertex can be constrained (ACSP) or not (ACSP-UE). We propose a reduction heuristic based on the transformation of any ACSP-UE instance into an Equality Generalized Traveling Salesman Problem one. Computational results show the algorithm to outperform the best previously known one.A branch-and-cut and MIP-based heuristics for the prize-collecting travelling salesman problemhttps://www.zbmath.org/1472.901092021-11-25T18:46:10.358925Z"Clímaco, Glaubos"https://www.zbmath.org/authors/?q=ai:climaco.glaubos"Simonetti, Luidi"https://www.zbmath.org/authors/?q=ai:simonetti.luidi-g"Rosseti, Isabel"https://www.zbmath.org/authors/?q=ai:rosseti.isabelSummary: The Prize Collecting Traveling Salesman Problem (PCTSP) represents a generalization of the well-known Traveling Salesman Problem. The PCTSP can be associated with a salesman that collects a prize in each visited city and pays a penalty for each unvisited city, with travel costs among the cities. The objective is to minimize the sum of the costs of the tour and penalties, while collecting a minimum amount of prize. This paper suggests MIP-based heuristics and a branch-and-cut algorithm to solve the PCTSP. Experiments were conducted with instances of the literature, and the results of our methods turned out to be quite satisfactory.An ILS-based heuristic applied to the car renter salesman problemhttps://www.zbmath.org/1472.901102021-11-25T18:46:10.358925Z"Dias, Sávio S."https://www.zbmath.org/authors/?q=ai:dias.savio-s"Simonetti, Luidi G."https://www.zbmath.org/authors/?q=ai:simonetti.luidi-g"Ochi, Luiz Satoru"https://www.zbmath.org/authors/?q=ai:ochi.luiz-satoruSummary: The present paper tackles the Car Renter Salesman Problem (CaRS), which is a Traveling Salesman Problem variant. In CaRS, the goal is to travel through a set of cities using rented vehicles at minimum cost. The main aim of the current problem is to establish an optimal route using rented vehicles of different types to each trip. Since CaRS is \textit{N P}-Hard, we herein present a heuristic approach to tackle it. The approach is based on a Multi-Start Iterated Local Search metaheuristic, where the local search step is based on the Random Variable Neighborhood Descent methodology. An Integer Linear Programming Formulation based on a Quadratic Formulation from literature is also proposed in the current study. Computational results for the proposed heuristic method in euclidean instances outperform current state-of-the-art results. The proposed formulation also has stronger bounds and relaxation when compared to others from literature.An optimal solution for the budgets assignment problemhttps://www.zbmath.org/1472.901112021-11-25T18:46:10.358925Z"Jemmali, Mahdi"https://www.zbmath.org/authors/?q=ai:jemmali.mahdiSummary: Municipalities are service organizations that have a major role in strategic planning and community development that consider the future changes and society developments, by implementing set of projects with pre-allocated budgets. Projects have standards, budgets and constraints that differ from one community to another and from one city to another. Fair distributing of different projects to municipalities, while ensuring the provision of various capabilities to reach developmental role is NP-Hard problem. Assuming that all municipalities have the same strategic characteristics. The problem is as follows: given a set of projects with different budgets, how to distribute all projects to all municipalities with a minimum budget gap between municipalities. To derive equity distribution between municipalities, this paper developed lower bounds and eleven heuristics to be utilized in the branch-and-bound algorithms. The performance of the developed heuristics, lower bounds and the exact solutions are presented in the experimental study.Open capacitated ARC routing problem by hybridized ant colony algorithmhttps://www.zbmath.org/1472.901122021-11-25T18:46:10.358925Z"Kanso, Bilal"https://www.zbmath.org/authors/?q=ai:kanso.bilal"Kansou, Ali"https://www.zbmath.org/authors/?q=ai:kansou.ali"Yassine, Adnan"https://www.zbmath.org/authors/?q=ai:yassine.adnanSummary: The Open Capacitated Arc Routing Problem OCARP is a well-known NP-hard real-world combinatorial optimization problem. It consists of determining optimal routes for vehicles in a given service area at a minimal cost distance. The main real application for OCARP is the Meter Reader Routing Problem (MRRP). In MRRP problem, each worker in the electric (or gas) company must visit and read the electric (or gas) meters to a set of customers by starting his route from the first customer on his visit list and finishing with the last one. The worker leaves where he wants once all the associated customers have been visited. In this paper, a metaheuristic called an Hybridized Ant Colony Algorithm (HACA) is developed and hybridized with a local search algorithm that involves the 2-opt, Swap, Relocate and Cross-exchange moves to solve OCARP problem. Computational results conducted on five different sets of OCARP-instances showed that our proposed algorithm HACA has reached good and competitive results on benchmark instances for the problem.Fractional Gallai-Edmonds decomposition and maximal graphs on fractional matching numberhttps://www.zbmath.org/1472.901132021-11-25T18:46:10.358925Z"Liu, Yan"https://www.zbmath.org/authors/?q=ai:liu.yan.1"Lei, Mengxia"https://www.zbmath.org/authors/?q=ai:lei.mengxia"Su, Xueli"https://www.zbmath.org/authors/?q=ai:su.xueliThe paper analyses the Gallai-Edmonds decomposition of a graph with fractional matching and characterizes the Turán number, saturation number and extremal graphs with respect to fractional matching.
A fractional matching extends the notion of a classical matching by assigning to each edge \(e\) of a graph \(G\) a real number \(f(e)\) from the interval \([0,1]\) such that for each vertex \(v\), \(\sum_{e\in\Gamma(v)} f (e) \le 1\). The fractional matching number \(\mu_f(G)\) of \(G\) is the supremum of \(\sum_{e\in E(G)} f(e)\) over all fractional matchings \(f\) of \(G\). A Gallai-Edmonds decomposition is a partition \((C_f(G), A_f(G), D_f(G))\), where \(D_f(G)\) is the set of vertices which are unsaturated by some maximum matching of \(G\), \(A_f(G)\) are vertices adjacent to them and \(C_f(G)\) are the remaining vertices. This partition can be naturally generalized to the fractional Gallai-Edmonds decomposition if we consider a maximum fractional matching instead. A graph \(G\) is maximal on \(\mu_f(G)\) if any addition of an edge increases the fractional matching number \(\mu_f(G)\). The Turán number is the maximum of edge numbers of maximal graphs and the saturation number is the minimum of edge numbers of maximal graphs. The authors show that the fractional Gallai-Edmonds decomposition can be done in a polynomial time. As a result, they obtain a characterization of maximal graphs, the Turán number, the saturation number and extremal graphs as well.On number of optimal solutions in some scheduling problemshttps://www.zbmath.org/1472.901142021-11-25T18:46:10.358925Z"Mamporia, Badri"https://www.zbmath.org/authors/?q=ai:mamporia.badri"Sanikidze, Zaza"https://www.zbmath.org/authors/?q=ai:sanikidze.zaza"Vakhania, Nodari"https://www.zbmath.org/authors/?q=ai:vakhania.nodari-nSummary: Some special cases of single-machine problems is considered. In these cases there are many optimal solutions. It is given the formulas of quantity of optimal solutions and calculated the probability of the event that an arbitrary schedule is optimal; the sufficient conditions to increase the value of this probability is given and the corresponding optimal full completion time is calculated.The problem of the compartmentalized knapsack: a proposal of three new heuristicshttps://www.zbmath.org/1472.901152021-11-25T18:46:10.358925Z"Pimenta-Zanon, Matheus Henrique"https://www.zbmath.org/authors/?q=ai:pimenta-zanon.matheus-henrique"Sakuray, Fabio"https://www.zbmath.org/authors/?q=ai:sakuray.fabio"Hoto, Robinson Samuel Vieira"https://www.zbmath.org/authors/?q=ai:hoto.robinson-samuel-vieiraSummary: The problem of the compartmentalized knapsack is classified NP-Hard and has several models, both for linear and nonlinear cases. The development of new heuristics for a resolution in a runtime useful for applications becomes necessary. In this work, three new heuristics are proposed, using the particularity of the linear model proposed by Inarejos (2017), which are considered only \(p_k\), compartments available for each class, being \(p_kX\), \(p_k\)GREEDY and \(p_k\)MTComp, the latter is based on the algorithm of Martello and Totti (1991). The heuristic \(p_k\)MTComp presents solutions close to optimum value, being a promising method in solving the problem of the compartmentalized knapsack, when compared with other heuristics recognized in the literature.A new penalty/stochastic approach to an application of the covering problem: the gamma knife treatmenthttps://www.zbmath.org/1472.901162021-11-25T18:46:10.358925Z"Venceslau, Marilis Bahr Karam"https://www.zbmath.org/authors/?q=ai:venceslau.marilis-bahr-karam"Venceslau, Helder Manoel"https://www.zbmath.org/authors/?q=ai:venceslau.helder-manoel"Pinto, Renan Vicente"https://www.zbmath.org/authors/?q=ai:pinto.renan-vicente"Dias, Gustavo"https://www.zbmath.org/authors/?q=ai:dias.gustavo-fruet"Maculan, Nelson"https://www.zbmath.org/authors/?q=ai:maculan.nelson-fSummary: The covering problem of a three dimensional body using different radii spheres is considered. The motivating application -- the treatment planning of Gamma Knife radiosurgery -- is briefly discussed. We approach the problem only by the geometric covering point of view, that is, given a set of spheres and a body, the objective is to cover the body using the smallest possible number of spheres, regardless of the dosage issue. In order to solve this mathematical programming problem, we consider an approach based on the application of penalty and stochastic local search techniques. Finally, some illustrative results and comparisons are presented.A new model for logistics and transportation of fashion goods in the presence of stochastic market demands considering restricted retailers capacityhttps://www.zbmath.org/1472.901172021-11-25T18:46:10.358925Z"Delgoshaei, Aidin"https://www.zbmath.org/authors/?q=ai:delgoshaei.aidin"Norozi, Hengameh"https://www.zbmath.org/authors/?q=ai:norozi.hengameh"Mirzazadeh, Abolfazl"https://www.zbmath.org/authors/?q=ai:mirzazadeh.abolfazl"Farhadi, Maryam"https://www.zbmath.org/authors/?q=ai:farhadi.maryam"Pakdel, Golnaz Hooshmand"https://www.zbmath.org/authors/?q=ai:pakdel.golnaz-hooshmand"Aram, Aisa Khoshniat"https://www.zbmath.org/authors/?q=ai:aram.aisa-khoshniatSummary: In today's world, using fashion goods is a vital of human. In this research, we focused on developing a scheduling method for distributing and selling fashion goods in a multi-market/multi-retailer supply chain while the product demands in markets are stochastic. For this purpose, a new multi-objective mathematical programming model is developed where maximizing the profit of selling fashion goods and minimizing delivering time and customer's dissatisfaction are considered as objective functions. In continue due to the complexity of the problem, a number of metaheuristics are compared and a hybrid of Non-dominated Sorting Genetic Algorithm II (NSGAII) and simulated annealing is selected for solving the case studies. Then, in order to find the best values for input parameters of the algorithm, a Taguchi method is applied. In continue, a number of case studies are selected from literature review and solved by the algorithm. The outcomes are analyzed and it is found that using multi-objective models can find more realistic solutions. Then, the model is applied for a case study with real data from industry and outcomes showed that the proposed algorithm can be successfully applied in practice.Correction to: ``A general branch-and-bound framework for continuous global multiobjective optimization''https://www.zbmath.org/1472.901182021-11-25T18:46:10.358925Z"Eichfelder, Gabriele"https://www.zbmath.org/authors/?q=ai:eichfelder.gabriele"Kirst, Peter"https://www.zbmath.org/authors/?q=ai:kirst.peter"Meng, Laura"https://www.zbmath.org/authors/?q=ai:meng.laura"Stein, Oliver"https://www.zbmath.org/authors/?q=ai:stein.oliver.1An error in the last sentence of the proof for Lemma 3.2 in the authors' paper [ibid. 80, No. 1, 195--227 (2021; Zbl 1470.90114)] is corrected.Recent advances and future trends in exploring Pareto-optimal topologies and additive manufacturing oriented topology optimizationhttps://www.zbmath.org/1472.901192021-11-25T18:46:10.358925Z"Fu, Yun-Fei"https://www.zbmath.org/authors/?q=ai:fu.yun-feiSummary: Topology optimization (TO) is a powerful technique capable of finding the optimal layout of material and connectivity within a design domain. However, designs obtained by TO are usually geometrically complex. Such complex designs cannot be fabricated easily by conventional manufacturing methods. Therefore, additive manufacturing (AM), a free-form manufacturing technique, is extensively coupled with TO. Like most techniques, AM has its own limitations. Consequently, a range of additive manufacturing oriented topology optimization (AM oriented TO) algorithms were proposed to generate the topologies suitable for AM. Due to existing trade-off relationships in AM oriented TO, investigating multi-objective AM oriented TO seems essential to obtain more practical solutions. This paper provides a review on the recent developments of MOTO, AM oriented TO, and trade-off relationships that exist in AM oriented TO. This review paper also discusses the challenges and future trends in these topics. It is hoped that this review paper could inspire both academics and engineers to make a contribution towards bridging together MOTO and AM.A sustainable cross-efficiency DEA model for international MSW-to-biofuel supply chain designhttps://www.zbmath.org/1472.901202021-11-25T18:46:10.358925Z"Ghadami, Mahsa"https://www.zbmath.org/authors/?q=ai:ghadami.mahsa"Sahebi, Hadi"https://www.zbmath.org/authors/?q=ai:sahebi.hadi"Pishvaee, Mirsaman"https://www.zbmath.org/authors/?q=ai:pishvaee.mirsaman"Gilani, Hani"https://www.zbmath.org/authors/?q=ai:gilani.haniSummary: Fossil fuels, as the primary source of the energy supply in today's global society, are being depleted much faster than expected and are raising serious environmental and social concerns for contemporary societies. To deal with issues, a global movement towards the generation of sustainable renewable energy is underway. One of the most promising sources of renewable energy alternatives is the use of municipal solid waste, as a biomass source since it does not endanger food security and considerably the biomass made by municipal solid waste will enable the appropriate management of the waste and help cities to be sustainable. The supply chain of converting the municipal solid waste to bioenergy is a challenging issue that have attracted the attention of academic and industrial research. In this direction, a three-echelon mathematical model is developed to design MSW-to-biofuel supply chain network. This supply network is a global network; hence, the international supply chain-related issues and the disruption in the raw material supply have also been studied. Identifying appropriate potential locations to site facilities is a challenge faced in the municipal solid waste-to-biofuel supply chain models. To achieve goal, in this research, the use has been made of a proposed sustainable cross-efficiency DEA model which is an effective ranking method, especially for finding potential points. To deal with sustainability, the social and environmental indicators have also been presented in the form of some criteria in this DEA method. In addition, effort has been made to improve the ecological indicators of the supply chain design in line with the sustainable development as an objective function. Finally, in order to validate the proposed model, a case study with real data is presented.An iterative vertex enumeration method for objective space based vector optimization algorithmshttps://www.zbmath.org/1472.901212021-11-25T18:46:10.358925Z"Kaya, İrfan Caner"https://www.zbmath.org/authors/?q=ai:kaya.irfan-caner"Ulus, Firdevs"https://www.zbmath.org/authors/?q=ai:ulus.firdevsSummary: An application area of vertex enumeration problem (VEP) is the usage within objective space based linear/convex vector optimization algorithms whose aim is to generate (an approximation of) the Pareto frontier. In such algorithms, VEP, which is defined in the objective space, is solved in each iteration and it has a special structure. Namely, the recession cone of the polyhedron to be generated is the ordering cone. We consider and give a detailed description of a vertex enumeration procedure, which iterates by calling a modified ``double description (DD) method'' that works for such unbounded polyhedrons. We employ this procedure as a function of an existing objective space based vector optimization algorithm (Algorithm 1); and test the performance of it for randomly generated linear multiobjective optimization problems. We compare the efficiency of this procedure with another existing DD method as well as with the current vertex enumeration subroutine of Algorithm 1. We observe that the modified procedure excels the others especially as the dimension of the vertex enumeration problem (the number of objectives of the corresponding multiobjective problem) increases.A two-step method for solving vector optimization problems on permutation configurationhttps://www.zbmath.org/1472.901222021-11-25T18:46:10.358925Z"Koliechkina, L. N."https://www.zbmath.org/authors/?q=ai:koliechkina.l-n"Dvirna, O. A."https://www.zbmath.org/authors/?q=ai:dvirna.o-a"Khovben, S. V."https://www.zbmath.org/authors/?q=ai:khovben.s-vSummary: A class of problems of vector Euclidean combinatorial optimization is considered as problems of discrete optimization on the set of combinatorial configurations mapped into the Euclidean space. The properties of the graphs of combinatorial configurations used to describe the new method are given. A two-stage method for solving problems of vector Euclidean combinatorial optimization on combinatorial configurations of permutations is proposed. The results of the numerical experiment and their analysis are presented.Evaluating the potential trade-off between students' satisfaction and school performance using evolutionary multiobjective optimizationhttps://www.zbmath.org/1472.901232021-11-25T18:46:10.358925Z"Marcenaro-Gutiérrez, Oscar D."https://www.zbmath.org/authors/?q=ai:marcenaro-gutierrez.oscar-d"González-Gallardo, Sandra"https://www.zbmath.org/authors/?q=ai:gonzalez-gallardo.sandra"Luque, Mariano"https://www.zbmath.org/authors/?q=ai:luque.marianoSummary: In this article, we carry out a combined econometric and multiobjective analysis using data from a representative sample of Andalusian schools. In particular, four econometric models are estimated in which the students' academic performance (scores in math and reading, and percentage of students reaching a certain threshold in both subjects, respectively) are regressed against the satisfaction of students with different aspects of the teaching-learning process. From these estimates, four objective functions are defined which have been simultaneously maximized, subject to a set of constraints obtained by analyzing dependencies between explanatory variables. This multiobjective programming model is intended to optimize the students' academic performance as a function of the students' satisfaction. To solve this problem we use a decomposition-based evolutionary multiobjective algorithm called Global WASF-GA with different scalarizing functions which allows generating an approximation of the Pareto optimal front. In general, the results show the importance of promoting respect and closer interaction between students and teachers, as a way to increase the average performance of the students and the proportion of high performance students.Multi-objective optimization based optimal sizing \& placement of multiple distributed generators for distribution network performance improvementhttps://www.zbmath.org/1472.901242021-11-25T18:46:10.358925Z"Markana, Anilkumar"https://www.zbmath.org/authors/?q=ai:markana.anilkumar"Trivedi, Gargi"https://www.zbmath.org/authors/?q=ai:trivedi.gargi"Bhatt, Praghnesh"https://www.zbmath.org/authors/?q=ai:bhatt.praghneshSummary: Integration of Distributed Generations (DGs) into radial distribution network (RDN) is an emerging need to explore the benefits of renewable energy sources (RES). Increasing penetration of RES based DGs in RDN without proper planning leads to several operational problems such as excessive energy losses, poor voltage quality and load balancing. Hence, in this work, multi-objective optimization (MOO) problem is formulated by carefully chosen three conflicting objectives such as power loss minimization, enhancement of load balancing index (LBI) and aggregate voltage deviation index (AVDI). Teaching-Learning-Based-Optimization (TLBO) is used to optimize MOO problem considering placement of DGs at multiple locations in RDN satisfying the constraints on bus voltage magnitude, branch flows and DG size. Comprehensive simulation studies have been carried out to obtain optimal performance for 69-nodes RDN with the increasing penetration of DGs at multiple locations. It is shown that determination of optimal sizing of DGs at multiple locations in RDN with MOO results in lesser power losses, improved voltage profiles and better load balancing as compared to placement of single DG in RDN. Performance measures such as spacing and spread indicators are used for characterizing Pareto solutions for MOO problem. Such set of non-dominated solutions obtained from Pareto front during multi-objective TLBO gives proper guidelines to the utility operator about sizing and placement of DGs based on the assigned priorities to the objectives.Operation simulation of urban rail train model based on multi-objective improved genetic algorithmhttps://www.zbmath.org/1472.901252021-11-25T18:46:10.358925Z"Wang, Xiaokan"https://www.zbmath.org/authors/?q=ai:wang.xiaokan"Dong, Hairong"https://www.zbmath.org/authors/?q=ai:dong.hairong"Wang, Qiong"https://www.zbmath.org/authors/?q=ai:wang.qiongSummary: In order to the simulation model of train operation, the condition conversion of train operation process is the gene encoding, and stop error, time error and energy consumption target requires of the train operation simulation are used to establish the fitness function, so the variable length chromosome based on multi-objective genetic algorithm is adopted to calculate the train operation process and improve the adaptability of the solution. The example calculation shows that the solution provided by the algorithm satisfies the prescribed running time and stop error range, and the energy consumption can be saved by 10\%--30\%.Optimality conditions of a nonsmooth composite minimization problemhttps://www.zbmath.org/1472.901262021-11-25T18:46:10.358925Z"Atarzadeh, Sahar"https://www.zbmath.org/authors/?q=ai:atarzadeh.sahar"Fakhar, Majid"https://www.zbmath.org/authors/?q=ai:fakhar.majid"Zafarani, Jafar"https://www.zbmath.org/authors/?q=ai:zafarani.jafarSummary: Paper considered a nonsmooth composite minimization problem with inequality constraints ((NCMP) in short). For this problem and in the setting of reflexive Banach spaces, the Fritz John (FJ) optimality condition for this problem at points which are not necessarily local minima is obtained. By using this result, the FJ optimality condition for a nonsmooth optimization problem with inequality constraints is established. Moreover, by applying the Clarke, the Michel-Penot and modified upper Dini derivatives, some equivalent conditions for the Karush-Kuhn-Tucker (KKT) optimality condition of (NCMP) without using the FJ optimality conditions are deduced.A subspace version of the Wang-Yuan augmented Lagrangian-trust region method for equality constrained optimizationhttps://www.zbmath.org/1472.901272021-11-25T18:46:10.358925Z"Costa, Carina Moreira"https://www.zbmath.org/authors/?q=ai:costa.carina-moreira"Grapiglia, Geovani Nunes"https://www.zbmath.org/authors/?q=ai:grapiglia.geovani-nunesSummary: Subspace properties are presented for the trust-region subproblem that appears in the Augmented Lagrangian-Trust-Region method recently proposed by \textit{X. Wang} and \textit{Y. Yuan} [Optim. Methods Softw. 30, No. 3, 559--582 (2015; Zbl 1325.90091)]. Specifically, when the approximate Lagrangian Hessians are updated by suitable quasi-Newton formulas, we show that any solution of the corresponding \(k\)th subproblem belongs to the subspace spanned by all gradient vectors of the objective and of the constraints computed up to iteration \(k\). From this result, a subspace version of the referred method is proposed for large-scale equality constrained optimization problems. The subspace method is suitable to problems in which the number of constraints is much lower than the number of variables.A neurodynamic approach to nonlinear optimization problems with affine equality and convex inequality constraintshttps://www.zbmath.org/1472.901282021-11-25T18:46:10.358925Z"Liu, Na"https://www.zbmath.org/authors/?q=ai:liu.na"Qin, Sitian"https://www.zbmath.org/authors/?q=ai:qin.sitianThe paper deals with the weakest possible conditions that optimization problems can be treated by using a recurrent neural network. Convex, generalized convex as well as nonlinear nonconvex problems are considered. The Introduction gives a good overview of the existing results in the literature, followed by four remarks showing that the network used in this paper is really new. Chapter 2 recalls needed definitions. Chapter 3 gives the optimization problem P (finite-dimensional space, convex inequalities, linear equalities with full row rank, the objective function is not necessarily convex or smooth), where some conditions must be fulfilled: Slater conditions, boundedness of the feasible domain, regularity and Lipschitz property of the objective function. Furthermore, the recurrent neural network to solve P is presented being a nonautonomous differential inclusion. Two figures support the mathematical presentation. Chapter 4 gives the theoretical analysis starting with the definition of a critical point of P and the state solution of the network together with its convergence behavior as for instance that the state of neural network enters the feasible region in finite time and remains thereafter, about the distance to the set of critical points and about relations to Kuhn-Tucker points of P and finally, if the objective function is pseudoconvex, then the state of the network is globally convergent to an optimal solution of P. Chapter 5 starts with the definition of a slow solution of a (common) differential inclusion and it is shown, that a solution of the network (with special initial point) is just its slow solution and is unique, if the objective function is convex Five test examples with remarks and figures supplement the paper.OR practice-data analytics for optimal detection of metastatic prostate cancerhttps://www.zbmath.org/1472.901292021-11-25T18:46:10.358925Z"Merdan, Selin"https://www.zbmath.org/authors/?q=ai:merdan.selin"Barnett, Christine L."https://www.zbmath.org/authors/?q=ai:barnett.christine-l"Denton, Brian T."https://www.zbmath.org/authors/?q=ai:denton.brian-t"Montie, James E."https://www.zbmath.org/authors/?q=ai:montie.james-e"Miller, David C."https://www.zbmath.org/authors/?q=ai:miller.david-cSummary: We used data-analytics approaches to develop, calibrate, and validate predictive models, to help urologists in a large statewide collaborative make prostate cancer staging decisions on the basis of individual patient risk factors. The models were validated using statistical methods based on bootstrapping and evaluation on out-of-sample data. These models were used to design guidelines that optimally weigh the benefits and harms of radiological imaging for the detection of metastatic prostate cancer. The Michigan Urological Surgery Improvement Collaborative, a statewide medical collaborative, implemented these guidelines, which were predicted to reduce unnecessary imaging by more than 40\% and limit the percentage of patients with missed metastatic disease to be less than 1\%. The effects of the guidelines were measured after implementation to confirm their impact on reducing unnecessary imaging across the state of Michigan.An efficient three-term conjugate gradient-type algorithm for monotone nonlinear equationshttps://www.zbmath.org/1472.901302021-11-25T18:46:10.358925Z"Sabi'u, Jamilu"https://www.zbmath.org/authors/?q=ai:sabiu.jamilu"Shah, Abdullah"https://www.zbmath.org/authors/?q=ai:shah.abdullahSummary: In this article, we proposed two Conjugate Gradient (CG) parameters using the modified Dai-Liao condition and the descent three-term CG search direction. Both parameters are incorporated with the projection technique for solving large-scale monotone nonlinear equations. Using the Lipschitz and monotone assumptions, the global convergence of methods has been proved. Finally, numerical results are provided to illustrate the robustness of the proposed methods.Sparse balanced layout of spherical voids in three-dimensional domainshttps://www.zbmath.org/1472.901312021-11-25T18:46:10.358925Z"Stoyan, Y. G."https://www.zbmath.org/authors/?q=ai:stoyan.yurii-grygorovych"Romanova, T. E."https://www.zbmath.org/authors/?q=ai:romanova.tatiana-e"Pankratov, O. V."https://www.zbmath.org/authors/?q=ai:pankratov.o-v"Stetsyuk, P. I."https://www.zbmath.org/authors/?q=ai:stetsyuk.petro-i"Stoian, Y. E."https://www.zbmath.org/authors/?q=ai:stoian.y-eSummary: The authors consider the optimization problem of layout of spherical voids in three-dimensional domains bounded by cylindrical and spherical surfaces and planes. The problem is reduced to arranging spherical objects in a composite container, with regard for the constraints on their ``sparseness'' and balance conditions (location of the gravity center of the system). A mathematical model in the form of a nonlinear programming problem is constructed. A method of fast search for feasible solutions based on the balanced homothetic transformations of 3D objects and methods of finding locally optimal solutions using the decomposition algorithm and r-algorithm are proposed. The results of numerical experiments are provided.Erratum to: ``A regularized Newton method without line search for unconstrained optimization''https://www.zbmath.org/1472.901322021-11-25T18:46:10.358925Z"Ueda, Kenji"https://www.zbmath.org/authors/?q=ai:ueda.kenji"Yamashita, Nobuo"https://www.zbmath.org/authors/?q=ai:yamashita.nobuoFrom the text: The original version of this article [the authors, ibid. 59, No. 1--2, 321--351 (2014; Zbl 1302.90218)] unfortunately contained an error in Lemma 1.
However, the main theorems of the paper are still true. The corrections of Lemma 1 and the corresponding statements are given .New subspace minimization conjugate gradient methods based on regularization model for unconstrained optimizationhttps://www.zbmath.org/1472.901332021-11-25T18:46:10.358925Z"Zhao, Ting"https://www.zbmath.org/authors/?q=ai:zhao.ting"Liu, Hongwei"https://www.zbmath.org/authors/?q=ai:liu.hongwei|liu.hongwei.1"Liu, Zexian"https://www.zbmath.org/authors/?q=ai:liu.zexianSummary: In this paper, two new subspace minimization conjugate gradient methods based on \(p\)-regularization models are proposed, where a special scaled norm in \(p\)-regularization model is analyzed. Different choices of special scaled norm lead to different solutions to the \(p\)-regularized subproblem. Based on the analyses of the solutions in a two-dimensional subspace, we derive new directions satisfying the sufficient descent condition. With a modified nonmonotone line search, we establish the global convergence of the proposed methods under mild assumptions. \(R\)-linear convergence of the proposed methods is also analyzed. Numerical results show that, for the CUTEr library, the proposed methods are superior to four conjugate gradient methods, which were proposed by \textit{W. W. Hager} and \textit{H. Zhang} [SIAM J. Optim. 16, No. 1, 170--192 (2005; Zbl 1093.90085)], \textit{Y.-H. Dai} and \textit{C.-X. Kou} [SIAM J. Optim. 23, No. 1, 296--320 (2013; Zbl 1266.49065)], \textit{H. Liu} and \textit{Z. Liu} [J. Optim. Theory Appl. 180, No. 3, 879--906 (2019; Zbl 1409.49031)] and \textit{Y. Li} et al. [Comput. Appl. Math. 38, No. 1, Paper No. 16, 28 p. (2019; Zbl 1438.90329)], respectively.Avoiding critical multipliers and slow convergence of primal-dual methods for fully stable minimizershttps://www.zbmath.org/1472.901342021-11-25T18:46:10.358925Z"Mordukhovich, Boris S."https://www.zbmath.org/authors/?q=ai:mordukhovich.boris-sSummary: This paper discusses the current stage of the author's conjecture on relationships between criticality of Lagrange multipliers in various classes of constrained optimization problems and full stability of local minimizers. It has been realized that the existence of critical multipliers associated with a given local minimizer leads to slow convergence of major primal-dual algorithms to calculate such minimizers. The paper demonstrates that for large classes of constrained optimization problems critical multipliers do not appear if the local minimizer in question is fully stable. The developed approach is mainly based on advanced tools of second-order variational analysis and generalized differentiation.SDO and LDO relaxation approaches to complex fractional quadratic optimizationhttps://www.zbmath.org/1472.901352021-11-25T18:46:10.358925Z"Ashrafi, Ali"https://www.zbmath.org/authors/?q=ai:ashrafi.ali-rreza|ashrafi.ali-reza"Zare, Arezu"https://www.zbmath.org/authors/?q=ai:zare.arezuSummary: This paper examines a complex fractional quadratic optimization problem subject to two quadratic constraints. The original problem is transformed into a parametric quadratic programming problem by the well-known classical Dinkelbach method. Then a semidefinite and Lagrangian dual optimization approaches are presented to solve the nonconvex parametric problem at each iteration of the bisection and generalized Newton algorithms. Finally, the numerical results demonstrate the effectiveness of the proposed approaches.Adaptive projection methods for linear fractional programminghttps://www.zbmath.org/1472.901362021-11-25T18:46:10.358925Z"Bennani, Ahlem"https://www.zbmath.org/authors/?q=ai:bennani.ahlem"Benterki, Djamel"https://www.zbmath.org/authors/?q=ai:benterki.djamel"Grar, Hassina"https://www.zbmath.org/authors/?q=ai:grar.hassinaSummary: In this paper, we are interested in solving a linear fractional program by two different approaches. The first one is based on interior point methods which makes it possible to solve an equivalent linear program to the linear fractional program. The second one allows us to solve a variational inequalities problem equivalent to the linear fractional program by an efficient projection method. Numerical tests were carried out by the two approaches and a comparative study was carried out. The numerical tests show clearly that interior point methods are more efficient than of projection one.On duality theorems for semidefinite linear fractional optimization problemshttps://www.zbmath.org/1472.901372021-11-25T18:46:10.358925Z"Kim, Moon Hee"https://www.zbmath.org/authors/?q=ai:kim.moon-hee"Kim, Gwi Soo"https://www.zbmath.org/authors/?q=ai:kim.gwi-soo"Lee, Gue Myung"https://www.zbmath.org/authors/?q=ai:lee.gue-myungSummary: Recently, semidefinite optimization problems have been intensively studied since many optimization problem can be changed into the problems and the problems are very tractable. In this paper, we consider a semidefinite linear fractional optimization problem (SLF), and formulate a semidefinite linear optimization problem (SLD) as the dual problem of (SLF). We directly prove the weak duality theorem, the strong duality theorem and the converse duality theorem which hold between (SLF) and (SLD).An improved evaporation rate-water cycle algorithm based genetic algorithm for solving generalized ratio problemshttps://www.zbmath.org/1472.901382021-11-25T18:46:10.358925Z"Veeramani, C."https://www.zbmath.org/authors/?q=ai:veeramani.chinnadurai"Sharanya, S."https://www.zbmath.org/authors/?q=ai:sharanya.sSummary: This paper presents an efficient metaheuristic approach for optimizing the generalized ratio problems such as the sum and multiplicative of linear or nonlinear ratio objective function with affine constraints. This paper focuses on the significance of hybrid techniques, which are implemented by using GA and ER-WCA to increase efficiency and robustness for solving linear and nonlinear generalized ratio problems. Initially, GA starts with an initial random population and it is processed by genetic operators. ER-WCA will observe and preserve the GAs fittest chromosome in each cycle and every generation. This Genetic ER-WCA algorithm is provided with better optimal solutions while solving constrained ratio optimization problems. Also, the effectiveness of the proposed genetic ER-WCA algorithm is analyzed while solving the large scale ratio problems. The results and performance of the proposed algorithm ensures a strong optimization and improves the exploitative process when compared to the other existing metaheuristic techniques. Numerical problems and applications are used to test the performance of the convergence and the accuracy of the approached method. The behavior of this Genetic ER-WCA algorithm is compared with those of evolutionary algorithms namely Neural Network Algorithm, Grey Wolf Optimization, Evaporation Rate -- Water Cycle Algorithm, Water Cycle Algorithm, Firefly algorithm, Cuckoo search algorithm. The evaluated results show that the proposed algorithm increases the convergence and accuracy more than other existing algorithms.A splitting subgradient algorithm for solving equilibrium problems involving the sum of two bifunctions and application to Cournot-Nash modelhttps://www.zbmath.org/1472.901392021-11-25T18:46:10.358925Z"Duc, Phung Minh"https://www.zbmath.org/authors/?q=ai:duc.phung-minh"Le, Xuan Thanh"https://www.zbmath.org/authors/?q=ai:le.xuan-thanhSummary: In this paper we propose a splitting subgradient algorithm for solving equilibrium problems involving the sum of two bifunctions. At each iteration of the algorithm, two strongly convex subprograms are required to solve separately, one for each component bifunction. In contrast to the splitting algorithms previously proposed in [\textit{K. A. Pham} and \textit{N. H. Trinh}, Numer. Algorithms 76, No. 1, 67--91 (2017; Zbl 06788827)] and [\textit{T. N. Hai} and \textit{N. T. Vinh}, Rev. R. Acad. Cienc. Exactas Fís. Nat., Ser. A Mat., RACSAM 111, No. 4, 1051--1069 (2017; Zbl 1422.65092)], our algorithm is convergent for paramonotone and strongly pseudomonotone bifunctions without any Lipschitz type as well as Hölder continuity condition of the bifunctions involved. Furthermore, we show that the ergodic sequence defined by the algorithm iterates converges to a solution without paramonotonicity property. Some numerical experiments on differentiated Cournot-Nash models are presented to show the behavior of our proposed algorithm with and without ergodic.On four discrete-type families of NCP-functionshttps://www.zbmath.org/1472.901402021-11-25T18:46:10.358925Z"Huang, Chien-Hao"https://www.zbmath.org/authors/?q=ai:huang.chien-hao"Weng, Kang-Jun"https://www.zbmath.org/authors/?q=ai:weng.kang-jun"Chen, Jein-Shan"https://www.zbmath.org/authors/?q=ai:chen.jein-shan"Chu, Hsun-Wei"https://www.zbmath.org/authors/?q=ai:chu.hsun-wei"Li, Ming-Yen"https://www.zbmath.org/authors/?q=ai:li.ming-yenSummary: In this paper, we look into the detailed properties of four discrete-type families of NCP-functions, which are newly discovered in recent literature. With the discrete-oriented feature, we are motivated to know what differences there are compared to the traditional NCP-functions. The properties obtained in this paper not only explain the difference but also provide background bricks for designing solution methods based on such discrete-type families of NCP-functions.A modified LM algorithm for tensor complementarity problems over the circular conehttps://www.zbmath.org/1472.901412021-11-25T18:46:10.358925Z"Ke, Yifen"https://www.zbmath.org/authors/?q=ai:ke.yifen"Ma, Changfeng"https://www.zbmath.org/authors/?q=ai:ma.changfeng"Zhang, Huai"https://www.zbmath.org/authors/?q=ai:zhang.huaiSummary: The tensor complementarity problem over circular cone (CCTCP for short) is studied, which is a specially structured nonlinear complementarity problem. Useful properties of the circular cone help to reformulate equivalently CCTCP as an implicit fixed-point equation. Based on the smoothing functions, we reformulate the obtained fixed-point equation as a family of parameterized smoothing equations. Moreover, we propose a modified Levenberg-Marquardt (LM) algorithm to solve the problem iteratively and show that the sequence generated by the new algorithm converges to a solution quadratically under suitable conditions. Preliminary numerical results demonstrate that the proposed algorithm is effective.An inexact proximal decomposition method for variational inequalities with separable structurehttps://www.zbmath.org/1472.901422021-11-25T18:46:10.358925Z"Quiroz, Erik A. Papa"https://www.zbmath.org/authors/?q=ai:quiroz.erik-a-papa"Sarmiento, Orlando"https://www.zbmath.org/authors/?q=ai:sarmiento.orlando"Oliveira, Paulo Roberto"https://www.zbmath.org/authors/?q=ai:oliveira.paulo-robertoSummary: This paper presents an inexact proximal method for solving monotone variational inequality problems with a given separable structure. The proposed algorithm is a natural extension of the Proximal Multiplier Algorithm with Proximal Distances (PMAPD) proposed by \textit{O. Sarmiento} et al. [Optimization 65, No. 2, 501--537 (2016; Zbl 1338.52012)], which unified the works of \textit{G. Chen} and \textit{M. Teboulle} [Math. Program. 64, No. 1 (A), 81--101 (1994; Zbl 0823.90097)] (PCPM method), and Kyono and Fukushima (NPCPMM) developed for solving convex programs with a particular separable structure. The resulting method combines the recent proximal distances theory introduced by \textit{A. Auslender} and \textit{M. Teboulle} [SIAM J. Optim. 16, No. 3, 697--725 (2006; Zbl 1113.90118)] with a decomposition method given by Chen and Teboulle [loc. cit.] for convex problems and extends the results of the Entropic Proximal Decomposition Method proposed by Auslender and Teboulle [loc. cit.], which used to Logarithmic Quadratic proximal distances. Under some mild assumptions on the problem we prove a global convergence of the primal-dual sequences produced by the algorithm.A modified self-adaptive extragradient method for pseudomonotone equilibrium problem in a real Hilbert space with applicationshttps://www.zbmath.org/1472.901432021-11-25T18:46:10.358925Z"Rehman, Habib Ur"https://www.zbmath.org/authors/?q=ai:rehman.habib-ur"Kumam, Poom"https://www.zbmath.org/authors/?q=ai:kumam.poom"Dong, Qiao-Li"https://www.zbmath.org/authors/?q=ai:dong.qiaoli"Cho, Yeol Je"https://www.zbmath.org/authors/?q=ai:cho.yeol-jeSummary: In this paper, we consider an improvement of the extragradient method to figure out the numerical solution for pseudomonotone equilibrium problems in arbitrary real Hilbert space. A new method is proposed with an inertial scheme and a self adaptive step size rule that is revised on each iteration based on the previous three iterations. The weak convergence of the method is proved by assuming standard cost bifunction assumptions. We also consider the application of our results to solve different kinds of variational inequality problems and a particular class of fixed point problems. For a numerical part, we study the well-known Nash-Cournot equilibrium model and other test problems to support our well-established convergence results and to ensure that our proposed method has a competitive edge over CPU time and a number of iterations.On the existence of solutions and Tikhonov regularization of hemivariational inequality problemshttps://www.zbmath.org/1472.901442021-11-25T18:46:10.358925Z"Tang, Guo-ji"https://www.zbmath.org/authors/?q=ai:tang.guoji"Wan, Zhongping"https://www.zbmath.org/authors/?q=ai:wan.zhongping"Wang, Xianfu"https://www.zbmath.org/authors/?q=ai:wang.xianfu.1|wang.xianfuIn this paper, the authors establish a Tikhonov regularization theory for a class of hemivariational inequalities. To this end, they prove a very general existence result for the class of hemeivariational inequalities provided that the mapping has the so-called hemivariational inequality property and satisfies a rather weak coercivity condition. Based on the existence result, they derive the Tikhonov regularization result.A modulus-based nonmonotone line search method for nonlinear complementarity problemshttps://www.zbmath.org/1472.901452021-11-25T18:46:10.358925Z"Zhang, Xu"https://www.zbmath.org/authors/?q=ai:zhang.xu.4|zhang.xu.3|zhang.xu.1|zhang.xu|zhang.xu.2"Peng, Zheng"https://www.zbmath.org/authors/?q=ai:peng.zhengSummary: A modulus-based nonmonotone line search method is proposed for nonlinear complementarity problem. The considered problem is first reformulated to a nonsmooth nonlinear system based on the modulus-based decomposition. Then a nonmonotone line search method using simulated annealing rule is generalized to solve the resulting system. The global convergence of the proposed method is established under some suitable assumptions. Preliminary numerical experiments show that, compared with some existing methods, the proposed method is feasible and effective.Formalization of influence processes of fuzzy time flow on the solution to time resource distribution problemshttps://www.zbmath.org/1472.901462021-11-25T18:46:10.358925Z"Ivohin, E. V."https://www.zbmath.org/authors/?q=ai:ivohin.e-vSummary: This paper considers an approach to constructing fuzzy structured numerical sets, which is based on the principle of generating a fuzzy preimage with its subsequent replication on the numerical axis. The formalization of a fuzzy preimage consists of determining a fuzzy triangular number with an appropriate support. The option of generating fuzzy number sets that formalize the ``fast'' and ``slow'' flow of time is considered. A method is proposed that allows us to formalize the problem of fuzzy description and to take into account the dynamics of the time frame when solving various optimization problems. Examples of the use of the fuzzy flow of time for different statements of problems that arise when determining the order of the set of tasks within the given time interval with or without additional constraints on the execution process are considered. An approach is proposed for the correction of the initial time distribution plans, taking into account different rates of time counting. A method for constructing feasible solutions based on greedy heuristics is formulated.Joint chance constrained shortest path problem with Copula theoryhttps://www.zbmath.org/1472.901472021-11-25T18:46:10.358925Z"Nodeh, Zohreh Hosseini"https://www.zbmath.org/authors/?q=ai:nodeh.zohreh-hosseini"Azar, Ali Babapour"https://www.zbmath.org/authors/?q=ai:azar.ali-babapour"Shiraz, Rashed Khanjani"https://www.zbmath.org/authors/?q=ai:shiraz.rashed-khanjani"Khodayifar, Salman"https://www.zbmath.org/authors/?q=ai:khodayifar.salman"Pardalos, Panos M."https://www.zbmath.org/authors/?q=ai:pardalos.panos-mThis paper deals with the linear joint probabilistic constraints problem where dependence among the distribution of the constraint rows is depicted by a relax Archimedean Copula. The proposed model determines the shortest path, with the possibility of transporting goods from the source to the destination, so that an optimal path can be selected finally. Since this is the SPP with exponential complexity, the Lagrangian relaxation method is proposed to solve a large-scale problem so that a lower bound and an upper bound are obtained for every fixed Lagrangian coefficient of the main problem, during the process of the algorithm. The model implemented in this paper is related to the shortest path problem which has more than one indicator for finding an optimal path. The problem presented is generally non-convex and a relaxed approximation is provided to solve the problem. Numerical results are presented to demonstrate an appropriate estimate of the proposed model and for a better examination of the examples, the MOSEK solver is used. The results show that the model developed solves the dependency between resource consumptions and finds a higher probability path. The authors appreciate that: ``It means that the dependency between constraints and the use of the Copula approach for solving dependency gives us better results.''Dynamic programming and optimal control for vector-valued functions: a state-of-the-art reviewhttps://www.zbmath.org/1472.901482021-11-25T18:46:10.358925Z"Abdelaziz, Fouad Ben"https://www.zbmath.org/authors/?q=ai:ben-abdelaziz.fouad"La Torre, Davide"https://www.zbmath.org/authors/?q=ai:la-torre.davide"Alaya, Houda"https://www.zbmath.org/authors/?q=ai:alaya.houdaSummary: This paper aims to present a state-of-the-art review of recent development within the areas of dynamic programming and optimal control for vector-valued functions.Performance of different optimal charging schemes in a solar charging station using dynamic programminghttps://www.zbmath.org/1472.901492021-11-25T18:46:10.358925Z"Hajidavalloo, Mohammad R."https://www.zbmath.org/authors/?q=ai:hajidavalloo.mohammad-r"Shirazi, Farzad A."https://www.zbmath.org/authors/?q=ai:shirazi.farzad-a"Mahjoob, Mohammad J."https://www.zbmath.org/authors/?q=ai:mahjoob.mohammad-jSummary: Electric Vehicles (EVs) are gradually replacing conventional vehicles as they are environmentally friendly and cause less pollution problems. Unregulated charging has severe impacts on the distribution grid and may incur EV owners higher charging costs. Therefore, controlled charging infrastructures to supply the charging needs of large numbers of EVs are of vital importance. In this article, an optimal control scenario is presented to formulate the charge scheduling problem of EVs in a solar charging station (CS). Two different objective functions are considered. The first objective function holds for minimizing the total charging cost of EVs. In this case, the benefits of Vehicle-to-Grid (V2G) are investigated by comparing the charging costs of EVs with and without this capability. The total EV charging costs and grid benefits are also investigated in the second objective function which holds for minimizing the extracted power from the grid. A modified version of Dynamic Programming is used to solve the large state-space model defined for the optimal control problem with extremely shorter computation time and minimal loss of optimality. Extensive simulations are done in two representative summer and winter climates to determine the role of solar energy in the CS performance. The results show that in the cost minimization algorithms, significant savings for EV owners and a smooth load shape for the grid are achieved. For the minimized power from the grid algorithm, a total near Photovoltaic (PV)-curve charging power is obtained to exploit the PV power as much as possible to minimize the impacts on the grid.A finite time analysis of temporal difference learning with linear function approximationhttps://www.zbmath.org/1472.901502021-11-25T18:46:10.358925Z"Bhandari, Jalaj"https://www.zbmath.org/authors/?q=ai:bhandari.jalaj"Russo, Daniel"https://www.zbmath.org/authors/?q=ai:russo.daniel-j"Singal, Raghav"https://www.zbmath.org/authors/?q=ai:singal.raghavSummary: Temporal difference learning (TD) is a simple iterative algorithm used to estimate the value function corresponding to a given policy in a Markov decision process. Although TD is one of the most widely used algorithms in reinforcement learning, its theoretical analysis has proved challenging and few guarantees on its statistical efficiency are available. In this work, we provide a \textit{simple and explicit finite time analysis} of temporal difference learning with linear function approximation. Except for a few key insights, our analysis mirrors standard techniques for analyzing stochastic gradient descent algorithms and therefore inherits the simplicity and elegance of that literature. Final sections of the paper show how all of our main results extend to the study of TD learning with eligibility traces, known as TD\(\lambda\), and to \(Q\)-learning applied in high-dimensional optimal stopping problems.
The online appendices are available at \url{https://doi.org/10.1287/opre.2020.2024}.Points gained in football: using Markov process-based value functions to assess team performancehttps://www.zbmath.org/1472.901512021-11-25T18:46:10.358925Z"Chan, Timothy C. Y."https://www.zbmath.org/authors/?q=ai:chan.timothy-c-y"Fernandes, Craig"https://www.zbmath.org/authors/?q=ai:fernandes.craig"Puterman, Martin L."https://www.zbmath.org/authors/?q=ai:puterman.martin-lSummary: To develop a novel approach for performance assessment, this paper considers the problem of computing value functions in professional American football. We provide a theoretical justification for using a dynamic programming approach to estimating value functions in sports by formulating the problem as a Markov chain for two asymmetric teams. We show that the Bellman equation has a unique solution equal to the bias of the underlying infinite horizon Markov reward process. This result provides, for the first time in the sports analytics literature, a precise interpretation of the value function as the expected number of points gained or lost over and above the steady state points gained or lost. We derive a martingale representation for the value function that provides justification, in addition to the analysis of our empirical transition probabilities, for using an infinite horizon approximation of a finite horizon game. Using more than 160,000 plays from the 2013-2016 National Football League seasons, we derive an empirical value function that forms our points gained performance assessment metric, which quantifies the value created or destroyed on any play relative to expected performance. We show how this metric provides new insight into factors that distinguish performance. For example, passing plays generate the most points gained, whereas running plays tend to generate negative value. Short passes account for the majority of the top teams' success and the worst teams' poor performance. Other insights include how teams differ by down, quarter, and field position. The paper concludes with a case study of the 2019 Super Bowl and suggests how the key concepts might apply outside of sports.Exact dual bounds for some nonconvex minimax quadratic optimization problemshttps://www.zbmath.org/1472.901522021-11-25T18:46:10.358925Z"Berezovskyi, O. A."https://www.zbmath.org/authors/?q=ai:berezovskij.o-aSummary: The nonconvex separable minimax quadratic optimization problem is analyzed. Two approaches to the problem solution are described, namely, by using SOCP relaxation and by using Lagrangian relaxation of a quadratic extremum analog problem. A condition is obtained that guarantees finding the value and the global extremum point of the problem of the considered class by calculating the dual bound of the equivalent quadratic extremum problem.A new two-stage variable neighborhood search algorithm for the nurse rostering problemhttps://www.zbmath.org/1472.901532021-11-25T18:46:10.358925Z"Abdelghany, Mohammed"https://www.zbmath.org/authors/?q=ai:abdelghany.mohammed"Yahia, Zakaria"https://www.zbmath.org/authors/?q=ai:yahia.zakaria"Eltawil, Amr B."https://www.zbmath.org/authors/?q=ai:eltawil.amr-bSummary: The nurse rostering problem refers to the assignment of nurses to daily shifts according to the required demand of each shift and day, with consideration for the operational requirements and nurses' preferences. This problem is known to be an NP-hard problem, difficult to be solved using the known exact solution methods especially for large size instances. Mostly, this problem is modeled with soft and hard constraint, and the objective is set to minimize the violations for the soft constraints. In this paper, a new two-stage variable neighborhood search algorithm is proposed for solving the nurse rostering problem. The first stage aims at minimizing the violations of the soft constraints with the higher penalty weights in the objective function. While the second stage considers minimizing the total solution penalty taking into account all the soft constraint. The proposed algorithm was tested on the 24 benchmark instances of \textit{T. Curtois} and \textit{R. Qu} [Computational results on new staff scheduling benchmark instances. Techn. Rep., ASAP Research Group, School of Computer Science, Univ. Nottingham (2014)]. The test results revealed that the proposed algorithm is able to compete with the results of a recent heuristic approach from literature for most of the tested instances.Hybrid cell selection-based heuristic for capacitated multi-facility Weber problem with continuous fixed costshttps://www.zbmath.org/1472.901542021-11-25T18:46:10.358925Z"Jamil, Nur Shifa Farah Ain"https://www.zbmath.org/authors/?q=ai:jamil.nur-shifa-farah-ain"Abdul-Rahman, Syariza"https://www.zbmath.org/authors/?q=ai:abdul-rahman.syariza"Luis, Martino"https://www.zbmath.org/authors/?q=ai:luis.martino"Benjamin, Aida Mauziah"https://www.zbmath.org/authors/?q=ai:benjamin.aida-mauziahSummary: Location-allocation problem (LAP) has attracted much attention in facility location field. The LAP in continuous plane is well-known as Weber problem. This paper assessed this problem by considering capacity constraints and fixed costs as each facility has different setup cost and capacity limit to serve customers. Previous studies considered profitable areas by dividing continuous space into a discrete number of equal cells to identify optimal locations from a smaller set of promising locations. Unfortunately, it may lead to avoid choosing good locations because unprofitable areas are still considered while locating the facilities. Hence, this allows a significant increment in the transportation costs. Thus, this paper intelligently selected profitable area through a hybridization of enhanced Cell Selection-based Heuristic (CSBH) and Furthest Distance Rule (FDR) to minimize total transportation and fixed costs. The CSBH divides customer distribution into smaller set of promising locations and intelligently selected profitable area to increase possibility of finding better locations, while FDR aims to forbid the new locations of the facilities to be close to the previously selected locations. Numerical experiments tested on well-known benchmark datasets showed that the results of hybrid heuristic outperformed single CSBH and FDR, while producing competitive results when compared with previously published results, apart from significantly improving total transportation cost. The new hybrid heuristic is simple yet effective in solving LAP.Physics based optimization: an enhanced matter search algorithmhttps://www.zbmath.org/1472.901552021-11-25T18:46:10.358925Z"Zhou, Guo"https://www.zbmath.org/authors/?q=ai:zhou.guo"Zhou, Yongquan"https://www.zbmath.org/authors/?q=ai:zhou.yongquan"Tang, Zhonghua"https://www.zbmath.org/authors/?q=ai:tang.zhonghua"Huang, Huajuan"https://www.zbmath.org/authors/?q=ai:huang.huajuanSummary: States of matter search (SMS) algorithm is physics based optimization algorithm inspired by the physics phenomenon of changing states of matter. Although this algorithm successfully used to solve many complex problems, it converges slowly and can fall into local optima. Here, a novel drift operator drive SMS (DSMS) algorithm base on physics phenomenon is proposed, this approach enhanced the rate of the DSMS convergence. In addition, we introduce a variable differential evolution operator to increase individual diversity, which allows the DSMS algorithm to escape the local optima. Experiments on sixteen benchmark functions and two engineering test functions show that the DSMS is more efficient than other metaheuristic algorithms.Fuzzy weak link approach to the two-stage DEAhttps://www.zbmath.org/1472.901562021-11-25T18:46:10.358925Z"Despotis, Dimitris"https://www.zbmath.org/authors/?q=ai:despotis.dimitris-k"Kuchta, Dorota"https://www.zbmath.org/authors/?q=ai:kuchta.dorotaSummary: This paper refers to a recent approach to two-stage DEA called the weak link approach. It underlines the lack of solution uniqueness in this approach to DEA and the fact that in order for the solution to the weak link approach to be unique, the decision maker needs to express a preference on which Pareto solution would be most satisfactory. In this paper, we propose to use a fuzzy set approach called fuzzy bicriterial programming to help the decision maker to express this preference. Fuzzy bicriterial programming is explained and then applied to the weak link approach to the DEA. It is shown that for each candidate (Pareto) solution to the original weak link approach, there exists an expert opinion that can lead to the unequivocal selection of this solution due to the use of the fuzzy approach. The proposal is illustrated with examples.Data replica's distribution optimization based on availability prediction using fuzzy theory in the cloudhttps://www.zbmath.org/1472.901572021-11-25T18:46:10.358925Z"Wu, Xiuguo"https://www.zbmath.org/authors/?q=ai:wu.xiuguo"Jiang, Xuejun"https://www.zbmath.org/authors/?q=ai:jiang.xuejunSummary: Cloud storage system has more advantages than traditional data processing mode, such as high scalability, high fault tolerance and huge storage space, where data replica is a common used technology aiming to enhance data access reliability and availability. However, traditional replicas distribution strategies mostly focused on current environment, usually leading to lower data availability in the near future. To solve this problem, a data replicas availability prediction model based on fuzzy theory is first presented using information of CPU, bandwidth, memory and security as input, while data replicas availability as output. After that, a two-phase data replicas distribution optimization algorithm based on the fuzzy availability prediction is proposed, including data replicas number and their placements. Simulations and experiments are performed to evaluate the validity and reliability of proposed approach, and results show that replicas space of data replica distribution optimization strategy accounts for nearly 70 percents compared with other two strategies, and less wait latency can be achieved through it, indicating the better effectiveness and practicality.Optimal non-anticipative scenarios for nonlinear hydro-thermal power systemshttps://www.zbmath.org/1472.901582021-11-25T18:46:10.358925Z"Periçaro, Gislaine A."https://www.zbmath.org/authors/?q=ai:pericaro.gislaine-a"Karas, Elizabeth W."https://www.zbmath.org/authors/?q=ai:karas.elizabeth-w"Gonzaga, Clóvis C."https://www.zbmath.org/authors/?q=ai:gonzaga.clovis-c"Marcílio, Débora C."https://www.zbmath.org/authors/?q=ai:marcilio.debora-cintia"Oening, Ana Paula"https://www.zbmath.org/authors/?q=ai:oening.ana-paula"Matioli, Luiz Carlos"https://www.zbmath.org/authors/?q=ai:matioli.luiz-carlos"Detzel, Daniel H. M."https://www.zbmath.org/authors/?q=ai:detzel.daniel-h-m"de Geus, Klaus"https://www.zbmath.org/authors/?q=ai:de-geus.klaus"Bessa, Marcelo R."https://www.zbmath.org/authors/?q=ai:bessa.marcelo-rSummary: The long-term operation of hydro-thermal power generation systems is modeled by a large-scale stochastic optimization problem that includes nonlinear constraints due to the head computation in hydroelectric plants. We do a detailed development of the problem model and state it by a non-anticipative scenario analysis, leading to a large-scale nonlinear programming problem. This is solved by a filter algorithm with sequential quadratic programming iterations that minimize quadratic Lagrangian approximations using exact hessians in \(L_\infty\) trust regions. The method is applied to the long-term planning of the Brazilian system, with over 100 hydroelectric and 50 thermoelectric plants, distributed in 5 interconnected subsystems. This problem with 50 synthetically generated inflow scenarios and a horizon of 60 months, amounting to about one million variables and 15000 nonlinear constraints was solved by the filter algorithm in a standard 2016 notebook computer in 10 h of CPU.Cross-modal retrieval based on optimized matrix factorization hashinghttps://www.zbmath.org/1472.901592021-11-25T18:46:10.358925Z"Wu, Wei"https://www.zbmath.org/authors/?q=ai:wu.wei|wu.wei.3|wu.wei.2|wu.wei.4"Jing, Xiaoyuan"https://www.zbmath.org/authors/?q=ai:jing.xiaoyuan"Du, Wencai"https://www.zbmath.org/authors/?q=ai:du.wencai"Cao, Xinghui"https://www.zbmath.org/authors/?q=ai:cao.xinghui"Zhou, Hui"https://www.zbmath.org/authors/?q=ai:zhou.huiSummary: Cross-modal retrieval aims to study the connections between different modalities, with the distance of related pairs reduced while irrelevant pairs increased. In this paper, we propose a new matrix factorization hashing model to study this process with both refined intra-modal and cross-modal local-geometry features. The optimization processing is given with sub-function global influential weights considered, instead of fixed similarity weights defined as 1 or \(-1\) manually. The experimental results on the benchmark data set show the effectiveness of the proposed method.Two-sided matching decision with trapezoidal intuitionistic fuzzy numbers using similarity measureshttps://www.zbmath.org/1472.910182021-11-25T18:46:10.358925Z"Yue, Qi"https://www.zbmath.org/authors/?q=ai:yue.qiSummary: In the paper, we propose one novel method for handling two-sided matching problems with trapezoidal intuitionistic fuzzy numbers (TrIFNs) based on similarity measures between TrIFNs. First, we present the two-sided matching problem based on TrIFNs. Then, the matching model with TrIFNs is built. For model solution, we propose one similarity measure for calculating the degree of similarity among TrIFNs. The presented similarity measure between TrIFNs is combined with two similarity measures between generalized trapezoidal fuzzy numbers (GTrFNs), where maximum membership degrees, minimum non-membership degrees, areas, perimeters are used to calculate it. Using the similarity measures between TrIFNs, the matching model with TrIFNs can be converted into that with similarity measures. By using the arithmetic mean method, normalization formulas and the linear weighting method, the matching model with similarity measures is changed to a mono-goal model. The optimum matching scheme is got through solving the model. In the end, the effectiveness of the developed method can be expounded using one matching example.Optimization model applied to radiotherapy planning problem with dose intensity and beam choicehttps://www.zbmath.org/1472.921212021-11-25T18:46:10.358925Z"Freitas, Juliana Campos de"https://www.zbmath.org/authors/?q=ai:freitas.juliana-campos-de"Florentino, Helenice de Oliveira"https://www.zbmath.org/authors/?q=ai:de-oliveira-florentino.helenice"Benedito, Antone dos Santos"https://www.zbmath.org/authors/?q=ai:benedito.antone-dos-santos"Cantane, Daniela Renata"https://www.zbmath.org/authors/?q=ai:cantane.daniela-renataSummary: Optimization applied to radiotherapy planning is a complex scientific issue seeking to deliver both possible highest dose into tumor tissue and lowest one into adjacent tissues. It is composed of one or more of the following main problems: beam choice, dose intensity and blades opening. In this paper, a mixed integer nonlinear optimization model is developed for radiation treatment planned by intensity modulated radiotherapy treatment involving both dose intensity and beam choice optimization problems. Moreover, metaheuristics proposed to solve the beam optimization problem are coupled with exact methods, which in turn solve the dose intensity problem. The proposed model is applied to two real computerized tomography images of prostate cases, where it has been shown to be highly efficient.Designing q-unique DNA sequences with integer linear programs and Euler tours in de Bruijn graphshttps://www.zbmath.org/1472.921622021-11-25T18:46:10.358925Z"D'Addario, Marianna"https://www.zbmath.org/authors/?q=ai:daddario.marianna"Kriege, Nils"https://www.zbmath.org/authors/?q=ai:kriege.nils-m"Rahmann, Sven"https://www.zbmath.org/authors/?q=ai:rahmann.svenSummary: DNA nanoarchitechtures require carefully designed oligonucleotides with certain non-hybridization guarantees, which can be formalized as the q-uniqueness property on the sequence level. We study the optimization problem of finding a longest q-unique DNA sequence. We first present a convenient formulation as an integer linear program on the underlying De Bruijn graph that allows to flexibly incorporate a variety of constraints; solution times for practically relevant values of q are short. We then provide additional insights into the problem structure using the quotient graph of the De Bruijn graph with respect to the equivalence relation induced by reverse complementarity. Specifically, for odd q the quotient graph is Eulerian, so finding a longest q-unique sequence is equivalent to finding an Euler tour and solved in linear time with respect to the output string length. For even q, self-complementary edges complicate the problem, and the graph has to be Eulerized by deleting a minimum number of edges. Two sub-cases arise, for one of which we present a complete solution, while the other one remains open.
For the entire collection see [Zbl 1472.92001].Convergence of distributed gradient-tracking-based optimization algorithms with random graphshttps://www.zbmath.org/1472.930062021-11-25T18:46:10.358925Z"Wang, Jiexiang"https://www.zbmath.org/authors/?q=ai:wang.jiexiang"Fu, Keli"https://www.zbmath.org/authors/?q=ai:fu.keli"Gu, Yu"https://www.zbmath.org/authors/?q=ai:gu.yu.1"Li, Tao"https://www.zbmath.org/authors/?q=ai:li.tao.3Summary: This paper studies distributed convex optimization over a multi-agent system, where each agent owns only a local cost function with convexity and Lipschitz continuous gradients. The goal of the agents is to cooperatively minimize a sum of the local cost functions. The underlying communication networks are modelled by a sequence of random and balanced digraphs, which are not required to be spatially or temporally independent and have any special distributions. The authors use a distributed gradient-tracking-based optimization algorithm to solve the optimization problem. In the algorithm, each agent makes an estimate of the optimal solution and an estimate of the average of all the local gradients. The values of the estimates are updated based on a combination of a consensus method and a gradient tracking method. The authors prove that the algorithm can achieve convergence to the optimal solution at a geometric rate if the conditional graphs are uniformly strongly connected, the global cost function is strongly convex and the step-sizes don't exceed some upper bounds.Distributed nonsmooth convex optimization over Markovian switching random networks with two step-sizeshttps://www.zbmath.org/1472.930072021-11-25T18:46:10.358925Z"Yi, Peng"https://www.zbmath.org/authors/?q=ai:yi.peng"Li, Li"https://www.zbmath.org/authors/?q=ai:li.li.18|li.li.15|li.li.2|li.li|li.li.17|li.li.16|li.li.7|li.li.11|li.li-erran|li.li.14|li.li.12|li.li.13|li.li.5|li.li.4|li.li.1|li.li.9|li.li.8Summary: This paper investigates the distributed convex optimization problem over a multi-agent system with Markovian switching communication networks. The objective function is the sum of each agent's local nonsmooth objective function, which cannot be known by other agents. The communication network is assumed to switch over a set of weight-balanced directed graphs with a Markovian property. The authors propose a consensus sub-gradient algorithm with two time-scale step-sizes to handle the Markovian switching topologies and the absence of global gradient information. With proper selection of step-sizes, the authors prove the almost sure convergence of all agents' local estimates to the same optimal solution when the union graph of the Markovian network' states is strongly connected and the Markovian chain is irreducible. The convergence rate analysis is also given for specific cases. Simulations are given to demonstrate the results.Experimental operation of a solar-driven climate system with thermal energy storages using mixed-integer nonlinear model predictive controlhttps://www.zbmath.org/1472.930352021-11-25T18:46:10.358925Z"Bürger, Adrian"https://www.zbmath.org/authors/?q=ai:burger.adrian"Bull, Daniel"https://www.zbmath.org/authors/?q=ai:bull.daniel"Sawant, Parantapa"https://www.zbmath.org/authors/?q=ai:sawant.parantapa"Bohlayer, Markus"https://www.zbmath.org/authors/?q=ai:bohlayer.markus"Klotz, Andreas"https://www.zbmath.org/authors/?q=ai:klotz.andreas"Beschütz, Daniel"https://www.zbmath.org/authors/?q=ai:beschutz.daniel"Altmann-Dieses, Angelika"https://www.zbmath.org/authors/?q=ai:altmann-dieses.angelika"Braun, Marco"https://www.zbmath.org/authors/?q=ai:braun.marco"Diehl, Moritz"https://www.zbmath.org/authors/?q=ai:diehl.moritz-mathiasSummary: This work presents the results of experimental operation of a solar-driven climate system using mixed-integer nonlinear model predictive control (MPC). The system is installed in a university building and consists of two solar thermal collector fields, an adsorption cooling machine with different operation modes, a stratified hot water storage with multiple inlets and outlets as well as a cold water storage. The system and the applied modeling approach is described and a parallelized algorithm for mixed-integer nonlinear MPC and a corresponding implementation for the system are presented. Finally, we show and discuss the results of experimental operation of the system and highlight the advantages of the mixed-integer nonlinear MPC application.Fast synchronization of distributed generators with power grid under transient conditions using hybrid optimization algorithmhttps://www.zbmath.org/1472.930622021-11-25T18:46:10.358925Z"Christopher, Alwin Vinifred"https://www.zbmath.org/authors/?q=ai:christopher.alwin-vinifred"Rengaswamy, Ramesh"https://www.zbmath.org/authors/?q=ai:rengaswamy.rameshSummary: The integration of nonrenewable and renewable energy resources is growing rapidly due to energy demand and smart grid technologies. In power grids, the performance of synchronization is reduced by some issues such as frequency instability, voltage distortion, and voltage unbalance. This work presents the fast synchronization of the PV grid-connected system utilized the hybrid optimized proportional resonant (PR) controller under transient condition. The proposed system is designed and controlled by the optimized PR controller strategy on stationary reference frame control. The AC voltage is switched into the AC grid voltage, and error can occur in the difference between the phase reference and measured value. So the current controller of the PR controller is considering the effects of harmonics. The controller is properly tuned by the hybrid algorithm of killer whale optimization (KWO) and the grasshopper optimization algorithm to reduce the harmonics. The synchronization reduces the phase angle, voltage, and frequency between the generator outcomes. The performance of a PV based optimized PR controller controlled the voltage source inverter to achieve the optimal signal of fast synchronization. The effect of total harmonic distortion transient response is improved by the well-designed PR control parameters based LC filter. The proposed system is implemented in MATLAB/Simulink platform. The robustness of the system is compared with traditional controllers of the proportional integral derivative and proportional-integral controller.Formulation of nonlinear control problems with actuator saturation as linear programshttps://www.zbmath.org/1472.930712021-11-25T18:46:10.358925Z"Merrikh-Bayat, Farshad"https://www.zbmath.org/authors/?q=ai:merrikh-bayat.farshad"Afshar, Mehdi"https://www.zbmath.org/authors/?q=ai:afshar.mehdiSummary: Control of input-affine nonlinear dynamical systems is investigated in this paper. In this regard, a system of linear inequalities (SLI) in the control inputs is developed, and it is proved that if this SLI has a solution at all times, applying it to the system leads to moving its state trajectories towards the desired point in space for all initial conditions. But, since it may happen that this SLI has infinitely many solutions or even no solution, the best (possibly, approximate) solution is obtained by solving a linear programming (LP) problem. Different LP problems with different properties and applications are proposed for this purpose. Formulation of the control problem as an LP makes it possible to take into account the effect of actuator saturation simply by adding bound constraints to the problem. We can also make the resulting control system robust to model uncertainties. Some numerical examples including the output voltage regulation of double-source DC-DC converter and robot path-planning, both by considering the effect of actuators saturation and taking into account the uncertainties in model, are also presented.Adaptive dynamic programing design for the neural control of hypersonic flight vehicleshttps://www.zbmath.org/1472.930912021-11-25T18:46:10.358925Z"Qi, Qiang"https://www.zbmath.org/authors/?q=ai:qi.qiang"Bu, Xiangwei"https://www.zbmath.org/authors/?q=ai:bu.xiangweiSummary: An adaptive dynamic programming controller based on backstepping method is designed for the optimal tracking control of hypersonic flight vehicles. The control input is divided into two parts namely stable control and optimal control. First, the back-stepping method is exploited via neural networks (NNs) to estimate unknown functions. Then, the computational load is reduced by the minimal-learning-parameter (MLP) scheme. To avoid the problem of ``explosion of terms'', a first-order filter is adopted. Next, the optimal controller is designed based on the adaptive dynamic programming. In order to solve the Hamiltonian equation, NNs estimators are introduced to approximate performance indicators, achieving the approximate optimal control of hypersonic flight vehicles. Finally, the effectiveness and advantages of the control method are verified by simulation results.Event-triggered decentralized optimal fault tolerant control for mismatched interconnected nonlinear systems through adaptive dynamic programminghttps://www.zbmath.org/1472.931182021-11-25T18:46:10.358925Z"Luo, Fangchao"https://www.zbmath.org/authors/?q=ai:luo.fangchao"Zhao, Bo"https://www.zbmath.org/authors/?q=ai:zhao.bo"Liu, Derong"https://www.zbmath.org/authors/?q=ai:liu.derongSummary: In this paper, we propose an event-triggered decentralized optimal fault tolerant control (ETDOFTC) scheme based on adaptive dynamic programming for mismatched interconnected nonlinear systems with actuator failures. For fault-free dynamic models, the decentralized control problem is addressed by developing a set of decentralized optimal control strategies for isolated subsystems with modified value functions, which are approximated by critic neural networks. Meanwhile, the neural network-based decentralized observer is established to approximate actuator failures and mismatched unknown interconnections. The weights of the neural networks are aperiodically updated at the designed triggering instants. Then, the proposed ETDOFTC scheme is obtained by combining the event-triggered decentralized optimal control strategies with the adaptive fault compensators. Furthermore, it is proved that all the signals of the closed-loop system are uniformly ultimately bounded via the Lyapunov stability analysis. Finally, simulation results of two examples are presented to confirm the effectiveness of the proposed ETDOFTC scheme.Research on global optimization method for multiple AGV collision avoidance in hybrid pathhttps://www.zbmath.org/1472.931252021-11-25T18:46:10.358925Z"Cao, Xiaohua"https://www.zbmath.org/authors/?q=ai:cao.xiaohua"Zhu, Meng"https://www.zbmath.org/authors/?q=ai:zhu.mengSummary: Due to the increasing number of automated guided vehicles (AGVs) in the multi-AGV system and the limitation of working environment, path conflicts often occur in the working process of AGVs, which affects the working efficiency of the multi-AGV system. Thus, a optimization method by arranging the AGVs' traffic sequence is proposed in this paper. First, an AGV working map is reconstructed with graph theory, and then the corresponding collision avoidance rules are formulated for different types of conflicts. In multi-AGV system, each collision avoidance decision has an impact on the efficiency of the system, so it is crucial to adopt appropriate decisions. To optimize the decisions, the system fitness of different collision avoidance decisions are calculated based on the global state of the system, and the particle swarm optimization (PSO) algorithm is used to optimize the decisions. Furthermore, the PSO algorithm is improved by planning the direction of particle motion in the solution space and introducing mutation operation, so as to improve the search ability of the particle in the solution space. To verify the feasibility and effectiveness of the improved particle swarm optimization (IPSO) algorithm, an experiment system is built based on. NET platform. Results show that the IPSO algorithm than the traditional algorithms experimental performs better. The IPSO algorithm can effectively reduce congestion caused by path conflict and enhance the efficiency of the multi-AGV system.Positive consensus for multi-agent systems with average dwell time switchinghttps://www.zbmath.org/1472.931672021-11-25T18:46:10.358925Z"Cao, Xiangyang"https://www.zbmath.org/authors/?q=ai:cao.xiangyang"Li, Yan"https://www.zbmath.org/authors/?q=ai:li.yan.8|li.yan.10|li.yan.6|li.yan|li.yan.9|li.yan.5|li.yan.3|li.yan.2|li.yan.7|li.yan.4|li.yan.1Summary: This paper considers the positive consensus for a class of multi-agent systems (MASs) with average dwell time (ADT) switching. First, sufficient and necessary conditions are derived for preserving the positivity of the closed-loop MASs. Second, the performance analysis of the consensus error system is accomplished by using the multiple Lyapunov functions (MLFs) approach, and an ADT switching technique designs the corresponding controlled switching signal. Then, both leaderless and leader-following positive consensus are achieved. Furthermore, to reduce the computational complexity, a novel leader-following positive consensus criterion is derived in the form of linear programming (LP). Finally, simulation examples are given to illustrate the effectiveness of the proposed method.Convergence of value functions for finite horizon Markov decision processes with constraintshttps://www.zbmath.org/1472.931972021-11-25T18:46:10.358925Z"Ichihara, Naoyuki"https://www.zbmath.org/authors/?q=ai:ichihara.naoyukiSummary: This paper is concerned with finite horizon countable state Markov decision processes (MDPs) having an absorbing set as a constraint. Convergence of value iteration is discussed to investigate the asymptotic behavior of value functions as the time horizon tends to infinity. It turns out that the value function exhibits three different limiting behaviors according to the critical value \(\lambda_{\ast}\), the so-called generalized principal eigenvalue, of the associated ergodic problem. Specifically, we prove that (i) if \(\lambda_{\ast}<0\), then the value function converges to a solution to the corresponding stationary equation; (ii) if \(\lambda_{\ast}>0\), then, after a suitable normalization, it approaches a solution to the corresponding ergodic problem; (iii) if \(\lambda_{\ast}=0\), then it diverges to infinity with, at most, a logarithmic order. We employ this convergence result to examine qualitative properties of the optimal Markovian policy for a finite horizon MDP when the time horizon is sufficiently large.Phase retrieval from Fourier measurements with maskshttps://www.zbmath.org/1472.940092021-11-25T18:46:10.358925Z"Li, Huiping"https://www.zbmath.org/authors/?q=ai:li.huiping"Li, Song"https://www.zbmath.org/authors/?q=ai:li.songSummary: This paper concerns the problem of phase retrieval from Fourier measurements with random masks. Here we focus on researching two kinds of random masks. Firstly, we utilize the Fourier measurements with real masks to estimate a general signal \(\mathfrak{x}_0\in \mathbb{R}^d\) in noiseless case when \(d\) is even. It is demonstrated that \(O(\log^2d)\) real random masks are able to ensure accurate recovery of \(\mathfrak{x}_0\). Then we find that such real masks are not adaptable to reconstruct complex signals of even dimension. Subsequently, we prove that \(O(\log^4d)\) complex masks are enough to stably estimate a general signal \(\mathfrak{x}_0\in \mathbb{C}^d\) under bounded noise interference, which extends \textit{E. J. Candès} et al.'s work [SIAM Rev. 57, No. 2, 225--251 (2015; Zbl 1344.49057)]. Meanwhile, we establish tighter error estimations for real signals of even dimensions or complex signals of odd dimensions by using \(O(\log^2d)\) real masks. Finally, we intend to tackle with the noisy phase problem about an \(s\)-sparse signal by a robust and efficient approach, namely, two-stage algorithm. Based on the stable guarantees for general signals, we show that the \(s\)-sparse signal \(\mathfrak{x}_0\) can be stably recovered from composite measurements under near-optimal sample complexity up to a \(\log\) factor, namely, \(O(s\log(\frac{ed}{s})\log^4(s\log(\frac{ed}{s})))\).Radio-frequency chain selection for energy and spectral efficiency maximization in hybrid beamforming under hardware imperfectionshttps://www.zbmath.org/1472.940422021-11-25T18:46:10.358925Z"Vlachos, Evangelos"https://www.zbmath.org/authors/?q=ai:vlachos.evangelos"Thompson, John"https://www.zbmath.org/authors/?q=ai:thompson.john-m|thompson.john-w|thompson.john-d|thompson.john-l|thompson.john-g|thompson.j-michael-t|thompson.john-r|thompson.john-s"Kaushik, Aryan"https://www.zbmath.org/authors/?q=ai:kaushik.aryan"Masouros, Christos"https://www.zbmath.org/authors/?q=ai:masouros.christosSummary: The next-generation wireless communications require reduced energy consumption, increased data rates and better signal coverage. The millimetre-wave frequency spectrum above 30 GHz can help fulfil the performance requirements of the next-generation mobile broadband systems. Multiple-input multiple-output technology can provide performance gains to help mitigate the increased path loss experienced at millimetre-wave frequencies compared with microwave bands. Emerging hybrid beamforming architectures can reduce the energy consumption and hardware complexity with the use of fewer radio-frequency (RF) chains. Energy efficiency is identified as a key fifth-generation metric and will have a major impact on the hybrid beamforming system design. In terms of transceiver power consumption, deactivating parts of the beamformer structure to reduce power typically leads to significant loss of spectral efficiency. Our aim is to achieve the highest energy efficiency for the millimetre-wave communications system while mitigating the resulting loss in spectral efficiency. To achieve this, we propose an optimal selection framework which activates specific RF chains that amplify the digitally beamformed signals with the analogue beamforming network. Practical precoding is considered by including the effects of user interference, noise and hardware impairments in the system modelling.