一类逼近l1精确罚函数的罚函数

本文对可微非线性规划问题提出了一个渐近算法,它是基于一类逼近l1精确罚函数的罚函数而提出的,我们证明了算法所得的极小点列的聚点均为原问题的最优解,并在Mangasarian-Fromovitz约束条件下,证明了有限次迭代之后,所有迭代均为可行的,即迭代所得的极小点为可行点.     

An augmented Lagrangian interior-point method using directions of negative curvature

 We describe an efficient implementation of an interior-point algorithm for non-convex problems that uses directions of negative curvature. These directions should ensure convergence to second-order KKT points and improve the computational efficiency of the procedure. Some relevant aspects of the implementation are the strategy to combine a direction of negative curvature and a modified Newton direction, and the conditions to ensure feasibility of the iterates with respect to the simple bounds. The use of multivariate barrier and penalty parameters is also discussed, as well as the update rules for these parameters. We analyze the convergence of the procedure; both the linesearch and the update rule for the barrier parameter behave appropriately. As the main goal of the paper is the practical usage of negative curvature, a set of numerical results on small test problems is presented. Based on these results, the relevance of using directions of negative curvature is discussed. Received: July 2000 / Accepted: October 2002 Published online: December 19, 2002 Key words. Primal-dual methods – Nonconvex optimization – Linesearches Research supported by Spanish MEC grant BEC2000-0167 Mathematics Subject Classification (1991): 49M37, 65K05, 90C30     

The speed of biased random walk on percolation clusters

 We consider biased random walk on supercritical percolation clusters in ℤ². We show that the random walk is transient and that there are two speed regimes: If the bias is large enough, the random walk has speed zero, while if the bias is small enough, the speed of the random walk is positive. Received: 20 November 2002 / Revised version: 17 January 2003 Published online: 15 April 2003 Research supported by Microsoft Research graduate fellowship. Research partially supported by the DFG under grant SPP 1033. Research partially supported by NSF grant #DMS-0104073 and by a Miller Professorship at UC Berkeley. Mathematics Subject Classification (2000): 60K37; 60K35; 60G50 Key words or phrases: Percolation – Random walk     

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     

An inexact bundle variant suited to column generation

We give a bundle method for constrained convex optimization. Instead of using penalty functions, it shifts iterates towards feasibility, by way of a Slater point, assumed to be known. Besides, the method accepts an oracle delivering function and subgradient values with unknown accuracy. Our approach is motivated by a number of applications in column generation, in which constraints are positively homogeneous—so that zero is a natural Slater point—and an exact oracle may be time consuming. Finally, our convergence analysis employs arguments which have been little used so far in the bundle community. The method is illustrated on a number of cutting-stock problems. Research supported by INRIA New Investigation Grant “Convex Optimization and Dantzig–Wolfe Decomposition”.     

On the exactness of a class of nondifferentiable penalty functions

In this paper, we consider a class of nondifferentiable penalty functions for the solution of nonlinear programming problems without convexity assumptions. Preliminarily, we introduce a notion of exactness which appears to be of relevance in connection with the solution of the constrained problem by means of unconstrained minimization methods. Then, we show that the class of penalty functions considered is exact, according to this notion. This research was partially supported by the National Research Program on “Modelli e Algoritmi per l'Ottimizzazione,” Ministero della Pubblica, Istruzione, Roma, Italy.     

Integral representation with weights I

 We describe a new approach to representation formulas for holomorphic functions, including the Cauchy-Fantappie-Leray formula, and provide a general method to generate weighted formulas. Received: 31 October 2001 / Published online: 28 March 2003 Mathematics Subject Classification (1991): 32 A 25. The author was partially supported by the Swedish Research Council.     

Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints

 Multidimensional optimization problems where the objective function and the constraints are multiextremal non-differentiable Lipschitz functions (with unknown Lipschitz constants) and the feasible region is a finite collection of robust nonconvex subregions are considered. Both the objective function and the constraints may be partially defined. To solve such problems an algorithm is proposed, that uses Peano space-filling curves and the index scheme to reduce the original problem to a H?lder one-dimensional one. Local tuning on the behaviour of the objective function and constraints is used during the work of the global optimization procedure in order to accelerate the search. The method neither uses penalty coefficients nor additional variables. Convergence conditions are established. Numerical experiments confirm the good performance of the technique. Received: April 2002 / Accepted: December 2002 Published online: March 21, 2003 RID="⋆" ID="⋆" This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 01–01–00587. Key Words. global optimization – multiextremal constraints – local tuning – index approach     

Exact penalty functions in nonlinear programming

In this paper some new theoretic results on piecewise differentiable exact penalty functions are presented. Sufficient conditions are given for the existence of exact penalty functions for inequality constrained problems more general than concave and several classes of such functions are presented.This research was partially supported by a grant from the Office of Naval Research; contract number N00014-67-A-0321-0003 (NR047-095).     

Non-autonomous semilinear evolution equations with almost sectorial operators

Inspired by the theory of semigroups of growth α, we construct an evolution process of growth α. The abstract theory is applied to study semilinear singular non-autonomous parabolic problems. We prove that, under natural assumptions, a reasonable concept of solution can be given to such semilinear singularly non-autonomous problems. Applications are considered to non-autonomous parabolic problems in space of H?lder continuous functions and to a parabolic problem in a domain with a one dimensional handle. Marcelo J. D. Nascimento: Research partially supported by FAPESP # 02/11855-2, Brazil.     

Non-Interior continuation methods for solving semidefinite complementarity problems

 There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported. Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002 RID="⋆" ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273. Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear convergence     

A feasible semismooth asymptotically Newton method for mixed complementarity problems

 Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region. As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods. In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges to the Newton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method, which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior to doing (curved) line searches. As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration. The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical results are reported on all problems from the MCPLIB collection [8]. Received: December 1999 / Accepted: March 2002 Published online: September 5, 2002 RID="★" ID="★" This work was supported in part by the Australian Research Council. Key Words. mixed complementarity problems – semismooth equations – projected Newton method – convergence AMS subject classifications. 90C33, 90C30, 65H10     

Variational conditions with smooth constraints: structure and analysis

 This is an expository paper about the analysis of variational conditions over sets defined in finite-dimensional spaces by fairly smooth functions satisfying a constraint qualification. The primary focus is on results that can provide quantitative and computable sensitivity information for particular instances of the problems under study, and our objective is to give a personal view of the state of current knowledge in this area and of gaps in that knowledge that require future work. The writing style is informal, in keeping with the objective of focusing the reader's attention on the basic concepts and the relationships between them, rather than on details of the particular results themselves. Received: December 1, 2002 / Accepted: April 25, 2003 Published online: May 28, 2003 Key words. variational condition – variational inequality – complementarity – sensitivity – stability – nondegeneracy Mathematics Subject Classification (2000): Primary: 90C31. Secondary: 47J20, 49J40, 49J53, 90C33     

Rank-dependent moderate deviations of U-empirical measures in strong topologies

 We prove a rank-dependent moderate deviation principle for U-empirical measures, where the underlying i.i.d. random variables take values in a measurable (not necessarily Polish) space (S,𝒮). The result can be formulated on a suitable subset of all signed measures on (S ^m ,𝒮^{⊗ m} ). We endow this space with a topology, which is stronger than the usual τ-topology. A moderate deviation principle for Banach-space valued U-statistics is obtained as a particular application. The advantage of our result is that we obtain in the degenerate case moderate deviations in non-Gaussian situations with non-convex rate functions. Received: 22 February 2000 / Revised version: 15 November 2002 / Published online: 28 March 2003 Research partially supported by the Swiss National Foundation, Contract No. 21-298333.90. Mathematics Subject Classification (2000): Primary 60F10; Secondary 62G20, 28A35 Key words or phrases: Rank-dependent moderate deviations – Empirical measures – Strong topology – U-statistics     

Discontinuous piecewise linear optimization

A theoretical framework and a practical algorithm are presented to solve discontinuous piecewise linear optimization problems dealing with functions for which theridges are known. A penalty approach allows one to consider such problems subject to a wide range of constraints involving piecewise linear functions. Although the theory is expounded in detail in the special case of discontinuous piecewiselinear functions, it is straightforwardly extendable, using standard nonlinear programming techniques, tononlinear (discontinuous piecewise differentiable) functions.The descent algorithm which is elaborated uses active-set and projected gradient approaches. It is a generalization of the ideas used by Conn to deal with nonsmoothness in thel ₁ exact penalty function, and it is based on the notion ofdecomposition of a function into a smooth and a nonsmooth part. The constrained case is reduced to the unconstrained minimization of a (piecewise linear)l ₁ exact penalty function. We also discuss how the algorithm is modified when it encounters degenerate points. Preliminary numerical results are presented: the algorithm is applied to discontinuous optimization problems from models in industrial engineering. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by the Natural Sciences and Engineering Council of Canada and the Centre de Recherches Mathématiques, Université de Montréal.This research was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No. F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.     

Exploring the complexity boundary between coloring and?list-coloring

Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ,μ)-coloring. Flavia Bonomo partially supported by UBACyT Grants X606 and X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). Guillermo Durán partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). Javier Marenco partially supported by UBACyT Grant X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

Corner Polyhedra and their connection with cutting planes

 We review the necessary background on Corner Polyhedra and use this to show how knowledge about Corner Polyhedra and subadditive functions translates into a great variety of cutting planes for general integer programming problems. Experiments are described that indicate the dominance of a relatively small number of the facets of Corner Polyhedra. This has implications for their value as cutting planes. Received: May 24, 2001 / Accepted: August 2002 Published online: March 21, 2003 Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

On projective curves of maximal regularity

 Let 𝒞⊆ℙ ^r _K be a non-degenerate projective curve of degree d>r+1 of maximal regularity so that 𝒞 has an extremal secant line . We show that 𝒞∪ is arithmetically Cohen Macaulay if d<2r−1 and we study the Betti numbers and the Hartshorne-Rao module of the curve 𝒞. Received: 27 March 2002; in final form: 24 May 2002 / Published online: 1 April 2003 Mathematics Subject Classification (1991): 14H45, 13D02. The second author was partially supported by Swiss National Science Foundation (Projects No. 20-52762.97 and 20-59237.99).     

A new correctness criterion for multiplicative non-commutative proof nets

 We introduce a new correctness criterion for multiplicative non commutative proof nets which can be considered as the non-commutative counterpart to the Danos-Regnier criterion for proof nets of linear logic. The main intuition relies on the fact that any switching for a proof net (obtained by mutilating one premise of each disjunction link) can be naturally viewed as a series-parallel order variety (a cyclic relation) on the conclusions of the proof net. Received: 8 November 2000 / Revised version: 21 June 2001 / Published online: 2 September 2002 Research supported by the EU TMR Research Programme ``Linear Logic and Theoretical Computer Science'. Mathematics Subject Classification (2000): 03F03, 03F07, 03F52, 03B70 Key words or phrases: Linear and non-commutative logic – Proof nets – Series-parallel orders and order varieties     

Real quadratic fields with class number divisible by 3

 We shall show that the number of real quadratic fields whose absolute discriminant is ≤ x and whose class number is divisible by 3 is improving the existing best known bound of K. Chakraborty and R. Murty. Received: 7 January 2003 Published online: 19 May 2003 This work was supported by Korea Research Foundation Grant KRF-2002-003-C00001. Mathematics Subject Classification(2000): 11R11, 11R29