Search

In this study, we investigate a class of linear multiplicative programs with positive exponents. By introducing p additional variables, the original problem is reformulated into an equivalent problem (EP) within the output space. Subsequently, a novel global optimization algorithm is introduced to tackle EP. The algorithm primarily leverages two key techniques. One is the outer approximation technique, which tightens the relaxed feasible region of EP and improves the upper bound by carefully examining suitable feasible points. The other is the branch and bound technique to guarantee the global optimality of the solution. Numerical results confirm the effectiveness and practicality of the proposed algorithm, thereby underscoring its potential for real-world applications. [ABSTRACT FROM AUTHOR]

Submodular maximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the query complexity and adaptive complexity are two important measures, where the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially many function evaluations in parallel. These two concepts reasonably quantify the efficiency and practicability of parallel computation. In this paper, we consider the problem of maximizing a nonnegative monotone DR-submodular function over a bounded integer lattice with a cardinality constraint in a value oracle model. Prior to our work, Soma and Yoshida (Math Program 172:539–563, 2018) have studied this problem and present an approximation algorithm with almost optimal approximate ratio and the same adaptivity and query complexity. We develop two novel algorithms, called low query algorithm and low adaptivity algorithm, which have approximation ratios equal to Soma and Yoshida (2018), but reach a new record of query complexity and adaptivity. As for methods, compared with the threshold greedy in Soma and Yoshida (2018), the low query algorithm reduces the number of possible thresholds and improves both the adaptivity and query complexity. The low adaptivity algorithm further integrates a vector sequencing technique to accelerate adaptive complexity in an exponential manner while only making logarithmic sacrifices on oracle queries. [ABSTRACT FROM AUTHOR]

We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as building blocks, we construct a triangulation scheme called crossing swords that requires at most - times the number of simplices in any optimal triangulation. In other words, we derive an approximation algorithm for the optimal triangulation problem. We also show that crossing swords yields optimal triangulations in the case that each simplex has at least one axis-parallel edge. Furthermore, we present approximation guarantees for other well-known triangulation schemes, namely for the red refinement and longest-edge bisection strategies as well as for a generalized version of K1-triangulations. Thereby, we are able to show that our novel approach dominates previous triangulation schemes from the literature, which is underlined by illustrative numerical examples. [ABSTRACT FROM AUTHOR]

In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021, http://arxiv.org/abs/2106.06446), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods. [ABSTRACT FROM AUTHOR]

Currently, few approaches are available for mixed-integer nonlinear robust optimization. Those that do exist typically either require restrictive assumptions on the problem structure or do not guarantee robust protection. In this work, we develop an algorithm for convex mixed-integer nonlinear robust optimization problems where a key feature is that the method does not rely on a specific structure of the inner worst-case (adversarial) problem and allows the latter to be non-convex. A major challenge of such a general nonlinear setting is ensuring robust protection, as this calls for a global solution of the non-convex adversarial problem. Our method is able to achieve this up to a tolerance, by requiring worst-case evaluations only up to a certain precision. For example, the necessary assumptions can be met by approximating a non-convex adversarial via piecewise relaxations and solving the resulting problem up to any requested error as a mixed-integer linear problem. In our approach, we model a robust optimization problem as a nonsmooth mixed-integer nonlinear problem and tackle it by an outer approximation method that requires only inexact function values and subgradients. To deal with the arising nonlinear subproblems, we render an adaptive bundle method applicable to this setting and extend it to generate cutting planes, which are valid up to a known precision. Relying on its convergence to approximate critical points, we prove, as a consequence, finite convergence of the outer approximation algorithm. As an application, we study the gas transport problem under uncertainties in demand and physical parameters on realistic instances and provide computational results demonstrating the efficiency of our method. [ABSTRACT FROM AUTHOR]

This work studies solution methods for approximating a given tensor by a sum of R rank-1 tensors with one or more of the latent factors being orthonormal. Such a problem arises from applications such as image processing, joint singular value decomposition, and independent component analysis. Most existing algorithms are of the iterative type, while algorithms of the approximation type are limited. By exploring the multilinearity and orthogonality of the problem, we introduce an approximation algorithm in this work. Depending on the computation of several key subproblems, the proposed approximation algorithm can be either deterministic or randomized. The approximation lower bound is established, both in the deterministic and the expected senses. The approximation ratio depends on the size of the tensor, the number of rank-1 terms, and is independent of the problem data. When reduced to the rank-1 approximation case, the approximation bound coincides with those in the literature. Moreover, the presented results fill a gap left in Yang (SIAM J Matrix Anal Appl 41:1797–1825, 2020), where the approximation bound of that approximation algorithm was established when there is only one orthonormal factor. Numerical studies show the usefulness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

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

A piezoelectric-type tensor is of order three that is symmetric with respect to the last two indices. Its largest C-eigenvalue determines the highest piezoelectric coupling constant. However, computing the largest C-eigenvalue is NP-hard. This paper addresses this problem using convex relaxation. To this end, we first establish an equivalence property that helps to rewrite the problem as a matrix optimization over rank-1 together with the partially symmetric tensor constraints. Then, via Lagrangian dual, convex relaxations are derived, yielding the problems of maximization of a linear function over one or two matrix nuclear norm constraint(s), together with a partially symmetric tensor constraint. Such relaxations define new norms, which are smaller than the spectral norms of the corresponding unfolding matrices. Several insights are provided for the tightness issues of the convex relaxations, including a certification, a sufficient criterion, and an equivalence condition. The spectral property of the dual variable, in particular, determines the tightness. When the convex relaxations are not tight, an approximation algorithm is proposed to extract a feasible approximation solution, with a theoretical lower bound provided. We provide several types of tensors to justify the tightness of the convex relaxations. In case that the relaxations are not tight, their optimal values, serving as upper bounds, are still tighter than those in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we propose new approximation algorithms for a NP-hard problem, i.e., weighted maximin dispersion problem. By using a uniformly distributed random sample method, we first propose a new random approximation algorithm for box constrained or ball constrained weighted maximin dispersion problems and analyze its approximation bound respectively. Moreover, we propose two improved approximation algorithms by combining our technique with an existing binary sample technique for both cases. To the best of our knowledge, they are the best approximation bounds for both box constrained and ball constrained weighted maximin dispersion problems respectively. [ABSTRACT FROM AUTHOR]

In this paper, we propose to study a wide class of combinatorial optimization problems called combinatorial optimization problems with labelling. First, we give a combinatorial method to deal with the labelling version of some classical combinatorial optimization problems including minimum vertex cover, maximum independent set, minimum dominating set and minimum set cover, and convert the labelling problems into the original problems by polynomial-time reduction. We show that, although the labelling version of these problem seems more universal than their original counterparts, they are actually equivalent to the corresponding original problem from an algorithmic point of view. Moreover, we generalize the greedy approach for solving submodular cover problem to its labelling version, and as simple applications of our new method, we use it to solve the labelling versions of the minimum weighted spanning tree and connected vertex cover problem in a unified way. [ABSTRACT FROM AUTHOR]

A new quasi-Newton method with a diagonal updating matrix is suggested, where the diagonal elements are determined by forward or by central finite differences. The search direction is a direction of sufficient descent. The algorithm is equipped with an acceleration scheme. The convergence of the algorithm is linear. The preliminary computational experiments use a set of 75 unconstrained optimization test problems classified in five groups according to the structure of their Hessian: diagonal, block-diagonal, band (tri- or penta-diagonal), sparse and dense. Subject to the CPU time metric, intensive numerical experiments show that, for problems with Hessian in a diagonal, block-diagonal or band structure, the algorithm with diagonal approximation of the Hessian by finite differences is top performer versus the well-established algorithms: the steepest descent and the Broyden–Fletcher–Goldfarb–Shanno. On the other hand, as a by-product of this numerical study, we show that the Broyden–Fletcher–Goldfarb–Shanno algorithm is faster for problems with sparse Hessian, followed by problems with dense Hessian. [ABSTRACT FROM AUTHOR]

In this paper, we consider a stochastic variational inequality, in which the mapping involved is an expectation of a given random function. Inspired by the work of He (Appl Math Optim 35:69–76, 1997) and the extragradient method proposed by Iusem et al. (SIAM J Optim 29:175–206, 2019), we propose an infeasible projection algorithm with line search scheme, which can be viewed as a modification of the above-mentioned method of Iusem et al. In particular, in the correction step, we replace the projection by computing search direction and stepsize, that is, we need only one projection at each iteration, while the method of Iusem et al. requires two projections at each iteration. Moreover, we use dynamic sampled scheme with line search to cope with the absence of Lipschitz constant and choose the stepsize to be bounded away from zero and the direction to be a descent direction. In the process of stochastic approximation, we iteratively reduce the variance of a stochastic error. Under appropriate assumptions, we derive some properties related to convergence, convergence rate, and oracle complexity. In particular, compared with the method of Iusem et al., our method uses less projections and has the same iteration complexity, which, however, has a higher oracle complexity for a given tolerance in a finite dimensional space. Finally, we report some numerical experiments to show its efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we mainly study nonsmooth mixed-integer nonlinear programming problems and solution algorithms by outer approximation and generalized Benders decomposition. Outer approximation and generalized Benders algorithms are provided to solve these problems with nonsmooth convex functions and with conic constraint, respectively. We illustrate these two algorithms by providing detailed procedure of solving several examples. The numerical examples show that outer approximation and generalized Benders decomposition provide a feasible alternative for solving such problems without differentiability. [ABSTRACT FROM AUTHOR]

Routing real-time traffic with maximum packet delay in contemporary telecommunication networks requires not only choosing a path but also reserving transmission capacity along its arcs, as the delay is a nonlinear function of both components. The problem is known to be solvable in polynomial time under quite restrictive assumptions, i.e., equal rate allocations (all arcs are reserved the same capacity) and identical reservation costs, whereas the general problem is $$\mathcal {NP}$$ -hard. We first extend the approaches to the equal rate allocation (ERA) version to a pseudo-polynomial Dynamic Programming one for integer arc costs and a FPTAS for the case of general arc costs. We then show that the general problem can be formulated as a mixed-integer Second-Order Cone (SOCP) program and therefore solved with off-the-shelf technology. We compare two formulations: one based on standard big-M constraints and one where Perspective Reformulation techniques are used to tighten the continuous relaxation. Extensive computational experiments on both real-world networks and randomly generated realistic ones show that the ERA approach is fast and provides an effective heuristic for the general problem whenever it manages to find a solution at all, but it fails for a significant fraction of the instances that the SOCP models can solve. We therefore propose a three-pronged approach that combines the fast running time of the ERA algorithm and the effectiveness of the SOCP models, and show that it is capable of solving realistic-sized instances with high accuracy at different levels of network load in a time compatible with real-time usage in an operating environment. [ABSTRACT FROM AUTHOR]

We introduce and analyze a novel scalarization technique and an associated algorithm for generating an approximation of the Pareto front (i.e., the efficient set) of nonlinear multiobjective optimization problems. Our approach is applicable to nonconvex problems, in particular to those with disconnected Pareto fronts and disconnected domains (i.e., disconnected feasible sets). We establish the theoretical properties of our new scalarization technique and present an algorithm for its implementation. By means of test problems, we illustrate the strengths and advantages of our approach over existing scalarization techniques such as those derived from the Pascoletti-Serafini method, as well as the popular weighted-sum method. [ABSTRACT FROM AUTHOR]

This work focuses on numerical methods for finding optimal dividend payment and investment policies to maximize the present value of the cumulative dividend payment until ruin; the surplus is modeled by a regime-switching jump diffusion process subject to both regular and singular controls. Using the dynamic programming principle, the optimal value function obeys a coupled system of nonlinear integro-differential quasi-variational inequalities. Since the closed-form solutions are virtually impossible to obtain, we use Markov chain approximation techniques to approximate the value function and optimal controls. Convergence of the approximation algorithms are proved. Examples are presented to illustrate the applicability of the numerical methods. [ABSTRACT FROM AUTHOR]

In this paper, we propose a method for finding a Nash equilibrium of two-person games with alternating offers. The proposed method is referred to as the inexact proximal alternating direction method. In this method, the idea of alternating direction method simulates alternating offers in the game, while the inexact solutions of subproblems can be matched to the assumptions of incomplete information and bounded individual rationality in practice. The convergence of the proposed method is proved under some suitable conditions. Numerical tests show that the proposed method is competitive to the state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the sensitivity analysis in vector optimization. More specifically, formulae for inner and outer evaluating the S-derivative of the efficient point multifunction in parametric vector optimization problems are established. These estimating formulae are presented via the set of efficient/weakly efficient points of the S-derivative of the original multifunction, a composite multifunction of the objective function and the constraint mapping. The elaboration of the formulae in vector optimization problems, having multifunction constraints and semiinfinite constraints, is also undertaken. Furthermore, examples are provided for analyzing and illustrating the obtained results. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new method, namely the level-value estimation method, for finding global minimizer of continuous optimization problem. For this purpose, we define the variance function and the mean deviation function, both depend on a level value of the objective function to be minimized. These functions have some good properties when Newton's method is used to solve a variance equation resulting by setting the variance function to zero. We prove that the largest root of the variance equation equals the global minimal value of the corresponding optimization problem. We also propose an implementable algorithm of the level-value estimation method where importance sampling is used to calculate integrals of the variance function and the mean deviation function. The main idea of the cross-entropy method is used to update the parameters of sample distribution at each iteration. The implementable level-value estimation method has been verified to satisfy the convergent conditions of the inexact Newton method for solving a single variable nonlinear equation. Thus, convergence is guaranteed. The numerical results indicate that the proposed method is applicable and efficient in solving global optimization problems. [ABSTRACT FROM AUTHOR]

Discretization algorithms for semiinfinite minimax problems replace the original problem, containing an infinite number of functions, by an approximation involving a finite number, and then solve the resulting approximate problem. The approximation gives rise to a discretization error, and suboptimal solution of the approximate problem gives rise to an optimization error. Accounting for both discretization and optimization errors, we determine the rate of convergence of discretization algorithms, as a computing budget tends to infinity. We find that the rate of convergence depends on the class of optimization algorithms used to solve the approximate problem as well as the policy for selecting discretization level and number of optimization iterations. We construct optimal policies that achieve the best possible rate of convergence and find that, under certain circumstances, the better rate is obtained by inexpensive gradient methods. [ABSTRACT FROM AUTHOR]

To construct an effective minimization algorithm for locally Lipschitz functions, we show how to compute a descent direction satisfying Armijo's condition. We present a finitely terminating algorithm to construct an approximating set for the Goldstein subdifferential leading to the desired descent direction. Using this direction, we propose a minimization algorithm for locally Lipschitz functions and prove its convergence. Finally, we implement our algorithm with matrix laboratory (MATLAB) codes and report our testing results. The comparative numerical results attest to the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Rollout algorithms are heuristic algorithms that can be applied to solve deterministic and stochastic dynamic programming problems. The basic idea is to use the cost obtained by applying a well known heuristic, called the base policy, to approximate the value of the optimal cost-to-go. We develop a theoretical approach to prove, for the 0-1 knapsack problem, that the minimum performance ratio of the rollout algorithms tends to be significantly greater when the performance ratio of the corresponding base policy is poor and that the worst-case performance ratio is significantly better than the one of the corresponding base policies. [ABSTRACT FROM AUTHOR]

US expenditures on search-based advertising exceeded $12 billion in 2010. Advertisers bid for keywords, where bid price determines ad placement, affecting click-through and conversion rates. Advertisers must select keywords, allocating each a proportion of their fixed daily budget. In this paper, we construct a stochastic model for the selection and allocation process. We provide analytical results for the single-keyword problem and examine the multiple-keyword problem numerically. We investigate trade-offs between keywords given varying levels of risk and return. We show the implications of enforcing a probabilistic budget constraint. Our paper provides a critical analysis of the advertiser's problem that may guide future research. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new concept of ϵ-efficiency for vector optimization problems. This extends and unifies various notions of approximate solutions in the literature. Some properties for this new class of approximate solutions are established, and several existence results, as well as nonlinear scalarizations, are obtained by means of the Ekeland's variational principle. Moreover, under the assumption of generalized subconvex functions, we derive the linear scalarization and the Lagrange multiplier rule for approximate solutions based on the scalarization in Asplund spaces. [ABSTRACT FROM AUTHOR]

This paper describes an optimal control problem involving a nonlinear impulsive control system, together with a nonlinear objective function and nonlinear control and state constraints. Both the magnitude of the impulses as well as the instants at which the impulses are applied can be regarded as decision variables. A computational method is described for solving the problem. To illustrate the usefulness of our method for real-life applications, we solve a Human Immunodeficiency Virus (HIV) treatment problem. The numerical results obtained clearly illustrate the efficiency of our method. [ABSTRACT FROM AUTHOR]

We consider a system of coupled singularly perturbed reaction-diffusion two-point boundary-value problems. A hybrid difference scheme on a piecewise-uniform Shishkin mesh is constructed for solving this system, which generates better approximations to the exact solution than the classical central difference scheme. Moreover, we prove that the method is third order uniformly convergent in the maximum norm when the singular perturbation parameter is small. Numerical experiments are conducted to validate the theoretical results. [ABSTRACT FROM AUTHOR]

Motivated by applications to the real world, various optimality criteria (also approximate ones) are developed for situations in vector optimization. We propose a new type of solution based on upper comprehensive sets and we discuss the existence of optimal points in multicriteria situations. [ABSTRACT FROM AUTHOR]

notion of boundedly ε-lower subdifferentiable functions is introduced and investigated. It is shown that a bounded from below, continuous, quasiconvex function is locally boundedly ε-lower subdifferentiable for every ε>0. Some algorithms of cutting plane type are constructed to solve minimization problems with approximately lower subdifferentiable objective and constraints. In those algorithms an approximate minimizer on a compact set is obtained in a finite number of iterations provided some boundedness assumption be satisfied. [ABSTRACT FROM AUTHOR]

The aim of this paper is to investigate from the numerical point of view the coupling of the Hamilton-Jacobi-Bellman (HJB) equation and the Pontryagin minimum principle (PMP) to solve some control problems. A rough approximation of the value function computed by the HJB method is used to obtain an initial guess for the PMP method. The advantage of our approach over other initialization techniques (such as continuation or direct methods) is to provide an initial guess close to the global minimum. Numerical tests involving multiple minima, discontinuous control, singular arcs and state constraints are considered. [ABSTRACT FROM AUTHOR]

This paper considers the expected residual minimization (ERM) method proposed by Luo and Lin (J. Optim. Theory Appl. 140:103–116, 2009) for a class of stochastic variational inequality problems. Different from the work mentioned above, the function involved is assumed to be nonlinear in this paper. We first consider a quasi-Monte Carlo method for the case where the underlying sample space is compact and show that the ERM method is convergent under very mild conditions. Then, we suggest a compact approximation approach for the case where the sample space is noncompact. [ABSTRACT FROM AUTHOR]

Given a set of points S = {x1, . . . , xm} ⊂ ℝn and ϵ > 0, we propose and analyze an algorithm for the problem of computing a (1 + ϵ )-approximation to the minimum-volume axis-aligned ellipsoid enclosing S.We establish that our algorithm is polynomial for fixed ϵ . In addition, the algorithm returns a small core set X ⊆ S, whose size is independent of the number of points m, with the property that the minimum-volume axis-aligned ellipsoid enclosing X is a good approximation of the minimum-volume axis-aligned ellipsoid enclosing S. Our computational results indicate that the algorithm exhibits significantly better performance than the theoretical worst-case complexity estimate. [ABSTRACT FROM AUTHOR]

We study the problem of computing a (1 + ϵ)-approximation to the minimum-volume enclosing ellipsoid of a given point set S = {p¹, p², ¡, pn} ⊆ Rd Based on a simple, initial volume approximation method, we propose a modification of the Khachiyan first-order algorithm. Our analysis leads to a slightly improved complexity bound of O(nd³/ϵ) operations for ϵ ∊ (0, 1). As a byproduct, our algorithm returns a core set X ⊆ S with the property that the minimum-volume enclosing ellipsoid of X provides a good approximation to that of S. Furthermore, the size of X depends on only the dimension d and ϵ, but not on the number of points n. In particular, our results imply that ∣X∣ = O(d²/ϵ) for ϵ ∊(0, 1). [ABSTRACT FROM AUTHOR]