Search

As one of the most plausible convex optimization methods for sparse data reconstruction, ℓ1-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as the restricted isometry property, null space property, and mutual coherence. In this paper, we propose a unified means to develop the so-called weak stability theory for ℓ1-minimization methods under the condition called the weak range space property of a transposed design matrix, which turns out to be a necessary and sufficient condition for the standard ℓ1-minimization method to be weakly stable in sparse data reconstruction. The reconstruction error bounds established in this paper are measured by the so-called Robinson's constant. We also provide a unified weak stability result for standard ℓ1-minimization under several existing compressed sensing matrix properties. In particular, the weak stability of this method under the constant-free range space property of the transposed design matrix is established, to our knowledge, for the first time in this paper. Different from the existing analysis, we utilize the classic Hoffman's lemma concerning the error bound of linear systems as well as Dudley's theorem concerning the polytope approximation of the unit ball to show that ℓ1-minimization is robustly and weakly stable in recovering sparse data from inaccurate measurements. [ABSTRACT FROM AUTHOR]

In this paper, we use the penalty approach in order to study constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper, we establish the exact penalty property for a large class of inequality-constrained minimization problems. [ABSTRACT FROM AUTHOR]

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e. starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games. [ABSTRACT FROM AUTHOR]

This paper deals with nonhomogeneous Markov decision processes with Borel state space and nonuniformly bounded rewards under the average criterion. First, under the minorant-type assumption we prove the existence of an appropriate solution to the optimality equations. Second, from the optimality equations we also establish the existence of ε(≥ 0)-optimal Markov policies under the additional conditions. Third, some sufficient conditions for the validity of the assumptions in this paper and several examples such as inventory/production systems are provided. Finally, as an application of the optimality equations, a rolling horizon algorithm is given. [ABSTRACT FROM AUTHOR]

The mathematical equivalence between linear scalarizations in multiobjective programming and expected-value functions in stochastic optimization suggests to investigate and establish further conceptual analogies between these two areas. In this paper, we focus on the notion of proper efficiency that allows us to provide a first comprehensive analysis of solution and scenario tradeoffs in stochastic optimization. In generalization of two standard characterizations of properly efficient solutions using weighted sums and augmented weighted Tchebycheff norms for finitely many criteria, we show that these results are generally false for infinitely many criteria. In particular, these observations motivate a slightly modified definition to prove that expected-value optimization over continuous random variables still yields bounded tradeoffs almost everywhere in general. Further consequences and practical implications of these results for decision-making under uncertainty and its related theory and methodology of multiple criteria, stochastic and robust optimization are discussed. [ABSTRACT FROM AUTHOR]

In this paper we consider the optimization problem of an agent who wants to maximize the total expected discounted utility from consumption over an infinite horizon. The agent is under obligation to pay a debt at a .fixed rate until he/she declares bankruptcy. At that point, after paying a .fixed cost, the agent will be able to keep a certain fraction of the present wealth, and the debt will be forgiven. The selection of the bankruptcy time is taken to be at the discretion of the agent. The novelty of this paper is that at the time of bankruptcy the wealth process has a discontinuity, and that the agent continues to invest and consume after bankruptcy. We show that the solution of a free boundary problem satisfying some additional conditions is the value function of the above optimization problem. Particular examples such as the logarithmic and the power utility functions will be provided, and in these cases explicit forms will be given for the optimal bankruptcy time, investment and consumption processes. [ABSTRACT FROM AUTHOR]

Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases. [ABSTRACT FROM AUTHOR]

This paper introduces a class of contest models in which each player decides when to stop a privately observed Brownian motion with drift and incurs costs depending on his stopping time. The player who stops his process at the highest value wins a prize. We prove existence and uniqueness of a Nash equilibrium outcome and derive the equilibrium distribution in closed form. As the variance tends to zero, the equilibrium outcome converges to the symmetric equilibrium of an all-pay auction. For two players and constant costs, each player's equilibrium profit decreases if the drift increases, the variance decreases, or the costs decrease. [ABSTRACT FROM AUTHOR]

Randomizing (stochastic) global optimization algorithms can be viewed as sampling procedures, where at each iteration a local optimum is sampled from the set of local optima. The effectiveness of such an algorithm depends crucially on the sampling distribution, i.e., on the probabilities of sampling the various local optima. There exists a very large body of research on stochastic global optimization. However, very little is known about the sampling distribution itself and, in particular, on the specific way in which it depends on the function being optimized, on the region in which the search takes place, and on the optimization routine. In this paper we set out to examine these issues in some detail and present some first results in this direction. The case analyzed in this paper is the optimization of a one-dimensional function using a randomizing version of binary search. We give an effective (computable in quadratic time) formula for the sampling distribution and obtain various interesting properties of this distribution which are relevant to the behavior of the algorithm in practice. We also discuss some issues related to adaptive search. [ABSTRACT FROM AUTHOR]

This paper considers the problem faced by a seller who has a single object to sell to ()ne of several possible buyers, when the seller has imperfect information about how much the buyers might be willing to pay for the object. The seller's problem is to design an auction game which has a Nash equilibrium giving him the highest possible expected utility. Optimal auctions are derived in this paper for a wide class of auction design problems. [ABSTRACT FROM AUTHOR]

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In a recent paper [Chen X, Peng J, Zhang S (2013) Sparse solutions to random standard quadratic optimization problems. Math. Programming 141(1-2):273-293], Chen, et al. showed that with a high probability close to 1, StQPs with random data have sparse optimal solutions when the associated data matrix is randomly generated from a certain distribution such as uniform and exponential distributions. In this paper, we present a new analysis for random StQPs combining probability inequalities derived from the first-order and second-order optimality conditions. The new analysis allows us to significantly improve the probability bounds. More important, it allows us to handle normal distributions, which is left open in Chen et al. (2013). The existence of sparse approximate solutions to convex StQPs and extensions to other classes of QPs are discussed as well. [ABSTRACT FROM AUTHOR]

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

Ryser’s max term rank formula with graph theoretic terminology is equivalent to a characterization of degree sequences of simple bipartite graphs with a specific matching number. In a previous paper by the authors, a generalization was developed for the case when the degrees are constrained by upper and lower bounds. Here, two other extensions of Ryser’s theorem are discussed. The first one is a matroidal model, while the second one settles the augmentation version. In fact, the two directions shall be integrated into one single framework. [ABSTRACT FROM AUTHOR]

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

Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location, and marketing over social networks. In this paper we consider the problem of maximizing any submodular function subject to d knapsack constraints, where d is a fixed constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through extension by expectation of the submodular function. Formally, we show that, for any nonnegative submodular function, an ∝-approximation algorithm for the continuous relaxation implies a randomized (∝-ε)-approximation algorithm for the discrete problem. We use this relation to obtain an (e-1-ε)-approximation for the problem, and a nearly optimal (1-e-1;-ε)-approximation ratio for the monotone case, for any ε>0. We further show that the probabilistic domain defined by a continuous solution can be reduced to yield a polynomial-size domain, given an oracle for the extension by expectation. This leads to a deterministic version of our technique. [ABSTRACT FROM AUTHOR]

This paper presents sufficient conditions for the existence of stationary optimal policies for average cost Markov decision processes with Borel state and action sets and weakly continuous transition probabilities. The one-step cost functions may be unbounded, and the action sets may be noncompact. The main contributions of this paper are: (i) general sufficient conditions for the existence of stationary discount optimal and average cost optimal policies and descriptions of properties of value functions and sets of optimal actions, (ii) a sufficient condition for the average cost optimality of a stationary policy in the form of optimality inequalities, and (iii) approximations of average cost optimal actions by discount optimal actions. [ABSTRACT FROM AUTHOR]

The multiobjective bilevel program is a sequence of two optimization problems, with the upper-level problem being multiobjective and the constraint region of the upper level problem being determined implicitly by the solution set to the lower-level problem. In the case where the Karush-Kuhn-Tucker (KKT) condition is necessary and sufficient for global optimality of all lower-level problems near the optimal solution, we present various optimality conditions by replacing the lower-level problem with its KKT conditions. For the general multiobjective bilevel problem, we derive necessary optimality conditions by considering a combined problem, with both the value function and the KKT condition of the lower-level problem involved in the constraints. Most results of this paper are new, even for the case of a single-objective bilevel program, the case of a mathematical program with complementarity constraints, and the case of a multiobjective optimization problem. [ABSTRACT FROM AUTHOR]

This paper is devoted to applications of modem methods of variational analysis to constrained optimization and control problems generally formulated in infinite-dimensional spaces. The main focus is on the study of problems with nonsmooth structures, which require the usage of advanced tools of generalized differentiation. In this way we derive new necessary optimality conditions in optimization problems with functional and operator constraints and then apply them to optimal control problems governed by discrete-time inclusions in infinite dimensions. The principal difference between finite-dimensional and infinite-dimensional frameworks of optimization and control consists of the "lack of compactness" in infinite dimensions, which leads to imposing certain "normal compactness" properties and developing their comprehensive calculus, together with appropriate calculus rules of generalized differentiation. On the other hand, one of the most important achievements of the paper consists of relaxing the latter assumptions for certain classes of optimization and control problems. In particular, we fully avoid the requirements of this type imposed on target endpoint sets in infinite-dimensional optimal control for discrete-time inclusions. [ABSTRACT FROM AUTHOR]

In this paper, optimization problems P with complementarity constraints are considered. Characterizations for local minimizers x̄ P of Orders 1 and 2 are presented. We analyze a parametric smoothing approach for solving these programs in which P is replaced by a perturbed problem PT depending on a (small) parameter τ. We are interested in the convergence behavior of the feasible set 퓕τ and the convergence of the solutions x̄ of Pτ for τ → 0. In particular, it is shown that, under generic assumptions, the solutions x̄τ are unique and converge to a solution x̄ of P with a rate ...(√τ). Moreover, the convergence for the Hausdorff distance d(퓕τ, 퓕) between the feasible sets of Pτ and P is of order ...(√τ). [ABSTRACT FROM AUTHOR]

The paper is devoted to a comprehensive study of composite models in variational analysis and optimization the importance of which for numerous theoretical, algorithmic, and applied issues of operations research is difficult to overstate. The underlying theme of our study is a systematical replacement of conventional metric regularity and related requirements by much weaker metric subregulatity ones that lead us to significantly stronger and completely new results of first-order and second-order variational analysis and optimization. In this way, we develop extended calculus rules for first-order and second-order generalized differential constructions while paying the main attention in second-order variational theory to the new and rather large class of fully subamenable compositions. Applications to optimization include deriving enhanced no-gap second-order optimality conditions in constrained composite models, complete characterizations of the uniqueness of Lagrange multipliers, strong metric subregularity of Karush-Kuhn-Tucker systems in parametric optimization, and so on. [ABSTRACT FROM AUTHOR]

In the linear programming approach to approximate dynamic programming, one tries to solve a certain linear program--the ALP--that has a relatively small number K of variables but an intractable number M of constraints. In this paper, we study a scheme that samples and imposes a subset of m«M constraints. A natural question that arises in this context is: How must m scale with respect to K and M in order to ensure that the resulting approximation is almost as good as one given by exact solution of the ALP? We show that, given an idealized sampling distribution and appropriate constraints on the K variables, m can be chosen independently of M and need grow only as a polynomial in K. We interpret this result in a context involving controlled queueing networks. [ABSTRACT FROM AUTHOR]

Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous efforts for exact algorithms have been unable to avoid structural problems that appear for instance in two-or higher-dimensional space. We present a new approach for modeling packings, using a graph-theoretical characterization of feasible packings. Our characterization allows it to deal with classes of packings that share a certain combinatorial structure, instead of having to consider one packing at a time. In addition, we can make use of elegant algorithmic properties of certain classes of graphs. This allows our characterization to be the basis for a successful branch-and-bound framework. This is the first in a series of papers describing new approaches to higher-dimensional packing. [ABSTRACT FROM AUTHOR]

In this paper, we present a framework for the condition-based maintenance optimization. A technical system which can be in one of N operational states or in a failure state is considered. The system state is not observable, except the failure state. The information that is stochastically related to the system state is obtained through condition monitoring at equidistant inspection times. The system can be replaced at any time; a preventive replacement is less costly than failure replacement. The objective is to find a replacement policy minimizing the long run expected average cost per unit time. The replacement problem is formulated as an optimal stopping problem with partial information and transformed to a problem with complete information by applying the projection theorem to a smooth semimartingale process in the objective function. The dynamic equation is derived and analyzed in the piecewise deterministic Markov process stopping framework. The contraction property is shown and an algorithm for the calculation of the value function is presented, illustrated by an example. [ABSTRACT FROM AUTHOR]

Primal methods constitute a common approach to solving (combinatorial) optimization problems. Starting from a given feasible solution, they successively produce new feasible solutions with increasingly better objective function value until an optimal solution is reached. From an abstract point of view, an augmentation problem is solved in each iteration. That is, given a feasible point, these methods find an augmenting vector, if one exists. Usually, augmenting vectors with certain properties are sought to guarantee the polynomial running time of the overall algorithm. In this paper, we show that one can solve every integer programming problem in polynomial time provided one can efficiently solve the directed augmentation problem. The directed augmentation problem arises from the ordinary augmentation problem by splitting each direction into its positive and its negative part and by considering linear objectives on these parts. Our main result states that in order to get a polynomial-time algorithm for optimization it is sufficient to efficiently find, for any linear objective function in the positive and negative part, an arbitrary augmenting vector. This result also provides a general framework for the design of polynomial-time algorithms for specific combinatorial optimization problems. We demonstrate its applicability by considering the min-cost flow problem, by giving a novel algorithm for linear programming over unimodular spaces, and by providing a different proof that for 0/1-integer programming an efficient algorithm solving the ordinary augmentation problem suffices for efficient optimization. Our main result also implies that directed augmentation is at least as hard as optimization. In other words, for an NP-hard problem already the task of finding a directed augmenting vector in polynomial time is hopeless, unless P = NP. We illustrate this kind of consequence with the help of the knapsack problem. [ABSTRACT FROM AUTHOR]

In this paper we examine a number of different definitions of strategic stability and the relations among them. In particular, we show that the stability requirement given by Hillas (1990) is weaker than the requirements involved in the various definitions of stability in Mertens' reformulation of stability (Mertens 1989,1991). To this end, we introduce a new definition of stability and show that it is equivalent to (a variant of ) the definition given by Hillas (1990). We also use the equivalence of our new definition with the definition of Hillas to provide correct proofs of some of the results that were originally claimed (and incorrectly 'proved') in Hillas (1990). [ABSTRACT FROM AUTHOR]

The use of generalized distances (e.g., Bregman distances), instead of the Euclidean one, in the proximal point method for convex optimization, allows for elimination of the inequality constraints from the subproblems. In this paper we consider the proximal point method with Bregman distances applied to linearly constrained convex optimization problems, and study the behavior of the dual sequence obtained from the optimal multipliers of the linear constraints of each subproblem. Under rather general assumptions, which cover most Bregman distances of interest, we obtain an ergodic convergence result, namely that a sequence of weighted averages of the dual sequence converges to a specific point of the dual optimal set. As an intermediate result, we prove under the same assumptions that the dual central path generated by a large class of barriers, including the generalized Bregman distances, converges to the same point. [ABSTRACT FROM AUTHOR]

In this paper we investigate the properties of multimodular functions. In doing so we give elementary proofs for properties already established by Hajek and we generalize some of his results. In particular, we extend the relation between convexity and multimodularity to some convex subsets of Zm. We also obtain general optimization results for average costs related lo a sequence of multimodular functions rather than to a single function. Under this general context, we show that the expected average cost problem is optimized by using regular sequences. We finally illustrate the usefulness of this theory in admission control into a D/D/1 queue with fixed batch arrivals, with no state information. We show that the regular policy minimizes the average queue length for the case of an infinite queue, but not for the case of a finite queue. When further adding a constraint on the losses, it is shown that a regular policy is also optimal for the finite queue case. [ABSTRACT FROM AUTHOR]

Calculating optimal policies is known to be computationally difficult for Markov decision processes (MDPs) with Borel state and action spaces. This paper studies finite-state approximations of discrete time Markov decision processes with Borel state and action spaces, for both discounted and average costs criteria. The stationary policies thus obtained are shown to approximate the optimal stationary policy with arbitrary precision under quite general conditions for discounted cost and more restrictive conditions for average cost. For compact-state MDPs, we obtain explicit rate of convergence bounds quantifying how the approximation improves as the size of the approximating finite state space increases. Using information theoretic arguments, the order optimality of the obtained convergence rates is established for a large class of problems. We also show that as a pre-processing step, the action space can also be finitely approximated with sufficiently large number points; thereby, well known algorithms, such as value or policy iteration, Q-learning, etc., can be used to calculate near optimal policies. [ABSTRACT FROM AUTHOR]

Ever since Tassiulas and Ephremides in 1992 proposed the maximum weight scheduling algorithm of throughput optimality for constrained queueing networks that arise in the context of communication networks, extensive efforts have been devoted to resolving its most important drawback: high complexity. This paper proposes a generic framework for designing throughput-optimal and low-complexity scheduling algorithms for constrained queueing networks. Under our framework, a scheduling algorithm updates current schedules by interacting with a given oracle system that generates an approximate solution to a related optimization task. One can use our framework to design a variety of scheduling algorithms by choosing an oracle system such as random 7524 Markov chain, belief propagation, and primal-dual methods. The complexity of the resulting scheduling algorithm is determined by the number of operations required for an oracle to process a single query, which is typically small. We provide sufficient conditions for throughput optimality of the scheduling algorithm, in general, constrained queueing network models. The linear time algorithm of Tassiulas in 1998 and the random access algorithm of Shah and Shin in 2012 correspond to special cases of our framework using random search and Markov chain oracles, respectively. Our generic framework, however, provides a unified proof with milder assumptions. [ABSTRACT FROM AUTHOR]

The famous Braess paradox describes the counterintuitive phenomenon in which, in certain settings, an increase of resources, such as a new road built within a congested network, may in fact lead to larger costs for the players in an equilibrium. In this paper, we consider general nonatomic congestion games and give a characterization of the combinatorial property of strategy spaces for which the Braess paradox does not occur. In short, matroid bases are precisely the required structure. We prove this characterization by two novel sensitivity results for convex separable optimization problems over polymatroid base polyhedra, which may be of independent interest. [ABSTRACT FROM AUTHOR]

The ℓ0-minimization problem that seeks the sparsest point of a polyhedral set is a long-standing, challenging problem in the fields of signal and image processing, numerical linear algebra, and mathematical optimization. The weighted ℓ1-method is one of the most plausible methods for solving this problem. In this paper we develop a new weighted ℓ1-method through the strict complementarity theory of linear programs. More specifically, we show that locating the sparsest point of a polyhedral set can be achieved by seeking the densest possible slack variable of the dual problem of weighted ℓ1-minimization. As a result, ℓ0-minimization can be transformed, in theory, to ℓ0-maximization in dual space through some weight. This theoretical result provides a basis and an incentive to develop a new weighted ℓ1-algorithm, which is remarkably distinct from existing sparsity-seeking methods. The weight used in our algorithm is computed via a certain convex optimization instead of being determined locally at an iterate. The guaranteed performance of this algorithm is shown under some conditions, and the numerical performance of the algorithm has been demonstrated by empirical simulations. [ABSTRACT FROM AUTHOR]

This paper generalizes the Debreu/Gorman characterization of additively decomposable functionals and separable preferences to infinite dimensions. The first novelty concerns the very definition of additively decomposable functionals for infinite dimensions. For decision under uncertainty, our result provides a state-dependent extension of Savage's expected utility. A characterization in terms of preference conditions identifies the empirical content of the model; it amounts to Savage's axiom system with P4 (likelihood ordering) dropped. Our approach does not require that a (probability) measure on the state space be given a priori, or can be derived from extraneous conditions outside the realm of decision theory. Bayesian updating of new information is still possible, even though no prior probabilities are given. The finding suggests that the sure-thing principle, rather than prior probability, is at the heart of Bayesian updating. [ABSTRACT FROM AUTHOR]

We study convex optimization problems for which the data is not specified exactly and it is only known to belong to a given uncertainty set U, yet the constraints must hold for all possible values of the data from U. The ensuing optimization problem is called robust optimization. In this paper we lay the foundation of robust convex optimization. In the main part of the paper we show that if U is an ellipsoidal uncertainty set, then for some of the most important generic convex optimization problems (linear programming, quadratically constrained programming, semidefinite programming and others) the corresponding robust convex program is either exactly, or approximately, a tractable problem which lends itself to efficient algorithms such as polynomial time interior point methods. [ABSTRACT FROM AUTHOR]

Develops a theory of sensors for the analysis of information available in stochastic optimization problems. Application to a variant of the newsboy problem; Properties of sensors; Comparison with the sigma-field or signals method.

In this paper we extend recent work on muting and capacity allocation in circuit-switched networks to include the possible use of trunk reservation. Trunk reservation is an easily implemented control mechanism which allows priority to be given to chosen traffic streams. It has the potential to be an extremely efficient control mechanism, but its use on any single link of a network has ramifications which may extend throughout the network, and it is important to take this into account. Using a simplified analytical model of a circuit-switched network incorporating trunk reservation, we show that there exist implied costs associated with the priority and nonpriority calls routed through a link, and shadow prices associated with the capacity for priority and nonpriority traffic through a link. Mathematically, this involves calculating derivatives of an implicitly defined function, and expressing these derivatives as simple functions of certain variables. These variables, the implied costs and shadow prices, are determined as solutions to a set of linear equations possessing a local or decentralized character, and can be used as a basis for routing and capacity allocation strategies. [ABSTRACT FROM AUTHOR]

Many important problems in economic dynamics can be formulated as optimal control problems in which the controls must be monotone functions of time. In this paper we will completely solve a problem with quadratic payoff involving the control and the derivative of the control by constructing optimal monotone controls. Several generalizations and examples are also given. [ABSTRACT FROM AUTHOR]

This paper compares solution concepts associated with three location problems on a network: (i) a single-facility distance minimization problem; (ii) a two-facility spatial competition problem; and (iii) a single-facility locational voting problem. It is shown that the three problems have a common global solution when the network exhibits a property of symmetry around a point. For more general networks, this ceases to be true for global solutions but an identity holds for local solutions. [ABSTRACT FROM AUTHOR]

In a recent paper [3] the authors gave sufficient conditions for the weak convergence of a sequence of discrete time Markov decision drift processes to a related continuous time Markov decision drift process. The goal of this analysis was to obtain for the continuous time model conditions for optimality of a limit point of a sequence of discounted discrete time optimal policies. However, the general conditions in [3] can only be applied to a very restrictive class of models. To obtain more widely applicable conditions we are concerned in this paper not with the weak convergence of the stochastic processes induced by policies, but rather with the convergence of the total expected discounted costs. Special attention is paid to the case of unbounded cost functions. Sufficient conditions on model parameters and policies are given to guarantee the convergence of the expected discounted costs of a sequence of discrete time models to those of a related continuous time model These results are used to identify the optimal policy of a continuous lime model by means of the optimal policies of a sequence of approximating discrete time models. An application to an M/M/l queueing model is given. [ABSTRACT FROM AUTHOR]

This paper gives sufficient conditions for the existence of average optimal policies in a decision model, which is a generalization of a denumerable state space semi-Markov decision model. The conditions extend most of those previously known; especially, neither unichainedness nor communicatingness is assumed. An average optimal policy can be obtained as a limit of discount optimal policies. If structured policies are discount optimal, there exists a structured average optimal policy. The results are applicable to more general continuous time models such as the one by Yushkevich and Fainberg [35]. [ABSTRACT FROM AUTHOR]

This paper establishes the existence of a solution to the optimality equations in undiscounted semi-Markov decision models with countable state space, under conditions generalizing the hitherto obtained results. In particular, we merely require the existence of a finite set of states in which every pair of states can reach each other via some stationary policy, instead of the traditional and restrictive assumption that every stationary policy has a single irreducible set of states. A replacement model and an inventory model illustrate why this extension is essential. Our approach differs fundamentally from classical approaches: we convert the optimality equations into a form suitable for the application of a fixed point theorem. [ABSTRACT FROM AUTHOR]

We find necessary and sufficient conditions for maximizing a wide class of nonlinear, nonseparable functionals under separable constraints. The crucial restriction on the functionals is that they have a Gateaux differential which is a linear functional with a kernel. The conditions obtained can be applied to a large variety of optimal search problems involving moving targets when effort is infinitely divisible in space. Moreover, the conditions have been used to construct very efficient algorithms for solving these problems. It is conjectured that these results are useful in a general class of optimization problems that extend well beyond the search theory examples presented in this paper. [ABSTRACT FROM AUTHOR]

Let A be the problem of minimizing c[sub1x[sub1] + ... + c[subn]x[subn] subject to certain constraints on x = (x[sub1], ...., x[subn]), and let B be the problem of minimizing (a[sub0] + a[sub1]x[sub1] + ... + a[subn]x[subn])/(b[sub0] + b[sub1]x[sub1]+ ...+ b[subn]x[subn]) subject to the same constraints, assuming the denominator is always positive. It is shown that if A is solvable within O [p(n)] comparisons and O [q(n)] additions, then B is solvable in time O[p(n)(q(n)+p(n))]. This applies to most of the "network" algorithms. Consequently, minimum ratio cycles, minimum ratio spanning trees, minimum ratio (simple) paths, maximum ratio weighted matchings, etc., can be computed withing polynomial-time in the number of variables. This improves a result of E. L. Lawler, namely, that a minimum ratio cycle can be computed within a time bound which is polynomial in the number of bits required to specify an instance of the problem. A recent result on minimum ratio spanning trees by R. Chandrasekaran is also improved by the general arguments presented in this paper. Algorithms of time-complexity O(|E|•|V|²•log|V|) for a minimum ratio cycle and O(|E|•log²|V|•log log|V|) for a minimum ratio spanning tree are developed. [ABSTRACT FROM AUTHOR]

A general multistage problem of stochastic optimization is studied. It is proved under some simple assumptions that the extremum in the problem is attained. The "Bellman functions" are constructed and a criterion of optimality in terms of these functions is given. The main tools used are measurable selection theorems. The paper generalizes the previous work of R. T. Rockafellar and R. J.-B. Wets devoted to the convex case. [ABSTRACT FROM AUTHOR]

The problem of finding a minimizer of the sum of two convex functions-or, more generally, that of finding a zero of the sum of two maximally monotone operators-is of central importance in variational analysis. Perhaps the most popular method of solving this problem is the Douglas-Rachford splitting method. Surprisingly, little is known about the range of the Douglas-Rachford operator. In this paper, we set out to study this range systematically. We prove that for 3* monotone operators a very pleasing formula can be found that reveals the range to be nearly equal to a simple set involving the domains and ranges of the underlying operators. A similar formula holds for the range of the corresponding displacement mapping. We discuss applications to subdifferential operators, to the infimal displacement vector, and to firmly nonexpansive mappings. Various examples and counterexamples are presented, including some concerning the celebrated Brezis-Haraux theorem. [ABSTRACT FROM AUTHOR]

In this paper, we study distributionally robust optimization approaches for a one-stage stochastic minimization problem, where the true distribution of the underlying random variables is unknown but it is possible to construct a set of probability distributions, which contains the true distribution and optimal decision is taken on the basis of the worst-possible distribution from that set. We consider the case when the distributional set (which is also known as the ambiguity set) varies and its impact on the optimal value and the optimal solutions. A typical example is when the ambiguity set is constructed through samples and we need to look into the impact of increasing the sample size. The analysis provides a unified framework for convergence of some problems where the ambiguity set is approximated in a process with increasing information on uncertainty and extends the classical convergence analysis in stochastic programming. The discussion is extended briefly to a stochastic Nash equilibrium problem where each player takes a robust action on the basis of the worst subjective expected objective values. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the portfolio optimization problem associated with a quasiconvex risk measure (satisfying some additional assumptions). For coherent/convex risk measures, the portfolio optimization problem has been already studied in the literature. Following the approach of Ruszczy'nski and Shapiro [Ruszczy'nski A, Shapiro A (2006) Optimization of convex risk functions. Math. Oper. Res. 31(3):433-452.], but by means of quasiconvex analysis and notions of subdifferentiability, we characterize optimal solutions of the portfolio problem associated with quasiconvex risk measures. The shape of the efficient frontier in the mean-risk space and some particular cases are also investigated. [ABSTRACT FROM AUTHOR]

Metric subregularity and regularity of multifunctions are fundamental notions in variational analysis and optimization. Using the concept of strong slope, in this paper we first establish a criterion for metric subregularity of multifunctions between metric spaces. Next, we use a combination of abstract coderivatives and contingent derivatives to derive verifiable first order conditions ensuring metric subregularity of multifunctions between Banach spaces. Then using second order approximations of convex multifunctions, we establish a second order condition for metric subregularity of mixed smooth-convex constraint systems, which generalizes a result established recently by Gfrerer [Gfrerer H (2011) First order and second order characterizations of metric subregularity and calmness of constraint set mapping. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of optimal design of experiments. A two-step inference strategy is proposed. The first step consists in minimizing the condition number of the so-called information matrix. This step can be turned into a semidefinite programming problem. The second step is more classical, and it entails the minimization of a convex integral functional under linear constraints. This step is formulated in some infinite-dimensional space and is solved by means of a dual approach. Numerical simulations will show the relevance of our approach. [ABSTRACT FROM AUTHOR]

One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast first order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gradients of the cost function required by deterministic first order saddle point algorithms and becoming prohibitively computationally expensive in the extremely large-scale case, can be replaced with incomparably cheaper computationally unbiased random estimates of the gradients. We show that for large-scale problems with favorable geometry, this randomization accelerates, progressively as the sizes of the problem grow, the solution process. This extends significantly previous results on acceleration by randomization, which, to the best of our knowledge, dealt solely with bilinear saddle point problems. We illustrate our theoretical findings by instructive and encouraging numerical experiments. [ABSTRACT FROM AUTHOR]

One of the fundamental problems in a cognitive radio network, known as the multichannel rendezvous problem, is for two secondary users to find a common channel that is not blocked by primary users. The basic idea for solving such a problem in most works in the literature is for the two users to select their own channel hopping sequences and then rendezvous when they both hop to a common unblocked channel at the same time. In this paper, we focus on the fundamental limits of the multichannel rendezvous problem and formulate such a problem as a constrained optimization problem, where the selection of the random hopping sequences of the two secondary users must satisfy certain constraints. We derive various lower bounds for the expected (respectively, maximum) time-to-rendezvous under certain constraints. For some of these lower bounds, we are also able to construct optimal channel hopping sequences that achieve the lower bounds. Inspired by the constructions of quorum systems and relative difference sets, our constructions of the channel hopping sequences are based on the mathematical theories of finite projective planes, orthogonal Latin squares, and sawtooth sequences. The use of such theories in the constructions of channel hopping sequences appear to be new and better than other existing schemes in terms of minimizing the expected (respectively, maximum) time-to-rendezvous. [ABSTRACT FROM AUTHOR]