Hidden convexity in some nonconvex quadratically constrained quadratic programming

We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs. This author's work was partially supported by GIF, the German-Israeli Foundation for Scientific Research and Development and by the Binational Science Foundation. This author's work was partially supported by National Science Foundation Grants DMS-9201297 and DMS-9401871.     

On the convergence of the coordinate descent method for convex differentiable minimization

The coordinate descent method enjoys a long history in convex differentiable minimization. Surprisingly, very little is known about the convergence of the iterates generated by this method. Convergence typically requires restrictive assumptions such as that the cost function has bounded level sets and is in some sense strictly convex. In a recent work, Luo and Tseng showed that the iterates are convergent for the symmetric monotone linear complementarity problem, for which the cost function is convex quadratic, but not necessarily strictly convex, and does not necessarily have bounded level sets. In this paper, we extend these results to problems for which the cost function is the composition of an affine mapping with a strictly convex function which is twice differentiable in its effective domain. In addition, we show that the convergence is at least linear. As a consequence of this result, we obtain, for the first time, that the dual iterates generated by a number of existing methods for matrix balancing and entropy optimization are linearly convergent.This work was partially supported by the U.S. Army Research Office, Contract No. DAAL03-86-K-0171, by the National Science Foundation, Grant No. ECS-8519058, and by the Science and Engineering Research Board of McMaster University.     

Convex composite minimization withC 1,1 functions

In this paper, we present second-order optimality conditions for convex composite minimization problems in which the objective function is a composition of a finite-valued or a nonfinite-valued lower semicontinuous convex function and aC ^1,1 function. The results provide optimality conditions for composite problems under reduced differentiability requirements.This paper is a revised version of the Departmental Preliminary Report AM92/32, School of Mathematics, University of New South Wales, Kensington, NSW, Australia.Research of this author was supported in part by an Australian Research Council Grant.     

Convex composite multi-objective nonsmooth programming

This paper examines nonsmooth constrained multi-objective optimization problems where the objective function and the constraints are compositions of convex functions, and locally Lipschitz and Gâteaux differentiable functions. Lagrangian necessary conditions, and new sufficient optimality conditions for efficient and properly efficient solutions are presented. Multi-objective duality results are given for convex composite problems which are not necessarily convex programming problems. Applications of the results to new and some special classes of nonlinear programming problems are discussed. A scalarization result and a characterization of the set of all properly efficient solutions for convex composite problems are also discussed under appropriate conditions.This research was partially supported by the Australian Research Council grant A68930162.This author wishes to acknowledge the financial support of the Australian Research Council.     

On the need for special purpose algorithms for minimax eigenvalue problems

It has been recently reported that minimax eigenvalue problems can be formulated as nonlinear optimization problems involving smooth objective and constraint functions. This result seems very appealing since minimax eigenvalue problems are known to be typically nondifferentiable. In this paper, we show, however, that general purpose nonlinear optimization algorithms usually fail to find a solution to these smooth problems even in the simple case of minimization of the maximum eigenvalue of an affine family of symmetric matrices, a convex problem for which efficient algorithms are available.This work was supported in part by NSF Engineering Research Centers Program No. NSFD-CDR-88-03012 and NSF Grant DMC-84-20740. The author wishes to thank Drs. M. K. H. Fan and A. L. Tits for their many useful suggestions.     

On the Characterization of Quadratic Splines

A quadratic spline is a differentiable piecewise quadratic function. Many problems in the numerical analysis and optimization literature can be reformulated as unconstrained minimizations of quadratic splines. However, only special cases of quadratic splines have been studied in the existing literature and algorithms have been developed on a case-by-case basis. There lacks an analytical representation of a general or even convex quadratic spline. The current paper fills this gap by providing an analytical representation of a general quadratic spline. Furthermore, for a convex quadratic spline, it is shown that the representation can be refined in the neighborhood of a nondegenerate point and a set of nondegenerate minimizers. Based on these characterizations, many existing algorithms for specific convex quadratic splines are also finitely convergent for a general convex quadratic spline. Finally, we study the relationship between the convexity of a quadratic spline function and the monotonicity of the corresponding linear complementarity problem. It is shown that, although both conditions lead to easy solvability of the problem, they are different in general.This project was initiated when the first author was visiting the Technical University of Denmark and Erasmus University. The visit was partially funded by the Danish Natural Science Research Council.     

Minimizing pseudoconvex functions on convex compact sets

An algorithm is presented which minimizes continuously differentiable pseudoconvex functions on convex compact sets which are characterized by their support functions. If the function can be minimized exactly on affine sets in a finite number of operations and the constraint set is a polytope, the algorithm has finite convergence. Numerical results are reported which illustrate the performance of the algorithm when applied to a specific search direction problem. The algorithm differs from existing algorithms in that it has proven convergence when applied to any convex compact set, and not just polytopal sets.This research was supported by the National Science Foundation Grant ECS-85-17362, the Air Force Office Scientific Research Grant 86-0116, the Office of Naval Research Contract N00014-86-K-0295, the California State MICRO program, and the Semiconductor Research Corporation Contract SRC-82-11-008.     

On games corresponding to sequencing situations with ready times

This paper considers the special class of cooperative sequencing games that arise from one-machine sequencing situations in which all jobs have equal processing times and the ready time of each job is a multiple of the processing time.By establishing relations between optimal orders of subcoalitions, it is shown that each sequencing game within this class is convex.This author is financially supported by the Dutch Organization for Scientific Research (NWO).     

Path-following proximal approach for solving Ill-posed convex semi-infinite programming problems

For a class of ill-posed, convex semi-infinite programming problems, a regularized path-following strategy is developed. This approach consists in a coordinated application of adaptive discretization and prox-regularization procedures combined with a penalty method. At each iteration, only an approximate minimum of a strongly convex differentiable function has to be calculated, and this can be done by any fast-convergent algorithm. The use of prox-regularization ensures the convergence of the iterates to some solution of the original problem. Due to regularization, an efficient deleting rule is applicable, which excludes an essential part of the constraints in the discretized problems.This research was supported by the German Research Society (DFG).The authors are grateful to the anonymous referees for their valuable comments.     

Equivalence of Equilibrium Problems and Least Element Problems

In this paper, we introduce the concept of feasible set for an equilibrium problem with a convex cone and generalize the notion of a Z-function for bifunctions. Under suitable assumptions, we derive some equivalence results of equilibrium problems, least element problems, and nonlinear programming problems. The results presented extend some results of [Riddell, R.C.: Equivalence of nonlinear complementarity problems and least element problems in Banach lattices. Math. Oper. Res. 6, 462–474 (1981)] to equilibrium problems. This work was supported by the National Natural Science Foundation of China (10671135) and Specialized Research Fund for the Doctoral Program of Higher Education (20060610005) and the Educational Science Foundation of Chongqing (KJ051307).     

Infinite-dimensional convex programming with applications to constrained approximation

In this paper, existence and characterization of solutions and duality aspects of infinite-dimensional convex programming problems are examined. Applications of the results to constrained approximation problems are considered. Various duality properties for constrained interpolation problems over convex sets are established under general regularity conditions. The regularity conditions are shown to hold for many constrained interpolation problems. Characterizations of local proximinal sets and the set of best approximations are also given in normed linear spaces.The author is grateful to the referee for helpful suggestions which have contributed to the final preparation of this paper. This research was partially supported by Grant A68930162 from the Australian Research Council.     

On fencing problems

Fencing problems regard the bisection of a convex body in a way that some geometric measures are optimized. We introduce the notion of relative diameter and study bisections of centrally symmetric planar convex bodies, bisections by straight line cuts in general planar convex bodies and also bisections by hyperplane cuts for convex bodies in higher dimensions. In the planar case we obtain the best possible lower bound for the ratio between the relative diameter and the area.     

Iterative linear programming solution of convex programs

An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

REFE-Acceptable Mappings: Necessary and Sufficient Condition for the Nonexistence of a Regular Exceptional Family of Elements

By considering the notion of regular exceptional family of elements (REFE), we define the class of REFE-acceptable mappings. By definition, a complementarity problem on a Hilbert space defined by a REFE-acceptable mapping and a closed convex cone has either a solution or a REFE. We present several classes of REFE-acceptable mappings. For this, neither the topological degree nor the Leray-Schauder alternative is necessary. By using the concept of REFE-acceptable mappings, we present necessary and sufficient conditions for the nonexistence of regular exceptional family of elements. These conditions are used for generating several existence theorems and existence and uniqueness theorems for complementarity problems. The authors are grateful to Prof. A.B. Németh for many helpful conversations. The research of S.Z. Németh was supported by Hungarian Research Grants OTKA T043276 and OTKA K60480.     

Total variation and Cheeger sets in Gauss space

The aim of this paper is to study the isoperimetric problem with fixed volume inside convex sets and other related geometric variational problems in the Gauss space, in both the finite and infinite dimensional case. We first study the finite dimensional case, proving the existence of a maximal Cheeger set which is convex inside any bounded convex set. We also prove the uniqueness and convexity of solutions of the isoperimetric problem with fixed volume inside any convex set. Then we extend these results in the context of the abstract Wiener space, and for that we study the total variation denoising problem in this context.     

A characterization of the Euclidean ball in terms of concurrent sections of constant width

We prove that the Euclidean ball is the unique convex body with the property that all its sections through a fixed point are convex bodies of constant width. Furthermore, we characterize those convex bodies which are sections of convex bodies of constant width.Research supported by the Alexander von Humboldt-Foundation.     

Infinite-dimensional quadratic optimization: Interior-point methods and control applications

An infinite-dimensional convex optimization problem with the linear-quadratic cost function and linear-quadratic constraints is considered. We generalize the interior-point techniques of Nesterov-Nemirovsky to this infinite-dimensional situation. The complexity estimates obtained are similar to finite-dimensional ones. We apply our results to the linear-quadratic control problem with quadratic constraints. It is shown that for this problem the Newton step is basically reduced to the standard LQ problem. This research was supported in part by the Cooperative Research Centre for Robust and Adaptive Systems while the first author visited the Australian National University and by NSF Grant DMS 94-23279.     

Efficient estimates of the solutions of perturbed control problems

In this paper, we obtain estimates of the solutions for a sequence of strongly convex extremal problems. As applications of our abstract results, we consider optimal control problems with various types of perturbations. We estimate the solutions of problems with perturbations in the state equation and in the control constraining set. A singularly perturbed problem and a problem with perturbed time delay parameter are studied.     

A Variational Proof of Alexandrov’s Convex Cap Theorem

We give a variational proof of the existence and uniqueness of a convex cap with the given metric on the boundary. The proof uses the concavity of the total scalar curvature functional (also called Hilbert-Einstein functional) on the space of generalized convex caps. As a by-product, we prove that generalized convex caps with the fixed metric on the boundary are globally rigid, that is uniquely determined by their curvatures. Research for this article was supported by the DFG Research Unit 565 “Polyhedral Surfaces”.