Deterministic solution approach for some classes of nonlinear multilevel programs with multiple followers

In this paper we investigate multilevel programming problems with multiple followers in each hierarchical decision level. It is known that such type of problems are highly non-convex and hard to solve. A solution algorithm have been proposed by reformulating the given multilevel program with multiple followers at each level that share common resources into its equivalent multilevel program having single follower at each decision level. Even though, the reformulated multilevel optimization problem may contain non-convex terms at the objective functions at each level of the decision hierarchy, we applied multi-parametric branch-and-bound algorithm to solve the resulting problem that has polyhedral constraints. The solution procedure is implemented and tested for a variety of illustrative examples.     

非凸极小极大问题的优化算法与复杂度分析

非凸极小极大问题是近期国际上优化与机器学习、信号处理等交叉领域的一个重要研究前沿和热点,包括对抗学习、强化学习、分布式非凸优化等前沿研究方向的一些关键科学问题都归结为该类问题。国际上凸-凹极小极大问题的研究已取得很好的成果,但非凸极小极大问题不同于凸-凹极小极大问题,是有其自身结构的非凸非光滑优化问题,理论研究和求解难度都更具挑战性,一般都是NP-难的。重点介绍非凸极小极大问题的优化算法和复杂度分析方面的最新进展。     

A constrained-optimization based half-quadratic algorithm for robustly fitting sets of linearly parametrized curves

We consider the problem of multiple fitting of linearly parametrized curves, that arises in many computer vision problems such as road scene analysis. Data extracted from images usually contain non-Gaussian noise and outliers, which makes classical estimation methods ineffective. In this paper, we first introduce a family of robust probability density functions which appears to be well-suited to many real-world problems. Also, such noise models are suitable for defining continuation heuristics to escape shallow local minima and their robustness is devised in terms of breakdown point. Second, the usual Iterative Reweighted Least Squares (IRLS) robust estimator is extended to the problem of robustly estimating sets of linearly parametrized curves. The resulting, non-convex optimization problem is tackled within a Lagrangian approach, leading to the so-called Simultaneous Robust Multiple Fitting (SRMF) algorithm, whose global convergence to a local minimum is proved using results from constrained optimization theory.     

A Posteriori Verification of Optimality Conditions for Control Problems with Finite-Dimensional Control Space

In this article, we investigate non-convex optimal control problems. We are concerned with a posteriori verification of sufficient optimality conditions. If the proposed verification method confirms the fulfillment of the sufficient condition then a posteriori error estimates can be computed. A special ingredient of our method is an error analysis for the Hessian of the underlying optimization problem. We derive conditions under which positive definiteness of the Hessian of the discrete problem implies positive definiteness of the Hessian of the continuous problem. The article is complemented with numerical experiments.     

Numerical study of learning algorithms on Stiefel manifold

Convex optimization methods are used for many machine learning models such as support vector machine. However, the requirement of a convex formulation can place limitations on machine learning models. In recent years, a number of machine learning methods not requiring convexity have emerged. In this paper, we study non-convex optimization problems on the Stiefel manifold in which the feasible set consists of a set of rectangular matrices with orthonormal column vectors. We present examples of non-convex optimization problems in machine learning and apply three nonlinear optimization methods for finding a local optimal solution; geometric gradient descent method, augmented Lagrangian method of multipliers, and alternating direction method of multipliers. Although the geometric gradient method is often used to solve non-convex optimization problems on the Stiefel manifold, we show that the alternating direction method of multipliers generally produces higher quality numerical solutions within a reasonable computation time.     

无线通信中的最优资源分配―复杂性分析与算法设计

最优资源分配问题是无线通信系统设计中的基本问题之一.最优地分配功率、传输波形和频谱等资源能够极大地提高整个通信系统的传输性能.目前,相对于通信技术在现实生活中的蓬勃发展,通信系统优化的数学理论和方法显得相对滞后,在某些方面已经成为影响其发展和应用的关键因素.无线通信中的最优资源分配问题常常可建模为带有特殊结构的非凸非线性约束优化问题.一方面,这些优化问题常常具有高度的非线性性,一般情况下难于求解;另一方面,它们又有自身的特殊结构,如隐含的凸性和可分结构等.本文着重考虑多用户干扰信道中物理层资源最优分配问题的复杂性刻画,以及如何利用问题的特殊结构设计有效且满足分布式应用等实际要求的计算方法.     

Fuzzy necessary optimality conditions for vector optimization problems

The primary aim of this article is to derive Lagrange multiplier rules for vector optimization problems using a non-convex separation technique and the concept of abstract subdifferential. Furthermore, we present a method of estimation of the norms of such multipliers in very general cases and for many particular subdifferentials.     

Generation of efficient frontiers in multi-objective optimization problems by generalized data envelopment analysis

In many practical problems such as engineering design problems, criteria functions cannot be given explicitly in terms of design variables. Under this circumstance, values of criteria functions for given values of design variables are usually obtained by some analyses such as structural analysis, thermodynamical analysis or fluid mechanical analysis. These analyses require considerably much computation time. Therefore, it is not unrealistic to apply existing interactive optimization methods to those problems. On the other hand, there have been many trials using genetic algorithms (GA) for generating efficient frontiers in multi-objective optimization problems. This approach is effective in problems with two or three objective functions. However, these methods cannot usually provide a good approximation to the exact efficient frontiers within a small number of generations in spite of our time limitation. The present paper proposes a method combining generalized data envelopment analysis (GDEA) and GA for generating efficient frontiers in multi-objective optimization problems. GDEA removes dominated design alternatives faster than methods based on only GA. The proposed method can yield desirable efficient frontiers even in non-convex problems as well as convex problems. The effectiveness of the proposed method will be shown through several numerical examples.     

Global optimization numerical strategies for rate-independent processes

This paper presents an approach to numerical solution of problems posed in the framework of quasi-static rate-independent processes. As soon as a problem allows for an energetic formulation there are known methods of its time discretization by time incremental minimization problems, which demand for global optimization of a non-convex functional. Moreover the two-sided energy inequality, a necessary condition for optimization, can be formulated. Here we present an algorithm for finding solutions of rate-independent processes that verifies this condition and uses the strategy of backtracking if it is violated. We present the selectivity of the mentioned necessary condition in general and give numerical examples of the efficiency of such an algorithm, but also of situations that are beyond its limits. For those we propose a second strategy relying on wisely chosen combinations of spatial discretizations.     

Spectral bundle methods for non-convex maximum eigenvalue functions: first-order methods

Many challenging problems in automatic control may be cast as optimization programs subject to matrix inequality constraints. Here we investigate an approach which converts such problems into non-convex eigenvalue optimization programs and makes them amenable to non-smooth analysis techniques like bundle or cutting plane methods. We prove global convergence of a first-order bundle method for programs with non-convex maximum eigenvalue functions. Dedicated to R. T. Rockafellar on the occasion of his 70th anniversary     

Iterative Algorithms for Multiscale State Estimation, Part 1: Concepts

The objective of the present investigation is to explore the potential of multiscale refinement schemes for the numerical solution of dynamic optimization problems arising in connection with chemical process systems monitoring. State estimation is accomplished by the solution of an appropriately posed least-squares problem. To offer at any instant of time an approximate solution, a hierarchy of successively refined problems is designed using a wavelet-based Galerkin discretization. In order to fully exploit at any stage the approximate solution obtained also for an efficient treatment of the arising linear algebra tasks, we employ iterative solvers. In particular, we will apply a nested iteration scheme to the hierarchy of arising equation systems and adapt the Uzawa algorithm to the present context. Moreover, we show that, using wavelets for the formulation of the problem hierarchy, the largest eigenvalues of the resulting linear systems can be controlled effectively with scaled diagonal preconditioning. Finally, we deduce appropriate stopping criteria and illustrate the characteristics of the solver with a numerical example.     

Parameter estimation in stochastic scenario generation systems

Scenario analysis offers an effective tool for addressing the stochastic elements in multi-period financial planning models. Critical to any scenario generation process is the estimation of the input parameters of the underlying stochastic model for economic factors. In this paper, we propose a new approach for estimation, known as the integrated parameter estimation (IPE). This approach combines the significant features of other well-known estimation techniques within a non-convex multiple objective optimization framework, with the objective weights controlling the relative importance of the features. We solve the non-convex optimization problem using adaptive memory programming – a variation of tabu search. Based on a short interest rate model using UK treasury rates from 1980 to 1995, the integrated approach compares favorably with maximum likelihood and the generalized method of moments. We also evaluate performance with Towers Perrin's CAP:Link scenario generation system.     

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution

In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.     

Maximization of the Choquet integral over a convex set and its application to resource allocation problems

We study the problem of the Choquet integral maximization over a convex set. The problem is shown to be generally non-convex (and non-differentiable). We analyze the problem structure, and propose local and global search algorithms. The special case when the problem becomes concave is analyzed separately. For the non-convex case we propose a decomposition scheme which allows to reduce a non-convex problem to several concave ones. Decomposition is performed by finding the coarsest partition of a capacity into disjunction of totally monotone measures. We discuss its effectiveness and prove that the scheme is optimal for 2-additive capacities. An application of the developed methods to resource allocation problems concludes the article.     

About the non-convex optimization problem induced by non-positive semidefinite kernel learning

During the last years, kernel based methods proved to be very successful for many real-world learning problems. One of the main reasons for this success is the efficiency on large data sets which is a result of the fact that kernel methods like support vector machines (SVM) are based on a convex optimization problem. Solving a new learning problem can now often be reduced to the choice of an appropriate kernel function and kernel parameters. However, it can be shown that even the most powerful kernel methods can still fail on quite simple data sets in cases where the inherent feature space induced by the used kernel function is not sufficient. In these cases, an explicit feature space transformation or detection of latent variables proved to be more successful. Since such an explicit feature construction is often not feasible for large data sets, the ultimate goal for efficient kernel learning would be the adaptive creation of new and appropriate kernel functions. It can, however, not be guaranteed that such a kernel function still leads to a convex optimization problem for Support Vector Machines. Therefore, we have to enhance the optimization core of the learning method itself before we can use it with arbitrary, i.e., non-positive semidefinite, kernel functions. This article motivates the usage of appropriate feature spaces and discusses the possible consequences leading to non-convex optimization problems. We will show that these new non-convex optimization SVM are at least as accurate as their quadratic programming counterparts on eight real-world benchmark data sets in terms of the generalization performance. They always outperform traditional approaches in terms of the original optimization problem. Additionally, the proposed algorithm is more generic than existing traditional solutions since it will also work for non-positive semidefinite or indefinite kernel functions.     

Stability of the Minimizers of Least Squares with a Non-Convex Regularization. Part II: Global Behavior

We address estimation problems where the sought-after solution is defined as the minimizer of an objective function composed of a quadratic data-fidelity term and a regularization term. We especially focus on non-convex and possibly non-smooth regularization terms because of their ability to yield good estimates. This work is dedicated to the stability of the minimizers of such piecewise C^m, with m ≥ 2, non-convex objective functions. It is composed of two parts. In the previous part of this work we considered general local minimizers. In this part we derive results on global minimizers. We show that the data domain contains an open, dense subset such that for every data point therein, the objective function has a finite number of local minimizers, and a unique global minimizer. It gives rise to a global minimizer function which is C^m-1 everywhere on an open and dense subset of the data domain.     

Hybrid algorithm for a vendor managed inventory system in a two-echelon supply chain

In this paper we address the issue of vendor managed inventory (VMI) by considering a two-echelon single vendor/multiple buyer supply chain network. We try to find the optimal sales quantity by maximizing profit, given as a nonlinear and non-convex objective function. For such complicated combinatorial optimization problems, exact algorithms and optimization commercial software such as LINGO are inefficient, especially on practical-size problems. In this paper we develop a hybrid genetic/simulated annealing algorithm to deal with this nonlinear problem. Our results demonstrate that the proposed hybrid algorithm outperforms previous methodologies and achieves more robust solutions.     

Mathematical modelling and parameter optimization of pulsating heat pipes

Proper heat transfer management is important to key electronic components in microelectronic applications. Pulsating heat pipes (PHP) can be an efficient solution to such heat transfer problems. However, mathematical modelling of a PHP system is still very challenging, due to the complexity and multiphysics nature of the system. In this work, we present a simplified, two-phase heat transfer model, and our analysis shows that it can make good predictions about startup characteristics. Furthermore, by considering parameter estimation as a nonlinear constrained optimization problem, we have used the firefly algorithm to find parameter estimates efficiently. We have also demonstrated that it is possible to obtain good estimates of key parameters using very limited experimental data.     

Robust solutions of quadratic optimization over single quadratic constraint under interval uncertainty

In this paper we examine non-convex quadratic optimization problems over a quadratic constraint under unknown but bounded interval perturbation of problem data in the constraint and develop criteria for characterizing robust (i.e. uncertainty-immunized) global solutions of classes of non-convex quadratic problems. Firstly, we derive robust solvability results for quadratic inequality systems under parameter uncertainty. Consequently, we obtain characterizations of robust solutions for uncertain homogeneous quadratic problems, including uncertain concave quadratic minimization problems and weighted least squares. Using homogenization, we also derive characterizations of robust solutions for non-homogeneous quadratic problems.     

A new model for sparse and low-rank matrix decomposition

The robust principal component analysis (RPCA) model is a popular method for solving problems with the nuclear norm and $\ell_1$ norm. However, it is time-consuming since in general one has to use the singular value decomposition in each iteration. In this paper, we introduce a novel model to reformulate the existed model by making use of low-rank matrix factorization to surrogate the nuclear norm for the sparse and low-rank decomposition problem. In such case we apply the Penalty Function Method (PFM) and Augmented Lagrangian Multipliers Method (ALMM) to solve this new non-convex optimization problem. Theoretically, corresponding to our methods, the convergence analysis is given respectively. Compared with classical RPCA, some practical numerical examples are simulated to show that our methods are much better than RPCA.