Search

The dual problem of a convex optimization problem can be obtained in a relatively simple and structural way by using a well-known result in convex analysis, namely Fenchel’s duality theorem. This alternative way of forming a strong dual problem is the subject of this paper. We recall some standard results from convex analysis and then discuss how the dual problem can be written in terms of the conjugates of the objective function and the constraint functions. This is a didactically valuable method to explicitly write the dual problem. We demonstrate the method by deriving dual problems for several classical problems and also for a practical model for radiotherapy treatment planning, for which deriving the dual problem using other methods is a more tedious task. Additional material is presented in the appendices, including useful tables for finding conjugate functions of many functions.

Many regions in the world are protected against flooding by a dike, which may be either natural or artificial. We deal with a model for finding the optimal height of such a dike in the future. The model minimizes the sum of investment costs and expected damage costs. It is highly nonlinear, nonconvex, and infinite-dimensional. Despite this, it is shown that the model can be solved analytically. Our model has been used in the Netherlands to define legal safety standards for the coming decades.

We deal with a recently proposed method of Chubanov [A polynomial projection algorithm for linear feasibility problems. Math. Program. 153 (2015), pp. 687–713] for solving linear homogeneous systems with positive variables. Some improvements of Chubanov's method and its analysis are presented. We propose a new and simple cut criterion and show that the cuts defined by the new criterion are at least as sharp as in [1]. The new cut criterion reduces the iteration bound for his Basic Procedure by a factor 5, without changing the order of its strongly polynomial complexity. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses our Modified Basic Procedure as a subroutine. It is shown that it has (Formula presented.) time complexity, just as in [1]. Some promising computational results are presented, in comparison with the optimization package Gurobi.

In the Netherlands, flood protection is a matter of national survival. In 2008, the Second Delta Committee recommended increasing legal flood protection standards at least tenfold to compensate for population and economic growth since 1953; this recommendation would have required dike improvement investments estimated at 11.5 billion euro. Our research group was charged with developing efficient flood protection standards in a more objective way. We used cost-benefit analysis and mixed-integer nonlinear programming to demonstrate the efficiency of increasing the legal standards in three critical regions only. Monte Carlo analysis confirms the robustness of this recommendation. In 2012, the state secretary of the Ministry of Infrastructure and the Environment accepted our results as a basis for legislation. Compared to the earlier recommendation, this successful application of operations research yields both a highly significant increase in protection for these regions (in which two-thirds of the benefits of the proposed improvements accrue) and approximately 7.8 billion euro in cost savings. Our methods can also be used in decision making for other flood-prone areas worldwide.

Dike height optimization is of major importance to the Netherlands because a large part of the country lies below sea level, and high water levels in rivers can cause floods. Recently impovements have been made on the cost-benefit model introduced by van Dantzig after the devastating flood in the Netherlands in 1953. We consider the extension of this model to nonhomogeneous dike rings, which may also be applicable to other deltas in the world. A nonhomogeneous dike ring consists of different segments with different characteristics with respect to flooding and investment costs. The individual segments can be heightened independently at different moments in time and by different amounts, making the problem considerably more complex than the homogeneous case. We show how the problem can be modeled as a mixed-integer nonlinear programming problem, and we present an iterative algorithm that can be used to solve the problem. Moreover, we consider a robust optimization approach to deal with uncertainty in the model parameters. The method has been implemented and integrated in software, which is used by the government to determine how the safety standards in the Dutch Water Act should be changed.

We study a one-parameter family of quadratic maps, which serves as a template for interior point methods. It is known that such methods can exhibit chaotic behavior, but this has been verified only for particular linear optimization problems. Our results indicate that this chaotic behavior is generic., Comment: 10 pages, 6 figures

We deal with a recently proposed method of Chubanov for solving linear homogeneous systems with positive variables. Our first aim is to show that the performance of this method can be improved by a slight modification of Chubanov’s so-called Basic Procedure. In theory this results in at least the same decrease of the merit function used by Chubanov, but both in theory and in practice the decrease may be much faster. Theoretical evidence for the speed-up follows from a lemma, whereas some numerical experiments provide convincing computational evidence. We also present a complete, somewhat simplified analysis of Chubanov’s Main Algorithm, thereby including also some numerical experiments.

A nodal nuclear reactor reload pattern optimization model is solved using mixed-integer nonlinear optimization techniques. Unlike currently used heuristic search methods, this method enables continuous optimization of the amount of Burnable Poisons in fresh fuel bundles in a natural way, which is shown in the first part of the article. The second part treats an algorithmic extension using dedicated cuts in a mixed-integer nonlinear optimization algorithm, which push the optimization towards solutions where local power peaks in parts of the core are avoided.

Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality property of basis tableaus.

We consider the eigenvalue problem in the max-plus algebra for matrices in {−∞∪ R } n×n but with eigenvectors in R n . The problem is relaxed to a linear optimization (LO) problem of which the dual problem is solved by finding a maximal average weight circuit in the graph of the matrix. The Floyd–Warshall procedure is used to find such a circuit. This procedure also provides an efficient algorithm for finding an eigenvector.

In the article titled Central Path and Barrier Algorithms for Linear Programs in this encyclopedia, the main ideas underlying the modern interior-point methods are presented. In these methods the central path plays a crucial role. To start these methods one needs a starting point on or close to the central path. Given such a point, a variant of Newton's method is used to generate a sequence of iterates that converges to an optimal solution of the problem. In this section, we show how to get into the situation that a starting point on the central path is known. This goes via the construction of an artificial problem whose solution either yields an optimal solution for a given problem, or detects that no such solution exists. Keywords: linear optimization; central path; interior-point method; optimal partition; self-dual embedding

In this article, the main ideas underlying the modern interior-point methods are presented. We discuss primal, dual, and primal-dual methods and show that each of these methods can be used to solve a linear optimization problem in polynomial time. It is made clear that the central path plays a crucial role in each of the methods. The described methods require a starting point on or close to the central path. Given such a point, a variant of Newton's method can be used to construct a numerical procedure that generates a sequence of iterates that converges to an optimal solution of the problem. Keywords: linear optimization; central path; interior-point method; barrier function; primal method; primal–dual method; dual method; KKT condition; complexity

In this chapter, we discuss a modification of the standard path-following scheme that tends to speed up the global convergence. This modification, the central region method, generates iterates that do not really trace the central path, or at least not closely. In this way, it has a relatively large freedom of movement, and consequently the ability to take long steps. This makes it interesting to consider more sophisticated search directions. We propose a search direction that is built up in three phases, viz. 1. Initial centering, 2. Predictor, 3. Second order centrality corrector.

In this chapter, we take a careful look at the behavior of the central path, when it approaches the optimal solution set of a semidefinite program. We will demonstrate that the primal-dual central path converges to the analytic center of the optimal solution set. Moreover, the distance to this analytic center from any point on the central path is shown to converge at the same R-rate as the duality gap. This result can be interpreted as an error-bound for solutions on the central path, with respect to the optimal solution set. Underlying the analysis is an assumption that a strictly complementary solution pair for the semidefinite program exists.

In Chapter 3, we have analyzed the iteration complexity of finding an ϵ-optimal solution, if an interior, sufficiently centered pair of primal and dual solutions is known beforehand. We will see in this chapter how we can adapt the algorithms of Chapter 3 to solve semidefinite programming problems without any pre-knowledge. To this end, we use the self-dual embedding technique. This technique will also be used to tackle semidefinite programming problems that may be unbounded, unsolvable, or infeasible.

Modern solvers for linear and quadratic programming often incorporate some variant of the primal-dual path-following method, which is a class of interior point methods. This method turns out to be suited for solving semidefinite programming problems as well. In this chapter, we propose a framework for analyzing primal-dual path-following algorithms for semidefinite programming. Our framework is a direct extension of the v-space approach, which was developed by Kojima et al. [63] in the context of complementarity problems.

In this chapter we describe the optimal set approach for sensitivity analysis for LP. We show that optimal partitions and optimal sets remain constant between two consecutive transition-points of the optimal value function. The advantage of using this approach instead of the classical approach (using optimal bases) is shown. Moreover, we present an algorithm to compute the partitions, optimal sets and the optimal value function. This is a new algorithm and uses primal and dual optimal solutions. We also extend some of the results to parametric quadratic programming, and discuss differences and resemblances with the linear programming case.

This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu's scaled Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine scaling algorithms generates an approximate solution (given a precision (Epsilon)) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial of n, ln(1/(Epsilon)) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen et al., SIAM Journal on Optimization 7 (1997) 126-140..

In this paper we prove the counterintuitive result that the quadratic least squares approximation of a multivariate convex function in a finite set of points is not necessarily convex, even though it is convex for a univariate convex function. This result has many consequences both for the field of statistics and optimization. We show that convexity can be enforced in the multivariate case by using semidefinite programming techniques. Key words: Convex function, least squares, quadratic interpolation, semidefinite programming

Most semidefinite programming algorithms found in the literature require strictly feasible starting points (X° ≻ 0, S° ≻ 0) for the primal and dual problems respectively. So-called ‘big-M’ methods (see e.g. [807]) are often employed in practice to obtain feasible starting points.