Duality for semi-definite and semi-infinite programming

In this article, we study semi-definite and semi-infinite programming problems (SDSIP), which includes semi-infinite linear programs and semi-definite programs as special cases. We establish that a uniform duality between the homogeneous (SDSIP) and its Lagrangian-type dual problem is equivalent to the closedness condition of certain cone. Moreover, this closedness condition was assured by a generalized canonically closedness condition and a Slater condition. Corresponding results for the nonhomogeneous (SDSIP) problem were obtained by transforming it into an equivalent homogeneous (SDSIP) problem.     

Duality and optimality conditions for generalized equilibrium problems involving DC functions

We consider a generalized equilibrium problem involving DC functions which is called (GEP). For this problem we establish two new dual formulations based on Toland-Fenchel-Lagrange duality for DC programming problems. The first one allows us to obtain a unified dual analysis for many interesting problems. So, this dual coincides with the dual problem proposed by Martinez-Legaz and Sosa (J Glob Optim 25:311–319, 2006) for equilibrium problems in the sense of Blum and Oettli. Furthermore it is equivalent to Mosco’s dual problem (Mosco in J Math Anal Appl 40:202–206, 1972) when applied to a variational inequality problem. The second dual problem generalizes to our problem another dual scheme that has been recently introduced by Jacinto and Scheimberg (Optimization 57:795–805, 2008) for convex equilibrium problems. Through these schemes, as by products, we obtain new optimality conditions for (GEP) and also, gap functions for (GEP), which cover the ones in Antangerel et al. (J Oper Res 24:353–371, 2007, Pac J Optim 2:667–678, 2006) for variational inequalities and standard convex equilibrium problems. These results, in turn, when applied to DC and convex optimization problems with convex constraints (considered as special cases of (GEP)) lead to Toland-Fenchel-Lagrange duality for DC problems in Dinh et al. (Optimization 1–20, 2008, J Convex Anal 15:235–262, 2008), Fenchel-Lagrange and Lagrange dualities for convex problems as in Antangerel et al. (Pac J Optim 2:667–678, 2006), Bot and Wanka (Nonlinear Anal to appear), Jeyakumar et al. (Applied Mathematics research report AMR04/8, 2004). Besides, as consequences of the main results, we obtain some new optimality conditions for DC and convex problems.     

Crisp and fuzzy <Emphasis Type="Italic">k</Emphasis>-means clustering algorithms for multivariate functional data

Functional data analysis, as proposed by Ramsay (Psychometrika 47:379–396, 1982), has recently attracted many researchers. The most popular approach taken in recent studies of functional data has been the extension of statistical methods for the analysis of usual data to that of functional data (e.g., Ramsay and Silverman in Functional data Analysis Springer, Berlin Heidelberg New York, 1997, Applied functional data analysis: methods and case studies. Springer, Berlin Heidelberg New York, 2002; Mizuta in Proceedings of the tenth Japan and Korea Joint Conference of Statistics, pp 77–82, 2000; Shimokawa et al. in Japan J Appl Stat 29:27–39, 2000). In addition, several methods for clustering functional data have been proposed (Abraham et al. in Scand J Stat 30:581–595, 2003; Gareth and Catherine in J Am Stat Assoc 98:397–408, 2003; Tarpey and kinateder in J Classif 20:93–114, 2003; Rossi et al. in Proceedings of European Symposium on Artificial Neural Networks pp 305–312, 2004). Furthermore, Tokushige et al. (J Jpn Soc Comput Stat 15:319–326, 2002) defined several dissimilarities between functions for the case of functional data. In this paper, we extend existing crisp and fuzzy k-means clustering algorithms to the analysis of multivariate functional data. In particular, we consider the dissimilarity between functions as a function. Furthermore, cluster centers and memberships, which are defined as functions, are determined at the minimum of a certain target function by using a calculus-of-variations approach.     

Global existence and nonexistence for diffusive polytropic filtration equations with nonlinear boundary conditions

In this paper, we deal with the global existence and nonexistence of solutions to a diffusive polytropic filtration system with nonlinear boundary conditions. By constructing various kinds of sub- and super-solutions and using the basic properties of M-matrix, we give the necessary and sufficient conditions for global existence of nonnegative solutions, which extend the recent results of Li et al. (Z Angew Math Phys 60:284–298, 2009) and Wang et al. (Nonlinear Anal 71:2134–2140, 2009) to more general equations and simplify their proofs slightly.     

No end of the world in 2012 for 4OR

The purpose of this note is to give the readers of 4OR information on the state of the journal and its future, abiding by a triennial tradition which started with Bouyssou et al. (4OR 1(1):1–6, 2003) and continued with Bouyssou et al. (4OR 4(1):1–9, 2006) and Bouyssou et al. (4OR Q J Oper Res 7(1):15, 2009). In the 3 years that have passed since the last editorial note, three volumes of the journal have been published, each containing four issues: vol. 7 (2009), vol. 8 (2010) and vol. 9 (2011).     

An application of matrix computations to classical second-order optimality conditions

For finite dimensional optimization problems with equality and inequality constraints, a weak constant rank condition (WCR) was introduced by Andreani–Martinez–Schuverdt (AMS) (Optimization 5–6:529–542, 2007) to study classical necessary second-order optimality conditions. However, this condition is not easy to check. Using a polynomial and matrix computation tools, we can substitute it by a weak constant rank condition (WCRQ) for an approximated problem and we present a method for checking points that satisfy WCRQ. We extend the result of (Andreani et al. in Optimization 5–6:529–542, 2007), we show that WCR can be replaced by WCRQ and we prove that these two conditions are independent.     

Simultaneously inpainting in image and transformed domains

In this paper, we focus on the restoration of images that have incomplete data in either the image domain or the transformed domain or in both. The transform used can be any orthonormal or tight frame transforms such as orthonormal wavelets, tight framelets, the discrete Fourier transform, the Gabor transform, the discrete cosine transform, and the discrete local cosine transform. We propose an iterative algorithm that can restore the incomplete data in both domains simultaneously. We prove the convergence of the algorithm and derive the optimal properties of its limit. The algorithm generalizes, unifies, and simplifies the inpainting algorithm in image domains given in Cai et al. (Appl Comput Harmon Anal 24:131–149, 2008) and the inpainting algorithms in the transformed domains given in Cai et al. (SIAM J Sci Comput 30(3):1205–1227, 2008), Chan et al. (SIAM J Sci Comput 24:1408–1432, 2003; Appl Comput Harmon Anal 17:91–115, 2004). Finally, applications of the new algorithm to super-resolution image reconstruction with different zooms are presented. R. H. Chan’s research was supported in part by HKRGC Grant 400505 and CUHK DAG 2060257. L. Shen’s research was supported by the US National Science Foundation under grant DMS-0712827. Z. Shen’s research was supported in part by Grant R-146-000-060-112 at the National University of Singapore.     

Symplectic duality between complex domains

In this paper after extending the definition of symplectic duality [given in Di Scala and Loi (Adv Math 217:2336–2352, 2008) for bounded symmetric domains] to arbitrary complex domains of \mathbbCⁿ{{\mathbb{C}}^n} centered at the origin we generalize some of the results proved in Di Scala and Loi (Adv Math 217:2336–2352, 2008) and Di Scala et al. (Trans Groups 13(2):283–304, 2008) to those domains.     

Understanding linear semi-infinite programming via linear programming over cones

In this article, the standard primal and dual linear semi-infinite programming (DLSIP) problems are reformulated as linear programming (LP) problems over cones. Therefore, the dual formulation via the minimal cone approach, which results in zero duality gap for the primal–dual pair for LP problems over cones, can be applied to linear semi-infinite programming (LSIP) problems. Results on the geometry of the set of the feasible solutions for the primal LSIP problem and the optimality criteria for the DLSIP problem are also discussed.     

Cascading: an adjusted exchange method for robust conic programming

It is well known that the robust counterpart introduced by Ben-Tal and Nemirovski (Math Oper Res 23:769–805, 1998) increases the numerical complexity of the solution compared to the original problem. Kočvara, Nemirovski and Zowe therefore introduced in Kočvara et al. (Comput Struct 76:431–442, 2000) an approximation algorithm for the special case of robust material optimization, called cascading. As the title already indicates, we will show that their method can be seen as an adjustment of standard exchange methods to semi-infinite conic programming. We will see that the adjustment can be motivated by a suitable reformulation of the robust conic problem.      

Various products for Lebesgue densities

In Macheras and Strauss (Atti Sem Math Fis Univ Modena, L, pp 349–361, 2002) and Musial et al. (J Theor Probab 20:545–560, 2007) various products for primitive liftings in the factors of a product of probability spaces have been considered. In this paper we settle for the d-dimensional Lebesgue densities open problems from Macheras and Strauss (Atti Sem Math Fis Univ Modena, L, pp 349–361, 2002) and Musial et al. (J Theor Probab 20:545–560, 2007) by applying results relying on the metrical group structure of \mathbb R^d{{\mathbb R}^d}, if d ? \mathbb N{d\in{\mathbb N}}. In particular, a lifting problem from Musial et al. (Arch Math 83:467–480, 2004), Question 3.3, is decided to the negative for the Lebesgue densities. The relation of the Lebesgue density in the product space and the results of the products taken for the Lebesgue densities in the factors under order is discussed. The results can be carried over to densities and liftings dominating Lebesgue densities and to multiplicative and positive linear liftings on function spaces.     

Analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms

This paper is devoted to the convergence and stability analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms. As soon as a nonlinear scheme can be written as a specific perturbation of a linear and convergent subdivision scheme, we show that if some contractivity properties are satisfied, then stability and convergence can be achieved. This approach is applied to various schemes, which give different new results. More precisely, we study uncentered Lagrange interpolatory linear schemes, WENO scheme (Liu et al., J Comput Phys 115:200–212, 1994), PPH and Power-P schemes (Amat and Liandrat, Appl Comput Harmon Anal 18(2):198–206, 2005; Serna and Marquina, J Comput Phys 194:632–658, 2004) and a nonlinear scheme using local spherical coordinates (Aspert et al., Comput Aided Geom Des 20:165–187, 2003). Finally, a stability proof is given for the multiresolution transform associated to a nonlinear scheme of Marinov et al. (2005).     

Minimal codewords in Reed–Muller codes

Minimal codewords were introduced by Massey (Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory, pp 276–279, 1993) for cryptographical purposes. They are used in particular secret sharing schemes, to model the access structures. We study minimal codewords of weight smaller than 3 · 2 ^m−r in binary Reed–Muller codes RM(r, m) and translate our problem into a geometrical one, using a classification result of Kasami and Tokura (IEEE Trans Inf Theory 16:752–759, 1970) and Kasami et al. (Inf Control 30(4):380–395, 1976) on Boolean functions. In this geometrical setting, we calculate numbers of non-minimal codewords. So we obtain the number of minimal codewords in the cases where we have information about the weight distribution of the code RM(r, m). The presented results improve previous results obtained theoretically by Borissov et al. (Discrete Appl Math 128(1), 65–74, 2003), and computer aided results of Borissov and Manev (Serdica Math J 30(2-3), 303–324, 2004). This paper is in fact an extended abstract. Full proofs can be found on the arXiv.     

Stability of the primal-dual partition in linear semi-infinite programming

We analyse the primal-dual states in linear semi-infinite programming (LSIP), where we consider the primal problem and the so called Haar's dual problem. Any linear programming problem and its dual can be classified as bounded, unbounded or inconsistent, giving rise to nine possible primal-dual states, which are reduced to six by the weak duality property. Recently, Goberna and Todorov have studied this partition and its stability in continuous LSIP in a series of papers [M.A. Goberna and M.I. Todorov, Primal, dual and primal-dual partitions in continuous linear semi-infinite programming, Optimization 56 (2007), pp. 617–628; M.A. Goberna and M.I. Todorov, Generic primal-dual solvability in continuous linear semi-infinite programming, Optimization 57 (2008), pp. 239–248]. In this article we consider the general case, with no continuity assumptions, discussing the maintenance of the primal-dual state of the problem by allowing small perturbations of the data. We characterize the stability of all of the six possible primal-dual states through necessary and sufficient conditions which depend on the data, and can be easily checked, showing some differences with the continuous case. These conditions involve the strong Slater constraint qualification, and some distinguished convex sets associated to the data.     

Comments on purification in continuum games

It is pointed out that Corollary 1 in a recent paper by Khan et al. (Int J Game Theory 34:91–104, 2006), presented there as an extension of the Dvoretzky–Wald–Wolfowitz theorem, is a special case of Lyapunov’s theorem for Young measures (Balder in Rend Instit Mat Univ Trieste 31 Suppl. 1:1–69) It is also pointed out that Theorems 1–4 in Khan et al. (Int J Game Theory 34:91–104, 2006) follow from a single strong purification per se result that is already contained, as an implementation of that Lyapunov theorem for Young measures, in the proof of Theorem 2.2.1 in Balder (J Econ Theory 102:437–470, 2002).     

On very weak solutions of the stationary Navier–Stokes equations

We study the stationary Navier–Stokes equations in a bounded domain Ω of R ³ with smooth connected boundary. The notion of very weak solutions has been introduced by Marušić-Paloka (Appl. Math. Optim. 41:365–375, 2000), Galdi et al. (Math. Ann. 331:41–74, 2005) and Kim (Arch. Ration. Mech. Anal. 193:117–152, 2009) to obtain solvability results for the Navier–Stokes equations with very irregular data. In this article, we prove a complete solvability result which unifies those in Marušić-Paloka (Appl. Math. Optim. 41:365–375, 2000), Galdi et al. (Math. Ann. 331:41–74, 2005) and Kim (Arch. Ration. Mech. Anal. 193:117–152, 2009) by adapting the arguments in Choe and Kim (Preprint) and Kim and Kozono (Preprint).     

Iterative algorithms for variational inequality and equilibrium problems with applications

In this paper, we introduce an iterative method for finding a common element of the set of solutions of equilibrium problems, of the set of variational inequalities and of the set of common fixed points of an infinite family of nonexpansive mappings in the framework of real Hilbert spaces. Strong convergence of the proposed iterative algorithm is obtained. As an application, we utilize the main results which improve the corresponding results announced in Chang et al. (Nonlinear Anal, 70:3307–3319, 2009), Colao et al. (J Math Anal Appl, 344:340–352, 2008), Plubtieng and Punpaeng (Appl Math Comput, 197:548–558, 2008) to study the optimization problem.     

Generalized equilibrium problems and fixed point problems for nonexpansive semigroups in Hilbert spaces

In this paper, we introduce two iterative schemes (one implicit and one explicit) for finding a common element of the set of solutions of the generalized equilibrium problems and the set of all common fixed points of a nonexpansive semigroup in the framework of a real Hilbert space. We prove that both approaches converge strongly to a common element of such two sets. Such common element is the unique solution of a variational inequality, which is the optimality condition for a minimization problem. Furthermore, we utilize the main results to obtain two mean ergodic theorems for nonexpansive mappings in a Hilbert space. The results of this paper extend and improve the results of Li et al. (J Nonlinear Anal 70:3065–3071, 2009), Cianciaruso et al. (J Optim Theory Appl 146:491–509, 2010) and many others.     

DrAmpl: a meta solver for optimization problem analysis

Optimization problems modeled in the AMPL modeling language (Fourer et al., in AMPL: a modeling language for mathematical programming, 2002) may be examined by a set of tools found in the AMPL Solver Library (Gay, in Hooking your solver to AMPL, 1997). DrAmpl is a meta solver which, by use of the AMPL Solver Library, dissects such optimization problems, obtains statistics on their data, is able to symbolically prove or numerically disprove convexity of the functions involved and provides aid in the decision for an appropriate solver. A problem is associated with a number of relevant solvers available on the NEOS Server for Optimization (Czyzyk et al., in IEEE J Comput Sci Eng 5:68–75, 1998) by means of a relational database. We describe the need for such a tool, the design of DrAmpl and some of its consequences, and keep in mind that a similar tool could be developed for other algebraic modeling languages.     

Finite volume schemes for locally constrained conservation laws

This paper is devoted to the numerical analysis of the road traffic model proposed by Colombo and Goatin (J. Differ. Equ. 234(2):654–675, 2007). The model involves a standard conservation law supplemented by a local unilateral constraint on the flux at the point x = 0 (modelling a road light, a toll gate, etc.). We first show that the problem can be interpreted in terms of the theory of conservation laws with discontinuous flux function, as developed by Adimurthi et al. (J. Hyperbolic Differ. Equ. 2(4):783–837, 2005) and Bürger et al. (SIAM J. Numer. Anal. 47(3):1684–1712, 2009). We reformulate accordingly the notion of entropy solution introduced by Colombo and Goatin (J. Differ. Equ. 234(2):654–675, 2007), and extend the well-posedness results to the L ^∞ framework. Then, starting from a general monotone finite volume scheme for the non-constrained conservation law, we produce a simple scheme for the constrained problem and show its convergence. The proof uses a new notion of entropy process solution. Numerical examples modelling a “green wave” are presented.