Universal duality in conic convex optimization

Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +∞ and −∞. In contrast, for optimization problems over nonpolyhedral convex cones, a nonzero duality gap can exist when either the primal or the dual is feasible. For a pair of dual conic convex programs, we provide simple conditions on the ``constraint matrices' and cone under which the duality gap is zero for every choice of linear objective function and constraint right-hand side. We refer to this property as ``universal duality'. Our conditions possess the following properties: (i) they are necessary and sufficient, in the sense that if (and only if) they do not hold, the duality gap is nonzero for some linear objective function and constraint right-hand side; (ii) they are metrically and topologically generic; and (iii) they can be verified by solving a single conic convex program. We relate to universal duality the fact that the feasible sets of a primal convex program and its dual cannot both be bounded, unless they are both empty. Finally we illustrate our theory on a class of semidefinite programs that appear in control theory applications. This work was supported by a fellowship at the University of Maryland, in addition to NSF grants DEMO-9813057, DMI0422931, CUR0204084, and DoE grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

Minimal conic quadratic reformulations and an optimization model

In this paper, we consider a particular form of inequalities which involves product of multiple variables with rational exponents. These inequalities can equivalently be represented by a number of conic quadratic forms called cone constraints. We propose an integer programming model and a heuristic algorithm to obtain the minimum number of cone constraints which equivalently represent the original inequality. The performance of the proposed algorithm and the computational effect of reformulations are numerically illustrated.     

A nonmonotone trust-region method of conic model for unconstrained optimization

In this paper, we present a nonmonotone trust-region method of conic model for unconstrained optimization. The new method combines a new trust-region subproblem of conic model proposed in [Y. Ji, S.J. Qu, Y.J. Wang, H.M. Li, A conic trust-region method for optimization with nonlinear equality and inequality 4 constrains via active-set strategy, Appl. Math. Comput. 183 (2006) 217–231] with a nonmonotone technique for solving unconstrained optimization. The local and global convergence properties are proved under reasonable assumptions. Numerical experiments are conducted to compare this method with the method of [Y. Ji, S.J. Qu, Y.J. Wang, H.M. Li, A conic trust-region method for optimization with nonlinear equality and inequality 4 constrains via active-set strategy, Appl. Math. Comput. 183 (2006) 217–231].     

A new nonmonotone trust-region method of conic model for solving unconstrained optimization

In this paper, we present a new nonmonotone trust-region method of conic model for solving unconstrained optimization problems. Both the local and global convergence properties are analyzed under reasonable assumptions. Numerical experiments are conducted to compare this method with some existed ones which indicate that the new method is efficient.     

A nonmonotone adaptive trust region method for unconstrained optimization based on conic model

In this paper, we present a nonmonotone adaptive trust region method for unconstrained optimization based on conic model. The new method combines nonmonotone technique and a new way to determine trust region radius at each iteration. The local and global convergence properties are proved under reasonable assumptions. Numerical experiments show that our algorithm is effective.     

The complementary unboundedness of dual feasible solution sets in convex programming

F.E. Clark has shown that if at least one of the feasible solution sets for a pair of dual linear programming problems is nonempty then at least one of them is both nonempty and unbounded. Subsequently, M. Avriel and A.C. Williams have obtained the same result in the more general context of (prototype posynomial) geometric programming. In this paper we show that the same result is actually false in the even more general context of convex programming — unless a certain regularity condition is satisfied.We also show that the regularity condition is so weak that it is automatically satisfied in linear programming (prototype posynomial) geometric programming, quadratic programming (with either linear or quadratic constraints),l _p -regression analysis, optimal location, roadway network analysis, and chemical equilibrium analysis. Moreover, we develop an equivalent regularity condition for each of the usual formulations of duality.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-73-2516.     

On the degree and separability of nonconvexity and applications to optimization problems

We study qualitative indications for d.c. representations of closed sets in and functions on Hilbert spaces. The first indication is an index of nonconvexity which can be regarded as a measure for the degree of nonconvexity. We show that a closed set is weakly closed if this indication is finite. Using this result we can prove the solvability of nonconvex minimization problems. By duality a minimization problem on a feasible set in which this indication is low, can be reduced to a quasi-concave minimization over a convex set in a low-dimensional space. The second indication is the separability which can be incorporated in solving dual problems. Both the index of nonconvexity and the separability can be characteristics to “good” d.c. representations. For practical computation we present a notion of clouds which enables us to obtain a good d.c. representation for a class of nonconvex sets. Using a generalized Caratheodory’s theorem we present various applications of clouds.     

The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

A dynamic system model for solving convex nonlinear optimization problems

This paper proposes a feedback neural network model for solving convex nonlinear programming (CNLP) problems. Under the condition that the objective function is convex and all constraint functions are strictly convex or that the objective function is strictly convex and the constraint function is convex, the proposed neural network is proved to be stable in the sense of Lyapunov and globally convergent to an exact optimal solution of the original problem. The validity and transient behavior of the neural network are demonstrated by using some examples.     

On the generic properties of convex optimization problems in conic form

We prove that strict complementarity, primal and dual nondegeneracy of optimal solutions of convex optimization problems in conic form are generic properties. In this paper, we say generic to mean that the set of data possessing the desired property (or properties) has strictly larger Hausdorff dimension than the set of data that does not. Our proof is elementary and it employs an important result due to Larman [7] on the boundary structure of convex bodies. Received: September 1997 / Accepted: May 2000?Published online November 17, 2000     

On duality for weakly minimized vector valued optimization problems

An ordering that accords with the definition of a weak minimum is used to establish quasiduality, duality and converse duality theorems for optimization problems where the objective function takes values in real normed spaces of any dimension.     

One-sided derivatives for the value function in convex parametric programming

In [9] it is shown that the one-sided derivatives of parametric linear semi-infinite programs can be expressed in terms of one-sided cluster points of solutions and Lagrange-multipliers of the perturbed problem.

In this paper convex programs on Banach-spaces are studied. We generalize the results in [9] to this case. The analysis is based on convex duality theory [2].     

Lipschitz behavior of convex semi-infinite optimization problems: a variational approach

In this paper we make use of subdifferential calculus and other variational techniques, traced out from [Ioffe, A.D.: Metric regularity and subdifferential calculus. Uspekhi Mat. Nauk 55, 3(333), 103–162; Engligh translation Math. Surveys 55, 501–558 (2000); Ioffe, A.D.: On rubustness of the regularity property of maps. Control cybernet 32, 543–554 (2003)], to derive different expressions for the Lipschitz modulus of the optimal set mapping of canonically perturbed convex semi-infinite optimization problems. In order to apply this background for obtaining the modulus of metric regularity of the associated inverse multifunction, we have to analyze the stable behavior of this inverse mapping. In our semi-infinite framework this analysis entails some specific technical difficulties. We also provide a new expression of a global variational nature for the referred regularity modulus.      

Theorems of the alternative for conic integer programming

Farkas’ Lemma is a foundational result in linear programming, with implications in duality, optimality conditions, and stochastic and bilevel programming. Its generalizations are known as theorems of the alternative. There exist theorems of the alternative for integer programming and conic programming. We present theorems of the alternative for conic integer programming. We provide a nested procedure to construct a function that characterizes feasibility over right-hand sides and can determine which statement in a theorem of the alternative holds.     

On boundedness of (quasi-)convex integer optimization problems

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained integer optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or quasi-convex polynomial function over the feasible set contained in , and defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities. The conditions for boundedness are provided in the form of an implementable algorithm, terminating after a finite number of iterations, showing that for the considered class of functions, the integer programming problem with nonempty feasible region is unbounded if and only if the associated continuous optimization problem is unbounded. We also prove that for a broad class of objective functions (which in particular includes polynomials with integer coefficients), an optimal solution set of the constrained integer problem is nonempty over any subset of .     

On the Separation and Order Law of Cancellation for Bounded Sets

In this paper we introduce the separation law for convex sets. Moreover, we prove that for a locally convex topological vector space the order cancellation law and separation law are equivalent.     

Projective re-normalization for improving the behavior of a homogeneous conic linear system

In this paper we study the homogeneous conic system . We choose a point that serves as a normalizer and consider computational properties of the normalized system . We show that the computational complexity of solving F via an interior-point method depends only on the complexity value of the barrier for C and on the symmetry of the origin in the image set , where the symmetry of 0 in is

Duality for almost convex optimization problems via the perturbation approach

We deal with duality for almost convex finite dimensional optimization problems by means of the classical perturbation approach. To this aim some standard results from the convex analysis are extended to the case of almost convex sets and functions. The duality for some classes of primal-dual problems is derived as a special case of the general approach. The sufficient regularity conditions we need for guaranteeing strong duality are proved to be similar to the ones in the convex case. The research of the first and third authors was partially supported by DFG (German Research Foundation), project WA 922/1. The research of the second author was supported by the grant PN II, ID 523/2007.     

On the projected subgradient method for nonsmooth convex optimization in a Hilbert space

We consider the method for constrained convex optimization in a Hilbert space, consisting of a step in the direction opposite to an _k -subgradient of the objective at a current iterate, followed by an orthogonal projection onto the feasible set. The normalized stepsizes _k are exogenously given, satisfying _{k=0 k} = , _{k=0 k} ² < , and _k is chosen so that _{k k} for some > 0. We prove that the sequence generated in this way is weakly convergent to a minimizer if the problem has solutions, and is unbounded otherwise. Among the features of our convergence analysis, we mention that it covers the nonsmooth case, in the sense that we make no assumption of differentiability off, and much less of Lipschitz continuity of its gradient. Also, we prove weak convergence of the whole sequence, rather than just boundedness of the sequence and optimality of its weak accumulation points, thus improving over all previously known convergence results. We present also convergence rate results. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research of this author was partially supported by CNPq grant nos. 301280/86 and 300734/95-6.     

On a proximal point method for convex optimization in banach spaces

We analyze the behavior of a parallel proximal point method for solving convex optimization problems in reflexive Banach spaces. Similar algorithms were known to converge under the implicit assumption that the norm of the space is Hilbertian. We extend the area of applicability of the proximal point method to solving convex optimization problems in Banach spaces on which totally convex functions can be found. This includes the class of all smooth uniformly convex Banach spaces. Also, our convergence results leave more flexibility for the choice of the penalty function involved in the algorithm and, in this way, allow simplification of the computational procedure.