Springer Science and Business Media LLC

This paper considers a conceptual version of a convex optimization algorithm which is based on replacing a convex optimization problem with the root-finding problem for the approximate sub-differential mapping which is solved by repeated projection onto the epigraph of conjugate function. Whilst the projection problem is not exactly solvable in finite space-time it can be approximately solved up to arbitrary precision by simple iterative methods, which use linear support functions of the epigraph. It seems therefore useful to study computational characteristics of the idealized version of this algorithm when projection on the epigraph is computed precisely to estimate the potential benefits for such development. The key results of this study are that the conceptual algorithm attains super-linear rate of convergence in general convex case, the rate of convergence becomes quadratic for objective functions forming super-set of strongly convex functions, and convergence is finite when objective function has sharp minimum. In all cases convergence is global and does not require differentiability of the objective.

The main purpose of this article is to address a problem that amalgamates approximation and optimization in the setting of a partially ordered set that is endowed with a metric. Indeed, if A and B are non-void subsets of a partially ordered set that is equipped with a metric, and S is a non-self mapping from A to B, this paper scrutinizes the existence of an optimal approximate solution, called a best proximity point of the mapping S, to the operator equation Sx = x where S is a continuous, proximally monotone, ordered proximal contraction. Further, this paper manifests an iterative algorithm for discovering such an optimal approximate solution. As a special case of the result obtained in this article, an interesting fixed point theorem on partially ordered sets is deduced.

In this paper, we consider a convex optimization problem with locally Lipschitz inequality constraints. The KKT optimality conditions (both necessary and sufficient) for quasi $$\epsilon $$ -solutions are established under Slater’s constraint qualification and a non-degeneracy condition. Moreover, we explore the optimality condition for weakly efficient solutions in multiobjective convex optimization involving locally Lipschitz constraints. Some examples are given to illustrate our results.

The vertex 3-colourability problem is to decide whether the vertex set of a given graph can be split into three subsets of pairwise non-adjacent vertices. This problem is known to be NP-complete in a certain class of graphs, defined by an explicit description of allowed 5-vertex induced subgraphs in them. In the present paper, we improve this result by showing that the vertex 3-colourability problem remains NP-complete for a reduced set of allowed 5-vertex induced structures. It gives a step towards obtaining a complete complexity dichotomy for the mentioned problem and all the classes, defined by 5-vertex forbidden induced prohibitions.

We propose a new large-step primal-dual second-order corrector interior-point method for linear optimization. At each iteration, our method uses the new wide neighborhood introduced by Darvay and Takács (Cent Eur J Oper Res 26(3):551–563, 2018. https://doi.org/10.1007/s10100-018-0524-0 ). In this paper we would like to improve the directions proposed by Darvay and Takács by adding a second-order corrector direction. The corrector step is multiplied by the square of the step length in the expression of the new iterate. To our best knowledge, this is the first primal-dual second-order corrector interior-point algorithm based on Darvay–Takács’s new wide neighborhood, which has the same complexity as the best short-step algorithms for linear optimization. Finally, numerical experiments show that the proposed algorithm is efficient and reliable.

This paper was originally motivated by the problem of providing a point-based formula (only involving the nominal data, and not data in a neighborhood) for estimating the calmness modulus of the optimal set mapping in linear semi-infinite optimization under perturbations of all coefficients. With this aim in mind, the paper establishes as a key tool a basic result on finite-valued convex functions in the $$n$$ -dimensional Euclidean space. Specifically, this result provides an upper limit characterization of the boundary of the subdifferential of such a convex function. When applied to the supremum function associated with our constraint system, this characterization allows us to derive an upper estimate for the aimed calmness modulus in linear semi-infinite optimization under the uniqueness of nominal optimal solution.

In the capacitated team orienteering problem, a fleet of vehicles visits and services a subset of customers in order to maximize the total profit collected while obeying capacity and route length constraints. In the split delivery team orienteering problem (SDCTOP), multiple vehicles can service the same customer; each vehicle satisfies some, but not all, of the customer demand. Allowing split deliveries may double the total profit, in the extreme case. However, split deliveries often cause inconvenience to the customers, so we introduce the split delivery team orienteering problem with minimum delivery amounts (SDCTOP–MDA). In this paper, we perform a worst-case analysis on the SDCTOP–MDA to determine tight bounds on the maximum possible profit increase.

Recently Bai and Yang in (Appl Numer Math 59:2923–2936, 2009) proposed the Picard–Hermitian and skew-Hermitian splitting (HSS) iteration method to solve the system of nonlinear equations $$Ax=\varphi (x)$$ , where $$A\in \mathbb {C}^{n \times n}$$ is a non-Hermitian positive definite matrix and $$\varphi :\mathbb {D}\subset \mathbb {C}^n \rightarrow \mathbb {C}^n$$ is continuously differentiable function defined on the open complex domain $$\mathbb {D}$$ in the $$n$$ -dimensional complex linear space $$\mathbb {C}^n$$ . In this paper, we focus our attention to the absolute value equation (AVE) $$Ax=\varphi (x)$$ where $$\varphi (x)=|x|+b$$ , where $$b\in \mathbb {C}^n$$ . Since the function $$\varphi $$ in AVE is not continuously differentiable function the convergence analysis of the Picard–HSS iteration method for this problem needs to be investigated. We give sufficient conditions for the convergence of the Picard–HSS iteration method for AVE. Some numerical experiments are given to show the effectiveness of the method and to compare with two available methods.