Computational Optimization and Applications

This paper looks at the task of computing efficient extreme points in multiple objective linear programming. Vector maximization software is reviewed and the ADBASE solver for computing all efficient extreme points of a multiple objective linear program is described. To create MOLP test problems, models for random problem generation are discussed. In the computational part of the paper, the numbers of efficient extreme points possessed by MOLPs (including multiple objective transportation problems) of different sizes are reported. In addition, the way the utility values of the efficient extreme points might be distributed over the efficient set for different types of utility functions is investigated. Not surprisingly, results show that it should be easier to find good near-optimal solutions with linear utility functions than with, for instance, Tchebycheff types of utility functions.

The class of Mesh Adaptive Direct Search (Mads) algorithms is designed for the optimization of constrained black-box problems. The purpose of this paper is to compare instantiations of Mads under different strategies to handle constraints. Intensive numerical tests are conducted from feasible and/or infeasible starting points on three real engineering applications. The three instantiations are Gps, LTMads and OrthoMads. Constraints are handled by the extreme barrier, the progressive barrier, or by a mixture of both. The applications are the optimization of a styrene production process, a MDO mechanical engineering problem, and a well positioning problem, and the codes are publicly available.

In this paper, we introduce a new variant of the BFGS method designed to perform well when gradient measurements are corrupted by noise. We show that treating the secant condition with a penalty method approach motivated by regularized least squares estimation generates a parametric family with the original BFGS update at one extreme and not updating the inverse Hessian approximation at the other extreme. Furthermore, we find the curvature condition is relaxed as the family moves towards not updating the inverse Hessian approximation, and disappears entirely at the extreme where the inverse Hessian approximation is not updated. These developments allow us to develop a method we refer to as Secant Penalized BFGS (SP-BFGS) that allows one to relax the secant condition based on the amount of noise in the gradient measurements. SP-BFGS provides a means of incrementally updating the new inverse Hessian approximation with a controlled amount of bias towards the previous inverse Hessian approximation, which allows one to replace the overwriting nature of the original BFGS update with an averaging nature that resists the destructive effects of noise and can cope with negative curvature measurements. We discuss the theoretical properties of SP-BFGS, including convergence when minimizing strongly convex functions in the presence of uniformly bounded noise. Finally, we present extensive numerical experiments using over 30 problems from the CUTEst test problem set that demonstrate the superior performance of SP-BFGS compared to BFGS in the presence of both noisy function and gradient evaluations.

Consider a nonempty convex set in ℝm which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and “convex cuts” instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/ε) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and ε is the maximum common slack of the original inequality system.

Non-negative matrix factorization (NMF) is a problem to obtain a representation of data using non-negativity constraints. Since the NMF was first proposed by Lee, NMF has attracted much attention for over a decade and has been successfully applied to numerous data analysis problems. Recent years, many variants of NMF have been proposed. Common methods are: iterative multiplicative update algorithms, gradient descent methods, alternating least squares (ANLS). Since alternating least squares has nice optimization properties, various optimization methods can be used to solve ANLS’s subproblems. In this paper, we propose a modified subspace Barzilai-Borwein for subproblems of ANLS. Moreover, we propose a modified strategy for ANLS. Global convergence results of our algorithm are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.

We consider the discretization of an optimal boundary control problem with distributed observation by the boundary concentrated finite element method. If the constraint is a $$H^{1+\delta }(\Omega )$$ regular elliptic PDE with smooth differential operator and source term, we prove for the two dimensional case that the discretization error in the $$L_2$$ norm decreases like $$N^{-\delta }$$ , where $$N$$ is the number of unknowns. Our approach is suitable for solving a wide class of problems, among them piecewise defined data and tracking functionals acting only on a subdomain of $$\Omega $$ . We present several numerical results.

The single facility location problem with demand regions seeks for a facility location minimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g. $$\ell _1$$ or $$\ell _\infty $$ . We develop an exact combinatorial algorithm running in time $$O(n\log ^c n)$$ for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.

Trong công trình này, chúng tôi đề xuất và phân tích các thuật toán kiểu tiến-lùi nhằm tìm một điểm zero của tổng của một số hữu hạn các toán tử đơn điệu, không dựa trên sự giảm thiểu thành một bài toán bao hàm hai toán tử trong không gian tích sản phẩm. Mỗi lần lặp lại của các thuật toán đã được nghiên cứu yêu cầu một lần đánh giá giải pháp cho mỗi toán tử giá trị tập, một lần đánh giá tiến cho mỗi toán tử đồng điệu, và hai lần đánh giá tiến cho mỗi toán tử đơn điệu. Khác với các phương pháp hiện có, cấu trúc của các thuật toán được đề xuất là phù hợp cho việc triển khai phân tán, phi tập trung trong các mạng hình nhẫn mà không cần phải tổng hợp toàn cầu để thực hiện sự đồng thuận giữa các nút.

We prove in this article lower bounds and upper bounds for the interatomic distance in cluster of atoms minimizing the Lennard-Jones energy. Our main result is in dimension three, but we also prove it in the two-dimensional case, since it seems interesting from a theoretical point of view.

Convex programming based robust optimization is an active research topic in the past two decades, partially because of its computational tractability for many classes of optimization problems and uncertainty sets. However, many problems arising from modern operations research and statistical learning applications are nonconvex even in the nominal case, let alone their robust counterpart. In this paper, we introduce a systematic approach for tackling the nonconvexity of the robust optimization problems that is usually coupled with the nonsmoothness of the objective function brought by the worst-case value function. A majorization-minimization algorithm is presented to solve the penalized min-max formulation of the robustified problem that deterministically generates a “better” solution compared with the starting point (that is usually chosen as an unrobustfied optimal solution). A generalized saddle-point theorem regarding the directional stationarity is established and a game-theoretic interpretation of the computed solutions is provided. Numerical experiments show that the computed solutions of the nonconvex robust optimization problems are less sensitive to the data perturbation compared with the unrobustfied ones.