Relaxations and approximations of chance constraints under finite distributions

Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulation has a weak relaxation bound and is quite difficult to solve. In this paper, we review some recent results on improving the relaxation bounds and constructing approximate solutions for MILP formulations of chance constraints. We also discuss a recently introduced bicriteria approximation algorithm for covering type chance constrained problems. This algorithm uses a relaxation to construct a solution whose (constraint violation) risk level may be larger than the pre-specified threshold, but is within a constant factor of it, and whose objective value is also within a constant factor of the true optimal value. Finally, we present some new results that improve on the bicriteria approximation factors in the finite scenario setting and shed light on the effect of strong relaxations on the approximation ratios.     

Unicity Results for General Linear Semi-Infinite Optimization Problems Using a New Concept of Active Constraints

We consider parametric semi-infinite optimization problems without the usual asssumptions on the continuity of the involved mappings and on the compactness of the index set counting the inequalities. We establish a characterization of those optimization problems which have a unique or strongly unique solution and which are stable under small pertubations. This result generalizes a well-known theorem of Nürnberger. The crucial roles in our investigations are a new concept of active constraints, a generalized Slater's condition, and a Kuhn—Tucker-type theorem. Finally, we give some applications in vector optimization, for approximation problems in normed spaces, and in the stability of the minimal value. Accepted 5 August 1996     

Approximation algorithms for homogeneous polynomial optimization with quadratic constraints

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.     

Convergent Outer Approximation Algorithms for Solving Unary Programs

Interesting cutting plane approaches for solving certain difficult multiextremal global optimization problems can fail to converge. Examples include the concavity cut method for concave minimization and Ramana's recent outer approximation method for unary programs which are linear programming problems with an additional constraint requiring that an affine mapping becomes unary. For the latter problem class, new convergent outer approximation algorithms are proposed which are based on sufficiently deep l-norm or quadratic cuts. Implementable versions construct optimal simplicial inner approximations of Euclidean balls and of intersections of Euclidean balls with halfspaces, which are of general interest in computational convexity. Computational behavior of the algorithms depends crucially on the matrices involved in the unary condition. Potential applications to the global minimization of indefinite quadratic functions subject to indefinite quadratic constraints are shown to be practical only for very small problem sizes.     

Approximating crossed symmetric solutions of nonlinear dynamic equations via quasilinearization

Crossed symmetric solutions of nonlinear boundary value dynamic problems play an important role in many applications, in particular in adaptive algorithm designs. This article is devoted to the continuation of our investigation on second-order nonlinear companion dynamic boundary value problems on time scales. Monotonically convergent upper and lower solutions of the problems and their quasilinear approximations are investigated. It is shown that, under proper smoothness constraints, the iterative sequences constructed not only converge to the analytic solutions of the desired companion problems monotonically, but also preserve important crossed symmetry properties. The quasilinearization offers an efficient way in the solution approximation. Computational examples are given to illustrate our results.     

Constrained optimization using multiple objective programming

In practical applications of mathematical programming it is frequently observed that the decision maker prefers apparently suboptimal solutions. A natural explanation for this phenomenon is that the applied mathematical model was not sufficiently realistic and did not fully represent all the decision makers criteria and constraints. Since multicriteria optimization approaches are specifically designed to incorporate such complex preference structures, they gain more and more importance in application areas as, for example, engineering design and capital budgeting. The aim of this paper is to analyze optimization problems both from a constrained programming and a multicriteria programming perspective. It is shown that both formulations share important properties, and that many classical solution approaches have correspondences in the respective models. The analysis naturally leads to a discussion of the applicability of some recent approximation techniques for multicriteria programming problems for the approximation of optimal solutions and of Lagrange multipliers in convex constrained programming. Convergence results are proven for convex and nonconvex problems.     

Average Case Analysis in Database Problems

In a variety of applications ranging from environmental and health sciences to bioinformatics, it is essential that data collected in large databases are generated stochastically. This states qualitatively new problems both for statistics and for computer science. Namely, instead of deterministic (usually worst case) analysis, the average case analysis is needed for many standard database problems. Since both stochastic and deterministic methods and notation are used it causes additional difficulties for an investigation of such problems and for an exposition of results. We consider a general class of probabilistic models for databases and study a few problems in a probabilistic framework. In order to demonstrate the general approach, the problems for systems of database constraints (keys, functional dependencies and related) are investigated in more detail. Our approach is based on consequent using Rényi entropy as a main characteristic of uncertainty of distribution and Poisson approximation (Stein–Chen technique) of the corresponding probabilities.     

Bivariate least squares approximation with linear constraints

In this article linear least squares problems with linear equality constraints are considered, where the data points lie on the vertices of a rectangular grid. A fast and efficient computational method for the case when the linear equality constraints can be formulated in a tensor product form is presented. Using the solution of several univariate approximation problems the solution of the bivariate approximation problem can be derived easily. AMS subject classification (2000)  65D05, 65D07, 65D10, 65F05, 65F20     

Optimal smoothing and interpolating splines with constraints

This paper considers the problem for designing optimal smoothing and interpolating splines with equality and/or inequality constraints. The splines are constituted by employing normalized uniform B-splines as the basis functions, namely as weighted sum of shifted B-splines of degree k. Then a central issue is to determine an optimal vector of the so-called control points. By employing such an approach, it is shown that various types of constraints are formulated as linear function of the control points, and the problems reduce to quadratic programming problems. We demonstrate the effectiveness and usefulness by numerical examples including approximation of probability density functions, approximation of discontinuous functions, and trajectory planning.     

A Posteriori Error Estimates for Distributed Convex Optimal Control Problems

In this paper, we present an a posteriori error analysis for finite element approximation of distributed convex optimal control problems. We derive a posteriori error estimates for the coupled state and control approximations under some assumptions which hold in many applications. Such estimates, which are apparently not available in the literature, can be used to construct reliable adaptive finite element approximation schemes for control problems. Explicit estimates are obtained for some model problems which frequently appear in real-life applications.     

Fractional 0–1 programming: applications and algorithms

We consider a class of nonlinear integer optimization problems commonly known as fractional 0–1 programming problems (also, often referred to as hyperbolic 0–1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0–1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.     

A Linear Approximation for Chance-Constrained Programming

Decision environments involve the need to solve problems with varying degrees of uncertainty as well as multiple, potentially conflicting objectives. Chance constraints consider the uncertainty encountered. Codes incorporating chance constraints into a mathematical programming model are not available on a widespread basis owing to the non-linear form of the chance constraints. Therefore, accurate linear approximations would be useful to analyse this class of problems with efficient linear codes. This paper presents an approximation formula for chance constraints which can be used in either the single- or multiple-objective case. The approximation presented will place a bound on the chance constraint at least as tight as the true non-linear form, thus overachieving the chance constraint at the expense of other constraints or objectives.     

经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

Discrete,linear approximation problems in polyhedral norms

Summary We introduce a class of polyhedral norms and study discrete linear approximation problems under these norms. It is possible to give a uniform treatment, in particular, ofL ₁ and maximum norm problems, at least as regards notation; and we develop a general exchange algorithm in which we permit also linear inequality constraints.     

经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

Approximation with Constraints by Conditionally Positive Definite Functions

This paper deals with interpolation and approximation satisfying constraints. We consider approximation by conditionally positive definite functions in norms which are associated with the conditionally positive definite functions. The theory of reproducing kernels is used to transform the approximation problems to quadratic optimization problems. Then we can give the existence, characterization and uniqueness results for the solutions. The methods of optimization theory can be used in order to determine solutions.     

ℓ1-Minimization with Magnitude Constraints in the Frequency Domain

In this paper, we study the -optimal control problem with additional constraints on the magnitude of the closed-loop frequency response. In particular, we study the case of magnitude constraints at fixed frequency points (a finite number of such constraints can be used to approximate an -norm constraint). In previous work, we have shown that the primal-dual formulation for this problem has no duality gap and both primal and dual problems are equivalent to convex, possibly infinite-dimensional, optimization problems with LMI constraints. Here, we study the effect of approximating the convex magnitude constraints with a finite number of linear constraints and provide a bound on the accuracy of the approximation. The resulting problems are linear programs. In the one-block case, both primal and dual programs are semi-infinite dimensional. The optimal cost can be approximated, arbitrarily well from above and within any predefined accuracy from below, by the solutions of finite-dimensional linear programs. In the multiblock case, the approximate LP problem (as well as the exact LMI problem) is infinite-dimensional in both the variables and the constraints. We show that the standard finite-dimensional approximation method, based on approximating the dual linear programming problem by sequences of finite-support problems, may fail to converge to the optimal cost of the infinite-dimensional problem.     

On an Extension of the Weak Law of Large Numbers of Kolmogorov and Feller

The robustness inequality for an optimization problem with constraints given by contractive operators is adapted to controlled stochastic differential equations. Some applications to estimation of approximation accuracy of controlled processes are discussed     

Optimization over analytic functions whose founrier coefficients are constrained

This article gives necessary and sufficient conditions for local solutions to several very general constrained optimization problems over spaces of analytic functions.The results presented here have many applications, a particular instance of which is the sup-norm approximation of functions continuous on the unit circle in the complex plane by functions continuous on the circle and analytic on the open disk and whose Fourier coefficients satisfy prescribed linear relations.Also, the results in this article generalize Nevanlinna-Pick and Caratheodory-Fejer Interpolation results to allow values of arbitrary derivatives of functions to be assigned or merely bounded. Classically, NP and CF solve only problems with consecutive derivatives specified.In engineering, constraints on the Fourier coefficients of a frequency response function correspond to constraints on its time domain behavior. Indeed the central problems of control theory involve both time and frequency domain constraints. That is precisely what the results in this paper handle.Supported in part by the AFOSR and the NSF     

Approximation of optimal control problems with state constraints

We study the approximation of control problems governed by elliptic partial differential equations with pointwise state constraints. For a finite dimensional approximation of the control set and for suitable perturbations of the state constraints, we prove that the corresponding sequence of discrete control problems converges to a relaxed problem. A similar analysis is carried out for problems in which the state equation is discretized by a finite element method.