Search

Near isometric orthogonal embeddings to lower dimensions are a fundamental tool in data science and machine learning. In this paper, we present the construction of such embeddings that minimizes the maximum distortion for a given set of points. We formulate the problem as a non convex constrained optimization problem. We first construct a primal relaxation and then use the theory of Lagrange duality to create a dual relaxation. We also suggest a polynomial time algorithm based on the theory of convex optimization to solve the dual relaxation provably. We provide a theoretical upper bound on the approximation guarantees for our algorithm, which depends only on the spectral properties of the dataset. We experimentally demonstrate the superiority of our algorithm compared to baselines in terms of the scalability and the ability to achieve lower distortion. [ABSTRACT FROM AUTHOR]

Background: This paper presents a novel approach for Generative Anatomy Modeling Language (GAML). This approach automatically detects the geometric partitions in 3D anatomy that in turn speeds up integrated non-linear optimization model in GAML for 3D anatomy modeling with constraints (e.g. joints). This integrated non-linear optimization model requires the exponential execution time. However, our approach effectively computes the solution for non-linear optimization model and reduces computation time from exponential to linear time. This is achieved by grouping the 3D geometric constraints into communities. Methods: Various community detection algorithms (k-means clustering, Clauset Newman Moore, and Density-Based Spatial Clustering of Applications with Noise) were used to find communities and partition the non-linear optimization problem into sub-problems. GAML was used to create a case study for 3D shoulder model to benchmark our approach with up to 5000 constraints. Results: Our results show that the computation time was reduced from exponential time to linear time and the error rate between the partitioned and non-partitioned approach decreases with the increasing number of constraints. For the largest constraint set (5000 constraints), speed up was over 2689-fold whereas error was computed as low as 2.2%. Conclusion: This study presents a novel approach to group anatomical constraints in 3D human shoulder model using community detection algorithms. A case study for 3D modeling for shoulder models developed for arthroscopic rotator cuff simulation was presented. Our results significantly reduced the computation time in conjunction with a decrease in error using constrained optimization by linear approximation, non-linear optimization solver. [ABSTRACT FROM AUTHOR]

Utility-based shortfall risk measures (SR) have received increasing attention over the past few years for their potential to quantify the risk of large tail losses more effectively than conditional value at risk. In this paper, we consider a distributionally robust version of the shortfall risk measure (DRSR) where the true probability distribution is unknown and the worst distribution from an ambiguity set of distributions is used to calculate the SR. We start by showing that the DRSR is a convex risk measure and under some special circumstance a coherent risk measure. We then move on to study an optimization problem with the objective of minimizing the DRSR of a random function and investigate numerical tractability of the optimization problem with the ambiguity set being constructed through ϕ -divergence ball and Kantorovich ball. In the case when the nominal distribution in the balls is an empirical distribution constructed through iid samples, we quantify convergence of the ambiguity sets to the true probability distribution as the sample size increases under the Kantorovich metric and consequently the optimal values of the corresponding DRSR problems. Specifically, we show that the error of the optimal value is linearly bounded by the error of each of the approximate ambiguity sets and subsequently derive a confidence interval of the optimal value under each of the approximation schemes. Some preliminary numerical test results are reported for the proposed modeling and computational schemes. [ABSTRACT FROM AUTHOR]

Over the past decade, several approximate adders have been proposed in the literature based on the design concept of Equal Segment Adder (ESA). In this approach, an $N$ -bit adder is segmented into several smaller and independent equally sized accurate sub-adders. An $N$ -bit ESA has two primary design parameters: (i) Segment size ($k$ ), which represents the maximum length of carry propagation; and (ii) Overlapping bits ($l$ ), which represents the minimum number of bits used in carry prediction, where $1 \leq k < N$ and $0 \leq l < k$ . Based on the combinations of $k$ and $l$ , an $N$ -bit ESA has $N(N-1)/2$ possible configurations. In this paper, we analyse ESAs and propose analytical models to estimate accuracy, delay, power and area of ESAs. The key features of the proposed analytical models are that: (i) They are generalized, i.e., work for all possible configurations of an $N$ -bit ESA; and (ii) They are superior (i.e., estimate more accurately) or at par to the existing analytical models. From the proposed analytical models, we observe that in an $N$ -bit ESA, there exist multiple (more than one) configurations which exhibit similar accuracy. However, these configurations exhibit different delay, power and area. Therefore, for a given accuracy, the configurations which provide minimal delay, power and/or area need to be known apriori for efficient, intelligent and goal oriented implementations of ESAs. In this regard, we present an optimization framework that exploits the proposed analytical models to find the optimal configurations of an $N$ -bit ESA. Further, we know that accuracy of an ESA does not depend on the adder architecture used to implement it, however, its delay, power and area depend significantly. Consequently, the optimal configurations vary with adder architectures used to implement the ESA. In order to cover a wide range of adders, we consider three types of adder architecture in our analysis: (i) Architectures having smaller area ($O(N)$ ); (ii) Architectures having smaller delay ($O(log_2N)$ ); and (iii) Architectures having in-between delay ($O(N/4)$ ) and area ($O(2N)$ ). [ABSTRACT FROM AUTHOR]

Global sensitivity analysis (GSA) aims at quantifying the effects of inputs on the output response globally. GSA is useful for identifying a few important inputs from a model with large number of inputs, which is critical for structural design and optimization. The method of Sobol' and the Morris method are two popular GSA techniques, and they have been widely used in many areas of science and engineering. It was proved that the Morris index is a good proxy of the method of Sobol' in some papers. However, some of the quantitative relationships between Morris index and Sobol' index are established by only considering the input with standard uniform distribution. When the input does not follow standard uniform distribution, some relationships are no longer valid. Therefore, an enhanced Morris method is developed as a better proxy of the Sobol' index for the input with arbitrary distribution, and it does not increase the model evaluations compared with the original Morris method. Test examples show the performance of the approximation and its usefulness in practice. [ABSTRACT FROM AUTHOR]

In this paper, we present a conditional gradient type (CGT) method for solving a class of composite optimization problems where the objective function consists of a (weakly) smooth term and a (strongly) convex regularization term. While including a strongly convex term in the subproblems of the classical conditional gradient method improves its rate of convergence, it does not cost per iteration as much as general proximal type algorithms. More specifically, we present a unified analysis for the CGT method in the sense that it achieves the best known rate of convergence when the weakly smooth term is nonconvex and possesses (nearly) optimal complexity if it turns out to be convex. While implementation of the CGT method requires explicitly estimating problem parameters like the level of smoothness of the first term in the objective function, we also present a few variants of this method which relax such estimation. Unlike general proximal type parameter free methods, these variants of the CGT method do not require any additional effort for computing (sub)gradients of the objective function and/or solving extra subproblems at each iteration. We then generalize these methods under stochastic setting and present a few new complexity results. To the best of our knowledge, this is the first time that such complexity results are presented for solving stochastic weakly smooth nonconvex and (strongly) convex optimization problems. [ABSTRACT FROM AUTHOR]

Detail enhancement algorithms are important for raw infrared images to improve their overall contrast and highlight important information in them. To solve the problems that current algorithms like GF&DDE have, an improved adaptive detail enhancement algorithm for infrared images based on a guided image filter is proposed in this paper. It chooses the threshold for the base layer image adaptively according to the histogram statistical information and adjusts the mapping range of the histograms according to the dynamic range of the image. Besides, the detail layer is handled by a simpler adaptive gain control method to achieve the good detail enhancement effect. Finally, the base layer and the detail are merged according to the approximate proportion of the background and the details. Experimental results show that the proposed algorithm can adaptively and efficiently enhance different dynamic range images in different scenarios. Moreover, this algorithm has high real-time performance. [ABSTRACT FROM AUTHOR]

Let G be a directed graph. A 2-directed block in G is a maximal vertex set C2d ⊆ V with ∣C2d∣ ≥ 2 such that for each pair of distinct vertices x, y ϵ C2d, there exist two vertex-disjoint paths from x to y and two vertex-disjoint paths from y to x in G. In this paper we present two algorithms for computing the 2-directed blocks of G in O(min{m, (tsap + tsb)n}n) time, where tsap is the number of the strong articulation points of G and tsb is the number of the strong bridges of G. Furthermore, we study two related concepts: the 2-strong blocks and the 2-edge blocks of G. We give two algorithms for computing the 2-strong blocks of G in O(min{m, tsapn}n) time and we show that the 2-edge blocks of G can be computed in O(min{m, tsbn}n) time. In this paper we also study some optimization problems related to the strong articulation points and the 2-blocks of a directed graph. Given a strongly connected graph G = (V,E), we want tofind a minimum strongly connected spanning subgraph G * = (V,E *) of G such that the strong articulation points of G coincide with the strong articulation points of G*. We show that there is a linear time 17/3 approximation algorithm for this NP-hard problem. We also consider the problem of finding a minimum strongly connected spanning subgraph with the same 2-blocks in a strongly connected graph G. We present approximation algorithms for three versions of this problem, depending on the type of 2-blocks. [ABSTRACT FROM AUTHOR]

Fast and accurate simulation of the electromagnetic field around frequency selective surfaces (FSSs) are needed for the design and optimization of devices based on the use of FSSs. The authors recently published a computationally efficient calculation method for the analysis of FSSs where the current distribution in the conducting parts are locally approximated by currents associated to electromagnetic waves propagating perpendicularly to the surface of the FSS. In this paper, an improved version of this method is presented. Here, in addition to the described assumption, local plane wave distribution of the current density is imposed also with respect to that surfaces being perpendicular to the surface of the FSS. By this modification, the error of the described calculations becomes very small in a very broad frequency range while the computational burden remains low, consequently the method can be advantageously applied for the solution of design and optimization problems. [ABSTRACT FROM PUBLISHER]

Despite the surrogate-based two-level algorithms that have been proposed for accelerating the optimization procedures, it may be still expensive for large problems. Therefore, this paper proposes the exploration of the approximation characteristics of the wavelet functions to define a coarse subspace for this kind of approach with relatively few float point operations. The wavelet transform is used to create the coarse model in a two-level genetic algorithm (GA), which is applied to a set of benchmark test problems. Although the coarse model is simpler and less accurate than the fine model, it behaves similarly to this last one and the original function. Moreover, the approach prevented the convergence to local minima whenever the GA presented such behavior and it is faster than the use of principal components analysis. [ABSTRACT FROM PUBLISHER]

In this paper, we consider computational methods for optimizing a multivariate inhomogeneous polynomial function over a general convex set. The focus is on the design and analysis of polynomial-time approximation algorithms. The methods are able to deal with optimization models with polynomial objective functions in any fixed degrees. In particular, we first study the problem of maximizing an inhomogeneous polynomial over the Euclidean ball. A polynomial-time approximation algorithm is proposed for this problem with an assured (relative) worst-case performance ratio, which is dependent only on the dimensions of the model. The method and approximation ratio are then generalized to optimize an inhomogeneous polynomial over the intersection of a finite number of co-centered ellipsoids. Furthermore, the constraint set is extended to a general convex compact set. Specifically, we propose a polynomial-time approximation algorithm with a (relative) worst-case performance ratio for polynomial optimization over some convex compact sets, e.g., a polytope. Finally, numerical results are reported, revealing good practical performance of the proposed algorithms for solving some randomly generated instances. [ABSTRACT FROM AUTHOR]

As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and wireless energy charging for wireless sensor networks, by devising improved approximation algorithms for it and its variants. The key ingredients in the algorithm design include exploiting the combinatorial properties of the problems and making use of tree decomposition and minimum weighted maximum matching techniques. Specifically, given a metric complete graph G and an integer k>0, we consider rootless, uncapacitated rooted, and capacitated rooted min-max cycle cover problems in G with an aim to find k rootless (or rooted) edge-disjoint cycles covering the vertices in V such that the maximum cycle weight among the k cycles is minimized. For each of the mentioned problems, we develop an improved approximate solution. That is, for the rootless min-max cycle cover problem, we develop a (5 1\over 3 +\epsilon)-approximation algorithm; for the uncapacitated rooted min-max cycle cover problem, we devise a (6 1\over 3 +\epsilon) -approximation algorithm; and for the capacitated rooted min-max cycle cover problem, we propose a (7+\epsilon)-approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems 6+\epsilon, 7+\epsilon, and 13+\epsilon, respectively, where \epsilon is a constant with 0< \epsilon <1. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the actual approximation ratios delivered by the proposed algorithms are always no more than 2, much better than their analytical counterparts. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm for the unconstrained minimization of a class of nonsmooth and nonconvex functions that can be written as finite-max functions. A gradient and function-based sampling method is proposed which, under special circumstances, either moves superlinearly to a minimizer of the problem of interest or improves the optimality certificate. Global and local convergence analysis are presented, as well as examples that illustrate the obtained theoretical results. [ABSTRACT FROM AUTHOR]

This paper focuses on two kinds of bi-objective topology optimization problems with uniform-stress constraints: compliance-volume minimization and local frequency response–volume minimization problems. An adaptive volume constraint (AVC) algorithm based on an improved bisection method is proposed. Using this algorithm, the bi-objective uniform-stress-constrained topology optimization problem is transformed into a single-objective topology optimization problem and a volume-decision problem. The parametric level set method based on the compactly supported radial basis functions is employed to solve the single-objective problem, in which a self-organized acceleration scheme based on shape derivative and topological sensitivity is proposed to adaptively adjust the derivative of the objective function and the step length during the optimization. To solve the volume-decision problem, an improved bisection method is proposed. Numerical examples are tested to illustrate the feasibility and effectiveness of the self-organized acceleration scheme and the AVC algorithm based on the improved bisection method. An extended application to the bi-objective stress-constrained topology optimization of a structure with stress concentration is also presented. [ABSTRACT FROM AUTHOR]

The inverse radiative transfer problem finds broad applications in medical imaging, atmospheric science, astronomy, and many other areas. This problem intends to recover optical properties, denoted as absorption and the scattering coefficient of the media, through source-measurement pairs. A typical computational approach is to form the inverse problem as a PDE-constraint optimization, with the minimizer being the to-be-recovered coefficients. The method is tested to be efficient in practice, but it lacks analytical justification: there is no guarantee of the existence or uniqueness of the minimizer, and the error is hard to quantify. In this paper, we provide a different algorithm by levering the ideas from singular decomposition analysis. Our approach is to decompose the measurements into three components, two of which encode the information of the two coefficients, respectively. We then split the optimization problem into two subproblems and use those two components to recover the absorption and scattering coefficients separately. In this regard, we prove the well-posedness of the new optimization, and the error could be quantified with better precision. In the end, we incorporate the diffusive scaling and show that the error is harder to control in the diffusive limit. [ABSTRACT FROM AUTHOR]

This paper explores methods for scheduling preventive maintenance by means of mathematical programming. Five integer linear programming models are posed, each based on a different optimality criterion dealing with manpower smoothing. By means of two hypothetical examples the models are tested for their computational properties. In addition to describing the experimental results of applying integer linear programming techniques to this class of problems, the paper also illustrates how effectively rounded linear programming solutions can be used as approximations to optimal solutions. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of recovering signals from undersampled data where such signals are not sparse in an orthonormal basis, but in an overcomplete dictionary. We show that if the combined matrix obeys a certain restricted isometry property and if the signal is sufficiently sparse, the reconstruction that relies on ℓ p minimization with 0 < p < 1 is exact. In addition, under a mild assumption about the dictionary D , we use a similar method [H. Rauhut et al., Compressed sensing and redundant dictionaries, IEEE Trans. Inf. Theory54(5) (2008) 2210–2219] to derive an estimation of the restricted isometry constant of the composed matrix A D. Finally, the performance of the ℓ p minimization is testified by some numerical examples. [ABSTRACT FROM AUTHOR]

Multistage stochastic optimization requires the definition and the generation of a discrete stochastic tree that represents the evolution of the uncertain parameters in time and space. The dimension of the tree is the result of a trade-off between the adaptability to the original probability distribution and the computational tractability. Moreover, the discrete approximation of a continuous random variable is not unique. The concept of the best discrete approximation has been widely explored and many enhancements to adjust and fix a stochastic tree in order to represent as well as possible the real distribution have been proposed. Yet, often, the same generation algorithm can produce multiple trees to represent the random variable. Therefore, the recent literature investigates the concept of distance between trees which are candidate to be adopted as stochastic framework for the multistage model optimization. The contribution of this paper is to compute the nested distance between a large set of multistage and multivariate trees and, for a sample of basic financial problems, to empirically show the positive relation between the tree distance and the distance of the corresponding optimal solutions, and between the tree distance and the optimal objective values. Moreover, we compute a lower bound for the Lipschitz constant that bounds the optimal value distance. [ABSTRACT FROM AUTHOR]

Abstract Matrix completion is a challenging problem with a range of real applications. Many existing methods are based on low-rank prior of the underlying matrix. However, this prior may not be sufficient to recover the original matrix from its incomplete observations. In this paper, we propose a novel matrix completion algorithm by employing the low-rank prior and a sparse prior simultaneously. Specifically, the matrix completion task is formulated as a rank minimization problem with a sparse regularizer. The low-rank property is modeled by the truncated nuclear norm to approximate the rank of the matrix, and the sparse regularizer is formulated as an ℓ 1 -norm term based on a given transform operator. To address the raised optimization problem, a method alternating between two steps is developed, and the problem involved in the second step is converted to several subproblems with closed-form solutions. Experimental results show the effectiveness of the proposed algorithm and its better performance as compared with the state-of-the-art matrix completion algorithms. Highlights • This paper proposes a novel matrix completion algorithm by employing a low-rank prior based on truncated nuclear norm and a sparse prior simultaneously. • To address the resulting optimization problem, a method alternating between two steps is developed, and the problem involved in the second step is converted to several subproblems with closed-form solutions. • Experimental results demonstrate the effectiveness of the proposed algorithm and its better performance as compared with the state-of-the-art matrix completion algorithms. [ABSTRACT FROM AUTHOR]

Shortest path query is one of the most fundamental and classic problems in graph analytics, which returns the complete shortest path between any two vertices. However, in many real-life scenarios, only critical vertices on the shortest path are desirable and it is unnecessary to search for the complete path. This paper investigates the shortest path sketch by defining a top- $k$ critical vertices ($k$ CV) query on the shortest path. Given a source vertex $s$ and target vertex $t$ in a graph, $k$ CV query can return the top- $k$ significant vertices on the shortest path $SP(s,t)$ . The significance of the vertices can be predefined. The key strategy for seeking the sketch is to apply off-line preprocessed distance oracle to accelerate on-line real-time queries. This allows us to omit unnecessary vertices and obtain the most representative sketch of the shortest path directly. We further explore a series of methods and optimizations to answer $k$ CV query on both centralized and distributed platforms, using exact and approximate approaches, respectively. We evaluate our methods in terms of time, space complexity and approximation quality. Experiments on large-scale real-world networks validate that our algorithms are of high efficiency and accuracy. [ABSTRACT FROM AUTHOR]

Numerical optimization is required in artifficial neural network to update weights iteratively for learning capability. In this paper, we propose the use of Approximate Greatest Descent (AGD) algorithm to optimize neural network weights using long-term backpropagation manner. The modiffication and development of AGD into stochastic diagonal AGD (SDAGD) algorithm could improve the learning ability and structural simplicity for deep learning neural networks. It is derived from the operation of a multi-stage decision control system which consists of two phases: (1) when local search region does not contain the minimum point, iteration shall be deffined at the boundary of the local search region, (2) when local region contains the minimum point, Newton method is approximated for faster convergence. The integration of SDAGD into Multilayered perceptron (MLP) network is investigated with the goal of improving the learning ability and structural simplicity. Simulation results showed that two-layer MLP with SDAGD achieved a misclassiffication rate of 9.4% on a smaller mixed national institute of national and technology (MNIST) dataset. MNIST is a database equipped with handwritten digits images suitable for algorithm prototyping in artifficial neural networks. [ABSTRACT FROM AUTHOR]

Weapon target allocation (WTA) is a classic NP-complete problem in the field of military operations research. In this paper, we addressed the multi-constraint WTA problems in multilayer defense scenario. To solve large-scale WTA problems effectively, a distributed MAX-MIN Ant System (MMAS) algorithm based on distributed computing framework Spark was developed and improved. An experiment environment comprising virtual machines was built for implementing the distributed MMAS. First, a small-scale WTA example, whose theoretical optimal solution can be obtained by existing optimization software, was taken as a benchmark problem to assess the performance of distributed MMAS. The result shows that it can find high-quality and robust approximate solutions. Then a large-scale WTA problem was constructed and used to further evaluate the performance of distributed MMAS in the experiment environment. The result shows that the distributed MMAS can also achieve high-quality approximate solutions with high robustness and computational efficiency even for large scale WTA problems. Our study demonstrates it is a promising approach for solving large-scale iteration-dependent optimization problems like WTA by means of incorporating heuristic optimization algorithms such as Ant Colony Optimization into distributed computing framework. [ABSTRACT FROM AUTHOR]

A typical interpolation strategy for line segments consists of a transition scheme, a Look-ahead ACC/DEC scheduling, and an interpolation algorithm. In these three parts, the main computation occurs in the first and second part. Some research work has been carried out to decrease the computation in the previous literatures, but these methods occupy a lot of computing resources for the optimization process during the calculation of transition curve parameters and feed rates. Consequently, the computational efficiency of interpolation strategy is greatly reduced. To deal with the issue, a real-time interpolation strategy is proposed in this paper. In the transition scheme, a Bézier curve is utilized to smooth the line segments. Based on the relationship among the approximation error, the approximation radius, and the transition curve, the curve can be directly generated when the approximation error is given. In the ACC/DEC scheduling, a 3-segment feed rate profile with jerk continuity is constructed. Meanwhile, a Look-ahead planning based on Backward Scanning and Forward Revision (BSFR) algorithm is utilized to eliminate redundant computation. Compared with Zhao’s and Shi’s strategy, the proposed strategy has the merits of C2 and G2 continuity for the tool path, jerk continuity for the tool movement, and distinguished real-time performance for interpolation. The experiments of 3D pentagram and 2D butterfly are carried out with different strategies and their results demonstrate that the interpolation efficiency can be greatly improved with the proposed strategy. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the separations and optimality conditions for the optimal solution defined by the improvement set of a constrained multiobjective optimization problem. We introduce a vector-valued regular weak separation function and a scalar weak separation function via a nonlinear scalarization function defined in terms of an improvement set. The nonlinear separation between the image of the multiobjective optimization problem and an improvement set in the image space is established by the scalar weak separation function. Saddle point type optimality conditions for the optimal solution of the multiobjective optimization problem are established, respectively, by the nonlinear and linear separation methods. We also obtain the relationships between the optimal solution and approximate efficient solution of the multiobjective optimization problem. Finally, sufficient and necessary conditions for the (regular) linear separation between the approximate image of the multiobjective optimization problem and a convex cone are also presented. [ABSTRACT FROM AUTHOR]

Approximation is central to many optimization problems and the supporting theory provides insight as well as foundation for algorithms. In this paper, we lay out a broad framework for quantifying approximations by viewing finite- and infinite-dimensional constrained minimization problems as instances of extended real-valued lower semicontinuous functions defined on a general metric space. Since the Attouch-Wets distance between such functions quantifies epi-convergence, we are able to obtain estimates of optimal solutions and optimal values through bounds of that distance. In particular, we show that near-optimal and near-feasible solutions are effectively Lipschitz continuous with modulus one in this distance. Under additional assumptions on the underlying metric space, we construct approximating functions involving only a finite number of parameters that still are close to an arbitrary extended real-valued lower semicontinuous functions. [ABSTRACT FROM AUTHOR]

The main result of this paper is motivated by the following two apparently unrelated graph optimization problems: (A) As an extension of Edmonds’ disjoint branchings theorem, characterize digraphs comprising k disjoint branchings Bi each having a specified number μi of arcs. (B) As an extension of Ryser’s maximum term rank formula, determine the largest possible matching number of simple bipartite graphs complying with degree-constraints. The solutions to these problems and to their generalizations will be obtained from a new min-max theorem on covering a supermodular function by a simple degree-constrained bipartite graph. A specific feature of the result is that its minimum cost extension is already NP-hard. Therefore classic polyhedral tools themselves definitely cannot be sufficient for solving the problem, even though they make some good service in our approach. [ABSTRACT FROM AUTHOR]

Multithreshold Entropy Linear Classifier (MELC) is a density based model which searches for a linear projection maximizing the Cauchy-Schwarz Divergence of dataset kernel density estimation. Despite its good empirical results, one of its drawbacks is the optimization speed. In this paper we analyze how one can speed it up through solving an approximate problem. We analyze two methods, both similar to the approximate solutions of the Kernel Density Estimation querying and provide adaptive schemes for selecting a crucial parameters based on user-specified acceptable error. Furthermore we show how one can exploit well known conjugate gradients and L-BFGS optimizers despite the fact that the original optimization problem should be solved on the sphere. All above methods and modifications are tested on 10 real life datasets from UCI repository to confirm their practical usability. [ABSTRACT FROM AUTHOR]

In this paper, we establish hardness and approximation results for various Lp-ball constrained homogeneous polynomial optimization problems, where p ∈ [2, ∞]. Specifically, we prove that for any given d ≥ 3 and p ∈ [2, ∞], both the problem of optimizing a degree-d homogeneous polynomial over the Lp-ball and the problem of optimizing a degree-d multilinear form (regardless of its super-symmetry) over Lp-balls are NP-hard. On the other hand, we show that these problems can be approximated to within a factor of Ω((log n)(d-2)/p/nd/2-1) in deterministic polynomial time, where n is the number of variables. We further show that with the help of randomization, the approximation guarantee can be improved to Ω((log n/n)d/2-1), which is independent of p and is currently the best for the aforementioned problems. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where p ∈ {2, ∞}. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of mathematical programs with robust equilibrium constraints represented by a system of semi-infinite complementarity constraints (SICC). We propose a numerical scheme for tackling SICC. Specifically, by relaxing the complementarity constraints and then randomizing the index set of SICC, we employ the well-known entropic risk measure to approximate the semi-infinite constraints with a finite number of stochastic inequality constraints. Under some moderate conditions, we quantify the approximation in terms of the feasible set and the optimal value. The approximation scheme is then applied to a class of two stage stochastic mathematical programs with complementarity constraints in combination with the polynomial decision rules. Finally, we extend the discussion to a mathematical program with distributionally robust equilibrium constraints, which is essentially a one stage stochastic program with semi-infinite stochastic constraints indexed by some probability measures from an ambiguity set defined through the KL-divergence. [ABSTRACT FROM AUTHOR]

Most conventional algorithms for non-Lambertian photometric stereo can be partitioned into two categories. The first category is built upon stable outlier rejection techniques while assuming a dense Lambertian structure for the inliers, and thus performance degrades when general diffuse regions are present. The second utilizes complex reflectance representations and non-linear optimization over pixels to handle non-Lambertian surfaces, but does not explicitly account for shadows or other forms of corrupting outliers. In this paper, we present a purely pixel-wise photometric stereo method that stably and efficiently handles various non-Lambertian effects by assuming that appearances can be decomposed into a sparse, non-diffuse component (e.g., shadows, specularities, etc.) and a diffuse component represented by a monotonic function of the surface normal and lighting dot-product. This function is constructed using a piecewise linear approximation to the inverse diffuse model, leading to closed-form estimates of the surface normals and model parameters in the absence of non-diffuse corruptions. The latter are modeled as latent variables embedded within a hierarchical Bayesian model such that we may accurately compute the unknown surface normals while simultaneously separating diffuse from non-diffuse components. Extensive evaluations are performed that show state-of-the-art performance using both synthetic and real-world images. [ABSTRACT FROM AUTHOR]

The paper deals with approximations of random sums. By random sum we mean a sum of random number of independent and identically distributed random variables. Distribution of this sum is called a compound distribution. The model is especially important in non-life insurance. There are many methods for approximating compound distributions, one of the most popular one is approximation with shifted gamma distribution. In this work we show an alternative way -- using kernel density, Fast Fourier Transform and numerical optimization methods -- for finding shifted gamma approximations and show results suggesting its superiority over classical method. [ABSTRACT FROM AUTHOR]

In this paper, we propose a model-hybrid approach for nonlinear optimization that employs both trust region method and quasi-Newton method, which can avoid possibly resolve the trust region subproblem if the trial step is not acceptable. In particular, unlike the traditional trust region methods, the new approach does not use a single approximate model from beginning to the end, but instead employs quadratic model or conic model at every iteration adaptively. We show that the new algorithm preserves the strong convergence properties of trust region methods. Numerical results are also presented. [ABSTRACT FROM AUTHOR]

In a classic optimization problem, the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In the case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multiobjective optimization problems. In this setting we are given a main objective function and a set of secondary objectives which are modeled via budget constraints. Multiobjective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely, approximate Pareto sets and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto sets, we devise truthful deterministic and randomized multicriteria fully polynomial-time approximation schemes (FPTASs) for multiobjective optimization problems whose exact version admits a pseudopolynomial-time algorithm, as, for instance, the multibudgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching,and matroid intersection. Our construction also applies to multidimensional knapsack and multiunit combinatorial auctions. Our FPTASs compute a (1+ε)-approximate solution violating each budget constraint by a factor (1+ ε). When feasible solutions induce an independence system, i.e., when subsets of feasible solutions are feasible as well, we present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint, where one wants to compute a minimum cost spanning tree whose length is at most a given value L. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time). This result can be derandomized in the case of integral lengths. All the mentioned results match the best known approximation ratios, which are, however, obtained by nontruthful algorithms. [ABSTRACT FROM AUTHOR]

Because of their complex behavior, wastewater treatment processes (WWTPs) are very difficult to control. In this paper, the design and implementation of a nonlinear model-predictive control (NMPC) system are discussed. The proposed NMPC comprises a self-organizing radial basis function neural network (SORBFNN) identifier and a multiobjective optimization method. The SORBFNN with concurrent structure and parameter learning is developed as a model identifier for approximating the online states of dynamic systems. Then, the solution of the multiobjective optimization is obtained by a gradient method which can shorten the solution time of optimal control problems. Moreover, the conditions for the stability analysis of NMPC are presented. Experiments reveal that the proposed control technique gives satisfactory tracking and disturbance rejection performance for WWTPs. Experimental results on a real WWTP show the efficacy of the proposed NMPC for industrial processes in many applications. [ABSTRACT FROM PUBLISHER]

The limited memory BFGS method (L-BFGS) is an adaptation of the BFGS method for large-scale unconstrained optimization. However, The L-BFGS method need not converge for nonconvex objective functions and it is inefficient on highly ill-conditioned problems. In this paper, we proposed a regularization strategy on the L-BFGS method, where the used regularization parameter may play a compensation role in some sense when the condition number of Hessian approximation tends to become ill-conditioned. Then we proposed a regularized L-BFGS method and established its global convergence even when the objective function is nonconvex. Numerical results show that the proposed method is efficient. [ABSTRACT FROM AUTHOR]

The general methodology of the interpolation theory of potential fields (gravity and magnetic anomalies), and, primarily, the three fundamental ideas underlying this methodology-(I) approximation, (II) linearization, and (III) optimization-are the matter of the utmost importance. The rationale of these ideas and the ways of their practical implementation are discussed in this paper. [ABSTRACT FROM AUTHOR]

In this paper, as an extension of a previous study, an improved approximation for the Gaussian Q-function is presented. The nonlinear least squares algorithm is employed to optimize the coefficients of the proposed approximation. The accuracy of the presented approximation is evaluated using extensive computer simulations. Results show that the proposed approximation has superior accuracy in high arguments' region when compared to the performance of other approaches introduced in the literature. [ABSTRACT FROM AUTHOR]

The set of polynomials that are nonnegative over a subset of the nonnegative orthant (we call them set-semidefinite) have many uses in optimization. A common example of this type set is the set of copositive matrices, where we are effectively considering nonnegativity over the entire nonnegative orthant and are restricted to homogeneous polynomials of degree two. Lasserre (SIAM J. Optim., 21(3):864-885, ) has previously considered a method using moments in order to provide an outer approximation to this set, for nonnegativity over a general subset of the real space. In this paper, we shall show that, in the special case of considering nonnegativity over a subset of the nonnegative orthant, we can provide a new outer approximation hierarchy. This is based on restricting moment matrices to be completely positive, and it is at least as good as Lasserre's method. This can then be relaxed to give tractable approximations that are still at least as good as Lasserre's method. In doing this, we also provide interesting new insights into the use of moments in constructing these approximations. [ABSTRACT FROM AUTHOR]

The paper studies stochastic optimization (programming) problems with compound functions containing expectations and extreme values of other random functions as arguments. Compound functions arise in various applications. A typical example is a variance function of nonlinear outcomes. Other examples include stochastic minimax problems, econometric models with latent variables, and multilevel and multicriteria stochastic optimization problems. As a solution technique a sample average approximation (SAA) method (also known as statistical or empirical (sample) mean method) is used. The method consists in approximation of all expectation functions by their empirical means and solving the resulting approximate deterministic optimization problems. In stochastic optimization, this method is widely used for optimization of standard expectation functions under constraints. In this paper, SAA method is extended to general compound stochastic optimization problems. The conditions for convergence in mean, almost surely, and rate of convergence are established. The study of the convergence rate is based on properties of Rademacher averages of functional sets, concentration inequalities for bounded random functions, and the concept of uniform normalized convergence of random variables. The convergence results are applicable both for discrete and continuous stochastic optimization problems. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of a heuristic approach to possibilistic clustering. The approach is based on the concept of allotment among fuzzy clusters. The paper provides the description of basic concepts of the heuristic approach to possibilistic clustering. Plans of direct prototype-based heuristic algorithms of possibilistic clustering based on a transitive approximation of a fuzzy tolerance are described in detail. An illustrative example of application of the basic version of the proposed algorithms to Sneath and Sokal's two-dimensional data set is considered. Preliminary conclusions are formulated. [ABSTRACT FROM AUTHOR]

Network throughput and energy consumption are two important performance metrics for a multihop wireless network. Current state-of-the-art research is limited to either maximizing throughput under some energy constraint or minimizing energy consumption while satisfying some throughput requirement. Although many of these prior efforts were able to offer some optimal solutions, there is still a critical need to have a systematic study on how to optimize both objectives simultaneously. In this paper, we take a multicriteria optimization approach to offer a systematic study on the relationship between the two performance objectives. To focus on throughput and energy performance, we simplify link layer scheduling by employing orthogonal channels among the links. We show that the solution to the multicriteria optimization problem characterizes the envelope of the entire throughput-energy region, i.e., the so-called optimal throughput-energy curve. We prove some important properties of the optimal throughput-energy curve. For case study, we consider both linear and nonlinear throughput functions. For the linear case, we characterize the optimal throughput-energy curve precisely through parametric analysis, while for the nonlinear case, we use a piecewise linear approximation to approximate the optimal throughput-energy curve with arbitrary accuracy. Our results offer important insights on exploiting the tradeoff between the two performance metrics. [ABSTRACT FROM PUBLISHER]

In this paper, to the semi-infinite optimization problem (P) , we attach the approximated semi-infinite optimization problems (P1,0) , (P0,1) and (P1,1) and some connections between the optimal solutions of the problems (P) , (P1,0) , (P0,1) and (P1,1) are given. [ABSTRACT FROM AUTHOR]

In this article the author reflects on the implication of post-decision states and separable approximations for approximate dynamic programming. He states that separable approximation works well for models of dynamic resource management. He appreciates Warren Powell's 2010 paper "Merging AI and OR to Solve High-Dimensional Stochastic Optimization Problems Using Approximate Dynamic Programming" which discusses the distribution of random variables.

In this paper, we introduce and study the notion of low risk mechanisms . Intuitively, we say a mechanism is a low risk mechanism if the randomization of the mechanism does not affect the utility of agents by a lot. Specifically, we desire to design mechanisms in which the variances of the utility of agents are small . Inspired by this work, later, Procaccia et al. (0000) study the approximation–variance tradeoffs in mechanism design. In particular, here we present a low risk mechanism for the pairwise kidney exchange game . This game naturally appears in situations that some service providers benefit from pairwise allocations on a network, such as the kidney exchanges between hospitals. Ashlagi et al. (2013) present a 2-approximation randomized truthful mechanism for this problem. This is the best-known result in this setting with multiple players. However, we note that the variance of the utility of an agent in this mechanism may be as large as Ω ( n 2 ) , where n is the number of vertices. Indeed, this is not desirable in a real application. In this paper, we resolve this issue by providing a 2-approximation randomized truthful mechanism in which the variance of the utility of each agent is at most 2 + ϵ . As a side result, we apply our technique to design a deterministic mechanism such that, if an agent deviates from the mechanism, she does not gain more than 2 ⌈ log 2 m ⌉ , where m is the number of players. [ABSTRACT FROM AUTHOR]

Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulation has a weak relaxation bound and is quite difficult to solve. In this paper, we review some recent results on improving the relaxation bounds and constructing approximate solutions for MILP formulations of chance constraints. We also discuss a recently introduced bicriteria approximation algorithm for covering type chance constrained problems. This algorithm uses a relaxation to construct a solution whose (constraint violation) risk level may be larger than the pre-specified threshold, but is within a constant factor of it, and whose objective value is also within a constant factor of the true optimal value. Finally, we present some new results that improve on the bicriteria approximation factors in the finite scenario setting and shed light on the effect of strong relaxations on the approximation ratios. [ABSTRACT FROM AUTHOR]

We study the max-min fair allocation problem in which a set of m indivisible items are to be distributed among n agents such that the minimum utility among all agents is maximized. In the restricted setting, the utility of each item j on agent i is either 0 or some non-negative weight wj. For this setting, Asadpour et al. (ACM Trans Algorithms 8(3):24, 2012) showed that a certain configuration-LP can be used to estimate the optimal value to within a factor of 4+δ, for any δ>0, which was recently extended by Annamalai et al. (in: Indyk (ed) Proceedings of the twenty-sixth annual ACMSIAM symposium on discrete algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015) to give a polynomial-time 13-approximation algorithm for the problem. For hardness results, Bezáková and Dani (SIGecom Exch 5(3):11-18, 2005) showed that it is NP-hard to approximate the problem within any ratio smaller than 2. In this paper we consider the (1,ϵ)-restricted max-min fair allocation problem in which each item j is either heavy (wj=1) or light (wj=ϵ), for some parameter ϵ∈(0,1). We show that the (1,ϵ)-restricted case is also NP-hard to approximate within any ratio smaller than 2. Using the configuration-LP, we are able to estimate the optimal value of the problem to within a factor of 3+δ, for any δ>0. Extending this idea, we also obtain a quasi-polynomial time (3+4ϵ)-approximation algorithm and a polynomial time 9-approximation algorithm. Moreover, we show that as ϵ tends to 0, the approximation ratio of our polynomial-time algorithm approaches 3+22≈5.83. [ABSTRACT FROM AUTHOR]

In this paper, an approximation on the distribution of population densities and the arrangement of urban activities, over a set of n locations, is derived by using the classical multiobjective optimization theory and Shannon entropy. [ABSTRACT FROM AUTHOR]

Recently, there has been growing interest in developing optimization methods for solving large-scale machine learning problems. Most of these boil down to the problem of minimizing an average of a finite set of smooth and strongly convex functions where the number of functions n is large. The gradient descent (GD) method is successful in minimizing convex problems at a fast linear rate; however, it is not applicable to the considered large-scale optimization setting because of the high computational complexity. Incremental methods resolve this drawback of gradient methods by replacing the required gradient for the descent direction with an incremental gradient approximation. They operate by evaluating one gradient per iteration and executing the average of the n available gradients as an approximate gradient. Although incremental methods reduce the computational cost of GD, their convergence rates do not justify their advantage relative to GD in terms of the total number of gradient evaluations until convergence. In this paper, we introduce a double incremental aggregated gradient method (DIAG) that computes the gradient of only one function at each iteration, which is chosen based on a cyclic scheme, and uses the aggregated average gradient of all the functions to approximate the full gradient. The iterates of the proposed DIAG method uses averages of both iterates and gradients in contrast to classic incremental methods that utilize gradient averages but do not utilize iterate averages. We prove that not only does the proposed DIAG method converge linearly to the optimal solution, but also its linear convergence factor justifies the advantage of incremental methods over GD. In particular, we prove that the worstcase performance of DIAG is better than the worst-case performance of GD. Numerical experiments on quadratic programming and logistic regression problems showcase the advantage of DIAG relative to GD and other incremental methods. [ABSTRACT FROM AUTHOR]

In this contribution, a new framework for -optimal reduction is presented, motivated by the local nature of both (tangential) interpolation and -optimal approximations. The main advantage is given by a decoupling of the cost of reduction from the cost of optimization, resulting in a significant speedup in -optimal reduction. In addition, a middle-sized surrogate model is produced at no additional cost and can be used e.g. for error estimation. Numerical examples illustrate the new framework, showing its effectiveness in producing -optimal reduced models at a far lower cost than conventional algorithms. Detailed discussions and optimality proofs are presented for applying this framework to the reduction of multiple-input, multiple-output linear dynamical systems. The paper ends with a brief discussion on how this framework could be extended to other system classes, thus indicating how this truly is a general framework for interpolatory reduction. [ABSTRACT FROM AUTHOR]