Local convergence analysis of a grouped variable version of coordinate descent

LetF(x,y) be a function of the vector variablesxR ⁿ andyR ^m . One possible scheme for minimizingF(x,y) is to successively alternate minimizations in one vector variable while holding the other fixed. Local convergence analysis is done for this vector (grouped variable) version of coordinate descent, and assuming certain regularity conditions, it is shown that such an approach is locally convergent to a minimizer and that the rate of convergence in each vector variable is linear. Examples where the algorithm is useful in clustering and mixture density decomposition are given, and global convergence properties are briefly discussed.This research was supported in part by NSF Grant No. IST-84-07860. The authors are indebted to Professor R. A. Tapia for his help in improving this paper.     

Global minimization of large-scale constrained concave quadratic problems by separable programming

The global minimization of a large-scale linearly constrained concave quadratic problem is considered. The concave quadratic part of the objective function is given in terms of the nonlinear variablesx R ⁿ , while the linear part is in terms ofy R ^k. For large-scale problems we may havek much larger thann. The original problem is reduced to an equivalent separable problem by solving a multiple-cost-row linear program with 2n cost rows. The solution of one additional linear program gives an incumbent vertex which is a candidate for the global minimum, and also gives a bound on the relative error in the function value of this incumbent. Ana priori bound on this relative error is obtained, which is shown to be 0.25, in important cases. If the incumbent is not a satisfactory approximation to the global minimum, a guaranteed-approximate solution is obtained by solving a single liner zero–one mixed integer programming problem. This integer problem is formulated by a simple piecewise-linear underestimation of the separable problem.This research was supported by the Division of Computer Research, National Science Foundation under Research Grant DCR8405489.Dedicated to Professor George Dantzig in honor of his 70th Birthday.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

An iff fixed point criterion for continuous self-mappings on a complete metric space

Summary Letf be a self-map on a metric space (X, d). We give necessary and sufficient conditions for the sequences {f ⁿ x} (x X) to be equivalent Cauchy. As a typical application we get the following result. Letf be continuous and (X, d) be complete. If, for anyx, y X d(f ⁿ x, f ⁿ y) 0 and for somec > 0, this convergence is uniform for allx, y inX withd(x, y) c thenf has a unique fixed pointp, andf ⁿ x p, for eachx inX. This theorem includes among others results of Angelov, Browder, Edelstein, Hicks and Matkowski.     

Construction of large-scale global minimum concave quadratic test problems

Construction of problems with known global solutions is important for the computational testing of constrained global minimization algorithms. In this paper, it is shown how to construct a concave quadratic function which attains its global minimum at a specified vertex of a polytope inR ^n+k. The constructed function is strictly concave in the variablesx R ⁿ and is linear in the variablesy R ^k. The number of linear variablesk may be much larger thann, so that large-scale global minimization test problems can be constructed by the methods described here.This research was supported by the Computer Science Section of the National Science Foundation under Grant No. MCS-81-01214.     

A Class of Iterative Algorithms and Solvability of Nonlinear Variational Inequalities Involving Multivalued Mappings

The solvability of the following class of nonlinear variational inequality (NVI) problems based on a class of iterative procedures, which possess an equivalence to a class of projection formulas, is presented.Determine an element x ^* K and u ^* T(x ^*) such that u ^*, x – x ^* 0 for all x K where T: K P(H) is a multivalued mapping from a real Hilbert space H into P(H), the power set of H, and K is a nonempty closed convex subset of H. The iterative procedure adopted here is represented by a nonlinear variational inequality: for arbitrarily chosen initial points x ⁰, y ⁰ K, u ⁰ T(y ⁰) and v ⁰ T(x ⁰), we have u ^k + x ^k+1 – y ^k , x – x ^k+1 0, x K, for u ^k T(y ^k ) and for k 0where v ^k + y ^k – x ^k , x – y ^k 0, x K and for v ^k T(x ^k ).     

Some minimax problems of vector-valued functions

The concepts of cone extreme points, cone saddle points, and cone saddle values are introduced. The relation of inclusion among the sets mini _xX max _yY f(x, y), maxi _yY min _xX f(x, y), and the set of all weak cone saddle values is investigated in the case where the image space ⁿ off is ordered by an acute convex cone.The author is grateful for the useful suggestions and comments given by Prof. K. Tanaka, Niigata University, Niigata, Japan.The author would like to thank the referees for their valuable suggestions on the original draft.     

Hybrid misclassification minimization

Given two finite point setsA andB in then-dimensional real spaceR ⁿ , we consider the NP-complete problem of minimizing the number of misclassified points by a plane attempting to divideR ⁿ into two halfspaces such that each open halfspace contains points mostly ofA orB. This problem is equivalent to determining a plane {x | x ^T w=} that maximizes the number of pointsx A satisfying inx ^T w>, plus the number of pointsx B satisfyingx ^T w<. A simple but fast algorithm is proposed that alternates between (i) minimizing the number of misclassified points by translation of the separating plane, and (ii) a rotation of the plane so that it minimizes a weighted average sum of the distances of the misclassified points to the separating plane. Existence of a global solution to an underlying hybrid minimization problem is established. Computational comparison with a parametric approach to solve the NP-complete problem indicates that our approach is considerably faster and appears to generalize better as determined by tenfold cross-validation.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Implicitly defined optimization problems

This paper considers the solution of the problem: inff[y, x(y)] s.t.y [y, x(y)] E ^k , wherex(y) solves: minF(x, y) s.t.x R(x, y) E ⁿ . In order to obtain local solutions, a first-order algorithm, which uses {dx(y)/dy} for solving a special case of the implicitly definedy-problem, is given. The derivative is obtained from {dx(y, r)/dy}, wherer is a penalty function parameter and {x(y, r)} are approximations to the solution of thex-problem given by a sequential minimization algorithm. Conditions are stated under whichx(y, r) and {dx(y, r)/dy} exist. The computation of {dx(y, r)/dy} requires the availability of _y F(x, y) and the partial derivatives of the other functions defining the setR(x, y) with respect to the parametersy.Research sponsored by National Science Foundation Grant ECS-8709795 and Office of Naval Research Contract N00014-89-J-1537. We thank the referees for constructive comments on an earlier version of this paper.     

Rectangular convexity of convex domains of constant width

An E R ² is r-convex if for every x, y E there exists a closed rectangle R such that x, y R and R E. Several results about r-convexity appeared in [1]. Its authors formulated a conjecture about conditions for a compact, convex set in R ² to be r-convex. We prove this conjecture in the case of convex domains of constant width.     

Infinitely constrained optimization problems

A generalized cutting-plane algorithm designed to solve problems of the form min{f(x) :x X andg(x,y) 0 for ally Y} is described. Convergence is established in the general case (f,g continuous,X andY compact). Constraint dropping is allowed in a special case [f,g(·,y) convex functions,X a convex set]. Applications are made to a variety of max-min problems. Computational considerations are discussed.Dr. Falk's research was supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under AFOSR Contract No. 73–2504.     

Outer approximation algorithm for nondifferentiable optimization problems

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ⁿ can be expressed as minimizing max{g(x, y)|y X}, whereg is a support function forf[f(x) g(x, y), for ally X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.This research was supported by the Science and Engineering Research Council, UK, and by the National Science Foundation under Grant No. ECS-79-13148.     

Line search by curve fitting in minimization algorithms

Summary Consider an unconstrained minimization of an uniformly convex functionf(z). Let be an algorithm that, for solving it constructs a sequence {z _i} withz _i+1 =z _i + ⁽ⁱ⁾ h _i ,h _i R ⁿ , ⁽ⁱ⁾ R ⁼ and –h _i ^T f(z _i ) > 0. For any algorithm that converges linearly and that uses parabolic or cubic interpolations for the line search, upper bounds on the number of function evaluations needed to approximate the minimum off(z) within a given accuracy, are calculated. The obtained results allow to compare the line search procedure under investigation.     

A maximization method for a class of quasiconcave programs

An implementable linearized method of centers is presented for solving a class of quasiconcave programs of the form (P): maximizef ⁰(x), subject tox B andf ⁱ (x)0, for everyi{1, ...,m}, whereB is a convex polyhedral subset ofR ⁿ (Euclideann-space). Each problem function is a continuous quasiconcave function fromR ⁿ intoR ¹. Also, it is assumed that the feasible region is bounded and there existsx B such thatf _i (x) for everyi {1, ...,m}. For a broad class of continuous quasiconcave problem functions, which may be nonsmooth, it is shown that the method produces a sequence of feasible points whose limit points are optimal for Problem (P). For many programs, no line searches are required. Additionally, the method is equipped with a constraint dropping devise.The author wishes to thank a referee for suggesting the use of generalized gradients and a second referee whose detailed informative comments have enhanced the paper.This work was done while the author was in the Department of Mathematical Sciences at the University of Delaware.     

Polynomials with two values

This paper investigates the minimal degree of polynomialsfR[x] that take exactly two values on a given range of integers {0,...n}. We show that thegap, defined asn-deg(f), isO(n ⁵⁴⁸). The maximal gap forn128 is 3. As an application, we obtain a bound on the Fourier degree of symmetric Boolean functions.     

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     

Projectivities in Moufang-Klingenberg planes

Let = = (,,) be a Moufang-Klingenberg plane coordinatized by a local alternative ring R. We define the projectivities of a line g in geometrically as products of perspectivities. It is shown that under certain conditions the group of projectivities of g is generated by the algebraically defined permutations xx+t (tR), xcx (cR a unit), xx ^–.     

D'Alembert's functional equation on restricted domains

Summary In the class of functionalsf:X , whereX is an inner product space with dimX 3, we study the D'Alembert functional equationf(x + y) + f(x – y) = 2f(x)f(y) (1) on the restricted domainsX ₁ = {(x, y) X ²/x, y = 0} andX ₂ = {(x, y) X ²/x = y}. In this paper we prove that the equation (1) restricted toX ₁ is not equivalent to (1) on the whole spaceX. We also succeed in characterizing all common solutions if we add the conditionf(2x) = 2f²(x) – 1. Using this result, we prove the equivalence between (1) restricted toX ₂ and (1) on the whole spaceX. This research follows similar previous studies concerning the additive, exponential and quadratic functional equations.