Saddle point approach to solving problem of optimal control with fixed ends

The global resolution of constrained non-linear bi-objective optimization problems (NLBOO) aims at covering their Pareto-optimal front which is in general a one-manifold in \(\mathbb {R}^2\). Continuation methods can help in this context as they can follow a continuous component of this front once an initial point on it is provided. They constitute somehow a generalization of the classical scalarization framework which transforms the bi-objective problem into a parametric single-objective problem. Recent works have shown that they can play a key role in global algorithms dedicated to bi-objective problems, e.g. population based algorithms, where they allow discovering large portions of locally Pareto optimal vectors, which turns out to strongly support diversification. The contribution of this paper is twofold: we first provide a survey on continuation techniques in global optimization methods for NLBOO, identifying relations between several work and usual limitations, among which the ability to handle inequality constraints. We then propose a rigorous active set management strategy on top of a continuation method based on interval analysis, certified with respect to feasibility, local optimality and connectivity. This allows overcoming the latter limitation as illustrated on a representative bi-objective problem.     

Problems with resource allocation constraints and optimization over the efficient set

The paper studies a nonlinear optimization problem under resource allocation constraints. Using quasi-gradient duality it is shown that the feasible set of the problem is a singleton (in the case of a single resource) or the set of Pareto efficient solutions of an associated vector maximization problem (in the case of $k>1$ resources). As a result, a nonlinear optimization problem under resource allocation constraints reduces to an optimization over the efficient set. The latter problem can further be converted into a quasiconvex maximization over a compact convex subset of $\mathbb{R }^k_+.$ Alternatively, it can be approached as a bilevel program and converted into a monotonic optimization problem in $\mathbb{R }^k_+.$ In either approach the converted problem falls into a common class of global optimization problems for which several practical solution methods exist when the number $k$ of resources is relatively small, as it often occurs.     

An exact algorithm for the bi-objective timing problem

The timing problem in the bi-objective just-in-time single-machine job-shop scheduling problem (JiT-JSP) is the task to schedule N jobs whose order is fixed, with each job incurring a linear earliness penalty for finishing ahead of its due date and a linear tardiness penalty for finishing after its due date. The goal is to minimize the earliness and tardiness simultaneously. We propose an exact greedy algorithm that finds the entire Pareto front in \(O(N^2)\) time. This algorithm is asymptotically optimal.     

Sufficient conditions for global weak Pareto solutions in multiobjective optimization

In this paper we derive new sufficient conditions for global weak Pareto solutions to set-valued optimization problems with general geometric constraints of the type $$\begin{aligned} \text{ maximize}\quad F(x) \quad \text{ subject} \text{ to}\quad x\in \Omega , \end{aligned}$$ where $F: X\rightrightarrows Z$ is a set-valued mapping between Banach spaces with a partial order on $Z$ . Our main results are established by using advanced tools of variational analysis and generalized differentiation; in particular, the extremal principle and full generalized differential calculus for the subdifferential/coderivative constructions involved. Various consequences and refined versions are also considered for special classes of problems in vector optimization including those with Lipschitzian data, with convex data, with finitely many objectives, and with no constraints.     

A new global optimization method for a symmetric Lipschitz continuous function and the application to searching for a globally optimal partition of a one-dimensional set

In this paper, we consider a global optimization problem for a symmetric Lipschitz continuous function \(g:[a,b]^k\rightarrow {\mathbb {R}}\), whose domain \([a,b]^k\subset {\mathbb {R}}^k\) consists of k! hypertetrahedrons of the same size and shape, in which function g attains equal values. A global minimum can therefore be searched for in one hypertetrahedron only, but then this becomes a global optimization problem with linear constraints. Apart from that, some known global optimization algorithms in standard form cannot be applied to solving the problem. In this paper, it is shown how this global optimization problem with linear constraints can easily be transformed into a global optimization problem on hypercube \([0,1]^k\), for the solving of which an applied DIRECT algorithm in standard form is possible. This approach has a somewhat lower efficiency than known global optimization methods for symmetric Lipschitz continuous functions (such as SymDIRECT or DISIMPL), but, on the other hand, this method allows for the use of publicly available and well developed computer codes for solving a global optimization problem on hypercube \([0,1]^k\) (e.g. the DIRECT algorithm). The method is illustrated and tested on standard symmetric functions and very demanding center-based clustering problems for the data that have only one feature. An application to the image segmentation problem is also shown.     

Eigenvalue analysis of constrained minimization problem for homogeneous polynomial

In this paper, the concepts of Pareto H-eigenvalue and Pareto Z-eigenvalue are introduced for studying constrained minimization problem and the necessary and sufficient conditions of such eigenvalues are given. It is proved that a symmetric tensor has at least one Pareto H-eigenvalue (Pareto Z-eigenvalue). Furthermore, the minimum Pareto H-eigenvalue (or Pareto Z-eigenvalue) of a symmetric tensor is exactly equal to the minimum value of constrained minimization problem of homogeneous polynomial deduced by such a tensor, which gives an alternative methods for solving the minimum value of constrained minimization problem. In particular, a symmetric tensor \({\mathcal {A}}\) is strictly copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is positive, and \({\mathcal {A}}\) is copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is non-negative.     

Variants of the $$ \vare psilon $$-constraint method for biobjective integer programming problems: a p plication to p-median-cover problems

We conduct an in-depth analysis of the \(\varepsilon \)-constraint method (ECM) for finding the exact Pareto front for biobjective integer programming problems. We have found up to six possible different variants of the ECM. We first discuss the complexity of each of these variants and their relationship with other exact methods for solving biobjective integer programming problems. By extending some results of Neumayer and Schweigert (OR Spektrum 16:267–276, 1994), we develop two variants of the ECM, both including an augmentation term and requiring \(N+1\) integer programs to be solved, where N is the number of nondominated points. In addition, we present another variant of the ECM, based on the use of elastic constraints and also including an augmentation term. This variant has the same complexity, namely \(N+1\), which is the minimum reached for any exact method. A comparison of the different variants is carried out on a set of biobjective location problems which we call p-median-cover problems; these include the objectives of the p-median and the maximal covering problems. As computational results show, for this class of problems, the augmented ECM with elastic constraint is the most effective variant for finding the Pareto front in an exact manner.     

Optimality conditions for weak {\psi} -sharp minima in vector optimization problems

In this paper, we develop the characterization of weak ${\psi}$ -sharp minimizer by means of an oriented distance function and investigate the weak ${\psi}$ -sharp minimizer of the composition of two functions. Moreover, we establish sufficient conditions of the weak ${\psi_1}$ -sharp and ${\psi_2}$ -sharp Pareto minimality for vector optimization problem with strictly differentiable and twice strictly differentiable objective function, respectively. Our results extend the corresponding ones in the literature.     

Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints

The well known DIRECT (DIviding RECTangles) algorithm for global optimization requires bound constraints on variables and does not naturally address additional linear or nonlinear constraints. A feasible region defined by linear constraints may be covered by simplices, therefore simplicial partitioning may tackle linear constraints in a very subtle way. In this paper we demonstrate this advantage of simplicial partitioning by applying a recently proposed deterministic simplicial partitions based DISIMPL algorithm for optimization problems defined by general linear constraints (Lc-DISIMPL). An extensive experimental investigation reveals advantages of this approach to such problems comparing with different constraint-handling methods, proposed for use with DIRECT. Furthermore the Lc-DISIMPL algorithm gives very competitive results compared to a derivative-free particle swarm algorithm (PSwarm) which was previously shown to give very promising results. Moreover, DISIMPL guarantees the convergence to the global solution, whereas the PSwarm algorithm sometimes fails to converge to the global minimum.     

Solving linear optimization over arithmetic constraint formula

Since Balas extended the classical linear programming problem to the disjunctive programming (DP) problem where the constraints are combinations of both logic AND and OR, many researchers explored this optimization problem under various theoretical or application scenarios such as generalized disjunctive programming (GDP), optimization modulo theories (OMT), robot path planning, real-time systems, etc. However, the possibility of combining these differently-described but form-equivalent problems into a single expression remains overlooked. The contribution of this paper is two folded. First, we convert the linear DP/GDP model, linear-arithmetic OMT problem and related application problems into an equivalent form, referred to as the linear optimization over arithmetic constraint formula (LOACF). Second, a tree-search-based algorithm named RS-LPT is proposed to solve LOACF. RS-LPT exploits the techniques of interval analysis and nonparametric estimation for reducing the search tree and lowering the number of visited nodes. Also, RS-LPT alleviates bad construction of search tree by backtracking and pruning dynamically. We evaluate RS-LPT against two most common DP/GDP methods, three state-of-the-art OMT solvers and the disjunctive transformation based method on optimization benchmarks with different types and scales. Our results favor RS-LPT as compared to existing competing methods, especially for large scale cases.     

A constrained optimization reformulation and a feasible descent direction method for L_{1/2} regularization

In this paper, we first propose a constrained optimization reformulation to the \(L_{1/2}\) regularization problem. The constrained problem is to minimize a smooth function subject to some quadratic constraints and nonnegative constraints. A good property of the constrained problem is that at any feasible point, the set of all feasible directions coincides with the set of all linearized feasible directions. Consequently, the KKT point always exists. Moreover, we will show that the KKT points are the same as the stationary points of the \(L_{1/2}\) regularization problem. Based on the constrained optimization reformulation, we propose a feasible descent direction method called feasible steepest descent method for solving the unconstrained \(L_{1/2}\) regularization problem. It is an extension of the steepest descent method for solving smooth unconstrained optimization problem. The feasible steepest descent direction has an explicit expression and the method is easy to implement. Under very mild conditions, we show that the proposed method is globally convergent. We apply the proposed method to solve some practical problems arising from compressed sensing. The results show its efficiency.     

Pareto–Fenchel {\epsilon} -subdifferential sum rule and {\epsilon} -efficiency

The paper is centered around a sum rule for the efficient (Pareto) ${\epsilon}$ -subdifferential of two convex vector mappings, having the property to be exact under a qualification condition. Such a formula has not been explored previously. Our formula which holds under the Attouch?CBrézis as well as Moreau?CRockafellar conditions, reveals strangely a primordial presence of the convex (Fenchel) ${\epsilon}$ -subdifferential. This appearance turns out to be rather favorable. This effectively permits to derive approximate efficiency conditions in terms of Pareto subgradient and vectorial normal cone, which completely characterizes an ${\epsilon}$ -efficient solution in constrained convex vector optimization in (partially) ordered spaces. Our sum rule also allows a fundamental deduction of relation between Pareto and Fenchel ${\epsilon}$ -subdifferentials, which, in reality, brings out a certain gap linking ${\epsilon}$ -efficiency with ${\epsilon}$ -optimality. Scalarization approaches in connection with ${\epsilon}$ -subdifferentials are first established by simple proofs. This principle has contributed for a large part, not only for discovering the sum formula, but also for establishing some punctual necessary and/or sufficient conditions for Pareto ${\epsilon}$ -subdifferentiability.     

Towards a multi-objective performance assessment and optimization model of a two-echelon supply chain using SCOR metrics

This paper aims at multi-objective performance assessment and optimization of a multi-period two-echelon supply chain consisting of a supplier and a manufacturer. On the basis of the assessment system of the supply-chain operations reference model, the supply chain’s performance is investigated with respect to costs, assets, agility, reliability and responsiveness. First, methods to quantify these five performance attributes are put forward. Then a multi-objective mathematical programming model is developed for production decision making of components and products so that the supply chain’s performance frontier formed with Pareto efficient performance values can be achieved. Thereafter a simple augmented \(\epsilon \) -constraint method is proposed for searching for all Pareto efficient solutions of the multi-objective mathematical programming problem. Finally, efficiency of the method is demonstrated with a numerical example and a sensitivity analysis is implemented to reveal effects of capacity expansion on supply chains’ performance.     

Solving inverse cone-constrained eigenvalue problems

We compare various algorithms for constructing a matrix of order $n$ whose Pareto spectrum contains a prescribed set $\Lambda =\{\lambda _1,\ldots , \lambda _p\}$ of reals. In order to avoid overdetermination one assumes that $p$ does not exceed $n^2.$ The inverse Pareto eigenvalue problem under consideration is formulated as an underdetermined system of nonlinear equations. We also address the issue of computing Lorentz spectra and solving inverse Lorentz eigenvalue problems.     

On the complexity of finding first-order critical points in constrained nonlinear optimization

The complexity of finding $\epsilon $ -approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that $O(\epsilon ^{-2})$ in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply.     

Solving convex optimization with side constraints in a multi-class queue by adaptive c\mu rule

We study convex optimization problems with side constraints in a multi-class \(M/G/1\) queue with controllable service rates. In the simplest problem of optimizing linear costs with fixed service rate, the \(c\mu \) rule is known to be optimal. A natural question to ask is whether such simple policies exist for more complex control objectives. In this paper, combining the achievable region approach in queueing systems and the Lyapunov drift theory suitable to optimize renewal systems with time-average constraints, we show that convex optimization problems can be solved by variants of adaptive \(c\mu \) rules. These policies greedily re-prioritize job classes at the end of busy periods in response to past observed delays in each job class. Our method transforms the original problems into a new set of queue stability problems, and the adaptive \(c\mu \) rules are queue stable policies. An attractive feature of the adaptive \(c\mu \) rules is that they use limited statistics of the queue, where no statistics are required for the problem of satisfying average queueing delay in each job class.     

New necessary and sufficient optimality conditions for strong bilevel programming problems

In this paper we are interested in a strong bilevel programming problem (S). For such a problem, we establish necessary and sufficient global optimality conditions. Our investigation is based on the use of a regularization of problem (S) and some well-known global optimization tools. These optimality conditions are new in the literature and are expressed in terms of \(\max \)–\(\min \) conditions with linked constraints.     

Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity

We provide motivations for the correlated equilibrium solution concept from the game-theoretic and optimization perspectives. We then propose an algorithm that computes ${\varepsilon}$ -correlated equilibria with global-optimal (i.e., maximum) expected social welfare for normal form polynomial games. We derive an infinite dimensional formulation of ${\varepsilon}$ -correlated equilibria using Kantorovich polynomials, and re-express it as a polynomial positivity constraint. We exploit polynomial sparsity to achieve a leaner problem formulation involving sum-of-squares constraints. By solving a sequence of semidefinite programming relaxations of the problem, our algorithm converges to a global-optimal ${\varepsilon}$ -correlated equilibrium. The paper ends with two numerical examples involving a two-player polynomial game, and a wireless game with two mutually-interfering communication links.     

Optimization of Quasi-Normal Eigenvalues for Krein–Nudelman Strings

The paper is devoted to optimization of resonances for Krein strings with total mass and statical moment constraints. The problem is to design for a given ${\alpha \in \mathbb{R}}$ a string that has a resonance on the line ${\alpha + {\rm i}\mathbb{R}}$ with a minimal possible modulus of the imaginary part. We find optimal resonances and strings explicitly.     

A continuous characterization of the maximum-edge biclique problem

The problem of finding large complete subgraphs in bipartite graphs (that is, bicliques) is a well-known combinatorial optimization problem referred to as the maximum-edge biclique problem (MBP), and has many applications, e.g., in web community discovery, biological data analysis and text mining. In this paper, we present a new continuous characterization for MBP. Given a bipartite graph $G$ , we are able to formulate a continuous optimization problem (namely, an approximate rank-one matrix factorization problem with nonnegativity constraints, R1N for short), and show that there is a one-to-one correspondence between (1) the maximum (i.e., the largest) bicliques of $G$ and the global minima of R1N, and (2) the maximal bicliques of $G$ (i.e., bicliques not contained in any larger biclique) and the local minima of R1N. We also show that any stationary points of R1N must be close to a biclique of $G$ . This allows us to design a new type of biclique finding algorithm based on the application of a block-coordinate descent scheme to R1N. We show that this algorithm, whose algorithmic complexity per iteration is proportional to the number of edges in the graph, is guaranteed to converge to a biclique and that it performs competitively with existing methods on random graphs and text mining datasets. Finally, we show how R1N is closely related to the Motzkin–Strauss formalism for cliques.