Monteiro R.D.C.,Georgia Institute of Technology |
Svaiter B.F.,Institute Matematica Pura e Aplicada
SIAM Journal on Optimization | Year: 2010
In this paper we analyze the iteration complexity of the hybrid proximal extragradient (HPE) method for finding a zero of a maximal monotone operator recently proposed by Solodov and Svaiter. One of the key points of our analysis is the use of new termination criteria based on the ε-enlargement of a maximal monotone operator. The advantage of using these termination criteria is that their definition do not depend on the boundedness of the domain of the operator. We then show that Korpelevich's extragradient method for solving monotone variational inequalities falls in the framework of the HPE method. As a consequence, using the complexity analysis of the HPE method, we obtain new complexity bounds for Korpelevich's extragradient method which do not require the feasible set to be bounded, as assumed in a recent paper by Nemirovski. Another feature of our analysis is that the derived iteration-complexity bounds are proportional to the distance of the initial point to the solution set. The HPE framework is also used to obtain the first iterationcomplexity result for Tseng's modified forward-backward splitting method for finding a zero of the sum of a monotone Lipschitz continuous map with an arbitr ary maximal monotone operator whose resolvent is assumed to be easily computable. Also using the framework of the HPE method, we study the complexity of a variant of a Newton-type extragradient algorithm proposed by Solodov and Svaiter for finding a zero of a smooth monotone function with Lipschitz continuous Jacobian. © 2010 Society for Industrial and Applied Mathematics.
Movasati H.,Institute Matematica Pura e Aplicada
Nuclear Physics B | Year: 2011
In this article we introduce an ordinary differential equation associated to the one parameter family of Calabi-Yau varieties which is mirror dual to the universal family of smooth quintic three folds. It is satisfied by seven functions written in the q-expansion form and the Yukawa coupling turns out to be rational in these functions. We prove that these functions are algebraically independent over the field of complex numbers, and hence, the algebra generated by such functions can be interpreted as the theory of (quasi) modular forms attached to the one parameter family of Calabi-Yau varieties. Our result is a reformulation and realization of a problem of Griffiths around seventies on the existence of automorphic functions for the moduli of polarized Hodge structures. It is a generalization of the Ramanujan differential equation satisfied by three Eisenstein series. © 2011 Elsevier B.V.
Izmailov A.F.,Moscow State University |
Solodov M.V.,Institute Matematica Pura e Aplicada
Mathematical Programming | Year: 2012
The stabilized version of the sequential quadratic programming algorithm (sSQP) had been developed in order to achieve superlinear convergence in situations when the Lagrange multipliers associated to a solution are not unique. Within the framework of Fischer (Math Program 94:91-124, 2002), the key to local superlinear convergence of sSQP are the following two properties: upper Lipschitzian behavior of solutions of the Karush-Kuhn-Tucker (KKT) system under canonical perturbations and local solvability of sSQP subproblems with the associated primal-dual step being of the order of the distance from the current iterate to the solution set of the unperturbed KKT system. According to Fernández and Solodov (Math Program 125:47-73, 2010), both of these properties are ensured by the second-order sufficient optimality condition (SOSC) without any constraint qualification assumptions. In this paper, we state precise relationships between the upper Lipschitzian property of solutions of KKT systems, error bounds for KKT systems, the notion of critical Lagrange multipliers (a subclass of multipliers that violate SOSC in a very special way), the second-order necessary condition for optimality, and solvability of sSQP subproblems. Moreover, for the problem with equality constraints only, we prove superlinear convergence of sSQP under the assumption that the dual starting point is close to a noncritical multiplier. Since noncritical multipliers include all those satisfying SOSC but are not limited to them, we believe this gives the first superlinear convergence result for any Newtonian method for constrained optimization under assumptions that do not include any constraint qualifications and are weaker than SOSC. In the general case when inequality constraints are present, we show that such a relaxation of assumptions is not possible. We also consider applying sSQP to the problem where inequality constraints are reformulated into equalities using slack variables, and discuss the assumptions needed for convergence in this approach. We conclude with consequences for local regularization methods proposed in (Izmailov and Solodov SIAM J Optim 16:210-228, 2004; Wright SIAM J. Optim. 15:673-676, 2005). In particular, we show that these methods are still locally superlinearly convergent under the noncritical multiplier assumption, weaker than SOSC employed originally. © 2010 Springer and Mathematical Optimization Society.
Guigues V.,Institute Matematica Pura e Aplicada |
Romisch W.,Humboldt University of Berlin
SIAM Journal on Optimization | Year: 2012
We define a risk-averse nonanticipative feasible policy for multistage stochastic programs and propose a methodology to implement it. The approach is based on dynamic programming equations written for a risk-averse formulation of the problem. This formulation relies on a new class of multiperiod risk functionals called extended polyhedral risk measures. Dual representations of such risk functionals are given and used to derive conditions of coherence. In the one-period case, conditions for convexity and consistency with second order stochastic dominance are also provided. The risk-averse dynamic programming equations are specialized considering convex combinations of one-period extended polyhedral risk measures such as spectral risk measures. To implement the proposed policy, the approximation of the risk-averse recourse functions for stochastic linear programs is discussed. In this context, we detail a stochastic dual dynamic programming algorithm which converges to the optimal value of the risk-averse problem. © 2012 Society for Industrial and Applied Mathematics.
Bello Cruz J.Y.,Federal University of Goais |
Iusem A.N.,Institute Matematica Pura e Aplicada
Numerical Functional Analysis and Optimization | Year: 2011
In this article, we propose a strongly convergent variant on the projected subgradient method for constrained convex minimization problems in Hilbert spaces. The advantage of the proposed method is that it converges strongly when the problem has solutions, without additional assumptions. The method also has the following desirable property: the sequence converges to the solution of the problem which lies closest to the initial iterate. Copyright © Taylor & Francis Group, LLC.