Search

This article provides instructions in preparing a paper for publication in the "Journal of Optimization Theory and Applications." Some of these guidelines are the following: 1)submission of manuscripts in triplicate; 2) reference to English as the official language of the journal; 3) inclusion of an abstract of at least 50 to 100 words in each contribution; and, 4) the abstract should be followed by a list of four to five key words identifying the subject.

A chance constrained optimization problem over a finite distribution involves a set of scenario constraints from which a small subset can be violated. We consider the setting where all scenario constraints are mixed-integer convex. Existing works typically consider a mixed integer nonlinear programming (MINLP) formulation of this problem by introducing binary variables to indicate which constraint systems are to be satisfied or violated. A variety of cutting plane approaches for this MINLP formulation have been developed. In this paper we consider a family of cuts in the original space rather than those in the extended space of the MINLP reformulation. These cuts, known as quantile cuts, can be viewed as a projection of the well known family of mixing inequalities for the MINLP reformulation onto the original problem space. We show that the closure of the infinite family of all quantile cuts has a finite description. An important corollary of this result is that for linear chance constrained problems the quantile closure is polyhedral. We further show that a recursive application of quantile closure operations recovers the convex hull of the nonconvex chance constrained set in the limit, and in the pure integer setting the convergence is finite. We show that separation of quantile cuts is in general NP-hard, develop a heuristic separation method, and demonstrate its effectiveness through a computational study. We also study an approximation of the quantile closure and propose a generalization by grouping scenarios. [ABSTRACT FROM AUTHOR]

In this paper, optimality conditions are presented and analyzed for the cardinality-constrained cone programming arising from finance, statistical regression, signal processing, etc. By introducing a restricted form of (strict) Robinson constraint qualification, the first-order optimality conditions for the cardinality-constrained cone programming are established based upon the properties of the normal cone. After characterizing further the second-order tangent set to the cardinality-constrained system, the second-order optimality conditions are also presented under some mild conditions. These proposed optimality conditions, to some extent, enrich the optimization theory for noncontinuous and nonconvex programming problems. [ABSTRACT FROM AUTHOR]

For 30 years after their invention half a century ago, cutting planes for integer programs have been an object of theoretical investigations that had no apparent practical use. When they finally proved their practical usefulness in the late eighties, that happened in the framework of branch and bound procedures, as an auxiliary tool meant to reduce the number of enumerated nodes. To this day, pure cutting plane methods alone have poor convergence properties and are typically not used in practice. Our reason for studying them is our belief that these negative properties can be understood and thus remedied only based on a thorough investigation of such procedures in their pure form. In this paper, the second in a sequence, we address some important issues arising when designing a computationally sound pure cutting plane method. We analyze the dual cutting plane procedure proposed by Gomory in 1958, which is the first (and most famous) convergent cutting plane method for integer linear programming. We focus on the enumerative nature of this method as evidenced by the relative computational success of its lexicographic version (as documented in our previous paper on the subject), and we propose new versions of Gomory's cutting plane procedure with an improved performance. In particular, the new versions are based on enumerative schemes that treat the objective function implicitly, and redefine the lexicographic order on the fly to mimic a sound branching strategy. Preliminary computational results are reported. [ABSTRACT FROM AUTHOR]

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

We found a minor error in the proof of paper “Universal Alignment Probability Revisited” by S.Y. Lin and Y.C. Ho (J. Optim. Theory Appl. 113(2):399–407, ). In this note, we give a counterexample and explain the reason. We also show that the conclusion of that paper is still correct despite this minor error. A new proof of the conclusion is given. [ABSTRACT FROM AUTHOR]

This paper deals with a parametric family of convex semi-infinite optimization problems for which linear perturbations of the objective function and continuous perturbations of the right-hand side of the constraint system are allowed. In this context, Cánovas et al. (SIAM J. Optim. 18:717–732, []) introduced a sufficient condition (called ENC in the present paper) for the strong Lipschitz stability of the optimal set mapping. Now, we show that ENC also entails high stability for the minimal subsets of indices involved in the KKT conditions, yielding a nice behavior not only for the optimal set mapping, but also for its inverse. Roughly speaking, points near optimal solutions are optimal for proximal parameters. In particular, this fact leads us to a remarkable simplification of a certain expression for the (metric) regularity modulus given in Cánovas et al. (J. Glob. Optim. 41:1–13, []) (and based on Ioffe (Usp. Mat. Nauk 55(3):103–162, []; Control Cybern. 32:543–554, [])), which provides a key step in further research oriented to find more computable expressions of this regularity modulus. [ABSTRACT FROM AUTHOR]

This paper examines a number of variants of the sparse k-spanner problem and presents hardness results concerning their approximability. Previously, it was known that most k-spanner problems are weakly inapproximable (namely, they are NP-hard to approximate with ratio O(log n), for every k ≥ 2) and that the unit-length k-spanner problem for constant stretch requirement k ≥ 5 is strongly inapproximable (namely, it is NP-hard to approximate with ratio $O(2^{{\log}^{1 - \epsilon} n})$ ). The results of this paper significantly expand the ranges of hardness for k-spanner problems. In general, strong hardness is shown for a number of k-spanner problems, for certain ranges of the stretch requirement k depending on the particular variant at hand. The problems studied differ by the types of edge weights and lengths used, and they include directed, augmentation and client-server variants. The paper also considers k-spanner problems in which the stretch requirement k is relaxed (e.g., $k = \Omega(\log n))$ . For these cases, no inapproximability results were known (even for a constant approximation ratio) for any spanner problem. Moreover, some versions of the k-spanner problem are known to enjoy the ratio-degradation property; namely, their complexity decreases exponentially with the inverse of the stretch requirement. So far, no hardness result existed precluding any k-spanner problem from enjoying this property. This paper establishes strong inapproximability results for the case of relaxed stretch requirement (up to $k = O(n^{{1 - \delta}})$ , for any $0 < \delta < 1$ ), for a large variety of k-spanner problems. It is also shown that these problems do not enjoy the ratio-degradation property. [ABSTRACT FROM AUTHOR]

This paper proposes several globally convergent geometric optimization algorithms on Riemannian manifolds, which extend some existing geometric optimization techniques. Since any set of smooth constraints in the Euclidean space Rn (corresponding to constrained optimization) and the Rn space itself (corresponding to unconstrained optimization) are both special Riemannian manifolds, and since these algorithms are developed on general Riemannian manifolds, the techniques discussed in this paper provide a uniform framework for constrained and unconstrained optimization problems. Unlike some earlier works, the new algorithms have less restrictions in both convergence results and in practice. For example, global minimization in the one-dimensional search is not required. All the algorithms addressed in this paper are globally convergent. For some special Riemannian manifold other than Rn, the newalgorithms are very efficient. Convergence rates are obtained. Applications are discussed. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new methodology for handling optimization problems with uncertain data. With the usual Robust Optimization paradigm, one looks for the decisions ensuring a required performance for all realizations of the data from a given bounded uncertainty set, whereas with the proposed approach, we require also a controlled deterioration in performance when the data is outside the uncertainty set. The extension of Robust Optimization methodology developed in this paper opens up new possibilities to solve efficiently multi-stage finite-horizon uncertain optimization problems, in particular, to analyze and to synthesize linear controllers for discrete time dynamical systems. [ABSTRACT FROM AUTHOR]

Rufus P. Isaacs joined the RAND Corporation4. Santa Monica, California in 1948 and started to develop the theory of dynamic games in the early 1950s. Until winter 1954/55, when Isaacs left the RAND Corporation, he investigated two player. zero-sum dynamic games of the classic pursuit-evasion type. Prior to 1965, Isaacs published his theory only in internal RAND papers and research memoranda. In his first RAND paper (Ref. 1), Isaacs sketched the basic ideas of zero-sum dynamic game theory The ideas already included rudimentary precursors of the maximum principle, dynamic programming, and backward analysis. At the end of 1954 and the beginning of 1955. Isaacs summarized his research in four research memoranda (Refs. 3–6), which ten years later formed the basis of his famous book on Differential Games (Ref. 7). This paper survey's Isaacs' research with an emphasis on the early years of dynamic games. The readers are kindly invited to discuss the author's point of view. Comments and statements sent to the author will be summarized and published later. [ABSTRACT FROM AUTHOR]

This paper deals with the numerical solution of optimal control problems for ODEs. The methods considered here rely on some standard optimization code to solve a discretized version of the control problem under consideration. We aim to make available to the optimization software not only the discrete objective functional, but also its gradient. The objective gradient can be computed either from forward (sensitivity) information or backward (adjoint) information. The purpose of this paper is to discuss various ways of adjoint computation. It will be shown both theoretically and numerically that methods based on the continuous adjoint equation require a careful choice of both the integrator and gradient assembly formulas in order to obtain a gradient consistent with the discretized control problem. Particular attention is given to automatic differentiation techniques which generate automatically a suitable integrator. [ABSTRACT FROM AUTHOR]

This paper studies the tracking and almost disturbance decoupling problem of the nonlinear AMIRA ball and beam system based on the feedback linearization approach. The main contribution of this study is to construct a controller, under appropriate conditions, such that the resulting closed-loop system is valid for any initial condition and bounded tracking signal with the following characteristics: input-to-state stability with respect to disturbance inputs and almost disturbance decoupling. Two examples on the almost disturbance decoupling problem, which cannot be solved via Ref. 1, are proposed in this paper exploiting the fact that the tracking and the almost disturbance decoupling performances are easily achieved by our proposed approach. [ABSTRACT FROM AUTHOR]

In this paper, a new sequential penalty algorithm, based on the L[sub ∞] exact penalty function, is proposed for a general nonlinear constrained optimization problem. The algorithm has the following characteristics: it can start from an arbitrary initial point; the feasibility of the subproblem is guaranteed; the penalty parameter is adjusted automatically; global convergence without any regularity assumption is proved. The update formula of the penalty parameter is new. It is proved that the algorithm proposed in this paper behaves equivalently to the standard SQP method after sufficiently many iterations. Hence, the local convergence results of the standard SQP method can be applied to this algorithm. Preliminary numerical experiments show the efficiency and stability of the algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the problem of minimizing a nonlinear objective function subject to a system of bipolar fuzzy relational equations with max- $T_{L}$ composition, where $T_{L}$ is the Łukasiewicz triangular norm. It shows that the feasible domain, i.e., the solution set of a system of bipolar fuzzy relational equations, can be reformulated as a system of 0-1 mixed integer inequalities. Consequently, such a type of optimization problems can be handled within the framework of 0-1 mixed integer optimization requiring no particular solving techniques. [ABSTRACT FROM AUTHOR]

The paper suggests a new-to the best of the author's knowledge-characterization of decisions, which are optimal in the multi-objective optimization problem with respect to a definite proper preference cone, a Euclidean cone with a prescribed angular radius. The main idea is to use the angle distances between the unit vector and points of utility space. A necessary and sufficient condition for the optimality in the form of an equation is derived. The first-order necessary optimality conditions are also obtained. [ABSTRACT FROM AUTHOR]

In the present paper, we consider the inequality constrained vector problem with continuously Fréchet differentiable objective functions and constraints. We obtain second-order necessary optimality conditions of Karush-Kuhn-Tucker type for weak efficiency. A new second-order constraint qualification of Zangwill type is introduced. It is applied in the optimality conditions. Some connections with other constraint qualifications are established. [ABSTRACT FROM AUTHOR]

In this paper, we consider a constrained nonconvex nonsmooth optimization, in which both objective and constraint functions may not be convex or smooth. With the help of the penalty function, we transform the problem into an unconstrained one and design an algorithm in proximal bundle method in which local convexification of the penalty function is utilized to deal with it. We show that, if adding a special constraint qualification, the penalty function can be an exact one, and the sequence generated by our algorithm converges to the KKT points of the problem under a moderate assumption. Finally, some illustrative examples are given to show the good performance of our algorithm. [ABSTRACT FROM AUTHOR]

The zero propellant maneuver (ZPM) is an advanced space station, large angle attitude maneuver technique, using only control momentum gyroscopes (CMGs). Path planning is the key to success, and this paper studies the associated multi-objective optimization problem. Three types of maneuver optimal control problem are formulated: (i) momentum-optimal, (ii) time-optimal, and (iii) energy-optimal. A sensitivity analysis approach is used to study the Pareto optimal front and allows the tradeoffs between the performance indices to be investigated. For example, it is proved that the minimum peak momentum decreases as the maneuver time increases, and the minimum maneuver energy decreases if a larger momentum is available from the CMGs. The analysis is verified and complemented by the numerical computations. Among the three types of ZPM paths, the momentum-optimal solution and the time-optimal solution generally possess the same structure, and they are singular. The energy-optimal solution saves significant energy, while generally maintaining a smooth control profile. [ABSTRACT FROM AUTHOR]

In this paper, epsilon and Ritz methods are applied for solving a general class of fractional constrained optimization problems. The goal is to minimize a functional subject to a number of constraints. The functional and constraints can have multiple dependent variables, multiorder fractional derivatives, and a group of initial and boundary conditions. The fractional derivative in the problem is in the Caputo sense. The constrained optimization problems include isoperimetric fractional variational problems (IFVPs) and fractional optimal control problems (FOCPs). In the presented approach, first by implementing epsilon method, we transform the given constrained optimization problem into an unconstrained problem, then by applying Ritz method and polynomial basis functions, we reduce the optimization problem to the problem of optimizing a real value function. The choice of polynomial basis functions provides the method with such a flexibility that initial and boundary conditions can be easily imposed. The convergence of the method is analytically studied and some illustrative examples including IFVPs and FOCPs are presented to demonstrate validity and applicability of the new technique. [ABSTRACT FROM AUTHOR]

In real linear spaces, partial orderings are usually generated by ordering cones. In many situations, however, such an ordering cone is too small with respect to the whole space. Therefore, in this paper, we extend the concept of ordering cones to a more general concept. For this purpose, we define a parameterized binary relation, based on a convex cone and a binary function. We investigate some geometrical and topological properties of this relation in detail. [ABSTRACT FROM AUTHOR]

In this paper, we consider a dynamic optimization problem involving a general switched system that evolves by switching between several subsystems of nonlinear delay-differential equations. The optimization variables in this system consist of: (1) the times at which the subsystem switches occur; and (2) a set of system parameters that influence the subsystem dynamics. We first establish the existence of the partial derivatives of the system state with respect to both the switching times and the system parameters. Then, on the basis of this result, we show that the gradient of the cost function can be computed by solving the state system forward in time followed by a costate system backward in time. This gradient computation procedure can be combined with any gradient-based optimization method to determine the optimal switching times and parameters. We propose an effective optimization algorithm based on this idea. Finally, we consider three numerical examples, one involving the 1,3-propanediol fed-batch production process, to illustrate the effectiveness and applicability of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Celebrating the sixtieth anniversary since the zeroth International Symposium on Mathematical Programming was held in 1949, this paper discusses several promising paradigms in mathematical programming that have gained momentum in recent years but have yet to reach the main stream of the field. These are: competition, dynamics, and hierarchy. The discussion emphasizes the interplay between these paradigms and their connections with existing subfields including disjunctive, equilibrium, and nonlinear programming, and variational inequalities. We will describe the modeling approaches, mathematical formulations, and recent results of these paradigms, and sketch some open mathematical and computational challenges arising from the resulting optimization and equilibrium problems. Our goal is to elucidate the need for a systematic study of these problems and to inspire new research in the field. [ABSTRACT FROM AUTHOR]

The Fermat-Torricelli problem is an optimization problem associated with a finite subset $\{a_{j}\}_{j=1}^{q}$ of ℝ and a family $\{c_{j}\}_{j=1}^{q}$ of positive weights. The function F to be minimized is defined by $F(x)=\sum _{j=1}^{q}c_{j}\Vert x-a_{j}\Vert$. In this paper, we extend this problem to the case of volumes. [ABSTRACT FROM AUTHOR]

The present paper studies the following constrained vector optimization problem: $$\mathop {\min }\limits_C f(x),g(x) \in - K,h(x) = 0$$, where f: ℝ n → ℝ m, g: ℝ n → ℝ p are locally Lipschitz functions, h: ℝ n → ℝ q is C1 function, and C ⊂ ℝ m and K ⊂ ℝ p are closed convex cones. Two types of solutions are important for the consideration, namely w-minimizers (weakly efficient points) and i-minimizers (isolated minimizers of order 1). In terms of the Dini directional derivative first-order necessary conditions for a point x0 to be a w-minimizer and first-order sufficient conditions for x0 to be an i-minimizer are obtained. Their effectiveness is illustrated on an example. A comparison with some known results is done. [ABSTRACT FROM AUTHOR]

In this paper, properties of the entropic risk measure are examined rigorously in a general framework. This risk measure is then applied in a dynamic portfolio optimization problem, appearing in the risk management constraint. By considering the dual problem, we prove the existence and uniqueness of the solution and obtain an analytic expression for the solution. [ABSTRACT FROM AUTHOR]

In this paper we study some optimization problems for nonlinear elastic membranes. More precisely, we consider the problem of optimizing the cost functional $\mathcal {J}(u)=\int_{\partial\Omega}f(x)u\,\mathrm {d}\mathcal {H}^{N-1}$ over some admissible class of loads f where u is the (unique) solution to the problem −Δ p u+| u| p−2 u=0 in Ω with | ∇ u| p−2 u ν= f on ∂Ω. [ABSTRACT FROM AUTHOR]

In this paper a new hybrid conjugate gradient algorithm is proposed and analyzed. The parameter β k is computed as a convex combination of the Polak-Ribière-Polyak and the Dai-Yuan conjugate gradient algorithms, i.e. β=(1− θ k) β+ θ k β. The parameter θ k in the convex combination is computed in such a way that the conjugacy condition is satisfied, independently of the line search. The line search uses the standard Wolfe conditions. The algorithm generates descent directions and when the iterates jam the directions satisfy the sufficient descent condition. Numerical comparisons with conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that this hybrid computational scheme outperforms the known hybrid conjugate gradient algorithms. [ABSTRACT FROM AUTHOR]

Proximal-point algorithms (PPAs) are classical solvers for convex optimization problems and monotone variational inequalities (VIs). The proximal term in existing PPAs usually is the gradient of a certain function. This paper presents a class of PPA-based methods for monotone VIs. For a given current point, a proximal point is obtained via solving a PPA-like subproblem whose proximal term is linear but may not be the gradient of any functions. The new iterate is updated via an additional slight calculation. Global convergence of the method is proved under the same mild assumptions as the original PPA. Finally, profiting from the less restrictions on the linear proximal terms, we propose some parallel splitting augmented Lagrangian methods for structured variational inequalities with separable operators. [ABSTRACT FROM AUTHOR]

Let X be a partially ordered real Banach space, let a, b∈ X with a≤ b. Let φ be a bounded linear functional on X. We say that X satisfies the box-optimization property (or X is a BOP space) if the box-constrained linear program: max 〈 φ, x〉, s.t. a≤ x≤ b, has an optimal solution for any φ, a and b. Such problems arise naturally in solving a class of problems known as interval linear programs. BOP spaces were introduced (in a different language) and systematically studied in the first author’s doctoral thesis. In this paper, we identify new classes of Banach spaces that are BOP spaces. We present also sufficient conditions under which answers are in the affirmative for the following questions: [ABSTRACT FROM AUTHOR]

The notion of extended-well-posedness has been introduced by Zolezzi for scalar minimization problems and has been further generalized to vector minimization problems by Huang. In this paper, we study the extended well-posedness properties of vector minimization problems in which the objective function is C-quasiconvex. To achieve this task, we first study some stability properties of such problems. [ABSTRACT FROM AUTHOR]

An interior point method (IPM) defines a search direction at an interior point of the feasible region. These search directions form a direction field, which in turn defines a system of ordinary differential equations (ODEs). The solutions of the system of ODEs are called off-central paths, underlying paths lying in the interior of the feasible region. It is known that not all off-central paths are analytic, whether w.r.t. μ or $\sqrt{\mu}$ , where μ represents the duality gap, at a solution of a given semidefinite linear complementarity problem, SDLCP (Sim and Zhao, Math. Program. 110:475–499, ). In Sim and Zhao (J. Optim. Theory Appl. 137:11–25, ), we give a necessary and sufficient condition for when an off-central path is analytic as a function of $\sqrt{\mu}$ at a solution of a general SDLCP. It is then natural to ask about the analyticity of a SDLCP off-central path at a solution, as a function of μ. We investigate this in the current paper. Again, we work under the assumption that the given SDLCP satisfies strict complementarity condition. [ABSTRACT FROM AUTHOR]

This paper provides a detailed analysis of a primal-dual interior-point method for PDE-constrained optimization. Considered are optimal control problems with control constraints in L p . It is shown that the developed primal-dual interior-point method converges globally and locally superlinearly. Not only the easier L ∞-setting is analyzed, but also a more involved L q -analysis, q < ∞, is presented. In L ∞, the set of feasible controls contains interior points and the Fréchet differentiability of the perturbed optimality system can be shown. In the L q -setting, which is highly relevant for PDE-constrained optimization, these nice properties are no longer available. Nevertheless, a convergence analysis is developed using refined techniques. In parti- cular, two-norm techniques and a smoothing step are required. The L q -analysis with smoothing step yields global linear and local superlinear convergence, whereas the L ∞-analysis without smoothing step yields only global linear convergence. [ABSTRACT FROM AUTHOR]

We consider a problem of finding optimal contracts in continuous time, when the agent’s actions are unobservable by the principal, who pays the agent with a one-time payoff at the end of the contract. We fully solve the case of quadratic cost and separable utility, for general utility functions. The optimal contract is, in general, a nonlinear function of the final outcome only, while in the previously solved cases, for exponential and linear utility functions, the optimal contract is linear in the final output value. In a specific example we compute, the first-best principal’s utility is infinite, while it becomes finite with hidden action, which is increasing in value of the output. In the second part of the paper we formulate a general mathematical theory for the problem. We apply the stochastic maximum principle to give necessary conditions for optimal contracts. Sufficient conditions are hard to establish, but we suggest a way to check sufficiency using non-convex optimization. [ABSTRACT FROM AUTHOR]

In this paper, following the method in the proof of the composition duality principle due to Robinson and using some basic properties of the ε-subdifferential and the conjugate function of a convex function, we establish duality results for an ε-variational inequality problem. Then, we give Fenchel duality results for the ε-optimal solution of an unconstrained convex optimization problem. Moreover, we present an example to illustrate our Fenchel duality results for the ε-optimal solutions. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to establish the second-order nonsmooth sufficient unconstrained optimality condition for so called ℓ-stable at some point functions and in this way to generalize some previous results in this direction. We provide the comparisons with other results by examples. [ABSTRACT FROM AUTHOR]

In his 1976 book, Proofs and Refutations, Lakatos presents a collection of case studies to illustrate methods of mathematical discovery in the history of mathematics. In this paper, we reframe these methods in ways that we have found make them more amenable for use as a framework for research on learning and teaching mathematics. We present an episode from an undergraduate abstract algebra classroom to illustrate the guided reinvention of mathematics through processes that strongly parallel those described by Lakatos. Our analysis suggests that the constructs described by Lakatos can provide a useful framework for making sense of the mathematical activity in classrooms where students are actively engaged in the development of mathematical ideas and provide design heuristics for instructional approaches that support the learning of mathematics through the process of guided reinvention. [ABSTRACT FROM AUTHOR]

Any Boolean function can be defined by a Boolean circuit, provided we may use sufficiently strong functions in its gates. On the other hand, what Boolean functions can be defined depends on these gate functions: Each set B of gate functions defines the class of Boolean functions that can be defined by circuits over B. Although these classes have been known since the 1920s, their computational complexity was never investigated. In this paper we will study how difficult it is to decide for a Boolean function f and a class B, whether f is in B. Moreover, we will provide such a decision algorithm with additional information: How difficult is it to decide whether or not f is in B, provided we already know a circuit for f, but with gates from another class A? Given such a circuit, we know that f is in A. Is the problem harder if we do not have a concrete representation for f, but still know that it is from A? For nearly all possible combinations, we show that this is not the case, and that the problem is either in P or coNP-complete. [ABSTRACT FROM AUTHOR]

We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of length n on an alphabet A. This is a remarkable improvement on current suffix trees which require O(n log n) bits. Though some components of suffix trees have been compressed, there is no linear-size data structure for suffix trees with full functionality such as computing suffix links, string-depths and lowest common ancestors. The data structure proposed in this paper is the first one that has linear size and supports all operations efficiently. Any algorithm running on a suffix tree can also be executed on our compressed suffix trees with a slight slowdown of a factor of polylog(n). [ABSTRACT FROM AUTHOR]

This paper studies the problem of maximizing the number of correct results of dependent tasks computed unreliably. We consider a distributed system composed of a reliable server that coordinates the computation of a massive number of unreliable workers. Any worker computes correctly with probability p < 1. Any incorrectly computed task corrupts all dependent tasks. The goal is to determine which tasks should be computed by the (reliable) server and which by the (unreliable) workers, and when, so as to maximize the expected number of correct results, under a constraint d on the computation time. This problem is motivated by distributed computing applications that persist partial results of computations for future use in other computations and that want to ensure that the persisted results are of high quality. We show that this optimization problem is NP-hard. Then we study optimal scheduling solutions for the mesh with the tightest deadline. We present combinatorial arguments that describe all optimal solutions for two ranges of values of worker reliability p, when p is close to zero and when p is close to one. [ABSTRACT FROM AUTHOR]

Due to the large amounts of data required to be processed by the typical Grid job, it is conceivable that the use of optical transport networks in Grid deployment (hence the term “Lambda Grid”) will increase. The exact topology of the interconnecting network is obtained by solving a dimensioning problem, and the outcome of this strongly depends on both the expected workload characteristics and Grid scheduling policy. Solving this combined scheduling and dimensioning problem using straightforward ILP modelling is cumbersome; however, for steady-state Grid operation, Divisible Load Theory (DLT) can yield scalable formulations of this problem. In this paper, the on-line hierarchical scheduling on a lambda Grid of workload approaching the Grid’s capacity in a two-tier Grid mode of operation is studied. A number of these algorithms are goal-driven, in the sense that target per-resource goals are obtained from the off-line solution to the Divisible Load model. We compare these on-line multiresource scheduling policies for different workloads, Grid interconnection topologies and Grid parameters. We show that these algorithms perform well in the studied scenarios when compared to a fully centralized scheduling algorithm. [ABSTRACT FROM AUTHOR]

The background for this article is the question of modification of the geometric configuration of an elastic structure by means of "volume"-type actuation. In this actuation mode stresses are applied to the elastic body by injection/extraction of a fluid into, or from, a large number of vacuoles in the elastic "matrix" material. Previous articles by the author, and others, have examined this process and studied its effectiveness in the context of a "naive" continuous model. The present paper develops modified models in the two-dimensional case by applying the "multiple scales" homogenization method to elastic bodies with increasingly small and numerous vacuoles arranged in a rectangularly periodic structure. The process leads to a modification of the naive model potentially useful in future elastic system control research. [ABSTRACT FROM AUTHOR]

K-means clustering is arguably the most popular technique for partitioning data. Unfortunately, K-means suffers from the well-known problem of locally optimal solutions. Furthermore, the final partition is dependent upon the initial configuration, making the choice of starting partitions all the more important. This paper evaluates 12 procedures proposed in the literature and provides recommendations for best practices. [ABSTRACT FROM AUTHOR]

We consider a convexification method for a class of nonsmooth monotone functions. Specifically, we prove that a semismooth monotone function can be converted into a convex function via certain convexification transformations. The results derived in this paper lay a theoretical base to extend the reach of convexification methods in monotone optimization to nonsmooth situations. [ABSTRACT FROM AUTHOR]

The idea of containment sets (csets) is due to Walster and Hansen, and the theory is mainly due to the first author. Now that floating point computation with infinities is widely accepted, it is necessary to achieve the same for interval computation. The cset of a function over a set in its domain space is the set of all limits of normal function values over that set. Csets form a sound basis for defining a number of practical models for interval arithmetic that handle division by zero and related operations in an intuitive and consistent manner. Cset-based systems offer new opportunities for compiler optimization by rearranging interval expressions, achieving tighter bounds by reducing dependencies within the expression. This paper presents basic theory. It discusses division by zero, the case for a global flag to support ``loose'' evaluation, performance, and semantics. It presents numerical examples using a trial Matlab implementation. [ABSTRACT FROM AUTHOR]

In this paper, we study the relationship between bilevel optimization and multicriteria optimization. Given a bilevel optimization problem, we introduce an order relation such that the optimal solutions of the bilevel problem are the nondominated points with respect to the order relation. In the case where the lower-level problem of the bilevel optimization problem is convex and continuously differentiable in the lower-level variables, this order relation is equivalent to a second, more tractable order relation. Then, we show how to construct a (nonconvex) cone for which we can prove that the nondominated points with respect to the order relation induced by the cone are also nondominated points with respect to any of the two order relations mentioned before. We comment also on the practical and computational implications of our approach. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a definition of generalized convexlike functions (preconvexlike functions). Then, under the weakened convexity, we study vector optimization problems in Hausdorff topological linear spaces. We establish some generalized Motzkin theorems of the alternative. By use of these theorems of the alternative, we obtain some Lagrangian multiplier theorems. A saddle-point theorem and a scalarization theorem are also derived. [ABSTRACT FROM AUTHOR]

In this paper, we study the stabilization problem for a class of linear nonautonomous systems with norm-bounded controls. Using the Lyapunov function technique, we establish simple verifiable stabilizability conditions without solving any Riccati differential equation. Numerical examples are given to illustrate the results. [ABSTRACT FROM AUTHOR]

The objective of this paper is to pose and solve a simple class of coordinated motion problems that capture the following question; When is formation travel optimal? This class of problems is complementary to two related classes of problems that have received significant attention: close formation travel and the generation of flocking behavior. We pose and solve this problem for the case of two agents traversing a finite, connected graph. Two examples are provided, illustrating the application of the results. [ABSTRACT FROM AUTHOR]

In this paper. the design problem of the dynamic output feedback controller for the asymptotic stabilization of a class of linear delay differential systems of the neutral type is considered. A criterion for the existence of such controller is derived based on the matrix inequality approach combined with the Lyapunov method. A parametrized characterization of the controller is given in terms of the feasible solutions to certain matrix inequalities, which can be solved by various convex optimization algorithms. A numerical example is given to illustrate the proposed design method. [ABSTRACT FROM AUTHOR]