Convergence results for an accelerated nonlinear cimmino algorithm

Summary We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested.     

A Full-Newton Step Infeasible Interior-Point Algorithm Based on Darvay Directions for Linear Optimization

We present a full-Newton step primal-dual infeasible interior-point algorithm based on Darvay’s search directions. These directions are obtained by an equivalent algebraic transformation of the centering equation. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. The starting point in the first iteration of the algorithm depends on a positive number ξ and it is strictly feasible for a perturbed pair, and feasibility steps find strictly feasible iterate for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterate close to the central path of the new perturbed pair. The algorithm finds an ?-optimal solution or detects infeasibility of the given problem. The iteration bound coincides with the best known iteration bound for linear optimization problems.     

A new infeasible interior-point method based on Darvay’s technique for symmetric optimization

We present a full Nesterov and Todd step primal-dual infeasible interior-point algorithm for symmetric optimization based on Darvay’s technique by using Euclidean Jordan algebras. The search directions are obtained by an equivalent algebraic transformation of the centering equation. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. The starting point in the first iteration of the algorithm depends on a positive number ξ and it is strictly feasible for a perturbed pair. The feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close to the central path of the new perturbed pair. The algorithm finds an ?-optimal solution or detects infeasibility of the given problem. Moreover, we derive the currently best known iteration bound for infeasible interior-point methods.     

一种原始——对偶单纯形算法的枢轴准则选择

Curet曾提出了一种有趣的原始一对偶技术,在优化对偶问题的同时单调减少原始不可行约束的数量,当原始可行性产生时也就产生了原问题的最优解.然而该算法需要一个初始对偶可行解来启动,目标行的选择也是灵活、不确定的.根据Curet的原始一对偶算法原理,提出了两种目标行选择准则,并通过数值试验进行比较和选择.对不存在初始对偶可行解的情形,通过适当改变目标函数的系数来构造一个对偶可行解,以求得一个原始可行解,再应用原始单纯形算法求得原问题的最优解.数值试验对这种算法的计算性能进行验证,通过与经典两阶段单纯形算法比较,结果表明,提出的算法在大部分问题上具有更高的计算效率.     

Continuous-time method and its discretization to inverse problem of intensity-modulated radiation therapy treatment planning

We propose a novel approach for solving box-constrained inverse problems in intensity-modulated radiation therapy (IMRT) treatment planning based on the idea of continuous dynamical methods and split-feasibility algorithms. Our method can compute a feasible solution without the second derivative of an objective function, which is required for gradient-based optimization algorithms. We prove theoretically that a double Kullback–Leibler divergence can be used as the Lyapunov function for the IMRT planning system.Moreover, we propose a non-negatively constrained iterative method formulated by discretizing a differential equation in the continuous method. We give proof for the convergence of a desired solution in the discretized system, theoretically. The proposed method not only reduces computational costs but also does not produce a solution with an unphysical negative radiation beam weight in solving IMRT planning inverse problems.The convergence properties of solutions for an ill-posed case are confirmed by numerical experiments using phantom data simulating a clinical setup.     

A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function

We propose a new full-Newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a simple locally-kernel function. The algorithm uses the simple locally-kernel function to determine the search directions and define the neighborhood of central path. Two types of full-Newton steps are used, feasibility step and centering step. The algorithm starts from strictly feasible iterates of a perturbed problem, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The procedure is repeated until an ?-approximate solution is found. We analyze the algorithm and obtain the complexity bound, which coincides with the best-known result for monotone linear complementarity problems.     

A majorization–minimization algorithm for split feasibility problems

The classical multi-set split feasibility problem seeks a point in the intersection of finitely many closed convex domain constraints, whose image under a linear mapping also lies in the intersection of finitely many closed convex range constraints. Split feasibility generalizes important inverse problems including convex feasibility, linear complementarity, and regression with constraint sets. When a feasible point does not exist, solution methods that proceed by minimizing a proximity function can be used to obtain optimal approximate solutions to the problem. We present an extension of the proximity function approach that generalizes the linear split feasibility problem to allow for non-linear mappings. Our algorithm is based on the principle of majorization–minimization, is amenable to quasi-Newton acceleration, and comes complete with convergence guarantees under mild assumptions. Furthermore, we show that the Euclidean norm appearing in the proximity function of the non-linear split feasibility problem can be replaced by arbitrary Bregman divergences. We explore several examples illustrating the merits of non-linear formulations over the linear case, with a focus on optimization for intensity-modulated radiation therapy.     

An artificial-free simplex-type algorithm for general LP models

The simplex algorithm requires additional variables (artificial variables) for solving linear programs which lack feasibility at the origin point. Some students, however, particularly nonmathematics majors, have difficulty understanding the intuitive notion of artificial variables.A new general purpose solution algorithm obviates the use of artificial variables. The algorithm consists of two phases. Phase 1 searches for a feasible segment of the boundary hyper-plane (a face of feasible region or an intersection of several faces) by using rules similar to the ordinary simplex. Each successive iteration augments the basic variable set, BVS, by including another hyper-plane, until the BVS is full, which specifies a feasible vertex. In this phase, movements are on faces of the feasible region rather than from a vertex to a vertex. This phase terminates successfully (or indicates the infeasibility of the problem) with a finite number of iterations, which is at most equal to the number of constraints. The second phase uses exactly the ordinary simplex rules (if needed) to achieve optimality. This unification with the simplex method is achieved by augmenting the feasible BVS, which is always initially considered empty at the beginning of Phase 1. The algorithm working space is the space of the original (decision, slack and surplus) variables in the primal problem. It also provides a solution to the dual problem with useful information. Geometric interpretation of the strategic process with some illustrative numerical examples are also presented.     

A two-stage feasible directions algorithm for nonlinear constrained optimization

We present a feasible directions algorithm, based on Lagrangian concepts, for the solution of the nonlinear programming problem with equality and inequality constraints. At each iteration a descent direction is defined; by modifying it, we obtain a feasible descent direction. The line search procedure assures the global convergence of the method and the feasibility of all the iterates. We prove the global convergence of the algorithm and apply it to the solution of some test problems. Although the present version of the algorithm does not include any second-order information, like quasi-Newton methods, these numerical results exhibit a behavior comparable to that of the best methods known at present for nonlinear programming. Research performed while the author was on a two years appointment at INRIA, Rocquencourt, France, and partially supported by the Brazilian Research Council (CNPq).     

Using objective values to start multiple objective linear programming algorithms

We introduce in this paper a new starting mechanism for multiple-objective linear programming (MOLP) algorithms. This makes it possible to start an algorithm from any solution in objective space. The original problem is first augmented in such a way that a given starting solution is feasible. The augmentation is explicitly or implicitly controlled by one parameter during the search process, which verifies the feasibility (efficiency) of the final solution. This starting mechanism can be applied either to traditional algorithms, which search the exterior of the constraint polytope, or to algorithms moving through the interior of the constraints. We provide recommendations on the suitability of an algorithm for the various locations of a starting point in objective space. Numerical considerations illustrate these ideas.     

A modeling framework and local search solution methodology for a production-distribution problem with supplier selection and time-aggregated quantity discounts

Supplier selection with quantity discounts has been an active research problem in the literature. In this paper, we focus on a new real-world quantity discounts scheme, where suppliers are selected in the beginning of a strategic planning period (e.g., 5 years). Monthly orders are placed from the selected suppliers, but the quantity discounts are based on the aggregated annual order quantities. We incorporate this type of cost structure in a multi-period, multi-product, multi-echelon supply chain planning problem, and develop a mixed integer linear programming (MIP) model for it. Our model is highly intractable; leading commercial solvers cannot construct high quality feasible solutions for realistic instances even after multiple hours of solution time. We develop an algorithm that constructs an initial feasible solution and a large neighborhood search method that combines two customized iterative algorithms based on MIP-based local search and improves such solution. We report numerical results for a food supply chain application and show the efficiency of using our methodology in getting very high quality primal solutions quickly.     

A nonisolated optimal solution for special reverse convex programming problems

In this paper, an efficient algorithm is proposed for globally solving special reverse convex programming problems with more than one reverse convex constraints. The proposed algorithm provides a nonisolated global optimal solution which is also stable under small perturbations of the constraints, and it turns out that such an optimal solution is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and the numerical experiment is given to illustrate the feasibility of the presented algorithm.     

Finite Convergence of a Subgradient Projections Method with Expanding Controls

We study finite convergence of the modified cyclic subgradient projections (MCSP) algorithm for the convex feasibility problem (CFP) in the Euclidean space. Expanding control sequences allow the indices of the sets of the CFP to re-appear and be used again by the algorithm within windows of iteration indices whose lengths are not constant but may increase without bound. Motivated by another development in finitely convergent sequential algorithms that has a significant real-world application in the field of radiation therapy treatment planning, we show that the MCSP algorithm retains its finite convergence when used with an expanding control that is repetitive and fulfills an additional condition.     

An improved unit decommitment algorithm for combined heat and power systems

This paper addresses the unit commitment in multi-period combined heat and power (CHP) production planning, considering the possibility to trade power on the spot market. In CHP plants (units), generation of heat and power follows joint characteristics, which means that production planning for both heat and power must be done in coordination. We present an improved unit decommitment (IUD) algorithm that starts with an improved initial solution with less heat surplus so that the relative cost-efficiency of the plants can be determined more accurately. Then the subsequent decommitment procedures can decommit (switch off) the least cost-efficient plants properly. The improved initial solution for the committed plants is generated by a heuristic procedure. The heuristic procedure utilizes both the Lagrangian relaxation principle that relaxes the system-wide (heat and power) demand constraints and a linear relaxation of the ON/OFF states of the plants. We compare the IUD algorithm with realistic test data against a generic unit decommitment (UD) algorithm. Numerical results show that IUD is an overall improvement of UD. The solution quality of IUD is better than that of UD for almost all of tested cases. The maximum improvement is 11.3% and the maximum degradation is only 0.04% (only two sub-cases out of 216 sub-cases) with an average improvement of 0.3–0.5% for different planning horizons. Moreover, IUD is more efficient (1.1–3 times faster on average) than UD.     

A new full-Newton step <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) infeasible interior-point algorithm for semidefinite optimization

Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed a primal-dual infeasible interior-point algorithm with the currently best iteration bound for linear optimization problems. Since the algorithm uses only full Newton steps, it has the advantage that no line-searches are needed. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem, close to their central paths. Two types of full-Newton steps are used, feasibility steps and (ordinary) centering steps, respectively. The algorithm starts from strictly feasible iterates of a perturbed pair, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close enough to the central path of the new perturbed pair. The starting point depends on a positive number ζ. The algorithm terminates either by finding an ε-solution or by detecting that the primal-dual problem pair has no optimal solution (X ^*,y ^*,S ^*) with vanishing duality gap such that the eigenvalues of X ^* and S ^* do not exceed ζ. The iteration bound coincides with the currently best iteration bound for semidefinite optimization problems.     

A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over

In this paper, the multi-item, single-level, capacitated, dynamic lot sizing problem with set-up carry-over and backlogging, abbreviated to CLSP⁺, is considered. The problem is formulated as a mixed integer programming problem. A heuristic method consisting of four elements: (1) a demand shifting rule, (2) lot size determination rules, (3) checking feasibility conditions and (4) set-up carry-over determination, provides us with an initial feasible solution. The resulting feasible solution is improved by adopting the corresponding set-up and set-up carry-over schedule and re-optimizing it by solving a minimum-cost network flow problem. Then the improved solution is used as a starting solution for a tabu search procedure, with the value of moves assessed using the same minimum-cost network problem. Computational results on randomly generated problems show that the algorithm, which is coded in C++, is able to provide optimal solutions or solutions extremely close to optimal. The computational efficiency makes it possible to solve reasonably large problem instances routinely on a personal computer.     

Reducing quadratic programming problem to regression problem: Stepwise algorithm

Quadratic programming is concerned with minimizing a convex quadratic function subject to linear inequality constraints. The variables are assumed to be nonnegative. The unique solution of quadratic programming (QP) problem (QPP) exists provided that a feasible region is non-empty (the QP has a feasible space).A method for searching for the solution to a QP is provided on the basis of statistical theory. It is shown that QPP can be reduced to an appropriately formulated least squares (LS) problem (LSP) with equality constraints and nonnegative variables. This approach allows us to obtain a simple algorithm to solve QPP. The applicability of the suggested method is illustrated with numerical examples.     

Two-stage fuzzy production planning expected value model and its approximation method

This work develops a novel two-stage fuzzy optimization method for solving the multi-product multi-period (MPMP) production planning problem, in which the market demands and some of the inventory costs are assumed to be uncertainty and characterized by fuzzy variables with known possibility distributions. Some basic properties about the MPMP production planning problem are discussed. Since the fuzzy market demands and inventory costs usually have infinite supports, the proposed two-stage fuzzy MPMP production planning problem is an infinite-dimensional optimization problem that cannot be solved directly by conventional numerical solution methods. To overcome this difficulty, this paper adopts an approximation method (AM) to turn the original two-stage fuzzy MPMP production planning problem into a finite-dimensional optimization problem. The convergence about the AM is discussed to ensure the solution quality. After that, we design a heuristic algorithm, which combines the AM and simulated annealing (SA) algorithm, to solve the proposed two-stage fuzzy MPMP production planning problem. Finally, one real case study about a furniture manufacturing company is presented to illustrate the effectiveness and feasibility of the proposed modeling idea and designed algorithm.     

Finite dimensional approximation in infinite dimensional mathematical programming

We consider the problem of approximating an optimal solution to a separable, doubly infinite mathematical program (P) with lower staircase structure by solutions to the programs (P(N)) obtained by truncating after the firstN variables andN constraints of (P). Viewing the surplus vector variable associated with theNth constraint as a state, and assuming that all feasible states are eventually reachable from any feasible state, we show that the efficient set of all solutions optimal to all possible feasible surplus states for (P(N)) converges to the set of optimal solutions to (P). A tie-breaking algorithm which selects a nearest-point efficient solution for (P(N)) is shown (for convex programs) to converge to an optimal solution to (P). A stopping rule is provided for discovering a value ofN sufficiently large to guarantee any prespecified level of accuracy. The theory is illustrated by an application to production planning.The work of Robert L. Smith was partially supported by the National Science Foundation under Grant ECS-8700836.     

AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM

A globally convergent infeasible-interior-point predictor-corrector algorithm is presented for the second-order cone programming （SOCP） by using the Alizadeh- Haeberly-Overton （AHO） search direction. This algorithm does not require the feasibility of the initial points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an -approximate solution of an SOCP in at most O（√n ln（ε0/ε）） iterations. The iteration-complexity bound of our algorithm is almost the same as the best known bound of feasible interior point algorithms for the SOCP.