On solving general reverse convex programming problems by a sequence of linear programs and line searches

Many multiextremal global optimization problems can be formulated as problems of minimizing a linear function over the intersection of a convex set with the complement of a convex set (so-called canonical d.c. programs or general reverse convex programming problems). In this paper it is shown that these general reverse convex programming problems can be solved by a sequence of linear programs and univariate convex minimization problems (line searches).Parts of the present paper were accomplished while this author was on leave at the University of Trier as a fellow of the Alexander von Humboldt foundation.     

Technical efficiency and distance to a reverse convex set

The problem of finding the distance to a reverse (or complement of a) convex subset in a normed vector space is considered. This nonconvex and, in general, nonsmooth optimization problem arises in quantitative economics in the theory of measuring the technical efficiency of production units. In this context, applying a suitable duality theorem similar to the Nirenberg's one known for the distance to a convex subset, the problem reduces to a finite number of independent linear programming problems.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

Homotopy classification of projective convex sets

A subset of projective space is called convex if its intersection with every line is connected. The complement of a projective convex set is again convex. We prove that for any projective convex set there exists a pair of complementary projective subspaces, one contained in the convex set and the other in its complement. This yields their classification up to homotopy.     

Quasi-relative interior-type constraint qualifications ensuring strong Lagrange duality for optimization problems with cone and affine constraints

In this article we provide weak sufficient strong duality conditions for a convex optimization problem with cone and affine constraints, stated in infinite dimensional spaces, and its Lagrange dual problem. Our results are given by using the notions of quasi-relative interior and quasi-interior for convex sets. The main strong duality theorem is accompanied by several stronger, yet easier to verify in practice, versions of it. As exemplification we treat a problem which is inspired from network equilibrium. Our results come as corrections and improvements to Daniele and Giuffré (2007) [9].     

Dual Characterizations of Set Containments with Strict Convex Inequalities

Characterizations of the containment of a convex set either in an arbitrary convex set or in the complement of a finite union of convex sets (i.e., the set, described by reverse-convex inequalities) are given. These characterizations provide ways of verifying the containments either by comparing their corresponding dual cones or by checking the consistency of suitable associated systems. The convex sets considered in this paper are the solution sets of an arbitrary number of convex inequalities, which can be either weak or strict inequalities. Particular cases of dual characterizations of set containments have played key roles in solving large scale knowledge-based data classification problems where they are used to describe the containments as inequality constraints in optimization problems. The idea of evenly convex set (intersection of open half spaces), which was introduced by W. Fenchel in 1952, is used to derive the dual conditions, characterizing the set containments.     

Optimal allocation of simulation experiments in discrete stochastic optimization and approximative algorithms

Approximate solutions for discrete stochastic optimization problems are often obtained via simulation. It is reasonable to complement these solutions by confidence regions for the argmin-set. We address the question how a certain total number of random draws should be distributed among the set of alternatives. Two goals are considered: the minimization of the costs caused by using a statistical estimate of the true argmin, and the minimization of the expected size of the confidence sets. We show that an asymptotically optimal sampling strategy in the case of normal errors can be obtained by solving a convex optimization problem. To reduce the computational effort we propose a regularization that leads to a simple one-step allocation rule.     

LMI Approach to Robust Model Predictive Control

This paper introduces a new approach to robust model predictive control (MPC) based on conservative approximations to semi-infinite optimization using linear matrix inequalities (LMIs). The method applies to problems with convex quadratic costs, linear and convex quadratic constraints, and linear predictive models with bounded uncertainty. If the MPC optimization problem is feasible at the initial control step (the first application of the MPC optimization), it is shown that the MPC optimization problems will be feasible at all future time steps and that the controlled system will be closed-loop stable. The method is illustrated with a solenoid control example. The authors thank the anonymous reviewers for suggestions that improved the presentation of this work. The work was supported in part by the EPRI/DoD Complex Interactive Networks/Systems Initiative under Contract EPRI-W08333-05 and by the US Army Research Office Contract DAAD19-01-1-0485.     

Methods of Chebyshev points of convex sets and their applications

Chebyshev points of bounded convex sets, search algorithms for them, and various applications to convex programming are considered for simple approximations of reachable sets, optimal control, global optimization of additive functions on convex polyhedra, and integer programming. The problem of searching for Chebyshev points in multicriteria models of development and operation of electric power systems is considered.     

Exceptional Families of Elements for Optimization Problems in Reflexive Banach Spaces with Applications

In this paper, we propose a new notion of ‘exceptional family of elements’ for convex optimization problems. By employing the notion of ‘exceptional family of elements’, we establish some existence results for convex optimization problem in reflexive Banach spaces. We show that the nonexistence of an exceptional family of elements is a sufficient and necessary condition for the solvability of the optimization problem. Furthermore, we establish several equivalent conditions for the solvability of convex optimization problems. As applications, the notion of ‘exceptional family of elements’ for convex optimization problems is applied to the constrained optimization problem and convex quadratic programming problem and some existence results for solutions of these problems are obtained.     

Shortening cycle times in multi-product,capacitated production environments through quality level improvements and setup reduction

This paper addresses the issue of investing in reduced setup times and defect rates for a manufacturer of several products operating in a JIT environment. Production cycle times can be shortened by investing in setup time and defect rate reductions, respectively. The objective is to determine optimal levels of setup time and defect rate reductions along with the corresponding optimal levels of investments respectively, and the optimal production cycle time for each product. The problem is constrained by demand requirements, process improvement budget limitations, and manufacturing and warehousing capacity constraints. We consider the cases of product-specific quality improvements and joint-product quality improvements. A general nonlinear optimization models of these problems are formulated. A convex geometric programming approximation of these models is developed respectively, in order to solve them. The approximation can be made to any desired degree of accuracy. Our empirical findings provide insights into a number of managerial issues surrounding investment decisions in product-specific quality improvements and setup reductions due to a product redesign as well as in joint-product improvements due to a process redesign.     

Symbolic Fenchel Conjugation

Of key importance in convex analysis and optimization is the notion of duality, and in particular that of Fenchel duality. This work explores improvements to existing algorithms for the symbolic calculation of subdifferentials and Fenchel conjugates of convex functions defined on the real line. More importantly, these algorithms are extended to enable the symbolic calculation of Fenchel conjugates on a class of real-valued functions defined on $\mathbb{R}^n$ . These algorithms are realized in the form of the Maple package SCAT.     

A Rigorous Global Optimization Algorithm for Problems with Ordinary Differential Equations

The optimization of systems which are described by ordinary differential equations (ODEs) is often complicated by the presence of nonconvexities. A deterministic spatial branch and bound global optimization algorithm is presented in this paper for systems with ODEs in the constraints. Upper bounds for the global optimum are produced using the sequential approach for the solution of the dynamic optimization problem. The required convex relaxation of the algebraic functions is carried out using well-known global optimization techniques. A convex relaxation of the time dependent information is obtained using the concept of differential inequalities in order to construct bounds on the space of solutions of parameter dependent ODEs as well as on their second-order sensitivities. This information is then incorporated in the convex lower bounding NLP problem. The global optimization algorithm is illustrated by applying it to four case studies. These include parameter estimation problems and simple optimal control problems. The application of different underestimation schemes and branching strategies is discussed.     

Approximation of convex bodies by multiple objective optimization and an application in reachable sets

In this paper, we focus on approximating convex compact bodies. For a convex body described as the feasible set in objective space of a multiple objective programme, we show that finding it is equivalent to finding the non-dominated set of a multiple objective programme. This equivalence implies that convex bodies can be approximated using multiple objective optimization algorithms. Therefore, we propose a revised outer approximation algorithm for convex multiple objective programming problems to approximate convex bodies. Finally, we apply the algorithm to solve reachable sets of control systems and use numerical examples to show the effectiveness of the algorithm.     

Verified Distance Computation Between Convex Hulls of Octrees Using Interval Optimization Techniques

Distance computation is an important task in many application areas, including biomechanics, robot systems and computer games. Depending on the intended use, requirements differ. For example, in a medical context, a verified result may be of interest. In this paper we will demonstrate the use of an interval optimization algorithm for computing a verified enclosure of the minimum distance between the convex hulls of two octrees. We will also discuss runtime improvements. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Open-loop criterion for the solvability of a closed-loop guidance problem with incomplete information: Linear control systems

The method of open-loop control packages is a tool for stating the solvability of guaranteed closed-loop control problems under incomplete information on the observed states. In this paper, a solution method is specified for the problem of guaranteed closed-loop guidance of a linear control system to a convex target set at a prescribed point in time. It is assumed that the observed signal on the system’s states is linear and the set of its admissible initial states is finite. It is proved that the problem under consideration is equivalent to the problem of open-loop guidance of an extended linear control system to an extended convex target set. Using a separation theorem for convex sets, we derive a solvability criterion, which reduces to solving a finite-dimensional optimization problem. An illustrative example is considered.     

A semidefinite programming approach for solving fractional optimal control problems

This paper presents a numerical scheme for solving fractional optimal control. The fractional derivative in this problem is in the Riemann–Liouville sense. The proposed method, based upon the method of moments, converts the fractional optimal control problem to a semidefinite optimization problem; namely, the nonlinear optimal control problem is converted to a convex optimization problem. The Grunwald–Letnikov formula is also used as an approximation for fractional derivative. The solution of fractional optimal control problem is found by solving the semidefinite optimization problem. Finally, numerical examples are presented to show the performance of the method.     

Vector optimization problems with nonconvex preferences

In this paper, some vector optimization problems are considered where pseudo-ordering relations are determined by nonconvex cones in Banach spaces. We give some characterizations of solution sets for vector complementarity problems and vector variational inequalities. When the nonconvex cone is the union of some convex cones, it is shown that the solution set of these problems is either an intersection or an union of the solution sets of all subproblems corresponding to each of these convex cones depending on whether these problems are defined by the nonconvex cone itself or its complement. Moreover, some relations of vector complementarity problems, vector variational inequalities, and minimal element problems are also given. While this paper was being revised in September 2006, Professor Alex Rubinov (the second author of the paper) left us due to the illness. This is a very sad news to us. We dedicate this paper to the memory of Professor Rubinov as a mathematician and truly friend.     

Characterizations of the nonemptiness and compactness for solution sets of convex set-valued optimization problems

In this paper, we first derive several characterizations of the nonemptiness and compactness for the solution set of a convex scalar set-valued optimization problem (with or without cone constraints) in which the decision space is finite-dimensional. The characterizations are expressed in terms of the coercivity of some scalar set-valued maps and the well-posedness of the set-valued optimization problem, respectively. Then we investigate characterizations of the nonemptiness and compactness for the weakly efficient solution set of a convex vector set-valued optimization problem (with or without cone constraints) in which the objective space is a normed space ordered by a nontrivial, closed and convex cone with nonempty interior and the decision space is finite-dimensional. We establish that the nonemptiness and compactness for the weakly efficient solution set of a convex vector set-valued optimization problem (with or without cone constraints) can be exactly characterized as those of a family of linearly scalarized convex set-valued optimization problems and the well-posedness of the original problem.