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 .     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

On Generalizations of the Frank-Wolfe Theorem to Convex and Quasi-Convex Programmes

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or a quasi-convex polynomial function over the feasible set defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities, where the faithfully convex functions satisfy some mild assumption. The conditions are provided in the form of an algorithm, terminating after a finite number of iterations, the implementation of which requires the identification of implicit equality constraints in a homogeneous linear system. We prove that the optimal solution set of the considered problem is nonempty, this way extending the attainability result well known as the so-called Frank-Wolfe theorem. Finally we show that our extension of the Frank-Wolfe theorem immediately implies continuity of the solution set defined by the considered system of (quasi)convex inequalities.     

A note on duality gaps in linear programming over convex sets

For certain types of mathematical programming problems, a related dual problem can be constructed in which the objective value of the dual problem is equal to the objective function of the given problem. If these two problems do not have equal values, a duality gap is said to exist. No such gap exists for pairs of ordinary dual linear programming problems, but this is not the case for linear programming problems in which the nonnegativity conditionx ? 0 is replaced by the condition thatx lies in a certain convex setK. Duffin (Ref. 1) has shown that, whenK is a cone and a certain interiority condition is fulfilled, there will be no duality gap. In this note, we show that no duality gap exists when the interiority condition is satisfied andK is an arbitrary closed convex set inR ⁿ .     

Dynamic convex duality in constrained utility maximization

ABSTRACT

In this paper, we study a constrained utility maximization problem following the convex duality approach. After formulating the primal and dual problems, we construct the necessary and sufficient conditions for both the primal and dual problems in terms of forward and backward stochastic differential equations (FBSDEs) plus some additional conditions. Such formulation then allows us to explicitly characterize the primal optimal control as a function of the adjoint process coming from the dual FBSDEs in a dynamic fashion and vice versa. We also find that the optimal wealth process coincides with the adjoint process of the dual problem and vice versa. Finally we solve three constrained utility maximization problems, which contrasts the simplicity of the duality approach we propose and the technical complexity of solving the primal problem directly.     

Duality in quasi-convex supremization and reverse convex infimization via abstract convex analysis,and applications to approximation **

We give duality theorems and dual characterizations of optimal solutions for abstract quasi-convex supremization problems and infimization problems with abstract reverse convex constraint sets. Our main tools are dualities between families of subsets, conjugations of type Lau associated to them, and subdifferentials with respect to conjugations of type Lau. These tools permit us to give explicitly the relation between.the constraint sets, and the relation between the objective functions, of the primal problem and the dual problem. As applications, we obtain duality theorems for quasi-convex supremization and reverse convex infimization in locally convex spaces and, in particular, for worst and best approximation in normed linear spaces.     

Entropic perturbation method for solving a system of linear inequalities

The problem of finding an $\text{x∈}\text{R}{}^{\mathrm{n}}$ such that Ax⩽b and x⩾0 arises in numerous contexts. We propose a new optimization method for solving this feasibility problem. After converting Ax⩽b into a system of equations by introducing a slack variable for each of the linear inequalities, the method imposes an entropy function over both the original and the slack variables as the objective function. The resulting entropy optimization problem is convex and has an unconstrained convex dual. If the system is consistent and has an interior solution, then a closed-form formula converts the dual optimal solution to the primal optimal solution, which is a feasible solution for the original system of linear inequalities. An algorithm based on the Newton method is proposed for solving the unconstrained dual problem. The proposed algorithm enjoys the global convergence property with a quadratic rate of local convergence. However, if the system is inconsistent, the unconstrained dual is shown to be unbounded. Moreover, the same algorithm can detect possible inconsistency of the system. Our numerical examples reveal the insensitivity of the number of iterations to both the size of the problem and the distance between the initial solution and the feasible region. The performance of the proposed algorithm is compared to that of the surrogate constraint algorithm recently developed by Yang and Murty. Our comparison indicates that the proposed method is particularly suitable when the number of constraints is larger than that of the variables and the initial solution is not close to the feasible region.     

Regularized gap function as penalty term for constrained minimization problems

By using the regularized gap function for variational inequalities, Li and Peng introduced a new penalty function Pα(x) for the problem of minimizing a twice continuously differentiable function in closed convex subset of the n-dimensional space Rn. Under certain assumptions, they proved that the original constrained minimization problem is equivalent to unconstrained minimization of Pα(x). The main purpose of this paper is to give an in-depth study of those properties of the objective function that can be extended from the feasible set to the whole Rn by Pα(x). For example, it is proved that the objective function has bounded level sets (or is strongly coercive) on the feasible set if and only if Pα(x) has bounded level sets (or is strongly coercive) on Rn. However, the convexity of the objective function does not imply the convexity of Pα(x) when the objective function is not quadratic, no matter how small α is. Instead, the convexity of the objective function on the feasible set only implies the invexity of Pα(x) on Rn. Moreover, a characterization for the invexity of Pα(x) is also given.     

Countably infinite quasi-convex sets in some locally compact abelian groups

We produce a class of countably infinite quasi-convex sets (sequences converging to zero) in the circle group T and in the group J₂ of 2-adic integers determined by sequences of integers satisfying a mild lacunarity condition. We also extend our results to the group R of real numbers. All these quasi-convex sets have a stronger property: Every infinite (necessarily) symmetric subset containing 0 is still quasi-convex.     

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.     

On Extensions of the Frank-Wolfe Theorems

In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.     

Augmented Lagrangian Objective Penalty Function

Augmented Lagrangian function is one of the most important tools used in solving some constrained optimization problems. In this article, we study an augmented Lagrangian objective penalty function and a modified augmented Lagrangian objective penalty function for inequality constrained optimization problems. First, we prove the dual properties of the augmented Lagrangian objective penalty function, which are at least as good as the traditional Lagrangian function's. Under some conditions, the saddle point of the augmented Lagrangian objective penalty function satisfies the first-order Karush-Kuhn-Tucker condition. This is especially so when the Karush-Kuhn-Tucker condition holds for convex programming of its saddle point existence. Second, we prove the dual properties of the modified augmented Lagrangian objective penalty function. For a global optimal solution, when the exactness of the modified augmented Lagrangian objective penalty function holds, its saddle point exists. The sufficient and necessary stability conditions used to determine whether the modified augmented Lagrangian objective penalty function is exact for a global solution is proved. Based on the modified augmented Lagrangian objective penalty function, an algorithm is developed to find a global solution to an inequality constrained optimization problem, and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the modified augmented Lagrangian objective penalty function is proved for a local solution. An algorithm is presented in finding a local solution, with its convergence proved under some conditions.     

Optimal partitions having disjoint convex and conic hulls

LetA ¹,,A ⁿ be distinctk-dimensional vectors. We consider the problem of partitioning these vectors intom sets so as to maximize an objective which is a quasi-convex function of the sum of vectors in each set. We show that there exists an optimal partition whose sets have (pairwise) disjoint conic hulls. We also show that if the number of vectors in each of the sets is constrained, then a weaker conclusion holds, namely, there exists an optimal partition whose sets have (pairwise) disjoint convex hulls. The results rely on deriving necessary and sufficient conditions for a point to be an extreme point of a corresponding polytope.Research of this author was partially supported by NSF Grant ECS-83-10213 and by a Grant for the Promotion of Research at the Technion.     

A dual algorithm for the one-machine scheduling problem

A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn ² and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.     

Inexact subgradient methods for quasi-convex optimization problems

In this paper, we consider a generic inexact subgradient algorithm to solve a nondifferentiable quasi-convex constrained optimization problem. The inexactness stems from computation errors and noise, which come from practical considerations and applications. Assuming that the computational errors and noise are deterministic and bounded, we study the effect of the inexactness on the subgradient method when the constraint set is compact or the objective function has a set of generalized weak sharp minima. In both cases, using the constant and diminishing stepsize rules, we describe convergence results in both objective values and iterates, and finite convergence to approximate optimality. We also investigate efficiency estimates of iterates and apply the inexact subgradient algorithm to solve the Cobb–Douglas production efficiency problem. The numerical results verify our theoretical analysis and show the high efficiency of our proposed algorithm, especially for the large-scale problems.     

A second-order smooth penalty function algorithm for constrained optimization problems

This paper introduces a second-order differentiability smoothing technique to the classical l ₁ exact penalty function for constrained optimization problems(COP). Error estimations among the optimal objective values of the nonsmooth penalty problem, the smoothed penalty problem and the original optimization problem are obtained. Based on the smoothed problem, an algorithm for solving COP is proposed and some preliminary numerical results indicate that the algorithm is quite promising.     

Dual gradient method for linearly constrained,strongly convex,separable mathematical programming problems

A new dual gradient method is given to solve linearly constrained, strongly convex, separable mathematical programming problems. The dual problem can be decomposed into one-dimensional problems whose solutions can be computed extremely easily. The dual objective function is shown to have a Lipschitz continuous gradient, and therefore a gradient-type algorithm can be used for solving the dual problem. The primal optimal solution can be obtained from the dual optimal solution in a straightforward way. Convergence proofs and computational results are given.     

Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization

The precedence constrained traveling salesman problem (TSP-PC), or the sequential ordering problem (SOP), consists of finding an optimal TSP tour that will also satisfy the namesake precedence constraints, typically specified as a partial order or a directed acyclic graph. Its dynamic programming (DP) solution was proposed as early as 1979, however, by late 1990s, it mostly fell out of use in plain TSP-PC. Revisiting this method, we are able to close one of the long-standing TSPLIB SOP problem instances, ry48p.3.sop, and provide improved bounds on its time complexity. Harnessing the “omnivorous” nature of DP, we prove the validity of DP optimality principle for TSP-PC with both (i) abstract cost aggregation function, which may be the arithmetic + operation as in “ordinary” TSP or $\max$ as in Bottleneck TSP, or any other left-associative nondecreasing in the first argument operation and (ii) travel cost functions depending on the set of pending tasks (“sequence dependence”). Using the latter generalization, we close several TD-SOP (time-dependent TSP-PC) instances based on TSPLIB SOP as proposed by Kinable et al., including rbg253a.sop. Through the restricted DP heuristic, which was originally formulated for time-dependent TSP by Malandraki and Dial, we improve the state-of-the-art upper bounds for all yet unsolved TSPLIB-based TD-SOP instances, including those with more than 100 cities. We also improve worst-case complexity estimates for DP in TSP-PC.     

Semiconcavity results for constrained optimal control problems in a half-space

In this paper we give semiconcavity results for the value function of some constrained optimal control problems with infinite horizon in a half-space. In particular, we assume that the control space is the l¹-ball or the l^∞-ball in Rn.     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.