Search

In this paper, to introduce approximate efficiency notions in variable ordering structures, some coradiant-valued maps are dealt with. Approximate nondominated and minimal elements are defined and some of their properties are studied. Corresponding to these concepts, necessary and sufficient conditions are provided. To obtain such conditions, some scalarization methods are investigated. The paper also investigates possible relationships between the Pascoletti-Serafini radial scalarization, approximate efficiency, approximate nondominance, and minimality utilizing some coradiant-valued maps. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of an efficient parallel implementation of the active-set Newton algorithm (ASNA), which is used to estimate the nonnegative weights of linear combinations of the atoms in a large-scale dictionary to approximate an observation vector by minimizing the Kullback–Leibler divergence between the observation vector and the approximation. The performance of ASNA has been proved in previous works against other state-of-the-art methods. The implementations analysed in this paper have been developed in C, using parallel programming techniques to obtain a better performance in multicore architectures than the original MATLAB implementation. Also a hardware analysis is performed to check the influence of CPU frequency and number of CPU cores in the different implementations proposed. The new implementations allow ASNA algorithm to tackle real-time problems due to the execution time reduction obtained. [ABSTRACT FROM AUTHOR]

In this paper, we consider a modified version of the control problem in a model free Markov decision process (MDP) setting with large state and action spaces. The control problem most commonly addressed in the contemporary literature is to find an optimal policy which maximizes the value function, i.e., the long run discounted reward of the MDP. The current settings also assume access to a generative model of the MDP with the hidden premise that observations of the system behaviour in the form of sample trajectories can be obtained with ease from the model. In this paper, we consider a modified version, where the cost function is the expectation of a non-convex function of the value function without access to the generative model. Rather, we assume that a sample trajectory generated using a priori chosen behaviour policy is made available. In this restricted setting, we solve the modified control problem in its true sense, i.e., to find the best possible policy given this limited information. We propose a stochastic approximation algorithm based on the well-known cross entropy method which is data (sample trajectory) efficient, stable, robust as well as computationally and storage efficient. We provide a proof of convergence of our algorithm to a policy which is globally optimal relative to the behaviour policy. We also present experimental results to corroborate our claims and we demonstrate the superiority of the solution produced by our algorithm compared to the state-of-the-art algorithms under appropriately chosen behaviour policy. [ABSTRACT FROM AUTHOR]

This paper introduces a novel technique to approximate a given continuous function f defined on a real compact interval by a new class of zipper α -fractal functions which contain a scaling vector and a binary vector or signature. For specific choices of scaling and signature vectors, the corresponding zipper fractal functions simultaneously interpolate and approximate f. When signature is zero, the proposed zipper fractal functions coincide with existing α -fractal functions. Hence, the zipper approximation proposed in this manuscript generalizes the existing fractal and classical approximations. Zipper fractal analogue of some elementary results in the classical approximation theory are obtained. Using convex optimization technique, we investigate the existence of optimal zipper fractal function for a given continuous function. The parameter identification problems for zipper α -fractal approximants are investigated. We derive sufficient conditions on the parameters of zipper α -fractal functions so that these functions preserve the positivity, monotonicity and convexity of the original function f. Also, we have studied the constructions of k-times continuously differentiable zipper α -fractal functions and one sided zipper fractal approximants for f. Numerical illustrations are provided to support the proposed theoretical results on zipper α -fractal functions. [ABSTRACT FROM AUTHOR]

This paper investigates a meta-heuristic (MH) for the Pareto-optimal dissimilar path problem (DPP) (PDPP) whose solution is a set composed of at least two different paths. The objective vector of a PDPP includes some conflicting objectives: on the one hand, the average path measures such as the length and risk of paths in a solution must be kept low and, on the other hand, the dissimilarity among these paths should be kept high. The dissimilarity of the DPP is a measure of a paths set with cardinality no less than two. However, just one path can be extracted from a chromosome in the existing MHs for various path problems. This results in a great difficulty to evaluate the chromosome in the existing MHs when we apply them to solve DPP and, consequently, there exists no MH for solving the DPP so far. In this paper, a new decoding approach of a chromosome is first explored and, with this approach, a set of paths can be extracted from a chromosome. By combining the simulated annealing (SA), in which the new decoding approach is adopted, with the well-known greedy randomized adaptive search procedure (GRASP), a SA-based GRASP for the PDPP is proposed. The proposed algorithm is compared against a most recent heuristic, whose performance is better than all of the early approaches, for the PDPP and the experimental results show that the proposed algorithm is able to quickly create superior approximation of the efficient set of the PDPP than the existing solution approaches for the PDPP. [ABSTRACT FROM AUTHOR]

In this paper, we consider k-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when k is fixed. We focus first on the case without backorders and we give a (2k-1)-approximation algorithm under general assumptions on the evolution of the holding costs as products move toward the final customers. We then improve this result to a k-approximation when the holding costs are monotonically non-increasing or non-decreasing (which is a natural situation in practice). Finally we address problems with backorders: we give a 3-approximation for the one-warehouse multi-retailer problem with backlog and a k-approximation algorithm for the k-level Joint Replenishment Problem with backlog (a variant where inventory can only be kept at the final retailers). Ours results are the first constant approximation algorithms for those problems. In addition, we demonstrate the potential of our approach on a practical case. Our preliminary experiments show that the average optimality gap is around 15%. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of fitting the B-spline curves to a set of ordered points, by finding the control points and the location parameters. The presented method takes two main steps: specifying initial B-spline curve and optimization. The method determines the number and the position of control points such that the initial B-spline curve is very close to the target curve. The proposed method introduces a length parameter in which this allows us to adjust the number of the control points and increases the precision of the initial B-spline curve. Afterwards, the scaled BFGS algorithm is used to optimize the control points and the foot points simultaneously and generates the final curve. Furthermore, we present a new procedure to insert a new control point and repeat the optimization method, if it is necessary to modify the fitting accuracy of the generated B-spline fitting curve. Associated examples are also offered to show that the proposed approach performs accurately for complex shapes with a large number of data points and is able to generate a precise fitting curve with a high degree of approximation. [ABSTRACT FROM AUTHOR]

The increasing popularity of location-based applications creates new opportunities for users to travel together. In this paper, we study a novel spatio-social optimization problem, i.e., Optimal Group Route, for multi-user itinerary planning. With our problem formulation, users can individually specify sources and destinations, preferences on the Point-of-interest (POI) categories, as well as the distance constraints. The goal is to find a itinerary that can be traversed by all the users while maximizing the group’s preference of POI categories in the itinerary. Our work advances existing group trip planning studies by maximizing the group’s social experience. To this end, individual preferences of POI categories are aggregated by considering the agreement and disagreement among group members. Furthermore, planning a multi-user itinerary on large road networks is computationally challenging. We propose two efficient greedy algorithms with bounded approximation ratio, one exact solution which computes the optimal itinerary by exploring a limited number of paths in the road network, and a scaled approximation algorithm to speed up the dynamic programming employed by the exact solution. We conduct extensive empirical evaluations on two real-world road network/POI datasets and our results confirm the effectiveness and efficiency of our solutions. [ABSTRACT FROM AUTHOR]

Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a convex and compact set and the uncertainty set is convex and compact, then robust solutions are also optimal for the corresponding ARO problem. Furthermore, we prove that if some of the uncertain parameters are constraint-wise and the rest are not, then under a similar set of assumptions there is an optimal decision rule for the ARO problem that does not depend on the constraint-wise uncertain parameters. Also, we show for a class of problems that using affine decision rules that depend on all of the uncertain parameters yields the same optimal objective value as when the rules depend solely on the non-constraint-wise uncertain parameters. Finally, we illustrate the usefulness of these results by applying them to convex quadratic and conic quadratic problems. [ABSTRACT FROM AUTHOR]

In this paper we propose a method for solving systems of nonlinear inequalities with predefined accuracy based on nonuniform covering concept formerly adopted for global optimization. The method generates inner and outer approximations of the solution set. We describe the general concept and three ways of numerical implementation of the method. The first one is applicable only in a few cases when a minimum and a maximum of the constraints convolution function can be found analytically. The second implementation uses a global optimization method to find extrema of the constraints convolution function numerically. The third one is based on extrema approximation with Lipschitz under- and overestimations. We obtain theoretical bounds on the complexity and the accuracy of the generated approximations as well as compare proposed approaches theoretically and experimentally. [ABSTRACT FROM AUTHOR]

This paper considers the numerical approximation for the optimal supporting position and related optimal control of a catalytic reaction system with some control and state constraints, which is governed by a nonlinear partial differential equations with given initial and boundary conditions. By the Galerkin finite element method, the original problem is projected into a semi-discrete optimal control problem governed by a system of ordinary differential equations. Then the control parameterization method is applied to approximate the control and reduce the original system to an optimal parameter selection problem, in which both the position and related control are taken as decision variables to be optimized. This problem can be solved as a nonlinear optimization problem by a particle swarm optimization algorithm. The numerical simulations are given to illustrate the effectiveness of the proposed numerical approximation method. [ABSTRACT FROM AUTHOR]

This paper considers a class of vector variational inequalities. First, we present an equivalent formulation, which is a scalar variational inequality, for the deterministic vector variational inequality. Then we concentrate on the stochastic circumstance. By noting that the stochastic vector variational inequality may not have a solution feasible for all realizations of the random variable in general, for tractability, we employ the expected residual minimization approach, which aims at minimizing the expected residual of the so-called regularized gap function. We investigate the properties of the expected residual minimization problem, and furthermore, we propose a sample average approximation method for solving the expected residual minimization problem. Comprehensive convergence analysis for the approximation approach is established as well. [ABSTRACT FROM AUTHOR]

This paper presents a real-time solution method of the maximum divert trajectory optimization problem for planetary landing. In mid-course, the vehicle is to abort and retarget to a landing site as far from the nominal as physically possible. The divert trajectory must satisfy velocity constraints in the range and cross range directions and a total speed constraint. The thrust magnitude is bounded above and below so that once on, the engine cannot be turned off. Because this constraint is not convex, it is relaxed to a convex constraint and lossless convexification is proved. A transformation of variables is introduced in the nonlinear dynamics and an approximation is made so that the problem becomes a second-order cone problem, which can be solved to global optimality in polynomial time whenever a feasible solution exists. A number of examples are solved to illustrate the effectiveness and efficiency of the solution method. [ABSTRACT FROM AUTHOR]

In this paper we present a stability analysis of a stochastic optimization problem with stochastic second order dominance constraints. We consider a perturbation of the underlying probability measure in the space of regular measures equipped with pseudometric discrepancy distance (Römisch in Stochastic Programming. Elsevier, Amsterdam, pp 483–554, 2003 ). By exploiting a result on error bounds in semi-infinite programming due to Gugat (Math Program Ser B 88:255–275, 2000 ), we show under the Slater constraint qualification that the optimal value function is Lipschitz continuous and the optimal solution set mapping is upper semicontinuous with respect to the perturbation of the probability measure. In particular, we consider the case when the probability measure is approximated by an empirical probability measure and show an exponential rate of convergence of the sequence of optimal solutions obtained from solving the approximation problem. The analysis is extended to the stationary points. [ABSTRACT FROM AUTHOR]

In this paper we illustrate some optimization challenges in the structured low rank approximation (SLRA) problem. SLRA can be described as the problem of finding a low rank approximation of an observed matrix which has the same structure as this matrix (such as Hankel). We demonstrate that the optimization problem arising is typically very difficult: in particular, the objective function is multiextremal even for simple cases. The main theme of the paper is to suggest that the difficulties described in approximating a solution of the SLRA problem open huge possibilities for the application of stochastic methods of global optimization. [ABSTRACT FROM AUTHOR]

The aim of this paper is to open up a new perspective on set and shape optimization by establishing a theory of Galerkin approximations to the space of convex and compact subsets of R d with favorable properties, both from a theoretical and from a computational perspective. Galerkin spaces consisting of polytopes with fixed facet normals are first explored in depth and then used to solve optimization problems in the space of convex and compact subsets of R d approximately. [ABSTRACT FROM AUTHOR]

The tolerance of an element of a combinatorial optimization problem with respect to its optimal solution is the maximum change of the cost of the element while preserving the optimality of the given optimal solution and keeping all other input data unchanged. Tolerances play an important role in the design of exact and approximation algorithms, but the computation of tolerances requires additional computational time. In this paper, we concentrate on combinatorial optimization problems for which the computation of all tolerances and an optimal solution have almost the same computational complexity as of finding an optimal solution only. We summarize efficient computational methods for computing tolerances for these problems and determine their time complexity experimentally. [ABSTRACT FROM AUTHOR]

Often decision makers have to cope with a programming problem with unknown quantitities. Then they will estimate these quantities and solve the problem as it then appears-the 'approximate problem'. Thus there is a need to establish conditions which will ensure that the solutions to the approximate problem will come close to the solutions to the true problem in a suitable manner. Confidence sets, i.e. sets that cover the true sets with a given prescribed probability, provide useful quantitative information. In this paper we consider multiobjective problems and derive confidence sets for the sets of efficient points, weakly efficient points, and the corresponding solution sets. Besides the crucial convergence conditions for the objective and/or constraint functions, one approach for the derivation of confidence sets requires some knowledge about the true problem, which may be not available. Therefore also another method, called relaxation, is suggested. This approach works without any knowledge about the true problem. The results are applied to the Markowitz model of portfolio optimization. [ABSTRACT FROM AUTHOR]

Modern problems of optimization, estimation, signal and image processing, pattern recognition, etc., deal with huge-dimensional data; this necessitates elaboration of efficient methods of processing such data. The idea of building low-dimensional approximations to huge data arrays is in the heart of the modern data analysis. One of the most appealing methods of compact data representation is the statistical method referred to as the principal component analysis; however, it is sensitive to uncertainties in the available data and to the presence of outliers. In this paper, robust versions of the principle component analysis approach are proposed along with numerical methods for their implementation. [ABSTRACT FROM AUTHOR]

In advanced tomographic experiments, large detector sizes and large numbers of acquired datasets can make it difficult to process the data in a reasonable time. At the same time, the acquired projections are often limited in some way, for example having a low number of projections or a low signal-to-noise ratio. Direct analytical reconstruction methods are able to produce reconstructions in very little time, even for large-scale data, but the quality of these reconstructions can be insufficient for further analysis in cases with limited data. Iterative reconstruction methods typically produce more accurate reconstructions, but take significantly more time to compute, which limits their usefulness in practice. In this paper, we present the application of the SIRT-FBP method to large-scale real-world tomographic data. The SIRT-FBP method is able to accurately approximate the simultaneous iterative reconstruction technique (SIRT) method by the computationally efficient filtered backprojection (FBP) method, using precomputed experiment-specific filters. We specifically focus on the many implementation details that are important for application on large-scale real-world data, and give solutions to common problems that occur with experimental data. We show that SIRT-FBP filters can be computed in reasonable time, even for large problem sizes, and that precomputed filters can be reused for future experiments. Reconstruction results are given for three different experiments, and are compared with results of popular existing methods. The results show that the SIRT-FBP method is able to accurately approximate iterative reconstructions of experimental data. Furthermore, they show that, in practice, the SIRT-FBP method can produce more accurate reconstructions than standard direct analytical reconstructions with popular filters, without increasing the required computation time. [ABSTRACT FROM AUTHOR]

Reliability-based design optimization (RBDO) has been widely used to design engineering products with minimum cost function while meeting reliability constraints. Although uncertainties, such as aleatory uncertainty and epistemic uncertainty, have been well considered in RBDO, they are mainly considered for model input parameters. Model uncertainty, i.e., the uncertainty of model bias indicating the inherent model inadequacy for representing the real physical system, is typically overlooked in RBDO. This paper addresses model uncertainty approximation in a product design space and further integrates the model uncertainty into RBDO. In particular, a copula-based bias modeling approach is proposed and results are demonstrated by two vehicle design problems. [ABSTRACT FROM AUTHOR]

Multi-instance multi-label learning (MIML) is an innovative learning framework where each sample is represented by multiple instances and associated with multiple class labels. In several learning situations, the multi-instance multi-label RBF neural networks (MIMLRBF) can exploit connections between the instances and the labels of an MIML example directly, while most of other algorithms cannot learn that directly. However, the singular value decomposition (SVD) method used to compute the weights of the output layer will cause augmented overall error in network performance when training data are noisy or not easily discernible. This paper presents an improved approach to learning algorithms used for training MIMLRBF. The steepest descent (SD) method is used to optimize the weights after they are initialized by the SVD method. Comparing results employing diverse learning strategies shows interesting outcomes as have come out of this paper. [ABSTRACT FROM AUTHOR]

In this paper, a new method is proposed to promote the efficiency and accuracy of nonlinear interval-based programming (NIP) based on approximation models and a local-densifying method. In conventional NIP methods, searching for the response bounds of objective and constraints are required at each iteration step, which forms a nested optimization and leads to extremely low efficiency. In order to reduce the computational cost, approximation models based on radial basis functions (RBF) are used to replace the actual computational models. A local-densifying method is suggested to guarantee the accuracy of the approximation models by reconstructing them with densified samples in iterations. Thus, through a sequence of optimization processes, an optimal result with fine accuracy can be finally achieved. Two numerical examples are used to test the effectiveness of the present method, and it is then applied to a practical engineering problem. [ABSTRACT FROM AUTHOR]

In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization of a multi-linear tensor function over the Cartesian product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which are shown to be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids centered at the origin, and propose polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating the effectiveness of the approximation algorithms studied. [ABSTRACT FROM AUTHOR]

Abstract  This paper describes a new method for approximate global optimization using convexity estimation of a multi-peaked or partially non-convex response surface. This method is based on convexity estimation of a response surface and a cell-based clustering technique. Convexity of an approximated function is estimated from the Hessian matrix and its eigenvalue. For this purpose, a Kriging-based convexity estimation method is also introduced in this paper. At first, a formulation for the convexity estimation with the Kriging method is provided. The convexity of an objective function at each location is estimated without using a finite difference based technique. With using this convexity estimation and a cell-based clustering technique, convex clusters are constructed in a solution space. The global optimization is performed with iterative local optimization to the convex clusters. From the numerical results, validity and effectiveness of the proposed method are confirmed. [ABSTRACT FROM AUTHOR]

Inspired by previous works on approximations of optimization problems and recent papers on the approximation of Walrasian and Nash equilibria and on stochastic variational inequalities, the present paper investigates the approximation of Nash equilibria and clarifies the conditions required for the convergence of the approximate equilibria via a direct approach, a variational approach, and an optimization approach. Besides directly addressing the issue of convergence of Nash equilibria via approximation, our investigation leads to a deeper understanding of various notions of functional convergence and their interconnections; more importantly, the investigation yields improved conditions for convergence of the approximate Nash equilibria via the variational approach. An illustrative application of our results to the approximation of a Nash equilibrium in a competitive capacity expansion model under uncertainty is presented. [ABSTRACT FROM AUTHOR]

This paper deals with optimal control problems described by higher index DAEs. We introduce a class of these problems which can be transformed to index one control problems. For this class of higher index DAEs, we derive first-order approximations and adjoint equations for the functionals defining the problem. These adjoint equations are then used to state, in the accompanying paper, the necessary optimality conditions in the form of a weak maximum principle. The constructive way used to prove these optimality conditions leads to globally convergent algorithms for control problems with state constraints and defined by higher index DAEs. [ABSTRACT FROM AUTHOR]

This paper deals with optimal control problems described by higher index DAEs. We introduce a class of problems which can be transformed to index one control problems. For these problems we show in the accompanying paper that, if the solutions to the adjoint equations are well-defined, then the first-order approximations to the functionals defining the problem can be expressed in terms of the adjoint variables. In this paper we show that the solutions to the adjoint equations are essentially bounded measurable functions. Then, based on the first order approximations, we derive the necessary optimality conditions for the considered class of control problems. These conditions do not require the transformation of the DAEs to index-one system; however, higher-index DAEs and their associated adjoint equations have to be solved. [ABSTRACT FROM AUTHOR]

In this paper, we study quasistatic abstract variational inequalities with time-dependent constraints. We prove existence results and present an approximation method valid for nonsmooth constraints. Then, we apply our results to the approximation of the quasistatic evolution of an elastic body in bilateral contact with a rigid foundation. The contact involves viscous friction of the Tresca or Coulomb type.We prove existence results for approximate problems and give a full asymptotic analysis, proving strong or weak convergence results. Our work is motivated by the numerical study in the paper [Delost, M.: Quasistatic Problem with Frictional Contact: Comparison between Numerical Methods and Asymptotic Analysis Related to Semi Discrete and Fully Discrete Approximations. University of Nice, Nice (2007, to appear)] and explains the choice of the approximation made in it. [ABSTRACT FROM AUTHOR]

The paper discusses several versions of the method of shortest residuals, a specific variant of the conjugate gradient algorithm, first introduced by Lemaréchal and Wolfe and discussed by Hestenes in a quadratic case. In the paper we analyze the global convergence of the versions considered. Numerical comparison of these versions of the method of shortest residuals and an implementation of a standard Polak–Ribière conjugate gradient algorithm is also provided. It supports the claim that the method of shortest residuals is a viable technique, competitive to other conjugate gradient algorithms. [ABSTRACT FROM AUTHOR]

The design of sparse array which is able to achieve good performance of beam-pattern satisfying the minimum peak sidelobe level (PSL) with the number of sensors as few as possible is a research area of increasing interest. This paper presents a method for planar optimization with sensor selection via convex optimization in condition of constrained beam-pattern. In the optimization procedure, the solution algorithm is based on convex optimization including a reweighted l- norm minimization. The objective is the minimum of the number of sensors and the PSL. Sparse array is obtained by removing those sensors with weights equal to zero or approximately equal to zero. In this paper, we also give the optimization algorithm respectively by row, column and the intersection on the basis of the linear array optimization. Numerical results are included, which illustrate the optimum method for planar arrays overall performs better than the other methods presented above for sensor selection. [ABSTRACT FROM AUTHOR]

In this paper we utilize a generalized weakly contractive mapping to establish some best proximity point results which are global optimization results for finding the minimum distances between two sets. Amongst many approaches to this problem, we adopt the approach where the problem is treated as that of finding global optimal approximate solution of the fixed point equation for the generalized weak contraction mapping. We use three control functions to define such mappings. The results are obtained in metric spaces with a partial ordering defined therein. There is a blending of analytic and order theoretic approaches in the proofs. The uniqueness is obtained by imposing some order theoretic conditions additionally. There are several corollaries. An illustration of the main theorem through an example is given which also shows that the corollaries are properly contained in the main theorem. [ABSTRACT FROM AUTHOR]

In this paper, the existence of ε-approximate equilibrium points for a bifunction is proved under suitable conditions in the framework of a Hadamard space. We also give the sufficient conditions for the continuity of ε-approximate solution maps to equilibrium problems. Then we apply our results to constrained minimization problems and Nash-equilibrium problems. [ABSTRACT FROM AUTHOR]

To solve complex problems such as multi-input function approximation by using neural networks and to overcome the inherent defects of traditional back-propagation neural networks, a single hidden-layer feed-forward sine-activated neural network, sine neural network (SNN), is proposed and investigated in this paper. Then, a double-stage weights and structure determination (DS-WASD) method, which is based on the weights direct determination method and the approximation theory of using linearly independent functions, is developed to train the proposed SNN. Such a DS-WASD method can efficiently and automatically obtain the relatively optimal SNN structure. Numerical results illustrate the validity and efficacy of the SNN model and the DS-WASD method. That is, the proposed SNN model equipped with the DS-WASD method has great performance of approximation on multi-input function data. [ABSTRACT FROM AUTHOR]

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]

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]

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]

In this paper, a semi-local convergence analysis of the Gauss-Newton method for convex composite optimization is presented using the concept of quasi-regularity in order to approximate fixed points in optimization. Our convergence analysis is presented first under the L-average Lipschitz and then under generalized convex majorant conditions. The results extend the applicability of the Gauss-Newton method under the same computational cost as in earlier studies such as Li and Ng (SIAM J. Optim. 18:613-642, 2007), Moldovan and Pellegrini (J. Optim. Theory Appl. 142:147-163, 2009), Moldovan and Pellegrini (J. Optim. Theory Appl. 142:165-183, 2009), Wang (Math. Comput. 68:169-186, 1999) and Wang (IMA J. Numer. Anal. 20:123-134, 2000). [ABSTRACT FROM AUTHOR]

In this paper, we consider a two-hop multiple-input multiple-output amplify-and-forward multiple relays communication networks with the assumption that the perfect channel state information is available at the source, the destination and the relays. We propose a joint design of the precoding matrices at the source and relays to maximize the system capacity. Based on the joint precoding matrices design results, we derive the joint source and relays power allocation (PA) optimization problem with the total source and relays transmit power constraint. Since it is difficult to derive an analytical solution to the original joint PA optimization problem, we simplified the problem and derive the closed-form solution based on high SNR approximation. The Monte Carlo simulation results shown that our proposed joint PA scheme significantly improves the system capacity compared with that solely considering PA at the relays. [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]

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]

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, 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]

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]

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]

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]