When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?

Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a convex and compact set and the uncertainty set is convex and compact, then robust solutions are also optimal for the corresponding ARO problem. Furthermore, we prove that if some of the uncertain parameters are constraint-wise and the rest are not, then under a similar set of assumptions there is an optimal decision rule for the ARO problem that does not depend on the constraint-wise uncertain parameters. Also, we show for a class of problems that using affine decision rules that depend on all of the uncertain parameters yields the same optimal objective value as when the rules depend solely on the non-constraint-wise uncertain parameters. Finally, we illustrate the usefulness of these results by applying them to convex quadratic and conic quadratic problems.     

Support vector machine classifiers with uncertain knowledge sets via robust optimization

In this article we study support vector machine (SVM) classifiers in the face of uncertain knowledge sets and show how data uncertainty in knowledge sets can be treated in SVM classification by employing robust optimization. We present knowledge-based SVM classifiers with uncertain knowledge sets using convex quadratic optimization duality. We show that the knowledge-based SVM, where prior knowledge is in the form of uncertain linear constraints, results in an uncertain convex optimization problem with a set containment constraint. Using a new extension of Farkas' lemma, we reformulate the robust counterpart of the uncertain convex optimization problem in the case of interval uncertainty as a convex quadratic optimization problem. We then reformulate the resulting convex optimization problems as a simple quadratic optimization problem with non-negativity constraints using the Lagrange duality. We obtain the solution of the converted problem by a fixed point iterative algorithm and establish the convergence of the algorithm. We finally present some preliminary results of our computational experiments of the method.     

On the sets of exact and approximate solutions

We consider the problem how big is the set of solutions of a given functional equation in the set of approximate solutions. It happens that in the cases of linear functional equations (like Cauchy, Jensen) or linear inequalities (like convex, Jensen convex) the sets of solutions are very small subsets of the sets of approximate solutions. The situation is different in the cases of superstable equations (like exponential or d'Alembert).     

On the shape of solution sets of systems of (functional) equations

Solution sets of systems of linear equations over fields are characterized as being affine subspaces. But what can we say about the “shape” of the set of all solutions of other systems of equations? We study solution sets over arbitrary algebraic structures, and we give a necessary condition for a set of n-tuples to be the set of solutions of a system of equations in n unknowns over a given algebra. In the case of Boolean equations we obtain a complete characterization, and we also characterize solution sets of systems of Boolean functional equations.     

Efficient solutions in generalized linear vector optimization

This paper establishes several new facts on generalized polyhedral convex sets and shows how they can be used in vector optimization. Among other things, a scalarization formula for the efficient solution sets of generalized linear vector optimization problems is obtained. We also prove that the efficient solution set of a generalized linear vector optimization problem in a locally convex Hausdorff topological vector space is the union of finitely many generalized polyhedral convex sets and it is connected by line segments.     

Generalization of the Lagrange Method to the Case of Second-Order Linear Differential Equations with Constant Operator Coefficients in Locally Convex Spaces

The well-known Lagrange method for linear inhomogeneous differential equations is generalized to the case of second-order equations with constant operator coefficients in locally convex spaces. The solutions are expressed in terms of uniformly convergent functional vector-valued series generated by a pair of elements of a locally convex space. Sufficient conditions for the continuous dependence of solutions on the generating pair are obtained. The solution of the Cauchy problem for the equations under consideration is also obtained and conditions for its existence and uniqueness are given. In addition, under certain conditions, the so-called general solution of the equations (a function of most general form from which any particular solution can be derived) is obtained. The study is carried out using the characteristics (order and type) of an operator and of a sequence of operators. Also, the convergence of operator series with respect to equicontinuous bornology is used.     

A dynamic programming method for controlled linear systems with delays

A linear system with permanent delay is considered. A method of dynamic programming for constructing attainability sets and solving the problem of target control for the systems is used. The expressions for value functionals described by solutions to the corresponding Hamilton-Jacobi-Bellman equation are obtained. It is proved that these value functionals calculated by means of convex analysis satisfy the above equations. Strategies for synthesized control for the problem of hitting on the target set are given.     

Minimum-support solutions of polyhedral concave programs *

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if

such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the

complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set     

An Exact Formula for Radius of Robust Feasibility of Uncertain Linear Programs

We present an exact formula for the radius of robust feasibility of uncertain linear programs with a compact and convex uncertainty set. The radius of robust feasibility provides a value for the maximal ‘size’ of an uncertainty set under which robust feasibility of the uncertain linear program can be guaranteed. By considering spectrahedral uncertainty sets, we obtain numerically tractable radius formulas for commonly used uncertainty sets of robust optimization, such as ellipsoids, balls, polytopes and boxes. In these cases, we show that the radius of robust feasibility can be found by solving a linearly constrained convex quadratic program or a minimax linear program. The results are illustrated by calculating the radius of robust feasibility of uncertain linear programs for several different uncertainty sets.     

Formal solution of an interval system of linear equations with an application in static responses of structures with interval forces

We are concerned with the so called formal solution of an interval system of linear equations. We focus on the case where the coefficient matrix is deterministic (real) and the right-hand side is an interval vector. We show that the set of formal solutions represents a convex polyhedral set. We propose new properties of the formal solution related to its existence, uniqueness and robustness. As particular classes of problems we investigate also the situation where the coefficient matrix is an M-matrix or H-matrix. Example problems related to the structures, such as 6-bar truss and a rectangular sheet, are solved to illustrate the computational aspects of the methods.     

常系数非齐次线性微分方程组的初等解法

利用初等变换将常系数非齐次线性微分方程组化为由若干个相互独立的高阶常系数非齐次线性微分方程组成的方程组,再利用高阶常系数齐次线性微分方程的特征根法和非齐次方程的待定系数法求该方程组的基本解组及特解,最后通过初等变换求原方程组的基本解组及特解,从而可求出其通解.     

Inner and outer estimates for the solution sets and their asymptotic cones in vector optimization

We use asymptotic analysis to develop finer estimates for the efficient, weak efficient and proper efficient solution sets (and for their asymptotic cones) to convex/quasiconvex vector optimization problems. We also provide a new representation for the efficient solution set without any convexity assumption, and the estimates involve the minima of the linear scalarization of the original vector problem. Some new necessary conditions for a point to be efficient or weak efficient solution for general convex vector optimization problems, as well as for the nonconvex quadratic multiobjective optimization problem, are established.     

Robust solutions to uncertain linear complementarity problems

In this paper,we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain,and it is only known to belong to a prescribed uncertainty set.We propose the notion of the p- robust counterpart and the p-robust solution of uncertain linear complementarity problems.We discuss uncertain linear complementarity problems with three different uncertainty sets,respectively,including an unknown-but-bounded uncertainty set,an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set,and present some sufficient and necessary(or sufficient) conditions which p- robust solutions satisfy.Some special cases are investigated in this paper.     

Dominating Sets for Convex Functions with Some Applications

A number of optimization methods require as a first step the construction of a dominating set (a set containing an optimal solution) enjoying properties such as compactness or convexity. In this paper, we address the problem of constructing dominating sets for problems whose objective is a componentwise nondecreasing function of (possibly an infinite number of) convex functions, and we show how to obtain a convex dominating set in terms of dominating sets of simpler problems. The applicability of the results obtained is illustrated with the statement of new localization results in the fields of linear regression and location.     

Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers

We present a new probabilistic method for solving systems of polynomial equations and inequations. Our algorithm computes the equidimensional decomposition of the Zariski closure of the solution set of such systems. Each equidimensional component is encoded by a generic fiber, that is a finite set of points obtained from the intersection of the component with a generic transverse affine subspace. Our algorithm is incremental in the number of equations to be solved. Its complexity is mainly cubic in the maximum of the degrees of the solution sets of the intermediate systems counting multiplicities.Our method is designed for coefficient fields having characteristic zero or big enough with respect to the number of solutions. If the base field is the field of the rational numbers then the resolution is first performed modulo a random prime number after we have applied a random change of coordinates. Then we search for coordinates with small integers and lift the solutions up to the rational numbers. Our implementation is available within our package Kronecker from version 0.166, which is written in the Magma computer algebra system.     

Application of wavelet transforms to the solution of boundary value problems for linear parabolic equations

A method based on wavelet transforms is proposed for finding weak solutions to initial-boundary value problems for linear parabolic equations with discontinuous coefficients and inexact data. In the framework of multiresolution analysis, the general scheme for finite-dimensional approximation in the regularization method is combined with the discrepancy principle. An error estimate is obtained for the stable approximate solution obtained by solving a set of linear algebraic equations for the wavelet coefficients of the desired solution.     

Finding all solutions to polynomial systems and other systems of equations

In a previous paper, the authors suggested a procedure for obtaining all solutions to certain systems ofn equations inn complex variables. The idea was to start with a trivial system of equations to which all solutions were easily known. The trivial system was then perturbed into the given system. During the perturbation process, one followed the solution paths from each of the trivial solutions into the solutions of the given system. All solutions to the given system were thereby obtained.This paper utilizes a different approach that eliminates the requirement of the previous paper for a leading dominating term in each equation. We add a dominating term artificially and then fade it. Also we rely on mathematically more fundamental concepts from differential topology. These advancements permit the calculation of all solutions to arbitrary polynomials and to various other systems ofn equations inn complex variables. In addition, information on the number of solutions can be obtained without calculation.Work supported in part by NSF Grant No. MCS77-15509 and ARO Grant No. DAAG-29-78-G-0160.Work supported in part by ARO Grant No. DAAG-29-78-G-0160     

An Open-loop criterion for the solvability of a closed-loop guidance problem with incomplete information: Linear control systems

The method of open-loop control packages is a tool for stating the solvability of guaranteed closed-loop control problems under incomplete information on the observed states. In this paper, a solution method is specified for the problem of guaranteed closed-loop guidance of a linear control system to a convex target set at a prescribed point in time. It is assumed that the observed signal on the system’s states is linear and the set of its admissible initial states is finite. It is proved that the problem under consideration is equivalent to the problem of open-loop guidance of an extended linear control system to an extended convex target set. Using a separation theorem for convex sets, we derive a solvability criterion, which reduces to solving a finite-dimensional optimization problem. An illustrative example is considered.     

Polytopes for Crystallized Demazure Modules and Extremal Vectors

We give a parametrization for crystal bases of Demazure modules as a set of lattice points in some convex polytope and we also describe explicitly the extremal vectors as solutions of some system of linear equations.     

Diagonalization of the system of static Lamé equations of isotropic linear elasticity

We find a simplest representation for the general solution to the system of the static Lamé equations of isotropic linear elasticity in the form of a linear combination of the first derivatives of three functions that satisfy three independent harmonic equations. The representation depends on 12 free parameters choosing which it is possible to obtain various representations of the general solution and simplify the boundary value conditions for the solution of boundary value problems as well as the representation of the general solution for dynamic Lamé equations. The system of Lamé equations diagonalizes; i.e., it is reduced to the solution of three independent harmonic equations. The representation implies three conservation laws and some formula for producing new solutions which makes it possible, given a solution, to find new solutions to the static Lamé equations by derivations. In the two-dimensional case of a plane deformation, the so-found solution immediately implies the Kolosov-Muskhelishvili representation for shifts by means of two analytic functions of complex variable. Two examples are given of applications of the proposed method of diagonalization of the two-dimensional elliptic systems.