Global Minimization of Increasing Positively Homogeneous Functions over the Unit Simplex

In this paper we study a method for global optimization of increasing positively homogeneous functions over the unit simplex, which is a version of the cutting angle method. Some properties of the auxiliary subproblem are studied and a special algorithm for its solution is proposed. A cutting angle method based on this algorithm allows one to find an approximate solution of some problems of global optimization with 50 variables. Results of numerical experiments are discussed.     

A reduced gradient method for quadratic programs with quadratic constraints and lp-constrained lp-approximation problems

A dual algorithm is developed for solving a general class of nonlinear programs that properly contains all convex quadratic programs with quadratic constraints and l_p-constrained l_p-approximation problems. The general dual program to be solved has essentially linear constraints but the objective function is nondifferentiable when certain variables equal zero. Modifications to the reduced gradient method for linearly constrained problems are presented that overcome the numerical difficulties associated with the nondifferentiable objective function. These modifications permit ‘blocks’ of variables to move to and away from zero on certain iterations even though the objective function is nondifferentiable at points having a block of variables equal to zero.     

A search method for optimal control of a flow shop system of traditional machines

We consider a convex and nondifferentiable optimization problem for deterministic flow shop systems in which the arrival times of the jobs are known and jobs are processed in the order they arrive. The decision variables are the service times that are to be set only once before processing the first job, and cannot be altered between processes. The cost objective is the sum of regular costs on job completion times and service costs inversely proportional to the controllable service times. A finite set of subproblems, which can be solved by trust-region methods, are defined and their solutions are related to the optimal solution of the optimization problem under consideration. Exploiting these relationships, we introduce a two-phase search method which converges in a finite number of iterations. A numerical study is held to demonstrate the solution performance of the search method compared to a subgradient method proposed in earlier work.     

A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation

We propose a primal-dual continuation approach for the capacitated multi-facility Weber problem (CMFWP) based on its nonlinear second-order cone program (SOCP) reformulation. The main idea of the approach is to reformulate the CMFWP as a nonlinear SOCP with a nonconvex objective function, and then introduce a logarithmic barrier term and a quadratic proximal term into the objective to construct a sequence of convexified subproblems. By this, this class of nondifferentiable and nonconvex optimization problems is converted into the solution of a sequence of nonlinear convex SOCPs. In this paper, we employ the semismooth Newton method proposed in Kanzow et al. (SIAM Journal of Optimization 20:297–320, 2009) to solve the KKT system of the resulting convex SOCPs. Preliminary numerical results are reported for eighteen test instances, which indicate that the continuation approach is promising to find a satisfying suboptimal solution, even a global optimal solution for some test problems.     

Necessary optimality conditions for Stackelberg problems

First-order necessary optimality conditions are derived for a class of two-level Stackelberg problems in which the followers' lower-level problems are convex programs with unique solutions. To this purpose, generalized Jacobians of the marginal maps corresponding to followers' problems are estimated. As illustrative examples, two discretized optimum design problems with elliptic variational inequalities are investigated. The theoretical results may be used also for the numerical solution of the Stackelberg problems considered by nondifferentiable optimization methods.Communicated by M. Simaan     

A modified reduced gradient method for a class of nondifferentiable problems

The class of nondifferentiable problems treated in this paper constitutes the dual of a class of convex differentiable problems. The primal problem involves faithfully convex functions of linear mappings of the independent variables in the objective function and in the constraints. The points of the dual problem where the objective function is nondifferentiable are known: the method presented here takes advantage of this fact to propose modifications necessary in the reduced gradient method to guarantee convergence.     

A primal-dual subgradient method for time staged capacity expansion planning

We model capacity expansion problems as nondifferentiable convex programs. A dual to this problem is also formulated as a nondifferentiable convex program. The solution methodology we utilize is a primal-dual subgradient approach. Here the primal-dual pair is utilized in step length determination. The special structure of these capacity expansion problems also results in other simplifications. In particular, unlike the application of subgradient optimization for general convex programs, the test for feasibility in certain capacity expansion problems is straightforward. Further, quadratic programs associated with projection operators are also avoided by using the special problem structure. The algorithm is shown to be convergent. In order to illustrate the applicability of our methodology, we discuss its application to a time dynamic power generation capacity planning problem. Computational results with this application is also provided.     

From solvability and approximation of variational inequalities to solution of nondifferentiable optimization problems in contact mechanics

In this paper, we first gather existence results for linear and for pseudo-monotone variational inequalities in reflexive Banach spaces. We discuss the necessity of the involved coerciveness conditions and their relationship. Then, we combine Mosco convergence of convex closed sets with an approximation of pseudo-monotone bifunctions and provide a convergent approximation procedure for pseudo-monotone variational inequalities in reflexive Banach spaces. Since hemivariational inequalities in linear elasticity are pseudo-monotone, our approximation method applies to nonmonotone contact problems. We sketch how regularization of the involved nonsmooth functionals together with finite element approximation lead to an efficient numerical solution method for these nonconvex nondifferentiable optimization problems. To illustrate our theory, we give a numerical example of a 2D linear elastic block under a given nonmonotone contact law.     

Nonmonotone and Monotone Active-Set Methods for Image Restoration,Part 2: Numerical Results

Active-set methods based on augmented Lagrangian smoothing of nondifferentiable optimization problems arising in image restoration are studied through numerical experiments. Implemented algorithms for solving both one-dimensional and two-dimensional image restoration problems are described. A new, direct way for solving the constrained optimization problem appearing in the inner iteration of the monotone algorithms is presented. Several numerical examples are included.     

Portfolio optimization by minimizing conditional value-at-risk via nondifferentiable optimization

Conditional Value-at-Risk (CVaR) is a portfolio evaluation function having appealing features such as sub-additivity and convexity. Although the CVaR function is nondifferentiable, scenario-based CVaR minimization problems can be reformulated as linear programs (LPs) that afford solutions via widely-used commercial softwares. However, finding solutions through LP formulations for problems having many financial instruments and a large number of price scenarios can be time-consuming as the dimension of the problem greatly increases. In this paper, we propose a two-phase approach that is suitable for solving CVaR minimization problems having a large number of price scenarios. In the first phase, conventional differentiable optimization techniques are used while circumventing nondifferentiable points, and in the second phase, we employ a theoretically convergent, variable target value nondifferentiable optimization technique. The resultant two-phase procedure guarantees infinite convergence to optimality. As an optional third phase, we additionally perform a switchover to a simplex solver starting with a crash basis obtained from the second phase when finite convergence to an exact optimum is desired. This three phase procedure substantially reduces the effort required in comparison with the direct use of a commercial stand-alone simplex solver (CPLEX 9.0). Moreover, the two-phase method provides highly-accurate near-optimal solutions with a significantly improved performance over the interior point barrier implementation of CPLEX 9.0 as well, especially when the number of scenarios is large. We also provide some benchmarking results on using an alternative popular proximal bundle nondifferentiable optimization technique.     

Regularization methods for optimization problems with probabilistic constraints

We analyze nonlinear stochastic optimization problems with probabilistic constraints on nonlinear inequalities with random right hand sides. We develop two numerical methods with regularization for their numerical solution. The methods are based on first order optimality conditions and successive inner approximations of the feasible set by progressive generation of p-efficient points. The algorithms yield an optimal solution for problems involving α-concave probability distributions. For arbitrary distributions, the algorithms solve the convex hull problem and provide upper and lower bounds for the optimal value and nearly optimal solutions. The methods are compared numerically to two cutting plane methods.     

Convergence and Computational Analyses for Some Variable Target Value and Subgradient Deflection Methods

We consider two variable target value frameworks for solving large-scale nondifferentiable optimization problems. We provide convergence analyses for various combinations of these variable target value frameworks with several direction-finding and step-length strategies including the pure subgradient method, the volume algorithm, the average direction strategy, and a generalized Polyak-Kelley cutting plane method. In addition, we suggest a further enhancement via a projected quadratic-fit line-search whenever any of these algorithmic procedures experiences an improvement in the objective value. Extensive computational results on different classes of problems reveal that these modifications and enhancements significantly improve the effectiveness of the algorithms to solve Lagrangian duals of linear programs, even yielding a favorable comparison against the commercial software CPLEX 8.1.     

Optimal Control of Continuous Casting by Nondifferentiable Multiobjective Optimization

A new version of an interactive NIMBUS method for nondifferentiable multiobjective optimization is described. It is based on the reference point idea and the classification of the objective functions. The original problem is transformed into a single objective form according to the classification information. NIMBUS has been designed especially to be able to handle complicated real-life problems in a user-friendly way.The NIMBUS method is used for solving an optimal control problem related to the continuous casting of steel. The main goal is to minimize the defects in the final product. Conflicting objective functions are constructed according to certain metallurgical criteria and some technological constraints. Due to the phase changes during the cooling process there exist discontinuities in the derivative of the temperature distribution. Thus, the problem is nondifferentiable.Like many real-life problems, the casting model is large and complicated and numerically demanding. NIMBUS provides an efficient way of handling the difficulties and, at the same time, aids the user in finding a satisficing solution. In the end, some numerical experiments are reported and compared with earlier results.     

An Algorithm for Non-Linear Network Programming: Implementation,Results and Comparisons

This paper evaluates an algorithm for solving network flow optimization problems with quadratic cost functions. Strategies for fast implementation are discussed and the results of extensive numerical tests are given. The performance of the algorithm measured by CPU time is compared with that of the convex simplex method specialized for quadratic network programming. Performance of the two methods is analysed with respect to network size and density, and other parameters of interest. The algorithm is shown to perform significantly better on the majority of problems. We also show how the algorithm may be used to solve non-linear convex network optimization problems by the use of sequential quadratic programming.     

The CoMirror algorithm for solving nonsmooth constrained convex problems

We introduce a first-order Mirror-Descent (MD) type algorithm for solving nondifferentiable convex problems having a combination of simple constraint set X (ball, simplex, etc.) and an additional functional constraint. The method is tuned to exploit the structure of X by employing an appropriate non-Euclidean distance-like function. Convergence results and efficiency estimates are derived. The performance of the algorithm is demonstrated by solving certain image deblurring problems.     

Extremal properties of nondifferentiable convex functions on euclidean sets of combinations with repetitions

A general approach is suggested for studying extremal properties of nondifferentiable convex functions on Euclidean combinatorial sets. On the basis of this approach, by solving the linear optimization problem on a set of combinations with repetitions, we obtain estimates of minimum values of convex and strongly convex objective functions in optimization problems on sets of combinations with repetitions and establish sufficient conditions for the existence of the corresponding minima. Kharkov Institute of Radioelectronics, Kharkov. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 6, pp. 680–691, June, 1994.     

A Smoothing Function Approach to Joint Chance-Constrained Programs

In this article, we consider a DC (difference of two convex functions) function approach for solving joint chance-constrained programs (JCCP), which was first established by Hong et al. (Oper Res 59:617–630, 2011). They used a DC function to approximate the probability function and constructed a sequential convex approximation method to solve the approximation problem. However, the DC function they used was nondifferentiable. To alleviate this difficulty, we propose a class of smoothing functions to approximate the joint chance-constraint function, based on which smooth optimization problems are constructed to approximate JCCP. We show that the solutions of a sequence of smoothing approximations converge to a Karush–Kuhn–Tucker point of JCCP under a certain asymptotic regime. To implement the proposed method, four examples in the class of smoothing functions are explored. Moreover, the numerical experiments show that our method is comparable and effective.     

Attractive force search algorithm for piecewise convex maximization problems

We consider mathematical programming problems with the so-called piecewise convex objective functions. A solution method for this interesting and important class of nonconvex problems is presented. This method is based on Newton??s law of universal gravitation, multicriteria optimization and Helly??s theorem on convex bodies. Numerical experiments using well known classes of test problems on piecewise convex maximization, convex maximization as well as the maximum clique problem show the efficiency of the approach.     

Exterior Minimum-Penalty Path-Following Methods in Semidefinite Programming

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable but convex. It covers several standard problems, such as linear and quadratic programming, and has many applications in engineering. In this paper, we introduce the notion of minimal-penalty path, which is defined as the collection of minimizers for a family of convex optimization problems, and propose two methods for solving the problem by following the minimal-penalty path from the exterior of the feasible set. Our first method, which is also a constraint-aggregation method, achieves the solution by solving a sequence of linear programs, but exhibits a zigzagging behavior around the minimal-penalty path. Our second method eliminates the above drawback by following efficiently the minimum-penalty path through the centering and ascending steps. The global convergence of the methods is proved and their performance is illustrated by means of an example.     

A bilinear approach to the pooling problem†

In this paper we present an algorithm for the pooling problem in refinery optimization based on a bilinear programming approach. The pooling problem occurs frequently in process optimization problems, especially refinery planning models. The main difficulty is that pooling causes an inherent nonlinearity in the otherwise linear models. We shall define the problem by formulating an aggregate mathematical model of a refinery, comment on solution methods for pooling problems that have been presented in the literature, and develop a new method based on convex approximations of the bilinear terms. The method is illustrated on numerical examples