Conjugate Duality and the Control of Linear Discrete Systems

In this paper we deal with the minimization of a convex function over the solution set of a range inclusion problem determined by a multivalued operator with convex graph. We attach a dual problem to it, provide regularity conditions guaranteeing strong duality and derive for the resulting primal–dual pair necessary and sufficient optimality conditions. We also discuss the existence of optimal solutions for the primal and dual problems by using duality arguments. The theoretical results are applied in the context of the control of linear discrete systems.     

The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

Existence of optimal controls for a partially observed semimartingale

For a partially observed control problem we prove the existence of an optimal control. Purely probabilistic means as Skorokhod imbedding and convergence are used to derive the result.     

Some Results on Skorokhod Embedding and Robust Hedging with Local Time

In this paper, we provide some results on Skorokhod embedding with local time and its applications to the robust hedging problem in finance. First we investigate the robust hedging of options depending on the local time by using the recently introduced stochastic control approach, in order to identify the optimal hedging strategies, as well as the market models that realize the extremal no-arbitrage prices. As a by-product, the optimality of Vallois’ Skorokhod embeddings is recovered. In addition, under appropriate conditions, we derive a new solution to the two-marginal Skorokhod embedding as a generalization of the Vallois solution. It turns out from our analysis that one needs to relax the monotonicity assumption on the embedding functions in order to embed a larger class of marginal distributions. Finally, in a full-marginal setting where the stopping times given by Vallois are well ordered, we construct a remarkable Markov martingale which provides a new example of fake Brownian motion.     

Convex duality and the Skorokhod Problem. II

In this paper we consider Skorokhod Problems on polyhedral domains with a constant and possibly oblique constraint direction specified on each face of the domain, and with a corresponding cone of constraint directions at the intersection of faces. In part one of this paper we used convex duality to develop new methods for the construction of solutions to such Skorokhod Problems, and for proving Lipschitz continuity of the associated Skorokhod Maps. The main alternative approach to Skorokhod Problems of this type is the reflection mapping technique introduced by Harrison and Reiman [8]. In this part of the paper we apply the theory developed in part one to show that the reflection mapping technique of [8] is restricted to a slight generalization of the class of problems originally considered in [8]. We further illustrate the power of the duality approach by applying it to two other classes of Skorokhod Problems – those with normal directions of constraint, and a new class that arises from a model of processor sharing in communication networks. In particular, we prove existence of solutions to and Lipschitz continuity of the Skorokhod Maps associated with each of these Skorokhod Problems. Received: 17 April 1998 / Revised: 8 January 1999     

Strictly feasible solutions and strict complementarity in multiple objective linear optimization

Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification.     

Duality in infinite dimensional linear programming

We consider the class of linear programs with infinitely many variables and constraints having the property that every constraint contains at most finitely many variables while every variable appears in at most finitely many constraints. Examples include production planning and equipment replacement over an infinite horizon. We form the natural dual linear programming problem and prove strong duality under a transversality condition that dual prices are asymptotically zero. That is, we show, under this transversality condition, that optimal solutions are attained in both primal and dual problems and their optimal values are equal. The transversality condition, and hence strong duality, is established for an infinite horizon production planning problem.This material is based on work supported by the National Science Foundation under Grant No. ECS-8700836.     

Implicit time discretization for the mean curvature flow equation

In this paper we apply the method of implicit time discretization to the mean curvature flow equation including outer forces. In the framework ofBV-functions we construct discrete solutions iteratively by minimizing a suitable energy-functional in each time step. Employing geometric and variational arguments we show an energy estimate which assures compactness of the discrete solutions. An additional convergence condition excludes a loss of area in the limit. Thus existence of solutions to the continuous problem can be derived. We append a brief discussion of the related Mullins-Sekerka equation.This work was supported by the Deutsche Forschungsgemeinschaft through Sonderforschungsbereich 256, Bonn     

Finite element approximation of a prestressed shell model

This work deals with the finite element approximation of a prestressed shell model formulated in Cartesian coordinates system. The considered constrained variational problem is not necessarily positive. Moreover, because of the constraint, it cannot be discretized by conforming finite element methods. A penalized version of the model and its discretization are then proposed. We prove existence and uniqueness results of solutions for the continuous and discrete problems, and we derive optimal a priori error estimates. Numerical tests that validate and illustrate our approach are given.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

On The Existence of a Countable Set of Positive Solutions for a Nonlocal Boundary-Value Problem with Vector-Valued Response

ABSTRACT

The existence of a countable set of positive solutions for a nonlocal boundary-value problem with vector-valued response is investigated by some variational methods based on the idea of the Fenchel conjugate. As a consequence of a duality developed here, we obtain the existence of a countable set of solutions for our problem that are minimizers to a certain integral functional. We derive (also in the superlinear case) a measure of a duality gap between primal and dual functional for approximate solutions.     

Complex Minimax Fractional Programming of Analytic Functions

We prove that a minmax fractional programming problem is equivalent to a minimax nonfractional parametric problem for a given parameter in complex space. Using a parametric approach, we establish the Kuhn-Tucker type necessary optimality conditions and prove the existence theorem of optimality for complex minimax fractional programming in the framework of generalized convexity. Subsequently, we apply the optimality conditions to formulate a one-parameter dual problem and prove weak duality, strong duality, and strict converse duality theorems involving generalized convex complex functions. This research was partly supported by NSC, Taiwan.     

Cahn-Hilliard方程的拟谱逼近

该文讨论用Ｌｅｇｅｎｄｒｅ拟谱方法数值求解非线性Ｃａｈｎ Ｈｉｌｌｉａｒｄ方程的Ｄｉｒｉｃｈｌｅｔ问题．建立了其半离散和全离散逼近格式，它们保持原问题能量耗散的性质．证明了离散解的存在唯一性，并给出了最佳误差估计．数值实验也证实了我们的结果．     

The fractional Landau�CLifshitz�CGilbert equation and the heat flow of harmonic maps

We consider a quasi-static droplet motion based on contact angle dynamics on a planar surface. We derive a natural time-discretization and prove the existence of a weak global-in-time solution in the continuum limit. The time discrete interface motion is described in comparison with barrier functions, which are classical sub- and super-solutions in a local neighborhood. This barrier property is different from standard viscosity solutions since there is no comparison principle for our problem. In the continuum limit the barrier properties still hold in a modified sense.     

An easy way to teach interior-point methods

In this paper the duality theory of Linear Optimization (LO) is built up based on ideas emerged from interior-point methods (IPMs). All we need is elementary calculus. We will embed the LO problem and its dual in a self-dual skew-symmetric problem. Most duality results, except the existence of a strictly complementary solution, are trivial for this embedding problem. The existence of the central path and its convergence to the analytic center of the optimal face will be proved. The proof is based on an elementary, careful analysis of a Newton step.We show also that if an almost optimal solution on the central path is known, then a simple strongly polynomial rounding procedure provides an exact strictly complementary optimal solution.The all-one vector is feasible for the embedding problem and it is an interior-point on the central path. This way an elegant solution to the initialization of IPMs is obtained as well. This approach allows to apply any IPM to the embedding problem while complexity results obtained for feasible IPMs are preserved.     

Linear Stieltjes equation with generalized riemann integral and existence of regulated solutions

1. IntroductiollIn the last two decades the memann generalized integral, having values in B-spaces,has been increasingly studied.The development in this area mainly concerns the HenstoCk-Kurzweil (see e.g. I1, 2]),and the Dushnik and the Young integrals (see e.g. I3]). Recently there appeared in the1iterature many proper app1ications in this field ("proper" here being considered in thesense that the results are not disguises of an essentially finite dimensional frame) (see e.g.[4, 5]).In t…     

Towards Strong Duality in Integer Programming

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.     

Pseudoinvexity,optimality conditions and efficiency in multiobjective problems; duality

In this paper, we establish characterizations for efficient solutions to multiobjective programming problems, which generalize the characterization of established results for optimal solutions to scalar programming problems. So, we prove that in order for Kuhn–Tucker points to be efficient solutions it is necessary and sufficient that the multiobjective problem functions belong to a new class of functions, which we introduce. Similarly, we obtain characterizations for efficient solutions by using Fritz–John optimality conditions. Some examples are proposed to illustrate these classes of functions and optimality results. We study the dual problem and establish weak, strong and converse duality results.     

Strong duality in robust semi-definite linear programming under data uncertainty

This article develops the deterministic approach to duality for semi-definite linear programming problems in the face of data uncertainty. We establish strong duality between the robust counterpart of an uncertain semi-definite linear programming model problem and the optimistic counterpart of its uncertain dual. We prove that strong duality between the deterministic counterparts holds under a characteristic cone condition. We also show that the characteristic cone condition is also necessary for the validity of strong duality for every linear objective function of the original model problem. In addition, we derive that a robust Slater condition alone ensures strong duality for uncertain semi-definite linear programs under spectral norm uncertainty and show, in this case, that the optimistic counterpart is also computationally tractable.     

Employing different loss functions for the classification of images via supervised learning

Supervised learning methods are powerful techniques to learn a function from a given set of labeled data, the so-called training data. In this paper the support vector machines approach is applied to an image classification task. Starting with the corresponding Tikhonov regularization problem, reformulated as a convex optimization problem, we introduce a conjugate dual problem to it and prove that, whenever strong duality holds, the function to be learned can be expressed via the dual optimal solutions. Corresponding dual problems are then derived for different loss functions. The theoretical results are applied by numerically solving a classification task using high dimensional real-world data in order to obtain optimal classifiers. The results demonstrate the excellent performance of support vector classification for this particular problem.