Optimization for Inconsistent Split Feasibility Problems

The split feasibility problem deals with finding a point in a closed convex subset of the domain space of a linear operator such that the image of the point under the linear operator is in a prescribed closed convex subset of the image space. The split feasibility problem and its variants and generalizations have been widely investigated as a means for resolving practical inverse problems in various disciplines. Many iterative algorithms have been proposed for solving the problem. This article discusses a split feasibility problem which does not have a solution, referred to as an inconsistent split feasibility problem. When the closed convex set of the domain space is the absolute set and the closed convex set of the image space is the subsidiary set, it would be reasonable to formulate a compromise solution of the inconsistent split feasibility problem by using a point in the absolute set such that its image of the linear operator is closest to the subsidiary set in terms of the norm. We show that the problem of finding the compromise solution can be expressed as a convex minimization problem over the fixed point set of a nonexpansive mapping and propose an iterative algorithm, with three-term conjugate gradient directions, for solving the minimization problem.     

Nonsmooth nonconvex optimization approach to clusterwise linear regression problems

Clusterwise regression consists of finding a number of regression functions each approximating a subset of the data. In this paper, a new approach for solving the clusterwise linear regression problems is proposed based on a nonsmooth nonconvex formulation. We present an algorithm for minimizing this nonsmooth nonconvex function. This algorithm incrementally divides the whole data set into groups which can be easily approximated by one linear regression function. A special procedure is introduced to generate a good starting point for solving global optimization problems at each iteration of the incremental algorithm. Such an approach allows one to find global or near global solution to the problem when the data sets are sufficiently dense. The algorithm is compared with the multistart Späth algorithm on several publicly available data sets for regression analysis.     

On the Pironneau-Polak method of centers

The method of centers is a well-known method for solving nonlinear programming problems having inequality constraints. Pironneau and Polak have recently presented a new version of this method. In the new method, the direction of search is obtained, at each iteration, by solving a convex quadratic programming problem. This direction finding subprocedure is essentially insensitive to the dimension of the space on which the problem is defined. Moreover, the method of Pironneau and Polak is known to converge linearly for finite-dimensional convex programs for which the objective function has a positive-definite Hessian near the solution (and for which the functions involved are twice continuously differentiable). In the present paper, the method and a completely implementable version of it are shown to converge linearly for a very general class of finite-dimensional problems; the class is determined by a second-order sufficiency condition and includes both convex and nonconvex problems. The arguments employed here are based on the indirect sufficiency method of Hestenes. Furthermore, the arguments can be modified to prove linear convergence for a certain class of infinite-dimensional convex problems, thus providing an answer to a conjecture made by Pironneau and Polak.     

A reformulation framework for global optimization

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called αBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.     

The complementary convex structure in global optimization

We show the importance of exploiting the complementary convex structure for efficiently solving a wide class of specially structured nonconvex global optimization problems. Roughly speaking, a specific feature of these problems is that their nonconvex nucleus can be transformed into a complementary convex structure which can then be shifted to a subspace of much lower dimension than the original underlying space. This approach leads to quite efficient algorithms for many problems of practical interest, including linear and convex multiplicative programming problems, concave minimization problems with few nonlinear variables, bilevel linear optimization problems, etc...     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

A global optimization method for nonconvex separable programming problems

Conventional methods of solving nonconvex separable programming (NSP) problems by mixed integer programming methods requires adding numerous 0–1 variables. In this work, we present a new method of deriving the global optimum of a NSP program using less number of 0–1 variables. A separable function is initially expressed by a piecewise linear function with summation of absolute terms. Linearizing these absolute terms allows us to convert a NSP problem into a linearly mixed 0–1 program solvable for reaching a solution which is extremely close to the global optimum.     

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.     

An interior point algorithm to solve computationally difficult set covering problems

We present an interior point approach to the zero–one integer programming feasibility problem based on the minimization of a nonconvex potential function. Given a polytope defined by a set of linear inequalities, this procedure generates a sequence of strict interior points of this polytope, such that each consecutive point reduces the value of the potential function. An integer solution (not necessarily feasible) is generated at each iteration by a rounding scheme. The direction used to determine the new iterate is computed by solving a nonconvex quadratic program on an ellipsoid. We illustrate the approach by considering a class of difficult set covering problems that arise from computing the 1-width of the incidence matrix of Steiner triple systems.     

Inequalities involving partial derivatives

This paper presents a method for obtaining closed form solutions to serial and nonserial dynamic programming problems with quadratic stage returns and linear transitions. Global parametric optimum solutions can be obtained regardless of the convexity of the stage returns. The closed form solutions are developed for linear, convex, and nonconvex quadratic returns, as well as the procedure for recursively solving each stage of the problem. Dynamic programming is a mathematical optimization technique which is especially powerful for certain types of problems. This paper presents a procedure for obtaining analytical solutions to a class of dynamic programming problems. In addition, the procedure has been programmed on the computer to facilitate the solution of large problems.     

Optimal Error Correction and Methods of Feasible Directions

The main objective of this study is to discuss the optimum correction of linear inequality systems and absolute value equations (AVE). In this work, a simple and efficient feasible direction method will be provided for solving two fractional nonconvex minimization problems that result from the optimal correction of a linear system. We will show that, in some special-but frequently encountered-cases, we can solve convex optimization problems instead of not-necessarily-convex fractional problems. And, by using the method of feasible directions, we solve the optimal correction problem. Some examples are provided to illustrate the efficiency and validity of the proposed method.     

Quadratic factorization heuristics for copositive programming

Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.     

Connectedness of Solution Sets of Strong Vector Equilibrium Problems with an Application

In this paper, the connectedness of solution set of a strong vector equilibrium problem in a finite dimensional space, is investigated. Firstly, a nonconvex separation theorem is given, that is, a neither open nor closed set and a compact subset in a finite dimensional space can be strictly separated by a sublinear and strongly monotone function. Secondly, in terms of the nonconvex separation theorem, the union relation between the solution set of the strong vector equilibrium problem and the solution sets of a series of nonlinear scalar problems, is established. Under suitable assumptions, the connectedness and the path connectedness of the solution set of the strong vector equilibrium problem are obtained. In particular, we solve partly the question related to the path connectedness of the solution set of the strong vector equilibrium problem. The question is proposed by Han and Huang in the reference (J Optim Theory Appl, 2016.  https://doi.org/10.1007/s10957-016-1032-9). Finally, as an application, we apply the main results to derive the connectedness of the solution set of a linear vector optimization problem.     

Separation Functions and Optimality Conditions in Vector Optimization

In this paper, we propose weak separation functions in the image space for general constrained vector optimization problems on strong and weak vector minimum points. Gerstewitz function is applied to construct a special class of nonlinear separation functions as well as the corresponding generalized Lagrangian functions. By virtue of such nonlinear separation functions, we derive Lagrangian-type sufficient optimality conditions in a general context. Especially for nonconvex problems, we establish Lagrangian-type necessary optimality conditions under suitable restriction conditions, and we further deduce Karush–Kuhn–Tucker necessary conditions in terms of Clarke subdifferentials.     

An incremental primal–dual method for nonlinear programming with special structure

We propose a new class of incremental primal–dual techniques for solving nonlinear programming problems with special structure. Specifically, the objective functions of the problems are sums of independent nonconvex continuously differentiable terms minimized subject to a set of nonlinear constraints for each term. The technique performs successive primal–dual increments for each decomposition term of the objective function. The primal–dual increments are calculated by performing one Newton step towards the solution of the Karush–Kuhn–Tucker optimality conditions of each subproblem associated with each objective function term. We show that the resulting incremental algorithm is q-linearly convergent under mild assumptions for the original problem.     

A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems

This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems.     

Convexity Properties Associated with Nonconvex Quadratic Matrix Functions and Applications to Quadratic Programming

We establish several convexity results which are concerned with nonconvex quadratic matrix (QM) functions: strong duality of quadratic matrix programming problems, convexity of the image of mappings comprised of several QM functions and existence of a corresponding S-lemma. As a consequence of our results, we prove that a class of quadratic problems involving several functions with similar matrix terms has a zero duality gap. We present applications to robust optimization, to solution of linear systems immune to implementation errors and to the problem of computing the Chebyshev center of an intersection of balls. This research was partially supported by the Israel Science Foundation under Grant ISF 489/06.     

Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations

We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we use rank-one matrices and constraint matrices to decompose the indefinite quadratic objective into a D.C. form and underestimate the concave terms in the D.C. decomposition formulation in order to get a convex relaxation of the original problem. We show that the best D.C. decomposition can be identified by solving an SDP problem. By suitably choosing the rank-one matrices and the linear underestimation, we are able to construct convex relaxations that dominate Shor’s SDP relaxation and the strengthened SDP relaxation. We then propose an extension of the D.C. decomposition to generate an SDP bound that is tighter than the SDP+RLT bound when additional box constraints are present. We demonstrate via computational results that the optimal D.C. decomposition schemes can generate both tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically constrained quadratic problems.     

Projection methods for nonconvex variational inequalities

In this paper, we introduce and consider a new class of variational inequalities, which is called the nonconvex variational inequalities. We establish the equivalence between the nonconvex variational inequalities and the fixed-point problems using the projection technique. This equivalent formulation is used to discuss the existence of a solution of the nonconvex variational inequalities. We also use this equivalent alternative formulation to suggest and analyze a new iterative method for solving the nonconvex variational inequalities. We also discuss the convergence of the iterative method under suitable conditions. Our method of proof is very simple as compared with other techniques.     

Reformulation and convex relaxation techniques for global optimization

We survey the main results obtained by the author in his PhD dissertation supervised by Prof. Costas Pantelides. It was defended at the Imperial College, London. The thesis is written in English and is available from . The most widely employed deterministic method for the global solution of nonconvex NLPs and MINLPs is the spatial Branch-and-Bound (sBB) algorithm, and one of its most crucial steps is the computation of the lower bound at each sBB node. We investigate different reformulations of the problem so that the resulting convex relaxation is tight. In particular, we suggest a novel technique for reformulating a wide class of bilinear problems so that some of the bilinear terms are replaced by linear constraints. Moreover, an in-depth analysis of a convex envelope for piecewise-convex and concave terms is performed. All the proposed algorithms were implemented in , an object-oriented callable library for constructing MINLPs in structured form and solving them using a variety of local and global solvers.Received: March 2004, MSC classification: 90C26, 90C20, 90C06