Search

The originality of this paper is to deal with the particular case of null infimum jump costs in the infinite horizon impulse control problem. The value function of such problems is a viscosity solution of the classic quasi-variational inequality (QVI) associated, but not the unique one. This is a drawback to characterize it. In this paper, a new QVI for which the value function is the unique viscosity solution is given. This allows us to approximate the value function. So, we give some discrete approximations of the new QVI and prove that the approximate value function converges locally uniformly, toward the value function of the impulse control problem with zero lower bound of impulse cost. We choose the classic example of continuous time inventory control in Rn to illustrate the results of this paper. [ABSTRACT FROM AUTHOR]

Switched systems, or systems whose control parameters include a continuous-valued input and a discrete-valued input which corresponds to the mode of the system that is active at a particular instance in time, have shown to be highly effective in modeling a variety of physical phenomena. Unfortunately, the construction of an optimal control algorithm for such systems has proved difficult since it demands some form of optimal mode scheduling. In a pair of papers, we construct a first order optimization algorithm to address this problem. Our approach, which we prove in this paper converges to local minimizers of the constrained optimal control problem, first relaxes the discrete-valued input, performs traditional optimal control, and then projects the constructed relaxed discrete-valued input back to a pure discrete-valued input by employing an extension to the classical chattering lemma that we formalize. In the second part of this pair of papers, we describe how this conceptual algorithm can be recast in order to devise an implementable algorithm that constructs a sequence of points by recursive application that converge to local minimizers of the optimal control problem for switched systems. [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]

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]

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]

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]

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]

Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of 1/e ≈ 0.36 In this paper, we introduce prophet secretary, a natural combination of the prophet inequality and the secretary problems. In the prophet secretary problem we are given a set {D1,...,Dn} of (not necessarily identical) distributions. A number Xi is drawn from each distribution Di and then, after applying a random permutation π1,..., πn, the numbers are given to us in an online fashion, i.e., at step k, Xπk is revealed. We are allowed to choose only one number, which can be done only upon receiving that number. The goal is to maximize the expectation of the chosen value, compared to the expectation of the optimum offline solution that knows the drawn values in advance. In particular, we show that by using a single uniform threshold one cannot break the 0.5 barrier of the prophet inequality for the prophet secretary problem. However, we show that • using n distinct nonadaptive thresholds one can obtain a competitive ratio that goes to (1 - 1/e ≈ 0.63) as n grows, and • no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) is chosen randomly. We also consider the minimization variants of stopping theory problems and, in particular, the prophet secretary problem. Interestingly, we show that, even for the simple case in which the input elements are drawn from identical and independent distributions, there is no constant competitive online algorithm for the minimization variant of the prophet secretary problems. We extend this hardness result to the minimization variants of both the prophet inequality and the secretary problem as well. [ABSTRACT FROM AUTHOR]

This paper is concerned with an optimal control problem governed by a regularized fracture model using a phase-field technique. To avoid the nondifferentiability due to the irreversibility constraint on the fracture growth, the phase-field fracture model is relaxed using a penalization approach. The existence of a solution to the penalized fracture model is shown, and the existence of at least one solution for the regularized optimal control problem is established. Moreover, the linearized fracture model is considered and used to establish first order necessary conditions as well as to discuss QP-approximations to the nonlinear optimization problem. A numerical example suggests that these can be used to obtain a fast convergent algorithm. [ABSTRACT FROM AUTHOR]

Numerous nonconvex continuous penalties have been proposed to approach the ℓ0 pseudonorm for optimization purpose. Apart from the theoretical results for convex ℓ1 relaxation under restrictive hypotheses, only few works have been devoted to analyze the consistency, in terms of minimizers, between the ℓ0-regularized least squares functional and relaxed ones using continuous approximations. In this context, two questions are of fundamental importance: do relaxed functionals preserve global minimizers of the initial one? Do these approximations introduce unwanted new (local) minimizers? In this paper we answer these questions by deriving necessary and sufficient conditions on such ℓ0 continuous approximations in order that each (local and global) minimizer of the underlying relaxation is also a minimizer of the ℓ2-ℓ0 functional and that all the global minimizers of the initial functional are preserved. Hence, a general class of penalties is provided giving a unified view of exact continuous approximations of the ℓ0-norm within the ℓ2-ℓ0 minimization framework. As the inferior limit of this class of penalties, we get the recently proposed continuous exact ℓ0 penalty. Finally, state of the art penalties, such as minimax concave penalty, smoothly clipped absolute deviation, or capped-ℓ1, are analyzed according to the proposed class of exact continuous penalties. [ABSTRACT FROM AUTHOR]

This paper is concerned with optimization of uncertain stochastic systems, in which uncertainty is described by a total variation distance constraint between the measures induced by the uncertain systems and the measure induced by the nominal system, while the payoff is a linear functional of the uncertain measure. Robustness at the abstract setting is formulated as a minimax game, in which the control seeks to minimize the payoff over the admissible controls while the uncertainty aims at maximizing it over the total variation distance constraint. It is shown that the maximizing measure in the total variation distance constraint exists, while the resulting payoff is a linear combination of L1 and L∞ norms. Further, the maximizing measure is characterized by a linear combination of a tilted measure and the nominal measure, giving rise to a payoff which is a nonlinear functional on the space of measures to be minimized over the admissible controls. The abstract formulation and results are subsequently applied to continuous-time uncertain stochastic controlled systems, in which the control seeks to minimize the payoff while the uncertainty aims to maximize it over the total variation distance constraint. The minimization over the admissible controls of the nonlinear functional payoff is addressed by developing a generalized principle of optimality or dynamic programming equation satisfied by the value function. Subsequently, it is proved that the value function satisfies a Hamilton-Jacobi-Bellman (HJB) equation. It is also shown that the value function is also a viscosity solution of the HJB equation. Finally, the linear quadratic case is studied, and it is shown that the infinity norm of a quadratic payoff is well defined and finite. Throughout the paper the formulation and conclusions are related to previous work found in the literature. [ABSTRACT FROM AUTHOR]

We consider approximation algorithms for nonnegative polynomial optimization over unit spheres. Such optimization models have wide applications, e.g., in signal and image processing, high order statistics, and computer vision. Since polynomial functions are nonconvex, the problems under consideration are all NP-hard. In this paper, based on convex polynomial optimization relaxations, we propose polynomial-time approximation algorithms with new approximation bounds. Numerical results are reported to show the effectiveness of the proposed approximation algorithms. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of minimizing condition numbers over a compact convex subset of the cone of symmetric positive semidefinite n x n matrices. We show that the condition number is a Clarke regular strongly pseudoconvex function. We prove that a global solution of the problem can be approximated by an exact or an inexact solution of a nonsmooth convex program. This asymptotic analysis provides a valuable tool for designing an implementable algorithm for solving the problem of minimizing condition numbers. [ABSTRACT FROM AUTHOR]

In this paper compressible, stationary Navier--Stokes equations are considered. A framework for analysis of such equations is established. In particular, the well-posedness for inhomogeneous boundary value problems of elliptic-hyperbolic type is shown. Analysis is performed for small perturbations of the so-called approximate solutions that take form (1.12). The approximate solutions are determined from Stokes problem (1.11). The small perturbations are given by solutions to (1.13). The uniqueness of solutions for problem (1.13) is proved, and, in addition, the differentiability of solutions with respect to the coefficients of differential operators is shown. The results on the well-posedness of nonlinear problems are interesting on their own and are used to obtain the shape differentiability of the drag functional for incompressible Navier--Stokes equations. The shape gradient of the drag functional is derived in the classical and useful for computations form; an appropriate adjoint state is introduced to this end. The material derivatives of solutions to the Navier--Stokes equations are given by smooth functions; however, the shape differentiability is shown in a weak norm. The method of analysis proposed in this paper is general and can be used to establish the well-posedness for distributed and boundary control problems as well as for inverse problems in the case of the state equations in the form of compressible Navier--Stokes equations. The differentiability of solutions to the Navier--Stokes equations with respect to the data leads to the first order necessary conditions for a broad class of optimization problems. [ABSTRACT FROM AUTHOR]

In this paper we discuss the issue of solving stochastic optimization problems by means of sample average approximations. Our focus is on rates of convergence of estimators of optimal solutions and optimal values with respect to the sample size. This is a well-studied problem in case the samples are independent and identically distributed (i.e., when standard Monte Carlo simulation is used); here we study the case where that assumption is dropped. Broadly speaking, our results show that, under appropriate assumptions, the rates of convergence for pointwise estimators under a sampling scheme carry over to the optimization case, in the sense that convergence of approximating optimal solutions and optimal values to their true counterparts has the same rates as in pointwise estimation. We apply our results to two well-established sampling schemes, namely, Latin hypercube sampling and randomized quasi-Monte Carlo (QMC). The novelty of our work arises from the fact that, while there has been some work on the use of variance reduction techniques and QMC methods in stochastic optimization, none of the existing work--to the best of our knowledge--has provided a theoretical study on the effect of these techniques on rates of convergence for the optimization problem. We present numerical results for some two-stage stochastic programs from the literature to illustrate the discussed ideas. [ABSTRACT FROM AUTHOR]

This paper concerns optimal control problems for dynamical systems described by a parametric family of discrete/finite-difference approximations of continuous-time control systems. Control theory for parametric systems governed by discrete approximations plays an important role in both qualitative and numerical aspects of optimal control and occupies an intermediate position in dynamic optimization: between optimal control of discrete-time (with fixed steps) and continuous-time control systems. The central result in optimal control of discrete approximation systems is the approximate maximum principle (AMP), which gives the necessary optimality condition in a perturbed maximum principle form with no a priori convexity assumptions and thus ensures the stability of the Pontryagin maximum principle (PMP) under discrete approximation procedures. The AMP has been justified for optimal control problems of smooth dynamical systems with endpoint constraints under some properness assumption imposed on the sequence of optimal controls. in this paper we show, by a series of counterexamples, that the properness assumption is essential for the validity of the AMP, and that the AMP does not hold, in its expected (lower) subdifferential form, for nonsmooth problems. Moreover, a new upper subdifferential form of the AMP is established for ordinary and time-delay control systems. The results obtained surprisingly solve (in both negative and positive directions) a long-standing and well-recognized question about the possibility of extending the AMP to nonsmooth control problems, for which the affirmative answer has been expected in the conventional lower subdifferential form. [ABSTRACT FROM AUTHOR]

The BFGS method is one of the most, famous quasi-Newton algorithms for unconstrained optimization. In 1984, Powell presented an example of a function of two variables that shows that the Polak Ribi[egrave;]re Polyak (PRP) conjugate gradient method and the BFGS quasi-Newt, on method may cycle around eight nonstationary points if each line search picks a local minimum that provides a reduction in the objective function. In this paper, a new technique of choosing parameters is introduced, and an example with only six cyclic points is provided. It is also noted through the examples that the BFGS method with Wolfe line searches need not converge for nonconvex objective functions. [ABSTRACT FROM AUTHOR]

In this paper, we study the portfolio optimization problem with general utility functions and when the return and volatility of the underlying asset are slowly varying. An asymptotic optimal strategy is provided within a specific class of admissible controls under this problem setup. Specifically, we establish a rigorous first order approximation of the value function associated to a fixed zeroth order suboptimal trading strategy, which is derived heuristically in [J.-P. Fouque, R. Sircar, and T. Zariphopoulou, Math. Finance, 2016]. Then, we show that this zeroth order suboptimal strategy is asymptotically optimal in a specific family of admissible trading strategies. Finally, we show that our assumptions are satisfied by a particular fully solvable model. [ABSTRACT FROM AUTHOR]

This paper studies models and algorithms for a class of tensor optimization problems, based on a rank-1 equivalence property between a tensor and certain unfoldings. It is first shown that in dth order tensor space, the set of rank-1 tensors is the same as the intersection of [log2(d)] tensor sets, of which tensors have a specific rank-1 balanced unfolding matrix. Moreover, the number [log2(d)] is proved to be optimal in some sense. Based on the above equivalence property, three relaxation approaches for solving the best rank-1 tensor approximation problems are proposed, including two convex relaxations and a nonconvex one. The two convex relaxations utilize the matrix nuclear norm regularization/constraints. They have the advantage of identifying whether the solution is a global optimizer of the original problem, by computing the nuclear norm or the Frobenius norm of a certain matrix. Under certain assumptions, the optimal solution of the original problem is characterized by the solution to the dual of the nuclear norm constrained problem. The nonconvex relaxation can be solved via the conventional alternating minimization scheme, with the output being always a rank-1 tensor. Numerical experiments demonstrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

Optimized Schwarz methods are based on transmission conditions between subdomains which are optimized for the problem class that is being solved. Such optimizations have been performed for many different types of partial differential equations, but were almost exclusively based on the assumption of straight interfaces. We study in this paper the influence of curvature on the optimization, and we obtain four interesting new results: first, we show that the curvature does indeed enter the optimized parameters and the contraction factor estimates. Second, we develop an asymptotically accurate approximation technique, based on Turán type inequalities in our case, to solve the much harder optimization problem on the curved interface, and this approximation technique will also be applicable to currently too complex best approximation problems in the area of optimized Schwarz methods. Third, we show that one can obtain transmission conditions from a simple circular model decomposition which have also been found using microlocal analysis but that these are not the best choices for the performance of the optimized Schwarz method. Finally, we find that in the case of curved interfaces, optimized Schwarz methods are not necessarily convergent for all admissible parameters. Our optimization leads, however, to parameter choices that give the same good performance for a circular decomposition as for a straight interface decomposition. We illustrate our analysis with numerical experiments. [ABSTRACT FROM AUTHOR]

The scenario-based optimization approach ("scenario approach" ) provides an intuitive way of approximating the solution to chance-constrained optimization programs, based on finding the optimal solution under a finite number of sampled outcomes of the uncertainty ("scenarios"). A key merit of this approach is that it neither requires explicit knowledge of the uncertainty set, as in robust optimization, nor of its probability distribution, as in stochastic optimization. The scenario approach is also computationally efficient because it only requires the solution to a convex optimization program, even if the original chance-constrained problem is nonconvex. Recent research has obtained a rigorous foundation for the scenario approach, by establishing a direct link between the number of scenarios and bounds on the constraint violation probability. These bounds are tight in the general case of an uncertain optimization problem with a single chance constraint. This paper shows that the bounds can be improved in situations where the chance constraints have a limited "support rank," meaning that they leave a linear subspace unconstrained. Moreover, it shows that also a combination of multiple chance constraints, each with individual probability level, is admissible. As a consequence of these results, the number of scenarios can be reduced from that prescribed by the existing theory for problems with the indicated structural property. This leads to an improvement in the objective value and a reduction in the computational complexity of the scenario approach. The proposed extensions have many practical applications, in particular, high-dimensional problems such as multistage uncertain decision problems or design problems of large-scale systems. [ABSTRACT FROM AUTHOR]

We derive residual-based a posteriori error estimates of optimal order for fully discrete approximations for linear parabolic problems. The time discretization uses the Crank--Nicolson method, and the space discretization uses finite element spaces that are allowed to change in time. The main tool in our analysis is the comparison with an appropriate reconstruction of the discrete solution, which is introduced in the present paper. [ABSTRACT FROM AUTHOR]

We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e.g., if it is a tree or if it is connected (every node knows at the end of the process whether H has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. In this paper we initiate a systematic study of distributed verification and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and s-t cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree (MST), shortest paths, and minimum cut. Many of these results are the first nontrivial lower bounds for both exact and approximate distributed computation, and they resolve previous open questions. Moreover, our unconditional lower bound of approximating MST subsumes and improves upon the previous hardness of approximation bound of Elkin [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [D. Peleg and V. Rubinovich, SIAM J. Comput., 30 (2000), pp. 1427-1442]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm for any approximation factor. Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computation of many problems. [ABSTRACT FROM AUTHOR]

The aim of this paper is to establish necessary optimality conditions for optimal control problems governed by steady, incompressible Navier-Stokes equations with shear-dependent viscosity. The main difficulty is related to the differentiability of the control-to-state mapping and is overcome by introducing a family of smooth approximate control problems and by passing to the limit in the corresponding optimality conditions. [ABSTRACT FROM AUTHOR]

The Development of patch test consistent quasi-continuum energies for multidimensional crystalline solids modeled by many-body potentials remains a challenge. The original quasi-continuum energy (QCE) [R. Miller and E. Tadmor, Model. Simul. Mater. Sci. Eng., 17 (2009), 053001] has been implemented for many-body potentials in two and three space dimensions, but it is not patch test consistent. We propose that by blending the atomistic and corresponding Cauchy Born continuum models of QCE in an interracial region with thickness of a small number k of blended atoms, a general blended quasi-continuum energy (BQCE) can be developed with the potential to significantly improve the accuracy of QCE near lattice instabilities such as dislocation formation and motion. In this paper, we give an error analysis of the blended quasi-continuum energy (BQCE) for a periodic one-dimensional chain of atoms with next-nearest neighbor interactions. Our analysis includes the optimization of the blending function for an improved convergence rate. We show that the κ² strain error for the nonblended QCE energy, which has low order O(ε1/2), where ε is the atomistic length scale [M. Dobson and M. Luskin, SIAM J. Numer. Anal., 47 (2009), pp. 2455-2475, P. Ming and J. Z. Yang, Multiscale Model. Simul., 7 (2009), pp. 1838-1875], can be reduced by a factor of κ3/2 for an optimized blending function where k is the number of atoms in the blending region. The QC, E energy has been further shown to suffer from a O(1) error in the critical strain at which the lattice loses stability IM. Dobson, M. Luskin, and C. Ortner, J. Mech. Phys. Solids, 58 (2010), pp. 1741 1757]. We prove that the error in the critical strain of BQCE can be reduced by a factor of κ² for an optimized blending function, thus demonstrating that the BQCE energy for an optimized blending function has the potential to give an accurate approximation of the deformation near lattice instabilities such as crack growth. [ABSTRACT FROM AUTHOR]

The goal of this paper is to formulate and solve free material optimization problems with constraints on the smallest eigenfrequency of the optimal structure. A natural formulation of this problem as a linear semidefinite program turns out to be numerically intractable. As an alternative, we propose a new approach, which is based on a nonlinear semidefinite low-rank approximation of the semidefinite dual. We introduce an algorithm based on this approach and analyze its convergence properties. The article is concluded by numerical experiments proving the effectiveness of the new approach. [ABSTRACT FROM AUTHOR]

The ℓp regression problem takes as input a matrix A ∈ ℝn×d, a vector b ∈ ℝn, and a number p ∈ [1,∞), and it returns as output a number Z and a vector xopt ∈ ℝd such that Z = min∈ ℝd ∥Ax-b∥p = ∥Axopt -b∥p. In this paper, we construct coresets and obtain an efficient two-stage sampling-based approximation algorithm for the very overconstrained (n ≫ d) version of this classical problem, for all p ∈ [1,∞). The first stage of our algorithm nonuniformly samples ȓ1 = O(36pdmax{p/2+1,p}+1) rows of A and the corresponding elements of b, and then it solves the ℓp regression problem on the sample; we prove this is an 8-approximation. The second stage of our algorithm uses the output of the first stage to resample ȓ1/ϵ² constraints, and then it solves the ℓp regression problem on the new sample; we prove this is a (1 + ϵ)-approximation. Our algorithm unifies, improves upon, and extends the existing algorithms for special cases of ℓp regression, namely, p = 1, 2 [K. L. Clarkson, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2005, pp. 257-266; P. Drineas, M. W. Mahoney, and S. Muthukrishnan, in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2006, pp. 1127-1136]. In the course of proving our result, we develop two concepts--well-conditioned bases and subspace-preserving sampling-that are of independent interest. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between the optimal value of a homogeneous quadratic optimization problem and its semidefinite programming (SDP) relaxation. We consider two quadratic optimization models: (1) min{x*Cx | x *Akx≥ 1, k = 0, 1,. . ., m, x ∈ Fn} and (2) max {x*Cx | x*Akχ ≤ 1, k = 0, 1,. . ., m, x ∈ 픞n}, where F is either the real field ℝ or the complex field ℂ, and Ak, C are symmetric matrices. For the minimization model (1), we prove that if the matrix C and all but one of the Ak's are positive semidefinite, then the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by O(m²) when 픞 = ℝ, and by O(m) when 픞 = ℂ. Moreover, when two or more of the Ak's are indefinite, this ratio can be arbitrarily large. For the maximization model (2), we show that if C and at most one of the Ak's are indefinite while other Ak's are positive semidefinite, then the ratio between the optimal value of (2) and its SDP relaxation is bounded from below by O(1/ logm) for both the real and the complex case. This result improves the bound based on the so-called approximate S-Lemma of Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535-560]. When two or more of the Ak's in (2) are indefinite, we derive a general bound in terms of the problem data and the SDP solution. For both optimization models, we present examples to show that the derived approximation bounds are essentially tight. [ABSTRACT FROM AUTHOR]

It is well known that the nonlinear filtering problem has important applications in both military and commercial industries. The central problem of nonlinear filtering is to solve the Duncan—Mortensen—Zakai (DMZ) equation in real time and in a memoryless manner. The purpose of this paper is to show that, under very mild conditions (which essentially say that the growth of the observation ∣h∣ is greater than the growth of the drift ∣f∣), the DMZ equation admits a unique nonnegative weak solution u which can be approximated by a solution uR of the DMZ equation on the ball BR with uR ∣∂BR = 0. The error of this approximation is bounded by a function of R which tends to zero as R goes to infinity. The solution uR can in turn be approximated efficiently by an algorithm depending only on solving the observation-independent Kolmogorov equation on BR. In theory, our algorithm can solve basically all engineering problems in real time. Specifically, we show that the solution obtained from our algorithms converges to the solution of the DMZ equation in the L¹ sense. Equally important, we have a precise error estimate of this convergence, which is important in numerical computation. [ABSTRACT FROM AUTHOR]

The Gegenbauer reconstruction method effectively eliminates the Gibbs phenomenon and restores exponential accuracy to the approximations of piecewise smooth functions. Recent investigations show that its success depends upon choosing parameters in such a way that the regularization and the truncation error estimates are equally considered. This paper shows that the underlying analyticity of the function in smooth regions plays a critical role in the regularization error estimate. Hence we develop a technique that first analyzes the behavior of the function in its regions of smoothness and then applies this knowledge to refine the regularization error estimate. Such refinement yields better parameter choices for the Gegenbauer reconstruction method, and is confirmed both by better accuracy and more robustness in the approximation of piecewise smooth functions. [ABSTRACT FROM AUTHOR]

In this paper we consider a general optimization problem (OP) and study the convergence and approximation of optimal values and optimal solutions to changes in the cost function and the set of feasible solutions. By a "general" OP we mean that the cost function and the constraints are defined on a Hausdorff topological space. First we obtain convergence results for a general OP, and then we present an application of these results on the approximation of the optimal value and the optimal solutions for the so-called general capacity problem in metric spaces. [ABSTRACT FROM AUTHOR]

This paper addresses the numerical approximation of Young measures appearing as generalized solutions to scalar nonconvex variational problems. We prove a priori and a posteriori error estimates for a macroscopic quantity, the stress. For a scalar three-well problem we show convergence of other quantities such as Young measure support and microstructure region. Numerical experiments indicate that the computational effort in the solution of the large optimization problem is significantly reduced by using an adaptive mesh refinement strategy based on a posteriori error estimates in combination with an active set strategy due to Carstensen and Roubíček. [ABSTRACT FROM AUTHOR]

At each iteration step for solving mathematical programming and constrained optimization problems by using interior-point methods, one often needs to solve the weighted least squares (WLS) problem minx∈Rn ¦¦W½(Ax - b)¦¦, or the weighted and constrained least squares (WLSE) problem minx∈Rn ¦¦W½(Kx - g)¦¦ subject to Lx = h, where W = diag(w1,…,wl) > 0 in which some wi → +∝ and some wi → 0. In this paper we will derive upper perturbation bounds of weighted projections associated with the WLS and WLSE problems when W ranges over the set D of positive diagonal matrices. We then apply these bounds to deduce upper perturbation bounds of solutions of WLS and WLSE problems when W ranges over D. We also extend the estimates to the cases when W ranges over a subset of real symmetric positive semidefinite matrices. [ABSTRACT FROM AUTHOR]

A new numerical method is presented for semi-infinite optimization problems which guarantees that each iterate is feasible for the original problem. The basic idea is to construct concave relaxations of the lower level problem, to compute the optimal values of the relaxation problems explicitly, and to solve the resulting approximate problems with finitely many constraints. The concave relaxations are constructed by replacing the objective function of the lower level problem by its concave upper bound functions. Under mild conditions, we prove that every accumulation point of the solutions of the approximate problems is an optimal solution of the original problem. An adaptive subdivision algorithm is proposed to solve semi-infinite optimization problems. It is shown that the Karush-Kuhn-Tucker points of the approximate problems converge to a Karush-Kuhn-Tucker point of the original problem within arbitrarily given tolerances. Numerical experiments show that our algorithm is much faster than the existing adaptive convexification algorithm in computation time. [ABSTRACT FROM AUTHOR]

We consider low-rank approximation of affinely structured matrices with missing elements. The method proposed is based on reformulation of the problem as inner and outer optimization. The inner minimization is a singular linear least-norm problem and admits an analytic solution. The outer problem is a nonlinear least-squares problem and is solved by local optimization methods: minimization subject to quadratic equality constraints and unconstrained minimization with regularized cost function. The method is generalized to weighted low-rank approximation with missing values and is illustrated on approximate low-rank matrix completion, system identification, and data-driven simulation problems. An extended version of this paper is a literate program, implementing the method and reproducing the presented results. [ABSTRACT FROM AUTHOR]

In this paper, we show that for a symmetric tensor, its best symmetric rank-1 approximation is its best rank-1 approximation. Based on this result, a positive lower bound for the best rank-1 approximation ratio of a symmetric tensor is given. Furthermore, a higher order polynomial spherical optimization problem can be reformulated as a multilinear spherical optimization problem. Then, we present a modified power algorithm for solving the homogeneous polynomial spherical optimization problem. Numerical results are presented, illustrating the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

For optimal design problems, defined in domains of class C and in arbitrary space dimension, governed by elliptic equations with boundary conditions of Neumann or mixed type, we introduce the corresponding discretized problems and we prove convergence results. The discretization method is of fixed domain type, in the sense that it is given in the domain that contains all the admissible open sets. [ABSTRACT FROM AUTHOR]

For the Helmholtz equation (with wavenumber κ) and analytic curves or surfaces ⌈, we analyze the Galerkin discretization of classical combined field integral equations in an L²- setting. We give abstract conditions on the approximation properties of the ansatz space that ensure stability and quasi-optimality of the Galerkin method. Special attention is paid to the hp-version of the boundary element method (hp-BEM). Under the assumption of polynomial growth of the solution operator we show stability and quasi-optimality of the hp-BEM if the following scale resolution condition is satisfied: the polynomial degree p is at least O(log κ) and κh/p is bounded by a number that is sufficiently small, but independent of κ. Under this assumption, the constant in the quasi-optimality estimate is independent of κ. Numerical examples in two dimensions illustrate the theoretical results and even suggest that in many cases quasi-optimality is given under the weaker condition that κh/p is sufficiently small. [ABSTRACT FROM AUTHOR]

We study the following all-or-nothing multicommodity ow problem in planar graphs: Input: A graph G with n vertices and k pairs of vertices (s1; t1); (s2; t2); …; (sk; tk) in G. Find: A largest subset W of f1; …; kg such that for every i in W, we can send one unit of ow between si and ti. This problem is diffierent from the well-known maximum edge-disjoint paths problem in that we do not require integral ows for the pairs. This problem is APX-hard even for trees, and a 2-approximation algorithm is known for trees. For general graphs, Chekuri, Khanna, and Shepherd [SIAM J. Comput., 42 (2013), pp. 1467{1493] give a polylogarithmic factor approximation algorithm and show that a natural LP-relaxation has a polylogarithmic integrality gap. This result is in contrast with the integrality gap (pn) for the maximum edge-disjoint paths problem. Our main result considerably strengthens this result when an input graph is planar. Namely, for the all-or-nothing multicommodity ow problem in planar graphs, we give an O(1)-approximation algorithm and show that the integrality gap is O(1). In particular, in polynomial time, we can find an index set W with jWj = Ω(OPT) and eight si-ti paths for each i ϵ W such that each edge is used at most eight times in these paths (with multiplicity), where OPT is the optimal value of the LP-relaxation of the all-or-nothing multicommodity ow problem. Our result can be compared to the result by Séguin-Charbonneau and Shepherd [Proceedings of FOCS, 2011, pp. 200{209], who give an O(1)-approximation algorithm for the maximum edge-disjoint paths problem in planar graphs with congestion 2 (but not implied by this result). [ABSTRACT FROM AUTHOR]

We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner forest problem in doubling metrics. Before our work, a PTAS was given only for the Euclidean plane in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115--124]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [Y. Bartal, L. Gottlieb, and R. Krauthgamer, in STOC, ACM, 2012, pp. 663--672] and [T-H. H. Chan and S.-H. Jiang, in SODA, SIAM, 2016, pp. 754--765]. However, extending previous approaches requires overcoming several nontrivial hurdles, and we make the following technical contributions. (1) We prove a technical lemma showing that Steiner points have to be ''near"" the terminals in an optimal Steiner tree. This enables us to define a heuristic to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. This lemma also generalizes previous results in the Euclidean plane and may be of independent interest for related problems involving Steiner points. (2) We develop a novel algorithmic technique known as ''adaptive cells"" to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed ''uniform cells"" in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115--124], where techniques cannot be readily applied to doubling metrics. [ABSTRACT FROM AUTHOR]

We present a class of linear programming approximations for polynomial optimization problems that take advantage of structured sparsity given by a graph theoretical parameter, the tree-width. We consider two schemes that use this feature to produce provably good solutions. First we study problems whose system of constraints exhibits small tree-width, and we show that for any desired tolerance there is a linear programming approximation of polynomial size. Second, we consider problems where an existing sparse network is used to define variables and constraints of a polynomial optimization problem. In important applications, in spite of the structural sparsity of the network, a direct formulation may still be dense. Nevertheless, we show how to obtain polynomial tractability of an approximation scheme in such a case as well. [ABSTRACT FROM AUTHOR]

We present a new approach for computing approximate global minimizers to a large class of nonlocal pairwise interaction problems defined over probability distributions. The approach predicts candidate global minimizers, with a recovery guarantee, that are sometimes exact, and often within a few percent of the optimum energy (under appropriate normalization of the energy). The procedure relies on a convex relaxation of the pairwise energy that exploits translational symmetry, followed by a recovery procedure that minimizes a relative entropy. Numerical discretizations of the convex relaxation yield a linear programming problem over convex cones that can be solved using well-known methods. One advantage of the approach is that it provides sufficient conditions for global minimizers to a nonconvex quadratic variational problem, in the form of a linear, convex, optimization problem for the autocorrelation of the probability density. We demonstrate the approach in a periodic domain for examples arising from models in materials, social phenomena, and ocking. The approach also exactly recovers the global minimizer when a lattice of Dirac masses solves the convex relaxation. An important by-product of the relaxation is a decomposition of the pairwise energy functional into the sum of a convex functional and nonconvex functional. We observe that in some cases, the nonconvex component of the decomposition can be used to characterize the support of the recovered minimizers. [ABSTRACT FROM AUTHOR]

Variational problems under uniform quasi-convex constraints on the gradient are studied. Our technique consists in approximating the original problem by a one-parameter family of smooth unconstrained optimization problems. Existence of solutions to the problems under consideration is proved as well as existence of Lagrange multipliers associated to the uniform constraint; no constraint qualification condition is required. The solution-multiplier pairs are shown to satisfy an Euler-Lagrange equation and a complementarity property. Numerical experiments confirm the ability of our method to accurately compute solutions and Lagrange multipliers. [ABSTRACT FROM AUTHOR]

We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function f : 2N → ℝ+, and the objective is to find a subset S ⊆ N maximizing f(S). This is one of the most basic submodular optimization problems, having a wide range of applications. Some well-known problems captured by Unconstrained Submodular Maximization include Max-Cut, Max-DiCut, and variants of Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1/2, thus matching the known hardness result of Feige, Mirrokni, and Vondrák [SIAM J. Comput., 40 (2011), pp. 1133-1153]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem. [ABSTRACT FROM AUTHOR]

When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∊ can be obtained by a second-order method using cubic regularization in at most O(∊-3/2) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear leastsquares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∊-2)) evaluation-complexity bound for solving general nonconvexly constrained optimization problems. [ABSTRACT FROM AUTHOR]

The symmetric rank-one update method is well known in optimization for its applications in quasi-Newton algorithms. In particular, Conn, Gould, and Toint proved in 1991 that the matrix sequence resulting from this method approximates the Hessian of the minimized function under a suitable linear-independence assumption. Extending their idea, we prove that symmetric rank-one updates can be used to approximate any sequence of symmetric invertible matrices, which has applications to more general problems, such as the computation of constrained geodesics in shape analysis imaging problems. We also provide numerical simulations for the method and some of these applications. [ABSTRACT FROM AUTHOR]

The article considers a particular class of optimization problems involving set-valued stochastic equilibrium constraints. We develop a solution procedure that relies on an approximation scheme for the equilibrium constraints. Based on regularization, we replace the approximated equilibrium constraints by those involving only single-valued Lipschitz continuous functions. In addition, sampling has the further effect of replacing the "simplified" equilibrium constraints by more manageable ones obtained by implicitly discretizing the (given) probability measure so as to render the problem computationally tractable. Convergence is obtained by relying, in particular, on the graphical convergence of the approximated equilibrium constraints. The problem of estimating the characteristics of a demand model, a widely studied problem in microeconometrics, serves both as motivation and illustration of the regularization and sampling procedure. [ABSTRACT FROM AUTHOR]

We present a framework for obtaining fully polynomial time approximation schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two sets of computational rules, namely, the calculus of Κ-approximation functions and the calculus of Κ-approximation sets. Using our framework, we provide the first FPTASs for several NP-hard problems in various fields of research such as knapsack models, logistics, operations management, economics, and mathematical finance. Extensions of our framework via the use of the newly established computational rules are also discussed. [ABSTRACT FROM AUTHOR]