A decomposition-dualization approach for solving constrained convex minimization problems with applications to discretized obstacle problems

Summary In this paper, we shall be concerned with the solution of constrained convex minimization problems. The constrained convex minimization problems are proposed to be transformable into a convex-additively decomposed and almost separable form, e.g. by decomposition of the objective functional and the restrictions. Unconstrained dual problems are generated by using Fenchel-Rockafellar duality. This decomposition-dualization concept has the advantage that the conjugate functionals occuring in the derived dual problem are easily computable. Moreover, the minimum point of the primal constrained convex minimization problem can be obtained from any maximum point of the corresponding dual unconstrained concave problem via explicit return-formulas. In quadratic programming the decomposition-dualization approach considered here becomes applicable if the quadratic part of the objective functional is generated byH-matrices. Numerical tests for solving obstacle problems in ¹ discretized by using piecewise quadratic finite elements and in ² by using the five-point difference approximation are presented.     

A Geometric Programming Framework for Univariate Cubic L 1 Smoothing Splines

Univariate cubic L ₁ smoothing splines are capable of providing shape-preserving C ¹-smooth approximation of multi-scale data. The minimization principle for univariate cubic L ₁ smoothing splines results in a nondifferentiable convex optimization problem that, for theoretical treatment and algorithm design, can be formulated as a generalized geometric program. In this framework, a geometric dual with a linear objective function over a convex feasible domain is derived, and a linear system for dual to primal conversion is established. Numerical examples are given to illustrate this approach. Sensitivity analysis for data with uncertainty is presented. This work is supported by research grant #DAAG55-98-D-0003 of the Army Research Office, USA.     

Canonical dual least square method for solving general nonlinear systems of quadratic equations

This paper presents a canonical dual approach for solving general nonlinear algebraic systems. By using least square method, the nonlinear system of m-quadratic equations in n-dimensional space is first formulated as a nonconvex optimization problem. We then proved that, by the canonical duality theory developed by the second author, this nonconvex problem is equivalent to a concave maximization problem in ℝ ^m , which can be solved easily by well-developed convex optimization techniques. Both existence and uniqueness of global optimal solutions are discussed, and several illustrative examples are presented.     

Least Squares Convex-Concave Data Smoothing

We consider n noisy measurements of a smooth (unknown) function, which suggest that the graph of the function consists of one convex and one concave section. Due to the noise the sequence of the second divided differences of the data exhibits more sign changes than those expected in the second derivative of the underlying function. We address the problem of smoothing the data so as to minimize the sum of squares of residuals subject to the condition that the sequence of successive second divided differences of the smoothed values changes sign at most once. It is a nonlinear problem, since the position of the sign change is also an unknown of the optimization process. We state a characterization theorem, which shows that the smoothed values can be derived by at most 2n – 2 quadratic programming calculations to subranges of data. Then, we develop an algorithm that solves the problem in about O(n ²) computer operations by employing several techniques, including B-splines, the use of active sets, quadratic programming and updating methods. A Fortran program has been written and some of its numerical results are presented. Applications of the smoothing technique may be found in scientific, economic and engineering calculations, when a potential shape for the underlying function is an S-curve. Generally, the smoothing calculation may arise from processes that show initially increasing and then decreasing rates of change.     

Classifying convex extremum problems over linear topologies having separation properties

It is shown that any convex or concave extremum problem possesses a subsidiary extremum problem which has certain homogeneous properties. Analogous to the given problem, the “homogenized” extremum problem seeks the minimum of a convex function or the maximum of a concave function over a convex domain. By using homogenized extremum problems, new relationships are developed between any given convex extremum problem (P) and a concave extremum problem (P¹) (also having a convex domain), called the “dual” problem of (P). This is achieved by combining all possibilities in tabular form of (1) the values of the extremum functions and (2) the nature of the convex domains including perturbations of all problems (P), (P¹), and each of their respective homogenized extremum problems.This detailed and refined classification is contrasted to the relationships obtainable by combining only the possible values of the extremum functions of the problems (P) and (P¹) and the possible limiting values of these functions stemming from perturbations of the convex constraint domains of (P) and (P¹), respectively.The extremum problems in this paper and classification results are set forth in real topologically paired vector spaces having the Hahn-Banach separation property.     

Dual gauge programs,with applications to quadratic programming and the minimum-norm problem

A gauge functionf(·) is a nonnegative convex function that is positively homogeneous and satisfiesf(0)=0. Norms and pseudonorms are specific instances of a gauge function. This paper presents a gauge duality theory for a gauge program, which is the problem of minimizing the value of a gauge functionf(·) over a convex set. The gauge dual program is also a gauge program, unlike the standard Lagrange dual. We present sufficient conditions onf(·) that ensure the existence of optimal solutions to the gauge program and its dual, with no duality gap. These sufficient conditions are relatively weak and are easy to verify, and are independent of any qualifications on the constraints. The theory is applied to a class of convex quadratic programs, and to the minimuml _p norm problem. The gauge dual program is shown to provide a smaller duality than the standard dual, in a certain sense discussed in the text.     

On Optimization over the Efficient Set in Linear Multicriteria Programming

The efficient set of a linear multicriteria programming problem can be represented by a reverse convex constraint of the form g(z)≤0, where g is a concave function. Consequently, the problem of optimizing some real function over the efficient set belongs to an important problem class of global optimization called reverse convex programming. Since the concave function used in the literature is only defined on some set containing the feasible set of the underlying multicriteria programming problem, most global optimization techniques for handling this kind of reverse convex constraint cannot be applied. The main purpose of our article is to present a method for overcoming this disadvantage. We construct a concave function which is finitely defined on the whole space and can be considered as an extension of the existing function. Different forms of the linear multicriteria programming problem are discussed, including the minimum maximal flow problem as an example. The research was partly done while the third author was visiting the Department of Mathematics, University of Trier with the support by the Alexander von Humboldt Foundation. He thanks the university as well as the foundation.     

Global optimal solutions to a class of quadrinomial minimization problems with one quadratic constraint

This paper studies the canonical duality theory for solving a class of quadrinomial minimization problems subject to one general quadratic constraint. It is shown that the nonconvex primal problem in \mathbb Rⁿ{\mathbb {R}^n} can be converted into a concave maximization dual problem over a convex set in \mathbb R²{\mathbb {R}^2}, such that the problem can be solved more efficiently. The existence and uniqueness theorems of global minimizers are provided using the triality theory. Examples are given to illustrate the results obtained.     

On the equipartition of plane convex bodies and convex polygons

In this paper we consider the problem of partitioning a plane compact convex body into equal-area parts, i.e., an equipartition, by means of chords. We prove two basic results that hold with some specific exceptions: (a) When chords are pairwise non-crossing, the dual tree of the partition has to be a path, (b) A convex n-gon admits no equipartition produced by more than n chords having a common interior point.     

Discrete Convexity

In the paper, we explain what subsets of the lattice ℤ ⁿ and what functions on the lattice ℤ ⁿ could be called convex. The basis of our theory is the following three main postulates of classical convex analysis: concave functions are closed under sums; they are also closed under convolutions; and the superdifferential of a concave function is nonempty at each point of the domain. Interesting (and even dual) classes of discrete concave functions arise if we require either the existence of superdifferentials and closeness under convolutions or the existence of superdifferentials and closeness under sums. The corresponding classes of convex sets are obtained as the affinity domains of such discretely concave functions. The classes of the first type are closed under (Minkowski) sums, and the classes of the second type are closed under intersections. In both classes, the separation theorem holds true. Unimodular sets play an important role in the classification of such classes. The so-called polymatroidal discretely concave functions, most interesting for applications, are related to the unimodular system . Such functions naturally appear in mathematical economics, in Gelfand-Tzetlin patterns, play an important role for solution of the Horn problem, for describing submodule invariants over discrete valuation rings, and so on. Bibliography: 6 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 312, 2004, pp. 86–93.     

A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC¹${\text{SC}}^1$) convex programming problem with fewer variables than the original one. The Karush–Kuhn–Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush–Kuhn–Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems.     

Canonical dual approach to solving the maximum cut problem

This paper presents a canonical dual approach for finding either an optimal or approximate solution to the maximum cut problem (MAX CUT). We show that, by introducing a linear perturbation term to the objective function, the maximum cut problem is perturbed to have a dual problem which is a concave maximization problem over a convex feasible domain under certain conditions. Consequently, some global optimality conditions are derived for finding an optimal or approximate solution. A gradient decent algorithm is proposed for this purpose and computational examples are provided to illustrate the proposed approach.     

Pseudo duality in mathematical programming: Unconstrained problems and problems with equality constraints

In this work non-convex programs are analyzed via Legendre transform. The first part includes definitions and the classification of programs that can be handled by the transformation. It is shown that differentiable functions that are represented as a sum of strictly concave and convex functions belong to this class. Conditions under which a function may have such representation are given. Pseudo duality is defined and the pseudo duality theorem for non linear programs with equality constraints is proved.The techniques described are constructive ones, and they enable tocalculate explicitly a pseudo dual once the primal program is given. Several examples are included. In the convex case these techniques enable the explicit calculation of the dual even in cases where direct calculation was not possible.     

Duality in nonlinear fractional programming

Summary The purpose of the present paper is to introduce, on the lines similar to that ofWolfe [1961], a dual program to a nonlinear fractional program in which the objective function, being the ratio of a convex function to a strictly positive linear function, is a special type of pseudo-convex function and the constraint set is a convex set constrained by convex functions in the form of inequalities. The main results proved are, (i) Weak duality theorem, (ii)Wolfe's (Direct) duality theorem and (iii)Mangasarian's Strict Converse duality theorem.Huard's [1963] andHanson's [1961] converse duality theorems for the present problem have just been stated because they can be obtained as a special case ofMangasarian's theorem [1969, p. 157]. The other important discussion included is to show that the dual program introduced in the present paper can also be obtained throughDinkelbach's Parametric Replacement [1967] of a nonlinear fractional program. Lastly, duality in convex programming is shown to be a special case of the present problem.The present research is partially supported by National Research Council of Canada.     

Canonical Dual Transformation Method and Generalized Triality Theory in Nonsmooth Global Optimization*

This paper presents, within a unified framework, a potentially powerful canonical dual transformation method and associated generalized duality theory in nonsmooth global optimization. It is shown that by the use of this method, many nonsmooth/nonconvex constrained primal problems in ⁿ can be reformulated into certain smooth/convex unconstrained dual problems in ^m with m n and without duality gap, and some NP-hard concave minimization problems can be transformed into unconstrained convex minimization dual problems. The extended Lagrange duality principles proposed recently in finite deformation theory are generalized suitable for solving a large class of nonconvex and nonsmooth problems. The very interesting generalized triality theory can be used to establish nice theoretical results and to develop efficient alternative algorithms for robust computations.     

Semidefinite Relaxations of Fractional Programs via Novel Convexification Techniques

In a recent work, we introduced the concept of convex extensions for lower semi-continuous functions and studied their properties. In this work, we present new techniques for constructing convex and concave envelopes of nonlinear functions using the theory of convex extensions. In particular, we develop the convex envelope and concave envelope of z=x/y over a hypercube. We show that the convex envelope is strictly tighter than previously known convex underestimators of x/y. We then propose a new relaxation technique for fractional programs which includes the derived envelopes. The resulting relaxation is shown to be a semidefinite program. Finally, we derive the convex envelope for a class of functions of the type f(x,y) over a hypercube under the assumption that f is concave in x and convex in y.     

Finite termination of a dual Newton method for convex best <Emphasis Type="Italic">C</Emphasis><Superscript><Emphasis Type="Italic">1</Emphasis></Superscript> interpolation and smoothing

Summary. Given the data (x _i ,y _i )², which are in convex position, the problem is to choose the convex best C ¹ interpolant with the smallest mean square second derivative among all admissible cubic C ¹ -splines on the grid. This problem can be efficiently solved by its dual program, developed by Schmdit and his collaborators in a series of papers. The Newton method remains the core of their suggested numerical scheme. It is observed through numerical experiments that the method terminates in a small number of steps and its total computational complexity is only of O(n). The purpose of this paper is to establish theoretical justification for the Newton method. In fact, we are able to prove its finite termination under a mild condition, and on the other hand, we illustrate that the Newton method may fail if the condition is violated, consistent with what is numerically observed for the Newton method. Corresponding results are also obtained for convex smoothing. Mathematics Subject Classification (2000):41A29, 65D15, 49J52, 90C25The work was supported by the Australian Research Council for the first author and by the Hong Kong Research Grant Council for the second author.