Abstract: We present model development and numerical solution approaches to the problem of packing a general set of ellipses without overlaps into an optimized polygon. Specifically, for a given set of ellipses, and a chosen integer m ≥ 3, we minimize the apothem of the regular m-polygon container. Our modeling and solution strategy is based on the concept of embedded Lagrange multipliers. To solve models with up to n ≤ 10 ellipses, we use the LGO solver suite for global–local nonlinear optimization. In order to reduce increasing runtimes, for model instances with 10 ≤ n ≤ 20 ellipses, we apply local search launching the Ipopt solver from selected random starting points. The numerical results demonstrate the applicability of our modeling and optimization approach to a broad class of highly non-convex ellipse packing problems, by consistently returning good quality feasible solutions in all (231) illustrative model instances considered here. PubDate: 2019-10-01

Abstract: A novel power penalty method is proposed to solve a nonlinear obstacle problem with nonlinear constraints arising from the discretization of an infinite-dimensional optimization problem. This approach is based on the formulation of a penalty equation approximating the mixed nonlinear complementarity problem arising from the Karush–Kuhn–Tucker conditions of the optimization problem. We show that the solution to the penalty equation converges to that of the complementarity problem with an exponential convergence rate depending on the parameters used in the penalty equation. Numerical experiments are performed to confirm the theoretical convergence rate established. PubDate: 2019-10-01

Abstract: In this paper we study the portfolio selection problem of an agent who has a bliss point of consumption and does not tolerate a decline in consumption. We show that the optimal consumption process exhibits ratcheting and, as time elapses, the agent’s consumption approaches but never reaches the bliss level and her/his optimal investment in the risky asset approaches zero if the initial wealth level is not sufficient to maintain it. We use the martingale method and study the dual problem, which is similar to an incremental irreversible investment problem. We transform the dual problem into an optimal stopping problem, which has the same characteristic as finding the optimal exercise time of a perpetual American put option. We recover the value function by establishing a duality relationship and obtain a closed-form solution for the optimal consumption and portfolio strategy. PubDate: 2019-10-01

Abstract: In this paper, a new derivative-free method for Worst Case Analysis (WCA) of circuit design is defined. A WCA of a device can be performed by solving a particular minimization problem where the objective function values are obtained by a simulation code and where some variables are subject to a spherical constraint and others to box constraints. In order to efficiently tackle such a problem, the paper defines a new DF algorithm which follows a two blocks Gauss Seidel approach, namely it alternates an approximated minimization with respect to the variables subject to the spherical constraint with an approximated minimization respect to the variables subject to the box constraints. The algorithm is described and its global convergence properties are analyzed. Furthermore it is tested in the WCA of a MOSFET operational amplifier and its computational behaviour is compared with the one of the efficient optimization tool of the WiCkeD suite for circuit analysis. The obtained results seem to indicate that the proposed algorithm is promising in terms of average efficiency, accuracy and robustness. PubDate: 2019-10-01

Abstract: For given integers k, n, r we aim at families of k sub-cliques called blocks, of a clique with n vertices, such that every block has r vertices, and the blocks together cover a maximum number of edges. We demonstrate a combinatorial optimization method that generates such optimal partial clique edge coverings. It takes certain packages of columns (corresponding to vertices) in the incidence matrix of the blocks, considers the number of uncovered edges as an energy term that has to be minimized by transforming these packages. As a proof of concept we can completely solve the above maximization problem in the case of \(k\le 4\) blocks and obtain optimal coverings for all integers n and r with \(r/n\ge 5/9\) . This generalizes known results for total coverings to partial coverings. The method as such is not restricted to \(k\le 4\) blocks, but a challenge for further research (also on total coverings) is to limit the case distinctions when more blocks are involved. PubDate: 2019-10-01

Abstract: In this paper we consider the problem of packing a fixed number of identical circles inside the unit circle container, where the packing is complicated by the presence of fixed size circular prohibited areas. Here the objective is to maximise the radius of the identical circles. We present a heuristic for the problem based upon formulation space search. Computational results are given for six test problems involving the packing of up to 100 circles. One test problem has a single prohibited area made up from the union of circles of different sizes. Four test problems are annular containers, which have a single inner circular prohibited area. One test problem has circular prohibited areas that are disconnected. PubDate: 2019-10-01

Abstract: For most optimisation methods an essential assumption is the vector space structure of the feasible set. This condition is not fulfilled if we consider optimisation problems over the sphere. We present an algorithm for solving a special global problem over the sphere, namely the determination of Fréchet means, which are points minimising the mean distance to a given set of points. The Branch and Bound method derived needs no further assumptions on the input data, but is able to cope with this objective function which is neither convex nor differentiable. The algorithm’s performance is tested on simulated and real data. PubDate: 2019-10-01

Abstract: The tree \(t^*\) -spanner problem is an NP-hard problem, which is concerned with finding a spanning tree in a given undirected weighted graph, such that for each pair of nodes the ratio of the shortest distance in the spanning tree and the shortest distance in the given graph is bounded by t. The goal is to find a spanning tree, which gives the minimal t. This problem is associated with many network design applications, but in particular, in the context of architecture of distributed systems. We introduce mixed-integer programming formulations for the tree \(t^*\) -spanner problem, and present a branch-and-cut solution approach based on these formulations. The branch-and-cut is enhanced with an initialization procedure and a primal heuristic. A computational study is done to assess the effectiveness of our proposed algorithmic strategies. To the best of our knowledge, this is the first time that an exact approach is proposed for this problem. PubDate: 2019-10-01

Abstract: In this paper, we study asymptotic behaviors of semidefinite programming with a covariance perturbation. We obtain some moderate deviations, Cramér-type moderate deviations and a law of the iterated logarithm of estimates of the respective optimal value and optimal solutions when the covariance matrix is estimated by its sample covariance. As an example, we also apply the main results to the Minimum Trace factor Analysis. PubDate: 2019-10-01

Abstract: We study online scheduling on two uniform machines in the MapReduce system. Each job consists of two sets of tasks, namely the map tasks and reduce tasks. A job’s reduce tasks can only be processed after all its map tasks are finished. The map tasks are fractional, i.e., they can be arbitrarily split and processed on different machines in parallel. Our goal is to find a schedule that minimizes the makespan. We consider two variants of the problem, namely the cases involving preemptive reduce tasks and non-preemptive reduce tasks. We provide lower bounds for both variants. For preemptive reduce tasks, we present an optimal online algorithm with a competitive ratio of \(\frac{\sqrt{s^{2}+2s+5}+1-s}{2}\) , where \(s\ge 1\) is the ratio between the speeds of the two machines. For non-preemptive reduce tasks, we show that the \({ LS}\) -like algorithm is optimal and its competitive ratio is \(\frac{2s+1}{s+1}\) if \(s<\frac{1+\sqrt{5}}{2}\) and \(\frac{s+1}{s}\) if \(s\ge \frac{1+\sqrt{5}}{2}\) . PubDate: 2019-10-01

Abstract: We study the covering-type k-violation linear program where at most k of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple \((k+1)\) -approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the LP relaxation is \(k+1\) . This implies we can not get better approximation algorithms when we use the LP-relaxation as a lower bound of the optimal value. PubDate: 2019-10-01

Abstract: Although several classes of cutting plane methods for deterministically solving disjoint bilinear programming (DBLP) have been proposed, the frequently encountered computational issue regarding the generation of a suitable cut from a degenerate vertex in a pseudo-global minimizer (PGM) still remains. Among the approaches to dealing with degeneracy, the most recent one is to generate a conservative cut. Nevertheless, the computational performance of the corresponding distance-following algorithm for its location seems far from satisfactory. This paper proposes several approaches that can be utilized to efficiently locate a conservative hyperplane from a degenerate vertex in a PGM. Extensive experiments are conducted to evaluate their performance from the dimensionality as well as the degree of degeneracy. From the computational viewpoint, these new approaches can outperform the earlier developed distance-following algorithm, and thereby can be incorporated into cutting plane methods for solving DBLP. PubDate: 2019-10-01

Abstract: This paper proposes a new second-order cone programming (SOCP) relaxation for convex quadratic programs with linear complementarity constraints. The new SOCP relaxation is derived by exploiting the technique that two positive semidefinite matrices can be simultaneously diagonalizable, and is proved to be at least as tight as the classical SOCP relaxation and virtually it can be tighter. We also prove that the proposed SOCP relaxation is equivalent to the semidefinite programming (SDP) relaxation when the objective function is strictly convex. Then an effective branch-and-bound algorithm is designed to find a global optimal solution. Numerical experiments indicate that the proposed SOCP relaxation based branch-and-bound algorithm spends less computing time than the SDP relaxation based branch-and-bound algorithm on condition that the rank of the quadratic objective function is large. The superiority is highlighted when solving the strictly convex quadratic program with linear complementarity constraints. PubDate: 2019-10-01

Abstract: This paper presents a mixed-integer quadratic programming formulation of an existing data-driven approach to computational elasticity. This formulation is suitable for application of a standard mixed-integer programming solver, which finds a global optimal solution. Therefore, the results obtained by the presented method can be used as benchmark instances for any other algorithm. Preliminary numerical experiments are performed to compare quality of solutions obtained by the proposed method and a heuristic conventionally used in the data-driven computational mechanics. PubDate: 2019-10-01

Abstract: In this paper, we first introduce the notion of cooperative equilibria for population games and prove its existence theorem by Proposition 2 in Kajii (J Econ Theory 56:194–205, 1992). We next identify a residual dense subclass of population games whose cooperative equilibria are all essential. Moreover, we show the existence of essential components of the cooperative equilibrium set by proving the connectivity of minimal essential sets of the cooperative equilibrium set. PubDate: 2019-10-01

Abstract: In this paper, we assign to each extended real-valued function f on a linear space a translative function which is generated by the epigraph of f and called the epitranslative function of f. Relationships between the properties of both functions are investigated. The results are applied to characterize continuity and Lipschitz continuity of f by its epigraph. Furthermore, an epitranslative function is used to derive a formula for the epigraph of the inf-convolution. The basis for the study is established by statements on Gerstewitz functionals and on the directional closure of sets. PubDate: 2019-10-01

Abstract: In this note, we show that the singular value condition \(\sigma _{\max }(B) < \sigma _{\min }(A)\) leads to the unique solvability of the absolute value equation \(Ax + B x = b\) for any b. This result is superior to those appeared in previously published works by Rohn (Optim Lett 3:603–606, 2009). PubDate: 2019-09-12

Abstract: This works investigates a conceptual algorithm for computing critical points of nonsmooth nonconvex optimization problems whose objective function is the sum of two locally Lipschitzian (component) functions. We show that upon additional assumptions on the component functions and or feasible set, the given algorithm extends several well-known optimization methods. PubDate: 2019-09-11

Abstract: A subset S of vertices in a graph G is called a resolving set for G if for arbitrary two distinct vertices \(u, v\in V\) , there exists a vertex x from S such that the distances \(d(u, x)\ne d(v, x)\) . The metric dimension of G is the minimum cardinality of a resolving set of G. A minimal resolving set is a resolving set which has no proper subsets that are resolving sets. Let \(\Box _{n}\) denote the folded n-cube. In this paper, we consider the metric dimension of \(\Box _{n}\) . By constructing explicitly minimal resolving sets for \(\Box _{n}\) , we obtain upper bounds on the metric dimension of this graph. PubDate: 2019-09-09