A Method Which Generates Splines in H-Locally Convex Spaces and Connections with Vectorial Optimization

In this research paper we present a modality for generating splines in H-locally convex spaces which allows us to solve some problems of best approximation by linear subspaces of spline functions in these spaces. In this way one shows that the elements of best vectorial approximation coincide with the spline functions introduced by us in a previous research work. These splines are also the only elements of best simultaneous approximation by their generated linear subspaces with respect to any family of seminorms which induces the H-locally convex topology and, consequently, they are the only solutions for some frequent strong and vectorial optimization programs. Moreover, as we shall see in the numerical examples, our construction leads to discover orthogonal decompositions for H-locally convex spaces which, in general, are difficult to be identified.     

A unified approach to certain problems of best local approximation

In this paper we study best local quasi-rational approximation and best local approximation from finite dimensional subspaces of vectorial functions of several variables. Our approach extends and unifies several problems concerning best local multi-point approximation in different norms.     

Znr yektoriellen linearen tschebyscheff-approximation

In this paper a problem of the linear Chebyshev approximation with respect to a vectorial norm in investigated. With the aid of abstract results of vector optimization a dual finite vector optimization problem will be assigned to this approximation problem. Further, an alternation theorem can be formulated.     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Scalarization method for Levitin–Polyak well-posedness of vectorial optimization problems

In this paper, we develop a method of study of Levitin?CPolyak well-posedness notions for vector valued optimization problems using a class of scalar optimization problems. We first introduce a non-linear scalarization function and consider its corresponding properties. We also introduce the Furi?CVignoli type measure and Dontchev?CZolezzi type measure to scalar optimization problems and vectorial optimization problems, respectively. Finally, we construct the equivalence relations between the Levitin?CPolyak well-posedness of scalar optimization problems and the vectorial optimization problems.     

Some convergence results for asynchronous algorithms

Resumé Nous présentons dans cet article des résultats de convergence des algorithmes asynchrones basés essentiellement sur la notion classique de contraction.Nous généralisons, en particulier, tous les résultats de convergence de ces algorithmes qui font l'hypothèse de contraction en norme vectorielle qui récemment a été très souvant utilisée.Par ailleurs, l'hypothèse de contraction en norme vectorielle peut se trouver difficile, voire impossible à vérifier pour certains problèmes qui peuvent être cependant abordés dans le cadre de la contraction classique que nous adoptons.

---

Some convergence results for asynchronous algorithms

Summary In this paper we present convergence results for the asynchronous algorithms based essentially on the notion of classical contraction.We generalize, in particular, all convergence results for those algorithms which are based on the vectorial norm hypothesis, in wide spread use recently.Certain problems, for which the vectorial norm hypothesis can be difficult or even impossible to verify, can nontheless be tackled within the scope of the classical contraction that we adopte.

     

Approximation of average cost optimal policies for general Markov decision processes with unbounded costs

The aim of the paper is to show that Lyapunov-like ergodicity conditions on Markov decision processes with Borel state space and possibly unbounded cost provide the approximation of an average cost optimal policy by solvingn-stage optimization problems (n = 1, 2, ...). The used approach ensures the exponential rate of convergence. The approximation of this type would be useful to find adaptive procedures of control and to estimate stability of an optimal control under disturbances of the transition probability.Research supported in part by Consejo Nacional de Ciencia y Tecnologia (CONACYT) under grant 0635P-E9506.Research supported by Fondo del Sistema de Investigatión del Mar de Cortés under Grant SIMAC/94/CT-005.     

On semi-infinite optimization and chebyshev approximation with contraints

The main purpose of this paper is to use the methods of semi-infinite optimization in order to study best Chebyshev approximation problems with constraints. We consider problems which do not satisfy the Haar condition. Characterization theorems of best approximations and an algorithm which computes these approximations are given.     

On Solution to an Optimal Shape Design Problem in 3-Dimensional Linear Magnetostatics

In this paper we present theoretical, computational, and practical aspects concerning 3-dimensional shape optimization governed by linear magnetostatics. The state solution is approximated by the finite element method using Nédélec elements on tetrahedra. Concerning optimization, the shape controls the interface between the air and the ferromagnetic parts while the whole domain is fixed. We prove the existence of an optimal shape. Then we state a finite element approximation to the optimization problem and prove the convergence of the approximated solutions. In the end, we solve the problem for the optimal shape of an electromagnet that arises in the research on magnetooptic effects and that was manufactured afterwards.     

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar graphs. We also define the concept of λ-precision unit disk graphs and show that for such graphs the approximation schemes have a better time versus performance trade-off than the approximation schemes for arbitrary unit disk graphs. Moreover, compared to unit disk graphs, we show that for λ-precision unit disk graphs many more graph problems have efficient approximation schemes.Our NC-approximation schemes can also be extended to obtain efficient NC-approximation schemes for several PSPACE-hard problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann, and Widmayer. The approximation schemes for hierarchically specified unit disk graphs presented in this paper are among the first approximation schemes in the literature for natural PSPACE-hard optimization problems.     

局部凸空间中最佳逼近研究纵览

通过对大量文献研究，回顾了最佳逼近论的研究进展．重点讨论了最有意义的可分离局部凸空间最佳逼近问题、以及最佳逼近问题与向量优化、Pareto有效性、多值函数等之间的直接联系．     

Eine Variationsungleichung und Anwendungen

In this paper we prove a variational inequality which gives a necessary condition for a minimum of a certain in general non-differentiable function. This inequality is applied to problems of best approximation and optimization to deduce global conditions for a minimum.     

Numerische Methoden zur Behandlung einiger Problemklassen der nichtlinearen Tschebyscheff-Approximation mit Nebenbedingungen

Summary The numerical treatment of Chebyshev approximation problems is often difficult in practice because of complicated constraints. These are common in applications, for instance in differential equations. In this paper algorithms are derived for a constructive treatment of several classes of approximation problems, including parameter restrictions by Fréchet-differentiable mappings and inequality constraints in the space of approximating functions. The convergence properties of these methods are discussed and applications to practical problems are given.     

On the approximability of adjustable robust convex optimization under uncertainty

In this paper, we consider adjustable robust versions of convex optimization problems with uncertain constraints and objectives and show that under fairly general assumptions, a static robust solution provides a good approximation for these adjustable robust problems. An adjustable robust optimization problem is usually intractable since it requires to compute a solution for all possible realizations of uncertain parameters, while an optimal static solution can be computed efficiently in most cases if the corresponding deterministic problem is tractable. The performance of the optimal static robust solution is related to a fundamental geometric property, namely, the symmetry of the uncertainty set. Our work allows for the constraint and objective function coefficients to be uncertain and for the constraints and objective functions to be convex, thereby providing significant extensions of the results in Bertsimas and Goyal (Math Oper Res 35:284–305, 2010) and Bertsimas et al. (Math Oper Res 36: 24–54, 2011b) where only linear objective and linear constraints were considered. The models in this paper encompass a wide variety of problems in revenue management, resource allocation under uncertainty, scheduling problems with uncertain processing times, semidefinite optimization among many others. To the best of our knowledge, these are the first approximation bounds for adjustable robust convex optimization problems in such generality.     

Some Deterministic and Random Vector Equilibrium Problems

In this paper, some generalized concepts about semicontinuity and convexity for vector-valued bifunctions are introduced. A new existence theorem for vector equilibrium problems is proved. Further, a random version of this result is considered. Applications to cone saddle points, random vector optimization, random vector variational inequalities, and random vector best approximation problems are finally given.     

Bounded sets of Lagrange multipliers for vector optimization problems in infinite dimension

The aim of this paper is to point out some sufficient constraint qualification conditions ensuring the boundedness of a set of Lagrange multipliers for vectorial optimization problems in infinite dimension. In some (smooth) cases these conditions turn out to be necessary for the existence of multipliers as well.     

Basic aspects of geopotential field approximation from satellite‐to‐satellite tracking data

The satellite‐to‐satellite tracking (SST) problems are characterized from mathematical point of view. Uniqueness results are formulated. Moreover, the basic relations are developed between (scalar) approximation of the earth's gravitational potential by ‘scalar basis systems’ and (vectorial) approximation of the gravitational field by ‘vectorial basis systems’. Finally, the mathematical justification is given for approximating the external geopotential field by finite linear combinations of certain gradient fields (for example, gradient fields of multi‐poles) consistent to a given set of SST data. Copyright © 2001 John Wiley & Sons, Ltd.     

Generation of higher-order polynomial basis of Nédélec H(curl) finite elements for Maxwell’s equations

The goal of this study is the automatic construction of a vectorial polynomial basis for Nédélec mixed finite elements, J.C. Nédélec (1980), in particular, the generation of finite elements without the expression of the polynomial basis functions, using symbolic calculus: the exhibition of basis functions has no practical interest.     

Robust Duality in Parametric Convex Optimization

Modelling of convex optimization in the face of data uncertainty often gives rise to families of parametric convex optimization problems. This motivates us to present, in this paper, a duality framework for a family of parametric convex optimization problems. By employing conjugate analysis, we present robust duality for the family of parametric problems by establishing strong duality between associated dual pair. We first show that robust duality holds whenever a constraint qualification holds. We then show that this constraint qualification is also necessary for robust duality in the sense that the constraint qualification holds if and only if robust duality holds for every linear perturbation of the objective function. As an application, we obtain a robust duality theorem for the best approximation problems with constraint data uncertainty under a strict feasibility condition.     

Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem

The Symmetric Rectilinear Steiner Arborescence (SRStA) problem is defined as follows: given a set of terminals in the positive quadrant of the plane, connect them using horizontal and vertical lines such that each terminal can be reached from the origin via a y-monotone path and the total length of all the line segments is the minimum possible. Finding an SRStA has applications in VLSI design, in data structures used in some optimization algorithms and in dynamic server problems. In this paper, we provide a polynomial time approximation scheme for the SRStA problem, improving the previous best approximation ratio of 3 for this problem.