Duality for Set-Valued Multiobjective Optimization Problems,Part 1: Mathematical Programming

The duality of multiobjective problems is studied with the help of the apparatus of conjugate set-valued mappings introduced by the author. In this paper (Part 1), a duality theory is developed for set-valued mappings, which is then used to derive dual relations for some general multiobjective optimization problems which include convex programming and optimal control problems. Using this result, in the companion paper (Part 2), duality theorems are proved for multiobjective quasilinear and linear optimal control problems. The theory is applied to get dual relations for some multiobjective optimal control problem.     

Characterizations of set order relations and constrained set optimization problems via oriented distance function

Set-valued optimization problems are important and fascinating field of optimization theory and widely applied to image processing, viability theory, optimal control and mathematical economics. There are two types of criteria of solutions for the set-valued optimization problems: the vector criterion and the set criterion. In this paper, we adopt the set criterion to study the optimality conditions of constrained set-valued optimization problems. We first present some characterizations of various set order relations using the classical oriented distance function without involving the nonempty interior assumption on the ordered cones. Then using the characterizations of set order relations, necessary and sufficient conditions are derived for four types of optimal solutions of constrained set optimization problem with respect to the set order relations. Finally, the image space analysis is employed to study the c-optimal solution of constrained set optimization problems, and then optimality conditions and an alternative result for the constrained set optimization problem are established by the classical oriented distance function.     

Moment inequalities for sums of random matrices and their applications in optimization

In this paper, we consider various moment inequalities for sums of random matrices—which are well-studied in the functional analysis and probability theory literature—and demonstrate how they can be used to obtain the best known performance guarantees for several problems in optimization. First, we show that the validity of a recent conjecture of Nemirovski is actually a direct consequence of the so-called non-commutative Khintchine’s inequality in functional analysis. Using this result, we show that an SDP-based algorithm of Nemirovski, which is developed for solving a class of quadratic optimization problems with orthogonality constraints, has a logarithmic approximation guarantee. This improves upon the polynomial approximation guarantee established earlier by Nemirovski. Furthermore, we obtain improved safe tractable approximations of a certain class of chance constrained linear matrix inequalities. Secondly, we consider a recent result of Delage and Ye on the so-called data-driven distributionally robust stochastic programming problem. One of the assumptions in the Delage–Ye result is that the underlying probability distribution has bounded support. However, using a suitable moment inequality, we show that the result in fact holds for a much larger class of probability distributions. Given the close connection between the behavior of sums of random matrices and the theoretical properties of various optimization problems, we expect that the moment inequalities discussed in this paper will find further applications in optimization.     

Optimality Conditions for Extended Ky Fan Inequality with Cone and Affine Constraints and Their Applications

The purpose of this paper is to establish necessary and sufficient conditions for a point to be solution of an extended Ky Fan inequality. Using a separation theorem for convex sets, involving the quasi-interior of a convex set, we obtain optimality conditions for solutions of the generalized problem with cone and affine constraints. Then the main result is applied to vector optimization problems with cone and affine constraints and to duality theory.     

Integration with respect to operator-valued measures with applications to quantum estimation theory

Summary This paper is concerned with the development of an integration theory with respect to operator-valued measures which is required in the study of certain convex optimization problems. These convex optimization problems in their turn are rigorous formulations of detection theory in a quantum communication context, which generalise classical (Bayesian) detection theory. The integration theory which is developed in this paper is used in conjunction with convex analysis in Banach spaces to give necessary and sufficient conditions of optimality for this class of convex optimization problems.This research has been supported by the Air Force Office of Scientific Research under Grants AFOSR 77-3281D and AFOSR 82-0135 and the National Science Foundation under Grant NSF ENG 76-02860. A portion of this research was done while the first author was a CNR Visiting Professor at Istituto Matematico U. Dini, Università di Firenze, Italy.     

Inverse Scattering for the Problem with Impedance-type Boundary

This paper deals with the inverse scattering problems for the Helmholtz equation with impedance boundary condition. It aims at reconstructing the unknown impedance coefficient from the knowledge of scattered wave fields. We generalize the concept of classic solution (CS) to optimal solution (OS) by a nonlinear optimization problem. Then, based on potential theory, we establish an inversion procedure to get the approximation of OS which is defined as the regularized solution (RS) in this paper. The convergence result for RS is proven from which one can get OS and CS stably and efficiently.     

An asymptotical study of combinatorial optimization problems by means of statistical mechanics

The analogy between combinatorial optimization and statistical mechanics has proven to be a fruitful object of study. Simulated annealing, a metaheuristic for combinatorial optimization problems, is based on this analogy. In this paper we show how a statistical mechanics formalism can be utilized to analyze the asymptotic behavior of combinatorial optimization problems with sum objective function and provide an alternative proof for the following result: Under a certain combinatorial condition and some natural probabilistic assumptions on the coefficients of the problem, the ratio between the optimal solution and an arbitrary feasible solution tends to one almost surely, as the size of the problem tends to infinity, so that the problem of optimization becomes trivial in some sense. Whereas this result can also be proven by purely probabilistic techniques, the above approach allows one to understand why the assumed combinatorial condition is essential for such a type of asymptotic behavior.     

Greedy expansions in convex optimization

This paper is a follow-up to the author’s previous paper on convex optimization. In that paper we began the process of adjusting greedy-type algorithms from nonlinear approximation for finding sparse solutions of convex optimization problems. We modified there the three most popular greedy algorithms in nonlinear approximation in Banach spaces-Weak Chebyshev Greedy Algorithm, Weak Greedy Algorithm with Free Relaxation, and Weak Relaxed Greedy Algorithm-for solving convex optimization problems. We continue to study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such sparse approximate solutions using different greedy-type algorithms. In this paper we concentrate on greedy algorithms that provide expansions, which means that the approximant at the mth iteration is equal to the sum of the approximant from the previous, (m ? 1)th, iteration and one element from the dictionary with an appropriate coefficient. The problem of greedy expansions of elements of a Banach space is well studied in nonlinear approximation theory. At first glance the setting of a problem of expansion of a given element and the setting of the problem of expansion in an optimization problem are very different. However, it turns out that the same technique can be used for solving both problems. We show how the technique developed in nonlinear approximation theory, in particular, the greedy expansions technique, can be adjusted for finding a sparse solution of an optimization problem given by an expansion with respect to a given dictionary.     

Existence of a Saddle Point in Nonconvex Constrained Optimization

The existence of a saddle point in nonconvex constrained optimization problems is considered in this paper. We show that, under some mild conditions, the existence of a saddle point can be ensured in an equivalent p-th power formulation for a general class of nonconvex constrained optimization problems. This result expands considerably the class of optimization problems where a saddle point exists and thus enlarges the family of nonconvex problems that can be solved by dual-search methods.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

卫星舱内长方体群布局的优化模型及全局优化算法

本文研究了卫星舱内长方体群优化问题,建立了一个三维布局优化模型,并用图论,群论等工具克服了布局优化问题时断时续性质带来的困难,在此基础上构造了一个全局收敛的优化算法,文中所用的方法可用于求解类似问题。     

Existence of a Solution and Variational Principles for Vector Equilibrium Problems

In this paper, we prove an existence result for a solution to the vector equilibrium problems. Then, we establish variational principles, that is, vector optimization formulations of set-valued maps for vector equilibrium problems. A perturbation function     

Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma

In this paper, we present Lagrange multiplier necessary conditions for global optimality that apply to non-convex optimization problems beyond quadratic optimization problems subject to a single quadratic constraint. In particular, we show that our optimality conditions apply to problems where the objective function is the difference of quadratic and convex functions over a quadratic constraint, and to certain class of fractional programming problems. Our necessary conditions become necessary and sufficient conditions for global optimality for quadratic minimization subject to quadratic constraint. As an application, we also obtain global optimality conditions for a class of trust-region problems. Our approach makes use of outer-estimators, and the powerful S-lemma which has played key role in control theory and semidefinite optimization. We discuss numerical examples to illustrate the significance of our optimality conditions. The authors are grateful to the referees for their useful comments which have contributed to the final preparation of the paper.     

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.     

Solving a class of geometric programming problems by an efficient dynamic model

In this paper, a neural network model is constructed on the basis of the duality theory, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle to solve geometric programming (GP) problems. The main idea is to convert the GP problem into an equivalent convex optimization problem. A neural network model is then constructed for solving the obtained convex programming problem. By employing Lyapunov function approach, it is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. The simulation results also show that the proposed neural network is feasible and efficient.     

Properly Weighted Independence Systemsand Applications to Scheduling Problems

1.IntroductionIncombinatorialoptimizationthetheoryofindependencesystemsplaysanimportantrole.Oneofthereasonswasthatawiderangeofpracticalproblemscanbeformulatedasthemaximumweightindependentsetproblem(MWIprobleminshort)onanindependencesystem.AmatroidisaspecialindependencesystemwiththecharacterizationthatthegreedyalgorithmcanalwaysworkforthecorrespondingMWIproblemwithanyweightfunction.Thisisafundamentalgreedilysolvablecase11,21.Theothergreedilysolvablecaseshavereceivedstronginterestsinrecentyea…     

An oscillation theory for second-order integral differential equations

The primary purpose of this paper is to give an oscillation theory for second-order integral differential equations. It is shown that this theory follows in a natural way as “a corollary” from the more abstract approximation theory of quadratic forms given previously by the author. Thus, our ideas are primarily constructive and quantitative as opposed to the usual qualitative methods. We also note that the usual oscillation theory for second-order differential equations follows directly by our methods. Furthermore, our methods provide a unified theory for eigenvalue problems, optimization problems, and numerical approximation problems within this setting.In Section 1 we give the preliminaries for the remainder of the paper. In Section 2 we define the basic quadratic form and integral differential equation and give the relationships between them. These relationships are used (in Section 3) to give a theory of oscillation in our setting and some basic oscillation results. Finally, in Section 4 we give some deeper oscillation results.To emphasize the unifying methods of our ideas, this paper is presented as a companion paper to “A Numerical Approximation Theory for Second Order Integral Differential Equations.”     

A dynamical model for solving degenerate quadratic minimax problems with constraints

This paper presents a new neural network model for solving degenerate quadratic minimax (DQM) problems. On the basis of the saddle point theorem, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle, the equilibrium point of the proposed network is proved to be equivalent to the optimal solution of the DQM problems. It is also shown that the proposed network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.     

Parametric vector optimization

In this paper we consider a sequence of vector optimization problems. We aim to generalize a vector condition that relates the parametric function and the limit function. In particular, we recover our condition given in the scalar case. Our stability approach is such that the limit of the sequence of solutions that correspond to vector optimization problems to be a solution of a limit vector optimization problem. Therefore, one can view our statement as an existence result. This general framework has been used in several previous works. In our main theorem, we use the notion of strong lower cone-semi-continuity. An example is given to illustrate why only cone-lower semi-continuity for the limit function is not sufficient for our result.     

Assessing solution quality in stochastic programs

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.