Multiobjective duality for convex ratios

In this paper we present a duality approach for a multiobjective fractional programming problem. The components of the vector objective function are particular ratios involving the square of a convex function and a positive concave function. Applying the Fenchel-Rockafellar duality theory for a scalar optimization problem associated to the multiobjective primal, a dual problem is derived. This scalar dual problem is formulated in terms of conjugate functions and its structure gives an idea about how to construct a multiobjective dual problem in a natural way. Weak and strong duality assertions are presented.     

Conjugate maps and duality in multiobjective optimization

This paper considers duality in convex vector optimization. A vector optimization problem requires one to find all the efficient points of the attainable value set for given multiple objective functions. Embedding the primal problem into a family of perturbed problems enables one to define a dual problem in terms of the conjugate map of the perturbed objective function. Every solution of the stable primal problem is associated with a certain solution of the dual problem, which is characterized as a subgradient of the perturbed efficient value map. This pair of solutions also provides a saddle point of the Lagrangian map.     

Ergodic,primal convergence in dual subgradient schemes for convex programming,II: the case of inconsistent primal problems

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.     

A New Self-Dual Embedding Method for Convex Programming

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.     

On the relations between different duals assigned to composed optimization problems

For an optimization problem with a composed objective function and composed constraint functions we determine, by means of the conjugacy approach based on the perturbation theory, some dual problems to it. The relations between the optimal objective values of these duals are studied. Moreover, sufficient conditions are given in order to achieve equality between the optimal objective values of the duals and strong duality between the primal and the dual problems, respectively. Finally, some special cases of this problem are presented.      

Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

Conjugate duality for multiobjective composed optimization problems

Given a multiobjective optimization problem with the components of the objective function as well as the constraint functions being composed convex functions, we introduce, by using the Fenchel-Moreau conjugate of the functions involved, a suitable dual problem. Under a standard constraint qualification and some convexity as well as monotonicity conditions we prove the existence of strong duality. Finally, some particular cases of this problem are presented.      

Duality of nonconvex optimization with positively homogeneous functions

We consider an optimization problem with positively homogeneous functions in its objective and constraint functions. Examples of such positively homogeneous functions include the absolute value function and the p-norm function, where p is a positive real number. The problem, which is not necessarily convex, extends the absolute value optimization proposed in Mangasarian (Comput Optim Appl 36:43–53, 2007). In this work, we propose a dual formulation that, differently from the Lagrangian dual approach, has a closed-form and some interesting properties. In particular, we discuss the relation between the Lagrangian duality and the one proposed here, and give some sufficient conditions under which these dual problems coincide. Finally, we show that some well-known problems, e.g., sum of norms optimization and the group Lasso-type optimization problems, can be reformulated as positively homogeneous optimization problems.     

Weak Fenchel and weak Fenchel-Lagrange conjugate duality for nonconvex scalar optimization problems

In this work, by using weak conjugate maps given in (Azimov and Gasimov, in Int J Appl Math 1:171–192, 1999), weak Fenchel conjugate dual problem, ${(D_F^w)}$ , and weak Fenchel Lagrange conjugate dual problem ${(D_{FL}^w)}$ are constructed. Necessary and sufficient conditions for strong duality for the ${(D_F^w)}$ , ${(D_{FL}^w)}$ and primal problem are given. Furthermore, relations among the optimal objective values of dual problem constructed by using Augmented Lagrangian in (Azimov and Gasimov, in Int J Appl Math 1:171–192, 1999), ${(D_F^w)}$ , ${(D_{FL}^w)}$ dual problems and primal problem are examined. Lastly, necessary and sufficient optimality conditions for the primal and the dual problems ${(D_F^w)}$ and ${(D_{FL}^w)}$ are established.     

Unboundedness in reverse convex and concave integer programming

In this paper we are concerned with the problem of unboundedness and existence of an optimal solution in reverse convex and concave integer optimization problems. In particular, we present necessary and sufficient conditions for existence of an upper bound for a convex objective function defined over the feasible region contained in ${\mathbb{Z}^n}$ . The conditions for boundedness are provided in a form of an implementable algorithm, showing that for the considered class of functions, the integer programming problem is unbounded if and only if the associated continuous problem is unbounded. We also address the problem of boundedness in the global optimization problem of maximizing a convex function over a set of integers contained in a convex and unbounded region. It is shown in the paper that in both types of integer programming problems, the objective function is either unbounded from above, or it attains its maximum at a feasible integer point.     

A distributed Douglas-Rachford splitting method for multi-block convex minimization problems

A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating direction method of multipliers (ADMM), the dual application of DRSM to the two-block convex minimization problem, in the sense that the subproblems can have larger opportunity of possessing closed-form solutions since they are unconstrained. In this paper, we further study along this way by considering the primal application of DRSM for the general case m≥3, i.e., we consider the multi-block separable convex minimization problem with linear constraints where the objective function is separable into m individual convex functions without coupled variables. The resulting method fully exploits the separable structure and enjoys decoupled subproblems which can be solved simultaneously. Both the exact and inexact versions of the new method are presented in a unified framework. Under mild conditions, we manage to prove the global convergence of the algorithm. Preliminary numerical experiments for extracting the background from corrupted surveillance video verify the encouraging efficiency of the new algorithm.     

L p -Norms, Log-Barriers and Cramer Transform in Optimization

We show that the Laplace approximation of a supremum by L ^p -norms has interesting consequences in optimization. For instance, the logarithmic barrier functions (LBF) of a primal convex problem P and its dual P ^* appear naturally when using this simple approximation technique for the value function g of P or its Legendre–Fenchel conjugate g ^*. In addition, minimizing the LBF of the dual P ^* is just evaluating the Cramer transform of the Laplace approximation of g. Finally, this technique permits to sometimes define an explicit dual problem P ^* in cases when the Legendre–Fenchel conjugate g ^* cannot be derived explicitly from its definition.     

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 .     

Saddle points and gap functions for vector equilibrium problems via conjugate duality in vector optimization

In this paper, two conjugate dual problems based on weak efficiency to a constrained vector optimization problem are introduced. Some inclusion relations between the dual objective mappings and the properties of the Lagrangian maps and their saddle points for primal problem are discussed. Gap functions for a vector equilibrium problem are established by using the weak and strong duality.     

Dual subgradient algorithms for large-scale nonsmooth learning problems

“Classical” First Order (FO) algorithms of convex optimization, such as Mirror Descent algorithm or Nesterov’s optimal algorithm of smooth convex optimization, are well known to have optimal (theoretical) complexity estimates which do not depend on the problem dimension. However, to attain the optimality, the domain of the problem should admit a “good proximal setup”. The latter essentially means that (1) the problem domain should satisfy certain geometric conditions of “favorable geometry”, and (2) the practical use of these methods is conditioned by our ability to compute at a moderate cost proximal transformation at each iteration. More often than not these two conditions are satisfied in optimization problems arising in computational learning, what explains why proximal type FO methods recently became methods of choice when solving various learning problems. Yet, they meet their limits in several important problems such as multi-task learning with large number of tasks, where the problem domain does not exhibit favorable geometry, and learning and matrix completion problems with nuclear norm constraint, when the numerical cost of computing proximal transformation becomes prohibitive in large-scale problems. We propose a novel approach to solving nonsmooth optimization problems arising in learning applications where Fenchel-type representation of the objective function is available. The approach is based on applying FO algorithms to the dual problem and using the accuracy certificates supplied by the method to recover the primal solution. While suboptimal in terms of accuracy guaranties, the proposed approach does not rely upon “good proximal setup” for the primal problem but requires the problem domain to admit a Linear Optimization oracle—the ability to efficiently maximize a linear form on the domain of the primal problem.     

Linearly constrained global minimization of functions with concave minorants

In this note, we show how a recent approach for solving linearly constrained multivariate Lipschitz optimization problems and corresponding systems of inequalities can be generalized to solve optimization problems where the objective function is only assumed to possess a concave minorant at each point. This class of functions includes not only Lipschitz functions and some generalizations, such as certain -convex functions and Hölder functions with exponent greater than one, but also all functions which can be expressed as differences of two convex functions (d.c. functions). Thus, in particular, a new approach is obtained for the important problem of minimizing a d.c. function over a polytope.     

Approximation methods for complex polynomial optimization

Complex polynomial optimization problems arise from real-life applications including radar code design, MIMO beamforming, and quantum mechanics. In this paper, we study complex polynomial optimization models where the objective function takes one of the following three forms: (1) multilinear; (2) homogeneous polynomial; (3) symmetric conjugate form. On the constraint side, the decision variables belong to one of the following three sets: (1) the \(m\) -th roots of complex unity; (2) the complex unity; (3) the Euclidean sphere. We first discuss the multilinear objective function. Polynomial-time approximation algorithms are proposed for such problems with assured worst-case performance ratios, which depend only on the dimensions of the model. Then we introduce complex homogenous polynomial functions and establish key linkages between complex multilinear forms and the complex polynomial functions. Approximation algorithms for the above-mentioned complex polynomial optimization models with worst-case performance ratios are presented. Numerical results are reported to illustrate the effectiveness of the proposed approximation algorithms.     

Variational Analysis on Local Sharp Minima via Exact Penalization

In this paper we study local sharp minima of the nonlinear programming problem via exact penalization. Utilizing generalized differentiation tools in variational analysis such as subderivatives and regular subdifferentials, we obtain some primal and dual characterizations for a penalty function associated with the nonlinear programming problem to have a local sharp minimum. These general results are then applied to the ? _p penalty function with 0 ≤ p ≤ 1. In particular, we present primal and dual equivalent conditions in terms of the original data of the nonlinear programming problem, which guarantee that the ? _p penalty function has a local sharp minimum with a finite penalty parameter in the case of \(p\in (\frac {1}{2}, 1]\) and \(p=\frac {1}{2}\) respectively. By assuming the Guignard constraint qualification (resp. the generalized Guignard constraint qualification), we also show that a local sharp minimum of the nonlinear programming problem can be an exact local sharp minimum of the ? _p penalty function with p ∈ [0, 1] (resp. \(p\in [0, \frac {1}{2}]\)). Finally, we give some formulas for calculating the smallest penalty parameter for a penalty function to have a local sharp minimum.     

Modified objective function method in nonsmooth vector optimization over cones

In this paper optimality for a nonsmooth vector optimization problem having generalized cone-invex objective and constraint functions is considered. An equivalent $\eta $ -approximated vector optimization problem is constructed by a modification of the objective function. The relationships between weakly efficient solutions and saddle points of the two problems are studied.