On the sum of distances along a circle

The arc distance between two points on a circle is their geodesic distance along the circle. We study the sum of the arc distances determined by n points on a circle, which is a useful measure of the evenness of scales and rhythms in music theory. We characterize the configurations with the maximum sum of arc distances by a balanced condition: for each line that goes through the circle center and touches no point, the numbers of points on each side of the line differ by at most one. When the points are restricted to lattice positions on a circle, we show that Toussaint's snap heuristic finds an optimal configuration. We derive closed-form formulas for the maximum sum of arc distances when the points are either allowed to move continuously on the circle or restricted to lattice positions. We also present a linear-time algorithm for computing the sum of arc distances when the points are presorted by the polar coordinates.     

Approximate KKT points and a proximity measure for termination

Karush–Kuhn–Tucker (KKT) optimality conditions are often checked for investigating whether a solution obtained by an optimization algorithm is a likely candidate for the optimum. In this study, we report that although the KKT conditions must all be satisfied at the optimal point, the extent of violation of KKT conditions at points arbitrarily close to the KKT point is not smooth, thereby making the KKT conditions difficult to use directly to evaluate the performance of an optimization algorithm. This happens due to the requirement of complimentary slackness condition associated with KKT optimality conditions. To overcome this difficulty, we define modified ${\epsilon}$ -KKT points by relaxing the complimentary slackness and equilibrium equations of KKT conditions and suggest a KKT-proximity measure, that is shown to reduce sequentially to zero as the iterates approach the KKT point. Besides the theoretical development defining the modified ${\epsilon}$ -KKT point, we present extensive computer simulations of the proposed methodology on a set of iterates obtained through an evolutionary optimization algorithm to illustrate the working of our proposed procedure on smooth and non-smooth problems. The results indicate that the proposed KKT-proximity measure can be used as a termination condition to optimization algorithms. As a by-product, the method helps to find Lagrange multipliers correspond to near-optimal solutions which can be of importance to practitioners. We also provide a comparison of our KKT-proximity measure with the stopping criterion used in popular commercial softwares.     

A regularized point cloud registration approach for orthogonal transformations

An important part of the well-known iterative closest point algorithm (ICP) is the variational problem. Several variants of the variational problem are known, such as point-to-point, point-to-plane, generalized ICP, and normal ICP (NICP). This paper proposes a closed-form exact solution for orthogonal registration of point clouds based on the generalized point-to-point ICP algorithm. We use points and normal vectors to align 3D point clouds, while the common point-to-point approach uses only the coordinates of points. The paper also presents a closed-form approximate solution to the variational problem of the NICP. In addition, the paper introduces a regularization approach and proposes reliable algorithms for solving variational problems using closed-form solutions. The performance of the algorithms is compared with that of common algorithms for solving variational problems of the ICP algorithm. The proposed paper is significantly extended version of Makovetskii et al. (CCIS 1090, 217–231, 2019).

     

Stabilized SQP revisited

The stabilized version of the sequential quadratic programming algorithm (sSQP) had been developed in order to achieve superlinear convergence in situations when the Lagrange multipliers associated to a solution are not unique. Within the framework of Fischer (Math Program 94:91–124, 2002), the key to local superlinear convergence of sSQP are the following two properties: upper Lipschitzian behavior of solutions of the Karush-Kuhn-Tucker (KKT) system under canonical perturbations and local solvability of sSQP subproblems with the associated primal-dual step being of the order of the distance from the current iterate to the solution set of the unperturbed KKT system. According to Fernández and Solodov (Math Program 125:47–73, 2010), both of these properties are ensured by the second-order sufficient optimality condition (SOSC) without any constraint qualification assumptions. In this paper, we state precise relationships between the upper Lipschitzian property of solutions of KKT systems, error bounds for KKT systems, the notion of critical Lagrange multipliers (a subclass of multipliers that violate SOSC in a very special way), the second-order necessary condition for optimality, and solvability of sSQP subproblems. Moreover, for the problem with equality constraints only, we prove superlinear convergence of sSQP under the assumption that the dual starting point is close to a noncritical multiplier. Since noncritical multipliers include all those satisfying SOSC but are not limited to them, we believe this gives the first superlinear convergence result for any Newtonian method for constrained optimization under assumptions that do not include any constraint qualifications and are weaker than SOSC. In the general case when inequality constraints are present, we show that such a relaxation of assumptions is not possible. We also consider applying sSQP to the problem where inequality constraints are reformulated into equalities using slack variables, and discuss the assumptions needed for convergence in this approach. We conclude with consequences for local regularization methods proposed in (Izmailov and Solodov SIAM J Optim 16:210–228, 2004; Wright SIAM J. Optim. 15:673–676, 2005). In particular, we show that these methods are still locally superlinearly convergent under the noncritical multiplier assumption, weaker than SOSC employed originally.     

A splitting method for quadratic programming problem

1. IntroductionThe quadratic programming (QP) problem is the most simple one in nonlinear pro-gramming and plays a very important role in optimization theory and applications.It is well known that matriX splitting teChniques are widely used for solving large-scalelinear system of equations very successfully. These algorithms generate an infinite sequence,in contrast to the direct algorithms which terminate in a finite number of steps. However,iterative algorithms are considerable simpler tha…     

A note on diameters of point sets

Relationships between the diameter of a set of n points in the plane at mutual distance at least one, the diameter of an equilateral n-gon and the radius of a circle including n unit disks are explored. Upper bounds on the minimal diameter of a point set at mutual distance at least one are presented for up to 30 points.     

Convergence Analysis of a Class of Penalty Methods for Vector Optimization Problems with Cone Constraints

In this paper, we consider convergence properties of a class of penalization methods for a general vector optimization problem with cone constraints in infinite dimensional spaces. Under certain assumptions, we show that any efficient point of the cone constrained vector optimization problem can be approached by a sequence of efficient points of the penalty problems. We also show, on the other hand, that any limit point of a sequence of approximate efficient solutions to the penalty problems is a weekly efficient solution of the original cone constrained vector optimization problem. Finally, when the constrained space is of finite dimension, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original cone constrained vector optimization problem if Mangasarian–Fromovitz constraint qualification holds at the limit point.This work is supported by the Postdoctoral Fellowship of Hong Kong Polytechnic University.     

An efficient Lagrangian smoothing heuristic for Max-Cut

Max-Cut is a famous NP-hard problem in combinatorial optimization. In this article, we propose a Lagrangian smoothing algorithm for Max-Cut, where the continuation subproblems are solved by the truncated Frank-Wolfe algorithm. We establish practical stopping criteria and prove that our algorithm finitely terminates at a KKT point, the distance between which and the neighbour optimal solution is also estimated. Additionally, we obtain a new sufficient optimality condition for Max-Cut. Numerical results indicate that our approach outperforms the existing smoothing algorithm in less time.     

Finding at Least One Point in Each Connected Component of a Real Algebraic Set Defined by a Single Equation

Deciding efficiently the emptiness of a real algebraic set defined by a single equation is a fundamental problem of computational real algebraic geometry. We propose an algorithm for this test. We find, when the algebraic set is non empty, at least one point on each semi-algebraically connected component. The problem is reduced to deciding the existence of real critical points of the distance function and computing them.     

A penalty method for rank minimization problems in symmetric matrices

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.     

Box-constrained multi-objective optimization: A gradient-like method without “a priori” scalarization

The aim of this paper is the development of an algorithm to find the critical points of a box-constrained multi-objective optimization problem. The proposed algorithm is an interior point method based on suitable directions that play the role of gradient-like directions for the vector objective function. The method does not rely on an “a priori” scalarization and is based on a dynamic system defined by a vector field of descent directions in the considered box. The key tool to define the mentioned vector field is the notion of vector pseudogradient. We prove that the limit points of the solutions of the system satisfy the Karush–Kuhn–Tucker (KKT) first order necessary condition for the box-constrained multi-objective optimization problem. These results allow us to develop an algorithm to solve box-constrained multi-objective optimization problems. Finally, we consider some test problems where we apply the proposed computational method. The numerical experience shows that the algorithm generates an approximation of the local optimal Pareto front representative of all parts of optimal front.     

最小最大二点集覆盖问题分析及改进算法设计

本文考虑二中心问题的扩展问题-最小最大二点集覆盖问题。给定两个平面点集P₁和P₂,分别包含m和n个点,求两个圆分别覆盖P₁和P₂,并且要求两圆半径与两圆圆心距三者中的最大值最小。本文主要贡献在于分析半径变化过程中两个点集中心包之间最近距离的变化关系,其中中心包是点集所具有的一个特殊几何结构,所得到的结果改进了Huang等人之前给出的结果,并且通过该结果设计相应算法,所得到的算法复杂性是目前最好的。     

Banach空间中的一类非光滑齐次优化问题

本文主要研究了一类非光滑齐次优化问题(HOP).通过运用Clarke次微分的广义欧拉恒等式获得了使得(HOP)问题的最优解成为KKT点的充分条件并给出了(HOP)问题与(HOP)问题的KKT点及最优解之间的等价刻画.本文的结果是文[1]中已有结果的推广.文中还举例说明了结果的正确性.     

Locating a minisum annulus: a new partial coverage distance model

The problem is to find the best location in the plane of a minisum annulus with fixed width using a partial coverage distance model. Using the concept of partial coverage distance, those demand points within the area of the annulus are served at no cost, while for ‘uncovered’ demand points there will be additional costs proportional to their distances to the annulus. The objective of the problem is to locate the annulus such that the sum of distances from the uncovered demand points to the annulus (covering area) is minimized. The distance is measured by the Euclidean norm. We discuss the case where the radius of the inner circle of the annulus is variable, and prove that at least two demand points must be on the boundary of any optimal annulus. An algorithm to solve the problem is derived based on this result.     

Interpolation of harmonic functions based on Radon projections

We consider an algebraic method for reconstruction of a harmonic function in the unit disk via a finite number of values of its Radon projections. The approach is to seek a harmonic polynomial which matches given values of Radon projections along some chords of the unit circle. We prove an analogue of the famous Marr’s formula for computing the Radon projection of the basis orthogonal polynomials in our setting of harmonic polynomials. Using this result, we show unique solvability for a family of schemes where all chords are chosen at equal distance to the origin. For the special case of chords forming a regular convex polygon, we prove error estimates on the unit circle and in the unit disk. We present an efficient reconstruction algorithm which is robust with respect to noise in the input data and provide numerical examples.     

Lower-Order Penalization Approach to Nonlinear Semidefinite Programming

In this paper, we reformulate a nonlinear semidefinite programming problem into an optimization problem with a matrix equality constraint. We apply a lower-order penalization approach to the reformulated problem. Necessary and sufficient conditions that guarantee the global (local) exactness of the lower-order penalty functions are derived. Convergence results of the optimal values and optimal solutions of the penalty problems to those of the original semidefinite program are established. Since the penalty functions may not be smooth or even locally Lipschitz, we invoke the Ekeland variational principle to derive necessary optimality conditions for the penalty problems. Under certain conditions, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original semidefinite program. Communicated by Y. Zhang This work was supported by a Postdoctoral Fellowship of Hong Kong Polytechnic University and by the Research Grants Council of Hong Kong.     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

On KKT points of Celis-Dennis-Tapia subproblem

The Celis-Dennis-Tapia(CDT) problem is a subproblem of the trust region algorithms for the constrained optimization. CDT subproblem is studied in this paper. It is shown that there exists the KKT point such that the Hessian matrix of the Lagrangian is positive semidefinite, if the multipliers at the global solution are not unique. Next the second order optimality conditions are also given, when the Hessian matrix of Lagrange at the solution has one negative eigenvalue. And furthermore, it is proved that all feasible KKT points satisfying that the corresponding Hessian matrices of Lagrange have one negative eigenvalue are the local optimal solutions of the CDT subproblem.     

A branch and bound algorithm for locating input and output points of departments on the block layout

We consider the problem of locating input and output (I/O) points of each department for a given layout. The objective of the problem is to minimise the total distance of material flows between the I/O points. Here, distances between the I/O points are computed as the lengths of the shortest path (not the rectilinear distances) between the I/O points. We developed a procedure to eliminate dominated candidate positions of I/O points that do not need to be considered. With this procedure, a large number of dominated candidate positions can be eliminated. A linear programming (LP) model for minimising the total rectilinear distance of flows is used to obtain a lower bound. Using the elimination procedure and the LP model, a branch and bound algorithm is developed to find an optimal location of the I/O points. Results from computational experiments show that the suggested algorithm finds optimal solutions in a very short time even for large-sized problems.     

Global Convergence Analysis of Line Search Interior-Point Methods for Nonlinear Programming without Regularity Assumptions

As noted by Wächter and Biegler (Ref. 1), a number of interior-point methods for nonlinear programming based on line-search strategy may generate a sequence converging to an infeasible point. We show that, by adopting a suitable merit function, a modified primal-dual equation, and a proper line-search procedure, a class of interior-point methods of line-search type will generate a sequence such that either all the limit points of the sequence are KKT points, or one of the limit points is a Fritz John point, or one of the limit points is an infeasible point that is a stationary point minimizing a function measuring the extent of violation to the constraint system. The analysis does not depend on the regularity assumptions on the problem. Instead, it uses a set of satisfiable conditions on the algorithm implementation to derive the desired convergence property.Communicated by Z. Q. LuoThis research was partially supported by Grant R-314-000-026/042/057-112 of National University of Singapore and Singapore-MIT Alliance. We thank Professor Khoo Boo Cheong, Cochair of the High Performance Computation Program of Singapore-MIT Alliance, for his support