Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

On convergence of the Gauss-Newton method for convex composite optimization

The local quadratic convergence of the Gauss-Newton method for convex composite optimization f=h∘F is established for any convex function h with the minima set C, extending Burke and Ferris’ results in the case when C is a set of weak sharp minima for h. Received: July 24, 1998 / Accepted: November 29, 2000?Published online September 3, 2001     

Existence and multiplicity of solutions for a nonlinear Neumann problem

We consider a Neumann problem of the type -εΔu+F ^′(u(x))=0 in an open bounded subset Ω of R ⁿ , where F is a real function which has exactly k maximum points. Using Morse theory we find that, for ε suitably small, there are at least 2k nontrivial solutions of the problem and we give some qualitative information about them. Received: October 30, 1999 Published online: December 19, 2001     

A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

A geometric study of duality gaps, with applications

Lagrangian relaxation is often an efficient tool to solve (large-scale) optimization problems, even nonconvex. However it introduces a duality gap, which should be small for the method to be really efficient. Here we make a geometric study of the duality gap. Given a nonconvex problem, we formulate in a first part a convex problem having the same dual. This formulation involves a convexification in the product of the three spaces containing respectively the variables, the objective and the constraints. We apply our results to several relaxation schemes, especially one called “Lagrangean decomposition” in the combinatorial-optimization community, or “operator splitting” elsewhere. We also study a specific application, highly nonlinear: the unit-commitment problem. Received: June 1997 / Accepted: December 2000?Published online April 12, 2001     

Some presentations for the special linear groups on finite fields

We simplify the Steinberg presentation of SL _n (F _d ), where n≥1 and F _d is any finite field with d elements. That presentation has the elementary matrices e _ij (r), with i,j∈{1,...,n}, i≠=j and r∈F _d , as generators, and (E1)–(E3), described at the opening of this work, as relations. The presentation that we shall obtain reduces the number of generators e _ij (r) and relations (E1)–(E3). In particular, relations (E3) are considerably reduced. Received: March 16, 1998; in final form: November 3, 2000?Published online: October 2, 2001     

The isometric extension of the into mapping from the unit sphere S 1( E ) to S 1( l ∞(Γ))

This paper considers the isometric extension problem concerning the mapping from the unit sphere S ₁(E) of the normed space E into the unit sphere S ₁(l ^∞(Γ)). We find a condition under which an isometry from S ₁(E) into S ₁(l ^∞(Γ)) can be linearly and isometrically extended to the whole space. Since l ^∞(Γ) is universal with respect to isometry for normed spaces, isometric extension problems on a class of normed spaces are solved. More precisely, if E and F are two normed spaces, and if V ₀: S ₁(E) → S ₁(F) is a surjective isometry, where c ₀₀(Γ) ⊆ F ⊆ l ^∞(Γ), then V ₀ can be extended to be an isometric operator defined on the whole space. This work is supported by Natural Science Foundation of Guangdong Province, China (Grant No. 7300614)     

Computing the nucleolus of some combinatorially-structured games

In this paper we introduce the ℬ-prenucleolus for a transferable utility game (N,v), where ℬ⊆2 ^N . The ℬ-prenucleolus is a straightforward generalization of the ordinary prenucleolus, where only the coalitions in ℬ determine the outcome. We impose a combinatorial structure on the collection ℬ which enables us to compute the ℬ-prenucleolus in ?(n ³|ℬ|) time. The algorithm can be used for computing the nucleolus of several classes of games, among which is the class of minimum cost spanning tree games. Received: September 4, 1995 / Accepted: May 5, 1997?Published online June 8, 2000     

Convex decompositions in the plane and continuous pair colorings of the irrationals

We address the structure of nonconvex closed subsets of the Euclidean plane. A closed subsetS⊆ℝ² which is not presentable as a countable union of convex sets satisfies the following dichotomy:

Self-regular functions and new search directions for linear and semidefinite optimization

In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy a polynomial ?(n log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension of the above results to semidefinite optimization (SDO) is also presented. Received: March 2000 / Accepted: December 2001?Published online April 12, 2002     

A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Entropic proximal decomposition methods for convex programs and variational inequalities

We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to produce for the first time provably convergent decomposition schemes based on C ^∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty solution sets, global convergence of the primal-dual sequences produced by the algorithm is established. Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001     

On the convexity of the multiplicative potential and penalty functions and related topics

It is well known that a function f of the real variable x is convex if and only if (x,y)→yf(y ^-1 x),y>0 is convex. This is used to derive a recursive proof of the convexity of the multiplicative potential function. In this paper, we obtain a conjugacy formula which gives rise, as a corollary, to a new rule for generating new convex functions from old ones. In particular, it allows to extend the aforementioned property to functions of the form (x,y)→g(y)f(g(y)^-1 x) and provides a new tool for the study of the multiplicative potential and penalty functions. Received: June 3, 1999 / Accepted: September 29, 2000?Published online January 17, 2001     

Some characterizations and properties of the “distance to ill-posedness” and the condition measure of a conic linear system

A conic linear system is a system of the form?P(d): find x that solves b - Ax∈C _Y , x∈C _X ,? where C _X and C _Y are closed convex cones, and the data for the system is d=(A,b). This system is“well-posed” to the extent that (small) changes in the data (A,b) do not alter the status of the system (the system remains solvable or not). Renegar defined the “distance to ill-posedness”, ρ(d), to be the smallest change in the data Δd=(ΔA,Δb) for which the system P(d+Δd) is “ill-posed”, i.e., d+Δd is in the intersection of the closure of feasible and infeasible instances d’=(A’,b’) of P(·). Renegar also defined the “condition measure” of the data instance d as C(d):=∥d∥/ρ(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear equations. This study presents two categories of results related to ρ(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of ρ(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal values provides an approximation of ρ(d) to within certain constants, depending on whether P(d) is feasible or not, and where the constants depend on properties of the cones and the norms used. The second category of results involves the existence of certain inscribed and intersecting balls involving the feasible region of P(d) or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that the feasible region of P(d) (or its alternative system when P(d) is not feasible) will contain a ball of radius r that is itself no more than a distance R from the origin, where the ratio R/r satisfies R/r≤c ₁ C(d), and such that r≥ and R≤c ₃ C(d), where c ₁,c ₂,c ₃ are constants that depend only on properties of the cones and the norms used. Therefore the condition measure C(d) is a relevant tool in proving the existence of an inscribed ball in the feasible region of P(d) that is not too far from the origin and whose radius is not too small. Received November 2, 1995 / Revised version received June 26, 1998?Published online May 12, 1999     

The stable admissions polytope

The stable admissions polytope– the convex hull of the stable assignments of the university admissions problem – is described by a set of linear inequalities. It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been fruitful in the analysis of the stable marriage problem. Received: April 10, 1998 / Accepted: June 3, 1999?Published online January 27, 2000     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Some subgroups of semilinearly ordered groups

Let G be a semilinearly ordered group with a positive cone P. Denote byn(G) the greatest convex directed normal subgroup of G, byo(G) the greatest convex right-ordered subgroup of G, and byr(G) a set of all elements x of G such that x and x⁻¹ are comparable with any element of P^± (the collection of all group elements comparable with an identity element). Previously. it was proved thatr(G) is a convex right-ordered subgroup of G. andn(G) ⊆r(G) ⊆o(G). Here, we establish a new property ofr(G). and show that the inequalities in the given system of inclusions are, generally, strict. Supported by RFFR grant No. 99-01-00156. Translated fromAlgebra i Logika, Vol. 39, No. 4, pp. 465–479, July–August, 2000.     

Canonical Theorems for Convex Sets

Let F be a family of pairwise disjoint compact convex sets in the plane such that none of them is contained in the convex hull of two others, and let r be a positive integer. We show that F has r disjoint ⌊ c _r n⌋ -membered subfamilies F _i (1 ≤ i ≤ r) such that no matter how we pick one element F _i from each F _i , they are in convex position, i.e., every F _i appears on the boundary of the convex hull of ⋃ _i=1 ^r F _i . (Here c _r is a positive constant depending only on r .) This generalizes and sharpens some results of Erdős and Szekeres, Bisztriczky and Fejes Tóth, Bárány and Valtr, and others. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p427.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received April 30, 1997, and in revised form August 5, 1997.     

The abc-conjecture for Algebraic Numbers

The abe-conjecture for the ring of integers states that, for every ε 〉 0 and every triple of relatively prime nonzero integers （a, b, c） satisfying a ＋ b = c, we have max（｜a｜, ｜b｜, ｜c｜） 〈 rad（abc）^1＋ε with a finite number of exceptions. Here the radical rad（m） is the product of all distinct prime factors of m. In the present paper we propose an abe-conjecture for the field of all algebraic numbers. It is based on the definition of the radical （in Section 1） and of the height （in Section 2） of an algebraic number. From this abc-conjecture we deduce some versions of Fermat＇s last theorem for the field of all algebraic numbers, and we discuss from this point of view known results on solutions of Fermat＇s equation in fields of small degrees over Q.     

Semicontinuity and Supremal Representation in the Calculus of Variations

We study the weak* lower semicontinuity properties of functionals of the form