A practical algorithm for decomposing polygonal domains into convex polygons by diagonals

We present algorithms for decomposing a polygon (with holes) into convex polygons by diagonals. The methods are computationally quick, and although the partitions that they produce may not have minimal cardinality they usually have a low number of convex pieces. Thus, the methods are suitable for being used when achieving a modest load on the CPU time is more important than finding optimal decompositions as, for instance, in location problems. Part of the results in this paper are from Fernández (1999), and were presented in Fernández et al. (1998). This work has been supported by the Ministry of Science and Technology of Spain under the research projects BEC2002-01026, SEJ2005-06273/ECON (J. Fernández, B. Tóth and B. Pelegrín) and TIC2003-05982-C05-03 (L. Cánovas), in part financed by the European Regional Development Fund (ERDF).     

A core-allocation family for generalized holding cost games

Inventory situations, introduced in Meca et al. (Eur J Oper Res 156: 127–139, 2004), study how a collective of firms can minimize its joint inventory cost by means of co-operation. Depending on the information revealed by the individual firms, they analyze two related cooperative TU games: inventory cost games and holding cost games, and focus on proportional division mechanisms to share the joint cost. In this paper we introduce a new class of inventory games: generalized holding cost games, which extends the class of holding cost games. It turns out that generalized holding cost games are totally balanced.We then focus on the study of a core-allocation family which is called N-rational solution family.It is proved that a particular relation of inclusion exists between the former and the core. In addition, an N-rational solution called minimum square proportional ruleis studied. This work was partially supported by the Spanish Ministry of Education and Science, and the Generalitat Valenciana (grants MTM2005-09184-C02-02, CSD2006-00032, ACOMP06/040). The author thanks Javier Toledo, Josefa Cá novas, and two anonymous referees for helpful comments.     

On the convergence of Newton-type methods under mild differentiability conditions

We introduce the new idea of recurrent functions to provide a new semilocal convergence analysis for Newton-type methods, under mild differentiability conditions. It turns out that our sufficient convergence conditions are weaker, and the error bounds are tighter than in earlier studies in some interesting cases (Chen, Ann Inst Stat Math 42:387–401, 1990; Chen, Numer Funct Anal Optim 10:37–48, 1989; Cianciaruso, Numer Funct Anal Optim 24:713–723, 2003; Cianciaruso, Nonlinear Funct Anal Appl 2009; Dennis 1971; Deuflhard 2004; Deuflhard, SIAM J Numer Anal 16:1–10, 1979; Gutiérrez, J Comput Appl Math 79:131–145, 1997; Hernández, J Optim Theory Appl 109:631–648, 2001; Hernández, J Comput Appl Math 115:245–254, 2000; Huang, J Comput Appl Math 47:211–217, 1993; Kantorovich 1982; Miel, Numer Math 33:391–396, 1979; Miel, Math Comput 34:185–202, 1980; Moret, Computing 33:65–73, 1984; Potra, Libertas Mathematica 5:71–84, 1985; Rheinboldt, SIAM J Numer Anal 5:42–63, 1968; Yamamoto, Numer Math 51: 545–557, 1987; Zabrejko, Numer Funct Anal Optim 9:671–684, 1987; Zinc̆ko 1963). Applications and numerical examples, involving a nonlinear integral equation of Chandrasekhar-type, and a differential equation are also provided in this study.     

Solution Methods for Pseudomonotone Variational Inequalities

We extend some results due to Thanh-Hao (Acta Math. Vietnam. 31: 283–289, [2006]) and Noor (J. Optim. Theory Appl. 115:447–452, [2002]). The first paper established a convergence theorem for the Tikhonov regularization method (TRM) applied to finite-dimensional pseudomonotone variational inequalities (VIs), answering in the affirmative an open question stated by Facchinei and Pang (Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, [2003]). The second paper discussed the application of the proximal point algorithm (PPA) to pseudomonotone VIs. In this paper, new facts on the convergence of TRM and PPA (both the exact and inexact versions of PPA) for pseudomonotone VIs in Hilbert spaces are obtained and a partial answer to a question stated in (Acta Math. Vietnam. 31:283–289, [2006]) is given. As a byproduct, we show that the convergence theorem for inexact PPA applied to infinite-dimensional monotone variational inequalities can be proved without using the theory of maximal monotone operators. This research was supported in part by a grant from the National Sun Yat-Sen University, Kaohsiung, Taiwan. It has been carried out under the agreement between the National Sun Yat-Sen University, Kaohsiung, Taiwan and the University of Pisa, Pisa, Italy. The authors thank the anonymous referee for useful comments and suggestions.     

Multi-step nonlinear conjugate gradient methods for unconstrained minimization

Conjugate gradient methods are appealing for large scale nonlinear optimization problems, because they avoid the storage of matrices. Recently, seeking fast convergence of these methods, Dai and Liao (Appl. Math. Optim. 43:87–101, 2001) proposed a conjugate gradient method based on the secant condition of quasi-Newton methods, and later Yabe and Takano (Comput. Optim. Appl. 28:203–225, 2004) proposed another conjugate gradient method based on the modified secant condition. In this paper, we make use of a multi-step secant condition given by Ford and Moghrabi (Optim. Methods Softw. 2:357–370, 1993; J. Comput. Appl. Math. 50:305–323, 1994) and propose two new conjugate gradient methods based on this condition. The methods are shown to be globally convergent under certain assumptions. Numerical results are reported.     

Non-Walker Self-Dual Neutral Einstein Four-Manifolds of Petrov Type III

The local structure of the manifolds named in the title is described. Although curvature homogeneous, they are not, in general, locally homogeneous. Not all of them are Ricci-flat, which answers an existence question about type III Jordan-Osserman metrics, raised by Díaz-Ramos, García-Río and Vázquez-Lorenzo (J. Geom. Anal. 16, 39–52, 2006). Work begun during the author’s visit to the University of Santiago de Compostela, supported by Grant MTM2006-01432 (Spain).     

New approach for the nonlinear programming with transient stability constraints arising from power systems

This paper presents a new approach for solving a class of complicated nonlinear programming problems arises from optimal power flow with transient stability constraints (denoted by OTS) in power systems. By using a functional transformation technology proposed in Chen et al. (IEEE Trans. Circuits Syst. I Fundam. Theory Appl. 48:327–339, [2001]), the OTS problem is transformed to a semi-infinite programming (SIP). Then based on the KKT (Karush-Kuhn-Tucker) system of the reformulated SIP problem and the finite approximation technology, an iterative method is presented, which develops Wu-Li-Qi-Zhou’ (Optim. Methods Softw. 20:629–643, [2005]) method. In order to save the computing cost, some typical computing technologies, such as active set strategy, quasi-Newton method for the subproblems coming from the finite approximation model, are addressed. The global convergence of the proposed algorithm is established. Numerical examples from power systems are tested. The computing results show the efficiency of the new approach.     

On a Zero Duality Gap Result in Extended Monotropic Programming

In this note we correct and improve a zero duality gap result in extended monotropic programming given by Bertsekas (J. Optim. Theory Appl. 139:209–225, 2008).     

A priori error estimates for space–time finite element discretization of semilinear parabolic optimal control problems

In this paper, a priori error estimates for space–time finite element discretizations of optimal control problems governed by semilinear parabolic PDEs and subject to pointwise control constraints are derived. We extend the approach from Meidner and Vexler (SIAM Control Optim 47(3):1150–1177, 2008; SIAM Control Optim 47(3):1301–1329, 2008) where linear-quadratic problems have been considered, discretizing the state equation by usual conforming finite elements in space and a discontinuous Galerkin method in time. Error estimates for controls discretized by piecewise constant functions in time and cellwise constant functions in space are derived in detail and we explain how error estimate for further discretization approaches, e.g., cellwise linear discretization in space, the postprocessing approach from Meyer and R?sch (SIAM J Control Optim 43:970–985, 2004), and the variationally discrete approach from Hinze (J Comput Optim Appl 30:45–63, 2005) can be obtained. In addition, we derive an estimate for a setting with finitely many time-dependent controls.     

Interactions between government and firms: a differential game approach

In this paper we study an extended version of the model described in Gradus (J. Econ. 81:1092–1109, 1989) in order to determine the optimal taxation policy of a government and its effects on the stock of capital goods growth as a result of the activity developed by firms. It is shown that, by introducing a wealth tax, there exists an optimal wealth tax rate for which the open-loop/feedback Nash/Stackelberg equilibria coincide, maximizing the payments for both agents (government and firms), so that the open-loop Stackelberg equilibrium becomes both time consistent and subgame perfect. Partially supported by MEC (Spain) Grants MTM2006-13468, BMF2002-03493 and project ‘Ingenio Mathematica (i-MATH)’ No. CSD2006-00032 (Consolider-Ingenio 2010).     

<Emphasis Type="Italic">p</Emphasis>-additive games: a class of totally balanced games arising from inventory situations with temporary discounts

We introduce a new class of totally balanced cooperative TU games, namely p-additive games. It is inspired by the class of inventory games that arises from inventory situations with temporary discounts (Toledo Ph.D. thesis, Universidad Miguel Hernández de Elche, 2002) and contains the class of inventory cost games (Meca et al. Math. Methods Oper. Res. 57:481–493, 2003). It is shown that every p-additive game and its corresponding subgames have a nonempty core. We also focus on studying the character of concave or convex and monotone p-additive games. In addition, the modified SOC-rule is proposed as a solution for p-additive games. This solution is suitable for p-additive games, since it is a core-allocation which can be reached through a population monotonic allocation scheme. Moreover, two characterizations of the modified SOC-rule are provided. This work was partially supported by the Spanish Ministry of Education and Science and Generalitat Valenciana (grants MTM2005-09184-C02-02, ACOMP06/040, CSD2006-00032). Authors acknowledge valuable comments made by the Editor and the referee.     

Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems

We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim. 17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci. 2(1):3–19, 2005).     

On a class of secant-like methods for solving nonlinear equations

We provide a semilocal convergence analysis for a certain class of secant-like methods considered also in Argyros (J Math Anal Appl 298:374–397, 2004, 2007), Potra (Libertas Mathematica 5:71–84, 1985), in order to approximate a locally unique solution of an equation in a Banach space. Using a combination of Lipschitz and center-Lipschitz conditions for the computation of the upper bounds on the inverses of the linear operators involved, instead of only Lipschitz conditions (Potra, Libertas Mathematica 5:71–84, 1985), we provide an analysis with the following advantages over the work in Potra (Libertas Mathematica 5:71–84, 1985) which improved the works in Bosarge and Falb (J Optim Theory Appl 4:156–166, 1969, Numer Math 14:264–286, 1970), Dennis (SIAM J Numer Anal 6(3):493–507, 1969, 1971), Kornstaedt (1975), Larsonen (Ann Acad Sci Fenn, A 450:1–10, 1969), Potra (L’Analyse Numérique et la Théorie de l’Approximation 8(2):203–214, 1979, Aplikace Mathematiky 26:111–120, 1981, 1982, Libertas Mathematica 5:71–84, 1985), Potra and Pták (Math Scand 46:236–250, 1980, Numer Func Anal Optim 2(1):107–120, 1980), Schmidt (Period Math Hung 9(3):241–247, 1978), Schmidt and Schwetlick (Computing 3:215–226, 1968), Traub (1964), Wolfe (Numer Math 31:153–174, 1978): larger convergence domain; weaker sufficient convergence conditions, finer error bounds on the distances involved, and a more precise information on the location of the solution. Numerical examples further validating the results are also provided.     

Error estimates for abstract linear–quadratic optimal control problems using proper orthogonal decomposition

In this paper we investigate POD discretizations of abstract linear–quadratic optimal control problems with control constraints. We apply the discrete technique developed by Hinze (Comput. Optim. Appl. 30:45–61, 2005) and prove error estimates for the corresponding discrete controls, where we combine error estimates for the state and the adjoint system from Kunisch and Volkwein (Numer. Math. 90:117–148, 2001; SIAM J. Numer. Anal. 40:492–515, 2002). Finally, we present numerical examples that illustrate the theoretical results.     

Proximal-Like Algorithm Using the Quasi D-Function for Convex Second-Order Cone Programming

In this paper, we present a measure of distance in a second-order cone based on a class of continuously differentiable strictly convex functions on ℝ₊₊. Since the distance function has some favorable properties similar to those of the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]), we refer to it as a quasi D-function. Then, a proximal-like algorithm using the quasi D-function is proposed and applied to the second-cone programming problem, which is to minimize a closed proper convex function with general second-order cone constraints. Like the proximal point algorithm using the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]; Chen and Teboulle in SIAM J. Optim. 3:538–543 [1993]), under some mild assumptions we establish the global convergence of the algorithm expressed in terms of function values; we show that the sequence generated by the proposed algorithm is bounded and that every accumulation point is a solution to the considered problem. Research of Shaohua Pan was partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province. Jein-Shan Chen is a member of the Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work was partially supported by National Science Council of Taiwan.     

Morse potential energy minimization: Improved bounds for optimal configurations

We improve lower bounds on the minimal distance between two points of a minimum energy configuration w.r.t. the Morse potential. This is achieved by generalizing a method that was already applied to the Lennard-Jones potential in Schachinger et al. (Comput. Optim. Appl. 38:329–349, 2007), resulting in improvements of the currently best bounds known for ρ∈[4.967,15] both for minimal distance and for energy of optimal configurations.     

Synthesis of Optimal Control for Cooperative Collision Avoidance for Aircraft (Ships) with Unequal Turn Capabilities

This paper presents a synthesis of an optimal control solution for cooperative collision avoidance strategies for aircraft (ships) with unequal turn capabilities in a close proximity coplanar encounter. The analytic expressions for the extremals are presented and their properties are analyzed. Simple algorithms for the synthesis of optimal control are developed. The structure of the synthesis is analyzed and its behavior with a change in the nondimensional turn rate ratio is studied. It is shown that Merz’s solution for identical aircraft (see Merz in Proc. Joint Automatic Control Conf., Paper 15-3, pp. 449–454, 1973; Navigation 20(2):144–152, 1973; Tarnopolskaya and Fulton in J. Optim. Theory Appl. 140(2):355–375, 2009) is a degenerate case of this more general solution. The results of this paper are useful for benchmarking and validating automated proximity management and collision avoidance systems.     

Error estimates for the numerical approximation of Neumann control problems

We continue the discussion of error estimates for the numerical analysis of Neumann boundary control problems we started in Casas et al. (Comput. Optim. Appl. 31:193–219, 2005). In that paper piecewise constant functions were used to approximate the control and a convergence of order O(h) was obtained. Here, we use continuous piecewise linear functions to discretize the control and obtain the rates of convergence in L ²(Γ). Error estimates in the uniform norm are also obtained. We also discuss the approach suggested by Hinze (Comput. Optim. Appl. 30:45–61, 2005) as well as the improvement of the error estimates by making an extra assumption over the set of points corresponding to the active control constraints. Finally, numerical evidence of our estimates is provided. The authors were supported by Ministerio de Ciencia y Tecnología (Spain).     

Further Results on the Robust Regulation of a One-Dimensional Dam-River System

In this paper, we consider a one-dimensional dam-river system studied by Chentouf and Wang (SIAM J. Control Optim. 47: 2275–2302, 2008). Then, using the frequency multiplier method, we provide a simple and alternative proof of stabilization and regulation results obtained in the work cited above. Moreover, we relax the conditions on the feedback gains involved in the feedback law and give a partial answer to the open problem left by the authors Chentouf and Wang (J. Optim. Theory Appl. 134: 223–239, 2007 and SIAM J. Control Optim. 47: 2275–2302, 2008) concerning the tuning of the gains.     

On Finite-Difference Approximations for Normalized Bellman Equations

A class of stochastic optimal control problems involving optimal stopping is considered. Methods of Krylov (Appl. Math. Optim. 52(3):365–399, 2005) are adapted to investigate the numerical solutions of the corresponding normalized Bellman equations and to estimate the rate of convergence of finite difference approximations for the optimal reward functions.