Strong Formulations of Robust Mixed 0–1 Programming

We introduce strong formulations for robust mixed 0–1 programming with uncertain objective coefficients. We focus on a polytopic uncertainty set described by a ``budget constraint' for allowed uncertainty in the objective coefficients. We show that for a robust 0–1 problem, there is an α–tight linear programming formulation with size polynomial in the size of an α–tight linear programming formulation for the nominal 0–1 problem. We give extensions to robust mixed 0–1 programming and present computational experiments with the proposed formulations.     

Algebraic polynomials least deviating from zero in measure on a segment

We investigate the problem of algebraic polynomials with given leading coefficients that deviate least from zero on the segment [–1, 1] with respect to a measure, or, more precisely, with respect to the functional μ(f) = mes{x ∈ [–1, 1]: ∣f (x)∣ ≥ 1}. We also discuss an analogous problem with respect to the integral functionals ∫_–1¹ φ (∣f (x)∣) dx for functions φ that are defined, nonnegative, and nondecreasing on the semiaxis [0, +∞).     

The two phase stochastic Stefan problem

 This work is concerned with existence for a stochastic free boundary problem arising in phase transition (the Stefan two phase problem). The existence of an invariant ergodic measure associated with the corresponding transition semigroup P(t) is also proved, together with an integration by parts formula for the generator of P(t). Received: 20 June 2001 / Revised version: 17 June 2002 / Published online: 24 October 2002 Mathematics Subject Classification (2000): 35K35, 35R15, 60H15 Key words or phrases: Stochastic Stefan problem – Invariant measures – Wiener process – Transition semigroup – Kolmogorov operator     

Construction of Solutions and L^1-error Estimates of Viscous Methods for Scalar Conservation Laws with Boundary

This paper is concerned with an initial boundary value problem for strictly convex conservation laws whose weak entropy solution is in the piecewise smooth solution class consisting of finitely many discontinuities. By the structure of the weak entropy solution of the corresponding initial value problem and the boundary entropy condition developed by Bardos-Leroux Nedelec, we give a construction method to the weak entropy solution of the initial boundary value problem. Compared with the initial value problem, the weak entropy solution of the initial boundary value problem includes the following new interaction type： an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary. According to the structure and some global estimates of the weak entropy solution, we derive the global L^1-error estimate for viscous methods to this initial boundary value problem by using the matching travelling wave solutions method. If the inviscid solution includes the interaction that an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary, or the inviscid solution includes some shock wave which is tangent to the boundary, then the error of the viscosity solution to the inviscid solution is bounded by O（ε^1/2） in L^1-norm; otherwise, as in the initial value problem, the L^1-error bound is O（ε｜ In ε｜）.     

Multiobjective optimization problem with variational inequality constraints

 We study a general multiobjective optimization problem with variational inequality, equality, inequality and abstract constraints. Fritz John type necessary optimality conditions involving Mordukhovich coderivatives are derived. They lead to Kuhn-Tucker type necessary optimality conditions under additional constraint qualifications including the calmness condition, the error bound constraint qualification, the no nonzero abnormal multiplier constraint qualification, the generalized Mangasarian-Fromovitz constraint qualification, the strong regularity constraint qualification and the linear constraint qualification. We then apply these results to the multiobjective optimization problem with complementarity constraints and the multiobjective bilevel programming problem. Received: November 2000 / Accepted: October 2001 Published online: December 19, 2002 Key Words. Multiobjective optimization – Variational inequality – Complementarity constraint – Constraint qualification – Bilevel programming problem – Preference – Utility function – Subdifferential calculus – Variational principle Research of this paper was supported by NSERC and a University of Victoria Internal Research Grant Research was supported by the National Science Foundation under grants DMS-9704203 and DMS-0102496 Mathematics Subject Classification (2000): Sub49K24, 90C29     

Scenario reduction in stochastic programming

 Given a convex stochastic programming problem with a discrete initial probability distribution, the problem of optimal scenario reduction is stated as follows: Determine a scenario subset of prescribed cardinality and a probability measure based on this set that is the closest to the initial distribution in terms of a natural (or canonical) probability metric. Arguments from stability analysis indicate that Fortet-Mourier type probability metrics may serve as such canonical metrics. Efficient algorithms are developed that determine optimal reduced measures approximately. Numerical experience is reported for reductions of electrical load scenario trees for power management under uncertainty. For instance, it turns out that after 50% reduction of the scenario tree the optimal reduced tree still has about 90% relative accuracy. Received: July 2000 / Accepted: May 2002 Published online: February 14, 2003 Key words. stochastic programming – quantitative stability – Fortet-Mourier metrics – scenario reduction – transportation problem – electrical load scenario tree Mathematics Subject Classification (1991): 90C15, 90C31     

Optimality and Duality Results for Bilevel Programming Problem Using Convexifactors

The paper is devoted to the applications of convexifactors to bilevel programming problem. Here we have defined ∂ ^∗-convex, ∂ ^∗-pseudoconvex and ∂ ^∗-quasiconvex bifunctions in terms of convexifactors on the lines of Dutta and Chandra (Optimization 53:77–94, 2004) and Li and Zhang (J. Opt. Theory Appl. 131:429–452, 2006). We derive sufficient optimality conditions for the bilevel programming problem by using these functions, and we establish various duality results by associating the given problem with two dual problems, namely Wolfe type dual and Mond–Weir type dual.     

On the unsteady Poiseuille flow in a pipe

We show that in an unsteady Poiseuille flow of a Navier–Stokes fluid in an infinite straight pipe of constant cross-section, σ, the flow rate, F(t), and the axial pressure drop, q(t), are related, at each time t, by a linear Volterra integral equation of the second type, where the kernel depends only upon t and σ. One significant consequence of this result is that it allows us to prove that the inverse parabolic problem of finding a Poiseuille flow corresponding to a given F(t) is equivalent to the resolution of the classical initial-boundary value problem for the heat equation. G. P. Galdi: Partially supported by the NSF grant DMS–0404834. K. Pileckas: Supported by EC FP6 MCToK program SPADE2, MTKD–CT–2004–014508 A. L. Silvestre: Supported by FCT-Project POCI/MAT/61792/2004     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

Multipoint Taylor formulæ

Summary. The main result of this paper is an abstract version of the Kowalewski–Ciarlet–Wagschal multipoint Taylor formula for representing the pointwise error in multivariate Lagrange interpolation. Several applications of this result are given in the paper. The most important of these is the construction of a multipoint Taylor error formula for a general finite element, together with the corresponding –error bounds. Another application is the construction of a family of error formul? for linear interpolation (indexed by real measures of unit mass) which includes some recently obtained formul?. It is also shown how the problem of constructing an error formula for Lagrange interpolation from a D–invariant space of polynomials with the property that it involves only derivatives which annihilate the interpolating space can be reduced to the problem of finding such a formula for a ‘simpler’ one–point interpolation map. Received March 29, 1996 / Revised version received November 22, 1996     

Orders of intersections of sylowp-subgroups in finite groups

Using the classification of finite simple groups, we tackle problem 5.12 from the “Kourovka Notebook,” for G a finite group satisfying O_p=1 for any prime p. Supported by RFFR. Translated fromAlgebra i Logika, Vol. 36, No. 2, pp. 156–165, March–April, 1997.     

Two-phase Stefan problem with vanishing specific heat

The unique solvability of the two-phase Stefan problem with a small parameter ε ∈ [0; ε ₀] at the time derivative in the heat equations is proved. The solution is obtained on a certain time interval [0; t ₀] independent of ε. The solution of the Stefan problem is compared with the solution to the Hele–Shaw problem corresponding to the case ε = 0. The solutions of both problems are not assumed to coincide at the initial moment of time. Bibliography: 18 titles. Dedicated to Vsevolod Alekseevich Solonnikov on the occasion of his jubilee Published in Zapiski Nauchnykh Seminarov POMI, Vol. 362, 2008, pp. 337–363.     

Refined common knowledge logics or logics of common information

 In terms of formal deductive systems and multi-dimensional Kripke frames we study logical operations know, informed, common knowledge and common information. Based on [6] we introduce formal axiomatic systems for common information logics and prove that these systems are sound and complete. Analyzing the common information operation we show that it can be understood as greatest open fixed points for knowledge formulas. Using obtained results we explore monotonicity, omniscience problem, and inward monotonocity, describe their connections and give dividing examples. Also we find algorithms recognizing these properties for some particular cases. Received: 21 October 2000 / Published online: 2 September 2002 Key words or phrases: Multi-agent systems – Non-standard logic – Knowledge representation – Common knowledge – Common information – Fixed points, Kripke models – Modal logic     

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee     

Influence of viscosity on the structure of shock waves in the MKdV model

A “non-self-adjoint” integrable MKdV model with boundary conditions of “step-like” type is considered. The time-asymptotic behavior of the solution for the Cauchy problem is obtained. A similar problem for the dissipative perturbation of this problem is discussed. Bibliography: 10 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 199, 1992, pp. 37–42. Translated by R. F. Bikbaev.     

Achieving high-efficiency second harmonic generation in a sequence of laser pulses with random peak intensity. Part III. Propagation of pulses in a bulk medium

Interpretation of geoelectric fields gives rise to multidimensional inverse problems, which include many problems for quasi-layered media. Such problems are solved by an iterative-asymptotic method. In the present article we consider a particular implementation of the method designed for a certain model of the medium, a certain method of solving the one-dimensional inverse problem, and a certain representation of magnetotelluric sounding data. For Parts I and II, see Prikladnaya Matematika i Informatika, No. 26, pp. 5–24, 2007 and No. 28, pp. 50–65, 2008; English translation: Computational Mathematics and Modeling, Vol. 19, No. 4, pp. 333–342, 2008 and Vol. 20, No. 1, pp. 1–25, 2009. Translated from Prikladnaya Matematika i Informatika, No. 29, pp. 5–18, 2008.     

On Best Approximations from RS-sets in Complex Banach Spaces

The concept of an RS-set in a complex Banach space is introduced and the problem of best approximation from an RS-set in a complex space is investigated. Results consisting of characterizations, uniqueness and strong uniqueness are established,     

L-functions for Jacobi forms and the basis problem

This paper deals with Jacobi forms Φ on ?×ℂ. The Rankin–Selberg doubling method is employed to study properties of the standard L-function of Hecke–Jacobi eigenforms. It is shown that every analytic Klingen–Jacobi Eisenstein series attached to Φ has a meromorphic continuation on the whole complex plane. Hecke–Jacobi cusp eigenforms of weight k > 4 and k≡ 0 mod 4 can written explicitly as a linear combination of theta series. Finally the basis problem of Jacobi forms of square-free index is solved. Received: 12 March 2000 / Revised version: 17 September 2001     

Optimal labeling of point features in rectangular labeling models

 We investigate the NP–hard label number maximization problem (LNM): Given a set of rectangular labels Λ, each of which belongs to a point feature in the plane, the task is to find a labeling for a largest subset Λ _P of Λ. A labeling is a placement such that none of the labels overlap and each λΛ _P is placed according to a labeling model: In the discrete models, the label must be placed so that the labeled point coincides with an element of a predefined subset of corners of the rectangular label, in the continuous or slider models, the point must lie on a subset of boundaries of the label. Obviously, the slider models allow a continuous movement of a label around its point feature, leading to a significantly higher number of labels that can be placed. We present exact algorithms for this problem that are based on a pair of so-called constraint graphs that code horizontal and vertical positioning relations. The key idea is to link the two graphs by a set of additional constraints, thus characterizing all feasible solutions of LNM. This enables us to formulate a zero-one integer linear program whose solution leads to an optimal labeling. We can express LNM in both the discrete and the slider labeling models. To our knowledge, we present the first algorithm that computes provably optimal solutions in the slider models. We find it remarkable that our approach is independent of the labeling model and results in a discrete algorithm even if the problem is of continuous nature as in the slider models. Extensive experimental results on both real-world instances and point sets created by a widely used benchmark generator show that the new approach - although being an exponential time algorithm - is applicable in practice. Received: November 20, 2000 / Accepted: April 9, 2002 Published online: September 5, 2002 RID="★" ID="★" This work is partially supported by the German Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie (No. 03-MU7MP1-4). Key words. map labeling – point feature map labeling – constraint graphs – combinatorial optimization – integer programming     

On solvability of an initial-boundary-value problem for equations of magnetohydrodynamics

In this paper, we consider a nonstationary problem of magnetohydrodynamics (MHD) for viscous incompressible fluid under the condition that the medium is poorly conducting. The problem is analyzed in a bounded one-connected domain Ω ⊂ ℝⁿ, n = 2,3, for t > 0 under the condition of ideal conductivity on the boundary. We prove a theorem on the unique solvability of the problem “in the small,” on a small time interval, and on a given time interval ]0, T[ (including T = +∞) when the given data of the problem are sufficiently small (precise formulations are given in Sect. 2). To investigate the nonlinear problem, several auxiliary linear problems are preliminarily considered. The results of this paper were announced by the author in the Trakai Conference on Mathematical Modeling and Analysis in spring of 2005. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 47, No. 2, pp. 234–279, April–June, 2007.