A progressive barrier derivative-free trust-region algorithm for constrained optimization

We study derivative-free constrained optimization problems and propose a trust-region method that builds linear or quadratic models around the best feasible and around the best infeasible solutions found so far. These models are optimized within a trust region, and the progressive barrier methodology handles the constraints by progressively pushing the infeasible solutions toward the feasible domain. Computational experiments on 40 smooth constrained problems indicate that the proposed method is competitive with COBYLA, and experiments on two nonsmooth multidisciplinary optimization problems from mechanical engineering show that it can be competitive with the NOMAD software.     

Underestimating the cost of a soft constraint is dangerous: revisiting the edit-distance based soft regular constraint

Many real-life problems are over-constrained, so that no solution satisfying all their constraints exists. Soft constraints, with costs denoting how much the constraints are violated, are used to solve these problems. We use the edit-distance based SoftRegular constraint as an example to show that a propagation algorithm that sometimes underestimates the cost may guide the search to incorrect (non-optimal) solutions to an over-constrained problem. To compute correctly the cost for the edit-distance based SoftRegular constraint, we present a quadratic-time propagation algorithm based on dynamic programming and a proof of its correctness. We also give an improved propagation algorithm using an idea of computing the edit distance between two strings, which may also be applied to other constraints with propagators based on dynamic programming. The asymptotic time complexity of our improved propagator is always at least as good as the one of our quadratic-time propagator, but significantly better when the edit distance is small. Our propagators achieve domain consistency on the problem variables and bounds consistency on the cost variable. Our method can also be adapted for the violation measure of the edit-distance based Regular constraint for constraint-based local search.     

Corrector-predictor methods for sufficient linear complementarity problems

We present a new corrector-predictor method for solving sufficient linear complementarity problems for which a sufficiently centered feasible starting point is available. In contrast with its predictor-corrector counterpart proposed by Miao, the method does not depend on the handicap κ of the problem. The method has \(O((1+\kappa)\sqrt{n}L)\)-iteration complexity, the same as Miao’s method, but our error estimates are sightly better. The algorithm is quadratically convergent for problems having a strictly complementary solution. We also present a family of infeasible higher order corrector-predictor methods that are superlinearly convergent even in the absence of strict complementarity. The algorithms of this class are globally convergent for general positive starting points. They have \(O((1+\kappa)\sqrt{n}L)\)-iteration complexity for feasible, or “almost feasible”, starting points and O((1+κ)² nL)-iteration complexity for “sufficiently large” infeasible starting points.     

Optimal control and relaxation of nonlinear elliptic systems

In this paper we study the optimal control of systems driven by nonlinear elliptic partial differential equations. First, with the aid of an appropriate convexity hypothesis we establish the existence of optimal admissible pairs. Then we drop the convexity hypothesis and we pass to the larger relaxed system. First we consider a relaxed system based on the Gamkrelidze-Warga approach, in which the controls are transition probabilities. We show that this relaxed problem has always had a solution and the value of the problem is that of the original one. We also introduce two alternative formulations of the relaxed problem (one of them control free), which we show that they are both equivalent to the first one. Then we compare those relaxed problems, with that of Buttazzo which is based on the -regularization of the extended cost functional. Finally, using a powerful multiplier rule of Ioffe-Tichomirov, we derive necessary conditions for optimality in systems with inequality state constraints.Research supported by NSF Grant DMS-8802688     

A branching scheme for minimum cost tournaments with regard to real-world constraints

Single round robin tournaments are a well-known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated with each possible match. Moreover, stadium availability, fixed matches, and regions’ capacities are taken into account. The goal is to find the minimum cost tournament among those having the minimum number of breaks and being feasible with regard to these additional constraints. A branching scheme is developed where branching is done by fixing a break for a team. Thus, the focus is on identifying breaks leading to an infeasible home away pattern set in order to avoid the resulting infeasible subtrees of a branch and bound tree.     

Tracing the Pareto frontier in bi-objective optimization problems by ODE techniques

In this paper we present a deterministic method for tracing the Pareto frontier in non-linear bi-objective optimization problems with equality and inequality constraints. We reformulate the bi-objective optimization problem as a parametric single-objective optimization problem with an additional Normalized Normal Equality Constraint (NNEC) similar to the existing Normal Boundary Intersection (NBI) and the Normalized Normal Constraint method (NNC). By computing the so called Defining Initial Value Problem (DIVP) for segments of the Pareto front and solving a continuation problem with a standard integrator for ordinary differential equations (ODE) we can trace the Pareto front. We call the resulting approach ODE NNEC method and demonstrate numerically that it can yield the entire Pareto frontier to high accuracy. Moreover, due to event detection capabilities available for common ODE integrators, changes in the active constraints can be automatically detected. The features of the current algorithm are illustrated for two case studies whose Matlab® code is available as Electronic Supplementary Material to this article.     

Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits

The placement problem in the layout design of electronic circuits consists of finding a nonoverlapping assignment of rectangular cells to positions on the chip so that wireability is guaranteed and certain technical constraints are met. This problem can be modelled as a quadratic 0/1-program subject to linear constraints. We will present a decomposition approach to the placement problem and give results above NP-hardness and the existence of-approximative algorithms for the involved optimization problems. A graph theoretic formulation of these problems will enable us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines.     

IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation

We present a new method for solving stochastic programs with joint chance constraints with random technology matrices and discretely distributed random data. The problem can be reformulated as a large-scale mixed 0–1 integer program. We derive a new class of optimality cuts called IIS cuts and apply them to our problem. The cuts are based on irreducibly infeasible subsystems (IIS) of an LP defined by requiring that all scenarios be satisfied. We propose a method for improving the upper bound of the problem when no cut can be found. We derive and implement a branch-and-cut algorithm based on IIS cuts, and refer to this algorithm as the IIS branch-and-cut algorithm. We report on computational results with several test instances from optimal vaccine allocation. The computational results are promising as the IIS branch-and-cut algorithm gives better results than a state-of-the-art commercial solver on one class of problems.     

Time-stepping discontinuous Galerkin approximation of optimal control problem governed by time fractional diffusion equation

In this paper, a piecewise constant time-stepping discontinuous Galerkin method combined with a piecewise linear finite element method is applied to solve control constrained optimal control problem governed by time fractional diffusion equation. The control variable is approximated by variational discretization approach. The discrete first-order optimality condition is derived based on the first discretize then optimize approach. We demonstrate the commutativity of discretization and optimization for the time-stepping discontinuous Galerkin discretization. Since the state variable and the adjoint state variable in general have weak singularity near t =?0and t = T, a time adaptive algorithm is developed based on step doubling technique, which can be used to guide the time mesh refinement. Numerical examples are given to illustrate the theoretical findings.     

Solution of Special Linear Programming Problems with Additional Constraints

This paper gives a method of solution for linear programming problems whose constraints can be split into two sets, the first having a special structure, such as that of the transportation problem for example, while the second set is quite general. A problem with only the first set of constraints is referred to as a favoured problem, while a problem with both sets is called a complete problem.The proposed method is basically the simplex procedure specialized for a problem with a particular structure, and the feasibility and optimality criteria and the rules for basis change are the same as those used in the simplex procedure. However, the method takes advantage of the simple algorithms developed for the favoured problem and uses them to solve the complete problem in an efficient manner.Such problems could also be solved by the Decomposition Principle and, vice versa, Decomposition problems can be solved by the present method. The two methods are, however, essentially different in their approach to the problem.     

Alternative Formulations of a Flow-shop Scheduling Problem

This paper presents an alternative approach to an earlier model developed by other authors to formulate a problem of sequencing N jobs on M machines in a standard flow-shop. The objectives of the model are to minimize makespan and flow-time. The new formulation involves substantially fewer variables, at the expense of a rise in the number of constraints. Practical limitations of both approaches are discussed.     

Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming

In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Most interior-point methods, on the other hand, do not provide such clear-cut information. If the primal and dual problems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primaldual iterates that approach feasibility and optimality. But if the primal or dual instance is infeasible, most methods give less precise diagnostics. There are methods with finite convergence to an exact solution even with real data. Unfortunately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and often quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general tools (extensions of the Farkas lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a homogeneous self-dual algorithm and for a generic infeasible-interior-point method for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain certificates that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A constrained optimization reformulation and a feasible descent direction method for L_{1/2} regularization

In this paper, we first propose a constrained optimization reformulation to the \(L_{1/2}\) regularization problem. The constrained problem is to minimize a smooth function subject to some quadratic constraints and nonnegative constraints. A good property of the constrained problem is that at any feasible point, the set of all feasible directions coincides with the set of all linearized feasible directions. Consequently, the KKT point always exists. Moreover, we will show that the KKT points are the same as the stationary points of the \(L_{1/2}\) regularization problem. Based on the constrained optimization reformulation, we propose a feasible descent direction method called feasible steepest descent method for solving the unconstrained \(L_{1/2}\) regularization problem. It is an extension of the steepest descent method for solving smooth unconstrained optimization problem. The feasible steepest descent direction has an explicit expression and the method is easy to implement. Under very mild conditions, we show that the proposed method is globally convergent. We apply the proposed method to solve some practical problems arising from compressed sensing. The results show its efficiency.     

Trajectory-following methods for large-scale degenerate convex quadratic programming

We consider a class of infeasible, path-following methods for convex quadratric programming. Our methods are designed to be effective for solving both nondegerate and degenerate problems, where degeneracy is understood to mean the failure of strict complementarity at a solution. Global convergence and a polynomial bound on the number of iterations required is given. An implementation, CQP, is available as part of GALAHAD. We illustrate the advantages of our approach on the CUTEr and Maros–Meszaros test sets.     

A unified solving approach for two and three dimensional coverage problems in sensor networks

The problem of designing a wired or a wireless sensor network to cover, monitor and/or control a region of interest has been widely treated in literature. This problem is referred to in literature as the sensor placement problem (SPP) and in the most general case it consists in determining the number and the location of one or more kind of sensors with the aim of covering all the region of interest or a significant part of it. In this paper we propose a unified and stepwise solving approach for two and three dimensional coverage problems to be used in omni-directional and directional sensor networks. The proposed approach is based on schematizing the region of interest and the sensor potential locations by a grid of points and representing the sensor coverage area by a circle or by a circular sector. On this basis, the SPP is reduced to an optimal coverage problem and can be formulated by integer linear programming (ILP) models. We will resume the main ILP models used in our approach, highlighting, for each of them, the specific target to be achieved and the design constraints taken into account. The paper concludes with an application of the proposed approach to a real test case and a discussion of the obtained results.     

An Extragradient-Based Alternating Direction Method for Convex Minimization

In this paper, we consider the problem of minimizing the sum of two convex functions subject to linear linking constraints. The classical alternating direction type methods usually assume that the two convex functions have relatively easy proximal mappings. However, many problems arising from statistics, image processing and other fields have the structure that while one of the two functions has an easy proximal mapping, the other function is smoothly convex but does not have an easy proximal mapping. Therefore, the classical alternating direction methods cannot be applied. To deal with the difficulty, we propose in this paper an alternating direction method based on extragradients. Under the assumption that the smooth function has a Lipschitz continuous gradient, we prove that the proposed method returns an \(\epsilon \)-optimal solution within \(O(1/\epsilon )\) iterations. We apply the proposed method to solve a new statistical model called fused logistic regression. Our numerical experiments show that the proposed method performs very well when solving the test problems. We also test the performance of the proposed method through solving the lasso problem arising from statistics and compare the result with several existing efficient solvers for this problem; the results are very encouraging.     

Solving convex optimization with side constraints in a multi-class queue by adaptive c\mu rule

We study convex optimization problems with side constraints in a multi-class \(M/G/1\) queue with controllable service rates. In the simplest problem of optimizing linear costs with fixed service rate, the \(c\mu \) rule is known to be optimal. A natural question to ask is whether such simple policies exist for more complex control objectives. In this paper, combining the achievable region approach in queueing systems and the Lyapunov drift theory suitable to optimize renewal systems with time-average constraints, we show that convex optimization problems can be solved by variants of adaptive \(c\mu \) rules. These policies greedily re-prioritize job classes at the end of busy periods in response to past observed delays in each job class. Our method transforms the original problems into a new set of queue stability problems, and the adaptive \(c\mu \) rules are queue stable policies. An attractive feature of the adaptive \(c\mu \) rules is that they use limited statistics of the queue, where no statistics are required for the problem of satisfying average queueing delay in each job class.     

An $$\ell _{2}$$-neighborhood infeasible interior-point algorithm for linear complementarity problems

In this paper, we propose an infeasible interior-point algorithm for linear complementarity problems. In every iteration, the algorithm constructs an ellipse and searches an \(\varepsilon \)-approximate solution of the problem along the ellipsoidal approximation of the central path. The theoretical iteration-complexity of the algorithm is derived and the algorithm is proved to be polynomial with the complexity bound \(O\left(n\log \varepsilon ^{-1}\right)\) which coincides with the best known iteration bound for infeasible interior-point methods.