Search

The problem of finding a best approximation pair of two sets, which in turn generalizes the well known convex feasibility problem, has a long history that dates back to work by Cheney and Goldstein in 1959. In 2018, Aharoni, Censor, and Jiang revisited this problem and proposed an algorithm that can be used when the two sets are finite intersections of halfspaces. Motivated by their work, we present alternative algorithms that utilize projection and proximity operators. Our modeling framework is able to accommodate even convex sets. Numerical experiments indicate that these methods are competitive and sometimes superior to the one proposed by Aharoni et al.

In this work, we develop a systematic framework for computing the resolvent of the sum of two or more monotone operators which only activates each operator in the sum individually. The key tool in the development of this framework is the notion of the “strengthening” of a set-valued operator, which can be viewed as a type of regularisation that preserves computational tractability. After deriving a number of iterative schemes through this framework, we demonstrate their application to best approximation problems, image denoising and elliptic PDEs. FJAA and RC were partially supported by the Ministry of Science, Innovation and Universities of Spain and the European Regional Development Fund (ERDF) of the European Commission, Grant PGC2018-097960-B-C22. MKT is supported in part by ARC grant DE200100063.

In this paper we address game theory problems arising in the context of network security. In traditional game theory problems, given a defender and an attacker, one searches for mixed strategies which minimize a linear payoff functional. In the problems addressed in this paper an additional quadratic term is added to the minimization problem. Such term represents switching costs, i.e., the costs for the defender of switching from a given strategy to another one at successive rounds of a Nash game. The resulting problems are nonconvex QP ones with linear constraints and turn out to be very challenging. We will show that the most recent approaches for the minimization of nonconvex QP functions over polytopes, including commercial solvers such as and , are unable to solve to optimality even test instances with $$n=50$$ n = 50 variables. For this reason, we propose to extend with them the current benchmark set of test instances for QP problems. We also present a spatial branch-and-bound approach for the solution of these problems, where a predominant role is played by an optimality-based domain reduction, with multiple solutions of LP problems at each node of the branch-and-bound tree. Of course, domain reductions are standard tools in spatial branch-and-bound approaches. However, our contribution lies in the observation that, from the computational point of view, a rather aggressive application of these tools appears to be the best way to tackle the proposed instances. Indeed, according to our experiments, while they make the computational cost per node high, this is largely compensated by the rather slow growth of the number of nodes in the branch-and-bound tree, so that the proposed approach strongly outperforms the existing solvers for QP problems.

The main focus in this paper is exact linesearch methods for minimizing a quadratic function whose Hessian is positive definite. We give a class of limited-memory quasi-Newton Hessian approximations which generate search directions parallel to those of the BFGS method, or equivalently, to those of the method of preconditioned conjugate gradients. In the setting of reduced Hessians, the class provides a dynamical framework for the construction of limited-memory quasi-Newton methods. These methods attain finite termination on quadratic optimization problems in exact arithmetic. We show performance of the methods within this framework in finite precision arithmetic by numerical simulations on sequences of related systems of linear equations, which originate from the CUTEst test collection. In addition, we give a compact representation of the Hessian approximations in the full Broyden class for the general unconstrained optimization problem. This representation consists of explicit matrices and gradients only as vector components.

The Karush-Kuhn-Tucker and value function (lower-level value function, to be precise) reformulations are the most common single-level transformations of the bilevel optimization problem. So far, these reformulations have either been studied independently or as a joint optimization problem in an attempt to take advantage of the best properties from each model. To the best of our knowledge, these reformulations have not yet been compared in the existing literature. This paper is a first attempt towards establishing whether one of these reformulations is best at solving a given class of the optimistic bilevel optimization problem. We design a comparison framework, which seems fair, considering the theoretical properties of these reformulations. This work reveals that although none of the models seems to particularly dominate the other from the theoretical point of view, the value function reformulation seems to numerically outperform the Karush-Kuhn-Tucker reformulation on a Newton-type algorithm. The computational experiments here are mostly based on test problems from the Bilevel Optimization LIBrary (BOLIB)., 33 pages, 4 figures

We consider an $\ell_0$-minimization problem where $f(x) + \gamma \|x\|_0$ is minimized over a polyhedral set and the $\ell_0$-norm regularizer implicitly emphasizes sparsity of the solution. Such a setting captures a range of problems in image processing and statistical learning. Given the nonconvex and discontinuous nature of this norm, convex regularizers are often employed as substitutes. Therefore, far less is known about directly solving the $\ell_0$-minimization problem. Inspired by [19], we consider resolving an equivalent formulation of the $\ell_0$-minimization problem as a mathematical program with complementarity constraints (MPCC) and make the following contributions towards the characterization and computation of its KKT points: (i) First, we show that feasible points of this formulation satisfy the relatively weak Guignard constraint qualification. Furthermore, under the suitable convexity assumption on $f(x)$, an equivalence is derived between first-order KKT points and local minimizers of the MPCC formulation. (ii) Next, we apply two alternating direction method of multiplier (ADMM) algorithms to exploit special structure of the MPCC formulation: (ADMM$_{\rm cf}^{\mu, \alpha, \rho}$) and (ADMM$_{\rm cf}$). These two ADMM schemes both have tractable subproblems. Specifically, in spite of the overall nonconvexity, we show that the first of the ADMM updates can be effectively reduced to a closed-form expression by recognizing a hidden convexity property while the second necessitates solving a convex program. In (ADMM$_{\rm cf}^{\mu, \alpha, \rho}$), we prove subsequential convergence to a perturbed KKT point under mild assumptions. Our preliminary numerical experiments suggest that the tractable ADMM schemes are more scalable than their standard counterpart and ADMM$_{\rm cf}$ compares well with its competitors to solve the $\ell_0$-minimization problem., Comment: 47 pages, 3 tables

This paper presents new Riemannian conjugate gradient methods and global convergence analyses under the strong Wolfe conditions. The main idea of the new methods is to combine the good global convergence properties of the Dai-Yuan method with the efficient numerical performance of the Hestenes-Stiefel method. The proposed methods compare well numerically with the existing methods for the Rayleigh quotient minimization problem on the unit sphere. Numerical comparisons show that they perform better than the existing ones., Comment: 17 pages, 2 figures and 2 tables

The problem of recovering acoustic sources, more specifically monopoles, from point-wise measurements of the corresponding acoustic pressure at a limited number of frequencies is addressed. To this purpose, a family of sparse optimization problems in measure space in combination with the Helmholtz equation on a bounded domain is considered. A weighted norm with unbounded weight near the observation points is incorporated into the formulation. Optimality conditions and conditions for recovery in the small noise case are discussed, which motivates concrete choices of the weight. The numerical realization is based on an accelerated conditional gradient method in measure space and a finite element discretization.

Euclidean distance matrix optimization with ordinal constraints (EDMOC) has found important applications in sensor network localization and molecular conformation. It can also be viewed as a matrix formulation of multidimensional scaling, which is to embed n points in a $r$-dimensional space such that the resulting distances follow the ordinal constraints. The ordinal constraints, though proved to be quite useful, may result in only zero solution when too many are added, leaving the feasibility of EDMOC as a question. In this paper, we first study the feasibility of EDMOC systematically. We show that if $r\ge n-2$, EDMOC always admits a nontrivial solution. Otherwise, it may have only zero solution. The latter interprets the numerical observations of 'crowding phenomenon'. Next we overcome two obstacles in designing fast algorithms for EDMOC, i.e., the low-rankness and the potential huge number of ordinal constraints. We apply the technique developed to take the low rank constraint as the conditional positive semidefinite cone with rank cut. This leads to a majorization penalty approach. The ordinal constraints are left to the subproblem, which is exactly the weighted isotonic regression, and can be solved by the enhanced implementation of Pool Adjacent Violators Algorithm (PAVA). Extensive numerical results demonstrate {the} superior performance of the proposed approach over some state-of-the-art solvers., 32 pages, 23 figures

This paper considers the efficient minimization of the infinite time average of a stationary ergodic process in the space of a handful of design parameters which affect it. Problems of this class, derived from physical or numerical experiments which are sometimes expensive to perform, are ubiquitous in engineering applications. In such problems, any given function evaluation, determined with finite sampling, is associated with a quantifiable amount of uncertainty, which may be reduced via additional sampling. The present paper proposes a new optimization algorithm to adjust the amount of sampling associated with each function evaluation, making function evaluations more accurate (and, thus, more expensive), as required, as convergence is approached. The work builds on our algorithm for Delaunay-based Derivative-free Optimization via Global Surrogates ($\Delta$-DOGS). The new algorithm, dubbed $\alpha$-DOGS, substantially reduces the overall cost of the optimization process for problems of this important class. Further, under certain well-defined conditions, rigorous proof of convergence to the global minimum of the problem considered is established., Comment: Submitted to Journal of Computational Optimization and Applications

The method of block coordinate gradient descent (BCD) has been a powerful method for large-scale optimization. This paper considers the BCD method that successively updates a series of blocks selected according to a Markov chain. This kind of block selection is neither i.i.d. random nor cyclic. On the other hand, it is a natural choice for some applications in distributed optimization and Markov decision process, where i.i.d. random and cyclic selections are either infeasible or very expensive. By applying mixing-time properties of a Markov chain, we prove convergence of Markov chain BCD for minimizing Lipschitz differentiable functions, which can be nonconvex. When the functions are convex and strongly convex, we establish both sublinear and linear convergence rates, respectively. We also present a method of Markov chain inertial BCD. Finally, we discuss potential applications.

In this paper, we consider the nonconvex quadratically constrained quadratic programming (QCQP) with one quadratic constraint. By employing the conjugate gradient method, an efficient algorithm is proposed to solve QCQP that exploits the sparsity of the involved matrices and solves the problem via solving a sequence of positive definite system of linear equations after identifying suitable generalized eigenvalues. Specifically, we analyze how to recognize hard case (case 2) in a preprocessing step, fixing an error in Sect. 2.2.2 of Pong and Wolkowicz (Comput Optim Appl 58(2):273–322, 2014) which studies the same problem with the two-sided constraint. Some numerical experiments are given to show the effectiveness of the proposed method and to compare it with some recent algorithms in the literature.

We propose a family of spectral gradient methods, whose stepsize is determined by a convex combination of the long Barzilai-Borwein (BB) stepsize and the short BB stepsize. Each member of the family is shown to share certain quasi-Newton property in the sense of least squares. The family also includes some other gradient methods as its special cases. We prove that the family of methods is $R$-superlinearly convergent for two-dimensional strictly convex quadratics. Moreover, the family is $R$-linearly convergent in the any-dimensional case. Numerical results of the family with different settings are presented, which demonstrate that the proposed family is promising., 22 pages, 2figures

Recent several years have witnessed the surge of asynchronous (async-) parallel computing methods due to the extremely big data involved in many modern applications and also the advancement of multi-core machines and computer clusters. In optimization, most works about async-parallel methods are on unconstrained problems or those with block separable constraints. In this paper, we propose an async-parallel method based on block coordinate update (BCU) for solving convex problems with nonseparable linear constraint. Running on a single node, the method becomes a novel randomized primal-dual BCU with adaptive stepsize for multi-block affinely constrained problems. For these problems, Gauss-Seidel cyclic primal-dual BCU needs strong convexity to have convergence. On the contrary, merely assuming convexity, we show that the objective value sequence generated by the proposed algorithm converges in probability to the optimal value and also the constraint residual to zero. In addition, we establish an ergodic $O(1/k)$ convergence result, where $k$ is the number of iterations. Numerical experiments are performed to demonstrate the efficiency of the proposed method and significantly better speed-up performance than its sync-parallel counterpart.

We consider an optimization problem with positively homogeneous functions in its objective and constraint functions. Examples of such positively homogeneous functions include the absolute value function and the $p$-norm function, where $p$ is a positive real number. The problem, which is not necessarily convex, extends the absolute value optimization proposed in [O. L. Mangasarian, Absolute value programming, Computational Optimization and Applications 36 (2007) pp. 43-53]. In this work, we propose a dual formulation that, differently from the Lagrangian dual approach, has a closed-form and some interesting properties. In particular, we discuss the relation between the Lagrangian duality and the one proposed here, and give some sufficient conditions under which these dual problems coincide. Finally, we show that some well-known problems, e.g., sum of norms optimization and the group Lasso-type optimization problems, can be reformulated as positively homogeneous optimization problems., 21 pages

The robust truss topology optimization against the uncertain static external load can be formulated as mixed-integer semidefinite programming. Although a global optimal solution can be computed with a branch-and-bound method, it is very time-consuming. This paper presents an alternative formulation, semidefinite programming with complementarity constraints, and proposes an efficient heuristic. The proposed method is based upon the convex-concave procedure for DC (difference-of-convex) programming. It is shown that the method can often find a practically reasonable truss design within the computational cost of solving some dozen of convex optimization subproblems.

The problem of minimizing the rank of a symmetric positive semidefinite matrix subject to constraints can be cast equivalently as a semidefinite program with complementarity constraints (SDCMPCC). The formulation requires two positive semidefinite matrices to be complementary. This is a continuous and nonconvex reformulation of the rank minimization problem. We investigate calmness of locally optimal solutions to the SDCMPCC formulation and hence show that any locally optimal solution is a KKT point. We develop a penalty formulation of the problem. We present calmness results for locally optimal solutions to the penalty formulation. We also develop a proximal alternating linearized minimization (PALM) scheme for the penalty formulation, and investigate the incorporation of a momentum term into the algorithm. Computational results are presented.

We present a novel randomized block coordinate descent method for the minimization of a convex composite objective function. The method uses (approximate) partial second-order (curvature) information, so that the algorithm performance is more robust when applied to highly nonseparable or ill conditioned problems. We call the method Flexible Coordinate Descent (FCD). At each iteration of FCD, a block of coordinates is sampled randomly, a quadratic model is formed about that block and the model is minimized \emph{approximately/inexactly} to determine the search direction. An inexpensive line search is then employed to ensure a monotonic decrease in the objective function and acceptance of large step sizes. We present several high probability iteration complexity results to show that convergence of FCD is guaranteed theoretically. Finally, we present numerical results on large-scale problems to demonstrate the practical performance of the method., Comment: 31 pages, 24 figures

We consider general nonlinear programming problems with cardinality constraints. By relaxing the binary variables which appear in the natural mixed-integer programming formulation, we obtain an almost equivalent nonlinear programming problem, which is thus still difficult to solve. Therefore, we apply a Scholtes-type regularization method to obtain a sequence of easier to solve problems and investigate the convergence of the obtained KKT points. We show that such a sequence converges to an S-stationary point, which corresponds to a local minimizer of the original problem under the assumption of convexity. Additionally, we consider portfolio optimization problems where we minimize a risk measure under a cardinality constraint on the portfolio. Various risk measures are considered, in particular Value-at-Risk and Conditional Value-at-Risk under normal distribution of returns and their robust counterparts under moment conditions. For these investment problems formulated as nonlinear programming problems with cardinality constraints we perform a numerical study on a large number of simulated instances taken from the literature and illuminate the computational performance of the Scholtes-type regularization method in comparison to other considered solution approaches: a mixed-integer solver, a direct continuous reformulation solver and the Kanzow-Schwartz regularization method, which has already been applied to Markowitz portfolio problems., 23 pages, 4 figures

We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which in turn leads to a class of tractable, semidefinite-based approximations that are at least as strong as the affine policy. We investigate several examples from the literature demonstrating that our tractable approximations significantly improve the affine policy. In particular, our approach solves exactly in polynomial time a class of instances of increasing size for which the affine policy admits an arbitrarily large gap., Comment: 30 pages and 2 tables

Block Coordinate Update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primal-dual BCU method for solving linearly constrained convex program in multi-block variables. The method is an accelerated version of a primal-dual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes an $O(1/t)$ convergence rate under weak convexity assumption. We show that the rate can be accelerated to $O(1/t^2)$ if the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can be modified to achieve a linear rate of convergence. The numerical experiments show that the accelerated method performs stably with a single set of parameters while the original method needs to tune the parameters for different datasets in order to achieve a comparable level of performance., Accepted to Computational Optimization and Applications

A general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed by Scheinberg and Tang (Math Program 160:495–529, 2016) and a sublinear global convergence rate has been established. In this paper, we analyze the global convergence rate of this method, in the both exact and inexact settings, in the case when the objective function is strongly convex. We also investigate a practical variant of this method by establishing a simple stopping criterion for the subproblem optimization. Furthermore, we consider an accelerated variant, based on FISTA of Beck and Teboulle (SIAM 2:183–202, 2009), to the proximal quasi-Newton algorithm. Jiang et al. (SIAM 22:1042–1064, 2012) considered a similar accelerated method, where the convergence rate analysis relies on very strong impractical assumptions on Hessian estimates. We present a modified analysis while relaxing these assumptions and perform a numerical comparison of the accelerated proximal quasi-Newton algorithm and the regular one. Our analysis and computational results show that acceleration may not bring any benefit in the quasi-Newton setting.

We study a Lagrangian decomposition algorithm recently proposed by Dan Bienstock and Mark Zuckerberg for solving the LP relaxation of a class of open pit mine project scheduling problems. In this study we show that the Bienstock---Zuckerberg (BZ) algorithm can be used to solve LP relaxations corresponding to a much broader class of scheduling problems, including the well-known Resource Constrained Project Scheduling Problem (RCPSP), and multi-modal variants of the RCPSP that consider batch processing of jobs. We present a new, intuitive proof of correctness for the BZ algorithm that works by casting the BZ algorithm as a column generation algorithm. This analysis allows us to draw parallels with the well-known Dantzig---Wolfe decomposition (DW) algorithm. We discuss practical computational techniques for speeding up the performance of the BZ and DW algorithms on project scheduling problems. Finally, we present computational experiments independently testing the effectiveness of the BZ and DW algorithms on different sets of publicly available test instances. Our computational experiments confirm that the BZ algorithm significantly outperforms the DW algorithm for the problems considered. Our computational experiments also show that the proposed speed-up techniques can have a significant impact on the solve time. We provide some insights on what might be explaining this significant difference in performance.

In this paper we present a new iterative projection method for finding the closest point in the intersection of convex sets to any arbitrary point in a Hilbert space. This method, termed AAMR for averaged alternating modified reflections, can be viewed as an adequate modification of the Douglas–Rachford method that yields a solution to the best approximation problem. Under a constraint qualification at the point of interest, we show strong convergence of the method. In fact, the so-called strong CHIP fully characterizes the convergence of the AAMR method for every point in the space. We report some promising numerical experiments where we compare the performance of AAMR against other projection methods for finding the closest point in the intersection of pairs of finite dimensional subspaces. This work was partially supported by MINECO of Spain and ERDF of EU, Grant MTM2014-59179-C2-1-P. F.J. Aragón Artacho was supported by the Ramón y Cajal program by MINECO of Spain and ERDF of EU (RYC-2013-13327) and R. Campoy was supported by MINECO of Spain and ESF of EU (BES-2015-073360) under the program “Ayudas para contratos predoctorales para la formación de doctores 2015”.

Computing explicitly the $$\varepsilon $$ź-subdifferential of a proper function amounts to computing the level set of a convex function namely the conjugate minus a linear function. The resulting theoretical algorithm is applied to the the class of (convex univariate) piecewise linear---quadratic functions for which existing numerical libraries allow practical computations. We visualize the results in a primal, dual, and subdifferential views through several numerical examples. We also provide a visualization of the BrOndsted---Rockafellar theorem.

In this paper, we consider a class of $n$-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.

We propose the use of controlled perturbations to address the challenging question of optimal active-set prediction for interior point methods. Namely, in the context of linear programming, we consider perturbing the inequality constraints/bounds so as to enlarge the feasible set. We show that if the perturbations are chosen appropriately, the solution of the original problem lies on or close to the central path of the perturbed problem. We also find that a primal-dual path-following algorithm applied to the perturbed problem is able to accurately predict the optimal active set of the original problem when the duality gap for the perturbed problem is not too small; furthermore, depending on problem conditioning, this prediction can happen sooner than predicting the active set for the perturbed problem or when the original one is solved. Encouraging preliminary numerical experience is reported when comparing activity prediction for the perturbed and unperturbed problem formulations., Second revision; 37 pages including appendices, 11 figures, submitted for publication

This article describes a new Riemannian conjugate gradient method and presents a global convergence analysis. The existing Fletcher-Reeves-type Riemannian conjugate gradient method is guaranteed to be globally convergent if it is implemented with the strong Wolfe conditions. On the other hand, the Dai-Yuan-type Euclidean conjugate gradient method generates globally convergent sequences under the weak Wolfe conditions. This article deals with a generalization of Dai-Yuan's Euclidean algorithm to a Riemannian algorithm that requires only the weak Wolfe conditions. The global convergence property of the proposed method is proved by means of the scaled vector transport associated with the differentiated retraction. The results of numerical experiments demonstrate the effectiveness of the proposed algorithm., Comment: 16 pages

In this paper, we consider the tensor generalized eigenvalue complementarity problem (TGEiCP), which is an interesting generalization of matrix eigenvalue complementarity problem (EiCP). First, we given an affirmative result showing that TGEiCP is solvable and has at least one solution under some reasonable assumptions. Then, we introduce two optimization reformulations of TGEiCP, thereby beneficially establishing an upper bound of cone eigenvalues of tensors. Moreover, some new results concerning the bounds of number of eigenvalues of TGEiCP further enrich the theory of TGEiCP. Last but not least, an implementable projection algorithm for solving TGEiCP is also developed for the problem under consideration. As an illustration of our theoretical results, preliminary computational results are reported., Comment: 26 pages, 2 figures, 3 tables