Global optimality conditions for cubic minimization problem with box or binary constraints

In this article, we provide optimality conditions for global solutions to cubic minimization problems with box or binary constraints. Our main tool is an extension of the global subdifferential approach, developed by Jeyakumar et al. (J Glob Optim 36:471–481, 2007; Math Program A 110:521–541, 2007). We also derive optimality conditions that characterize global solutions completely in the case where the cubic objective function contains no cross terms. Examples are given to demonstrate that the optimality conditions can effectively be used for identifying global minimizers of certain cubic minimization problems with box or binary constraints.     

Iterative Thresholding Meets Free-Discontinuity Problems

Free-discontinuity problems describe situations where the solution of interest is defined by a function and a lower-dimensional set consisting of the discontinuities of the function. Hence, the derivative of the solution is assumed to be a ‘small’ function almost everywhere except on sets where it concentrates as a singular measure. This is the case, for instance, in crack detection from fracture mechanics or in certain digital image segmentation problems. If we discretize such situations for numerical purposes, the free-discontinuity problem in the discrete setting can be re-formulated as that of finding a derivative vector with small components at all but a few entries that exceed a certain threshold. This problem is similar to those encountered in the field of ‘sparse recovery’, where vectors with a small number of dominating components in absolute value are recovered from a few given linear measurements via the minimization of related energy functionals. Several iterative thresholding algorithms that intertwine gradient-type iterations with thresholding steps have been designed to recover sparse solutions in this setting. It is natural to wonder if and/or how such algorithms can be used towards solving discrete free-discontinuity problems. The current paper explores this connection, and, by establishing an iterative thresholding algorithm for discrete free-discontinuity problems, provides new insights on properties of minimizing solutions thereof.     

Improvement sets and vector optimization

In this paper we focus on minimal points in linear spaces and minimal solutions of vector optimization problems, where the preference relation is defined via an improvement set E. To be precise, we extend the notion of E-optimal point due to Chicco et al. in [4] to a general (non-necessarily Pareto) quasi ordered linear space and we study its properties. In particular, we relate the notion of improvement set with other similar concepts of the literature and we characterize it by means of sublevel sets of scalar functions. Moreover, we obtain necessary and sufficient conditions for E-optimal solutions of vector optimization problems through scalarization processes by assuming convexity assumptions and also in the general (nonconvex) case. By applying the obtained results to certain improvement sets we generalize well-known results of the literature referred to efficient, weak efficient and approximate efficient solutions of vector optimization problems.     

Optimal allocation of simulation experiments in discrete stochastic optimization and approximative algorithms

Approximate solutions for discrete stochastic optimization problems are often obtained via simulation. It is reasonable to complement these solutions by confidence regions for the argmin-set. We address the question how a certain total number of random draws should be distributed among the set of alternatives. Two goals are considered: the minimization of the costs caused by using a statistical estimate of the true argmin, and the minimization of the expected size of the confidence sets. We show that an asymptotically optimal sampling strategy in the case of normal errors can be obtained by solving a convex optimization problem. To reduce the computational effort we propose a regularization that leads to a simple one-step allocation rule.     

Smoothing methods for nonsmooth, nonconvex minimization

We consider a class of smoothing methods for minimization problems where the feasible set is convex but the objective function is not convex, not differentiable and perhaps not even locally Lipschitz at the solutions. Such optimization problems arise from wide applications including image restoration, signal reconstruction, variable selection, optimal control, stochastic equilibrium and spherical approximations. In this paper, we focus on smoothing methods for solving such optimization problems, which use the structure of the minimization problems and composition of smoothing functions for the plus function (x)₊. Many existing optimization algorithms and codes can be used in the inner iteration of the smoothing methods. We present properties of the smoothing functions and the gradient consistency of subdifferential associated with a smoothing function. Moreover, we describe how to update the smoothing parameter in the outer iteration of the smoothing methods to guarantee convergence of the smoothing methods to a stationary point of the original minimization problem.     

Minimization of Linear Functionals Defined on Solutions of Large-Scale Discrete Ill-Posed Problems

The minimization of linear functionals defined on the solutions of discrete ill-posed problems arises, e.g., in the computation of confidence intervals for these solutions. In 1990, Eldén proposed an algorithm for this minimization problem based on a parametric programming reformulation involving the solution of a sequence of trust-region problems, and using matrix factorizations. In this paper, we describe MLFIP, a large-scale version of this algorithm where a limited-memory trust-region solver is used on the subproblems. We illustrate the use of our algorithm in connection with an inverse heat conduction problem. AMS subject classification (2000) 65F22     

On the structure of the solution set for the single facility location problem with average distances

This paper analyzes continuous single facility location problems where the demand is randomly defined by a given probability distribution. For these types of problems that deal with the minimization of average distances, we obtain geometrical characterizations of the entire set of optimal solutions. For the important case of total polyhedrality on the plane we derive efficient algorithms with polynomially bounded complexity. We also develop a discretization scheme that provides ${\varepsilon}$ -approximate solutions of the original problem by solving simpler location problems with points as demand facilities.     

Maximax and minimax rearrangement optimization problems

In this paper we present a general theory concerning two rearrangement optimization problems; one of maximization and the other of minimization type. The structure of the cost functional allows to formulate the two problems as maximax and minimax optimization problems. The latter proves to be far more interesting than the former. As an application of the theory we investigate a shape optimization problem which has already been addressed by other authors; however, here we prove our method is more efficient, and has the advantage that it captures more features of the optimal solutions than those obtained by others. The paper ends with a special case of the minimax problem, where we are able to obtain a minimum size estimate related to the optimal solution.     

Equilibrium programming using proximal-like algorithms

We compute constrained equilibria satisfying an optimality condition. Important examples include convex programming, saddle problems, noncooperative games, and variational inequalities. Under a monotonicity hypothesis we show that equilibrium solutions can be found via iterative convex minimization. In the main algorithm each stage of computation requires two proximal steps, possibly using Bregman functions. One step serves to predict the next point; the other helps to correct the new prediction. To enhance practical applicability we tolerate numerical errors. Research supported partly by the Norwegian Research Council, project: Quantec 111039/401.     

A penalty approximation for a unilateral contact problem in non-linear elasticity

Using Ball's approach to non-linear elasticity, and in particular his concept of polyconvexity, we treat a unilateral three-dimensional contact problem for a hyperelastic body under volume and surface forces. Here the unilateral constraint is described by a sublinear function which can model the contact with a rigid convex cone. We obtain a solution to this generally non-convex, semicoercive Signorinin problem as a limit of solutions of related energy minimization problems involving friction normal to the contact surface where the friction coefficient goes to infinity. Thus we extend an approximation result of Duvaut and Lions for linear-elastic unilateral contact problems to finite deformations and to a class of non-linear elastic materials including the material models of Ogden and of Mooney-Rivlin for rubberlike materials. Moreover, the underlying penalty method is shown to be exact, that is a sufficiently large friction coefficient in the auxiliary energy minimization problems suffices to produce a solution of the original unilateral problem, provided a Lagrange multiplier to the unilateral constraint exists.     

Randomized first order algorithms with applications to ℓ 1-minimization

In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of the solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of ? ₁ minimization arising in sparsity-oriented signal processing. We demonstrate, both theoretically and by numerical examples, that when seeking for medium-accuracy solutions of large-scale ? ₁ minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the state-of-the art deterministic methods.     

Mixed sensitivity minimization problems with rationall 1-optimal solutions

Up to this time, the only known method to solve the discrete-time mixed sensitivity minimization problem inl ¹ has been to use a certain infinite-dimensional linear programming approach, presented by Dahleh and Pearson in 1988 and later modified by Mendlovitz. That approach does not give in general true optimal solutions; only suboptimal ones are obtained. Here, for the first time, the truel ¹-optimal solutions are found for some mixed sensitivity minimization problems. In particular, Dahleh and Pearson construct an 11h order suboptimal compensator for a certain second-order plan with first-order weight functions; it is shown that the unique optimal compensator for that problem is rational and of order two. The author discovered this fact when trying out a new scheme of solving the infinite-dimensional linear programming system. This scheme is of independent interest, because when it is combined with the Dahleh-Pearson-Mendlovitz scheme, it gives both an upper bound and a lower bound on the optimal performance; hence, it provides the missing error bound that enables one to truncate the solution. Of course, truncation is appropriate only if the order of the optimal compensator is too high. This may indeed be the case, as is shown with an example where the order of the optimal compensator can be arbitrarily high.     

Lyapunov inequalities for the periodic boundary value problem at higher eigenvalues

This paper is devoted to provide some new results on Lyapunov type inequalities for the periodic boundary value problem at higher eigenvalues. Our main result is derived from a detailed analysis on the number and distribution of zeros of nontrivial solutions and their first derivatives, together with the study of some special minimization problems. This allows to obtain the optimal constants. Our applications include the Hill's equation where we give some new conditions on its stability properties and also the study of periodic and nonlinear problems at resonance where we show some new conditions which allow to prove the existence and uniqueness of solutions.     

On Hölder continuity of approximate solutions to parametric equilibrium problems

We establish verifiable sufficient conditions for Hölder continuity of approximate solutions to parametric equilibrium problems, when solutions may be not unique. Many examples are provided to illustrate the need of considering approximate solutions instead of exact solutions and the essentialness of the imposed assumptions. As applications, we derive this Hölder continuity for constrained minimization, variational inequalities and fixed point problems.     

An approximation theory of matrix rank minimization and its application to quadratic equations

Matrix rank minimization problems are gaining plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization problem can be approximated to any level of accuracy via continuous optimization (especially, linear and nonlinear semidefinite programming) problems. One of the main results in this paper shows that if the feasible set of the problem has a minimum rank element with the least Frobenius norm, then any accumulation point of solutions to the approximation problem, as the approximation parameter tends to zero, is a minimum rank solution of the original problem. The tractability under certain conditions and convex relaxation of the approximation problem are also discussed. An immediate application of this theory to the system of quadratic equations is presented in this paper. It turns out that the condition for such a system without a nonzero solution can be characterized by a rank minimization problem, and thus the proposed approximation theory can be used to establish some sufficient conditions for the system to possess only zero solution.     

A polynomial oracle-time algorithm for convex integer minimization

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer minimization problems for which our approach provides polynomial time solution algorithms.     

Γ-convergence and homogenization of functionals in Sobolev spaces with variable exponents

This paper is devoted to homogenization and minimization problems for variational functionals in the framework of Sobolev spaces with continuous variable exponents. We assume that the sequence of exponents converges in the uniform metric and that the Lagrangian has a periodic microstructure. Then under natural coerciveness assumptions we prove a Γ-convergence result and, as a consequence, the convergence of minimizers (solutions to the corresponding Euler equations).     

Minimal Zero Norm Solutions of Linear Complementarity Problems

In this paper, we study minimal zero norm solutions of the linear complementarity problems, defined as the solutions with smallest cardinality. Minimal zero norm solutions are often desired in some real applications such as bimatrix game and portfolio selection. We first show the uniqueness of the minimal zero norm solution for Z-matrix linear complementarity problems. To find minimal zero norm solutions is equivalent to solve a difficult zero norm minimization problem with linear complementarity constraints. We then propose a p norm regularized minimization model with p in the open interval from zero to one, and show that it can approximate minimal zero norm solutions very well by sequentially decreasing the regularization parameter. We establish a threshold lower bound for any nonzero entry in its local minimizers, that can be used to identify zero entries precisely in computed solutions. We also consider the choice of regularization parameter to get desired sparsity. Based on the theoretical results, we design a sequential smoothing gradient method to solve the model. Numerical results demonstrate that the sequential smoothing gradient method can effectively solve the regularized model and get minimal zero norm solutions of linear complementarity problems.     

A new greedy algorithm for the quadratic assignment problem

The classical greedy algorithm for discrete optimization problems where the optimal solution is a maximal independent subset of a finite ground set of weighted elements, can be defined in two ways which are dual to each other. The Greedy-In where a solution is constructed from the empty set by adding the next best element, one at a time, until we reach infeasibility, and the Greedy-Out where starting from the ground set we delete the next worst element, one at a time, until feasibility is reached. It is known that while the former provides an approximation ratio for maximization problems, its worst case performance is not bounded for minimization problems, and vice-versa for the later. However the Greedy-Out algorithm requires an oracle for checking the existence of a maximal independent subset which for most discrete optimization problems is a difficult task. In this work we present a Greedy-Out algorithm for the quadratic assignment problem by providing a combinatorial characterization of its solutions.