On approximate solutions for robust convex semidefinite optimization problems

In this paper, we consider approximate solutions (\(\epsilon \)-solutions) for a convex semidefinite programming problem in the face of data uncertainty. Using robust optimization approach (worst-case approach), we prove an approximate optimality theorem and approximate duality theorems for \(\epsilon \)-solutions in robust convex semidefinite programming problem under the robust characteristic cone constraint qualification. Moreover, an example is given to illustrate the obtained results.     

An Algorithm for Approximate Multiparametric Convex Programming

For multiparametric convex nonlinear programming problems we propose a recursive algorithm for approximating, within a given suboptimality tolerance, the value function and an optimizer as functions of the parameters. The approximate solution is expressed as a piecewise affine function over a simplicial partition of a subset of the feasible parameters, and it is organized over a tree structure for efficiency of evaluation. Adaptations of the algorithm to deal with multiparametric semidefinite programming and multiparametric geometric programming are provided and exemplified. The approach is relevant for real-time implementation of several optimization-based feedback control strategies.     

On quasi $$\epsilon $$-solution for robust convex optimization problems

This paper devotes to the quasi \(\epsilon \)-solution (one sort of approximate solutions) for a robust convex optimization problem in the face of data uncertainty. Using robust optimization approach (worst-case approach), we establish approximate optimality theorem and approximate duality theorems in term of Wolfe type on quasi \(\epsilon \)-solution for the robust convex optimization problem. Moreover, some examples are given to illustrate the obtained results.     

非光滑向量均衡问题近似拟全局真有效解的最优性条件

本文研究一类非光滑向量均衡问题(Vector Equilibrium Problem)(VEP)关于近似拟全局真有效解的最优性条件.首先,利用凸集的拟相对内部型分离定理和Clarke次微分的性质,得到了问题(VEP)关于近似拟全局真有效解的最优性必要条件.其次,引入近似伪拟凸函数的概念,并给出具体实例验证其存在性,且在该凸性假设下建立了问题(VEP)关于近似拟全局真有效解的充分条件.最后,利用Tammer函数以及构建满足一定性质的非线性泛函,得到了问题(VEP)近似拟全局真有效解的标量化定理.     

非凸多目标优化模型的一类鲁棒逼近最优性条件

通过引入一类非凸多目标不确定优化问题，借助鲁棒优化方法，先建立了该不确定多目标优化问题的鲁棒对应模型；再借助标量化方法和广义次微分性质，刻画了该不确定多目标优化问题的鲁棒拟逼近有效解的最优性条件，推广和改进了相关文献的结论.     

Approximate Duality

We extend the Lagrangian duality theory for convex optimization problems to incorporate approximate solutions. In particular, we generalize well-known relationships between minimizers of a convex optimization problem, maximizers of its Lagrangian dual, saddle points of the Lagrangian, Kuhn–Tucker vectors, and Kuhn–Tucker conditions to incorporate approximate versions. As an application, we show how the theory can be used for convex quadratic programming and then apply the results to support vector machines from learning theory.     

Approximate solutions and scalarization in set-valued optimization

Abstract

Certain notions of approximate weak efficient solutions are considered for a set-valued optimization problem based on vector and set criteria approaches. For approximate solutions based on the vector approach, a characterization is provided in terms of an extended Gerstewitz’s function. For the set approach case, two notions of approximate weak efficient solutions are introduced using a lower and an upper quasi order relations for sets and further compactness and stability aspects are discussed for these approximate solutions. Existence and scalarization using a generalized Gerstewitz’s function are also established for approximate solutions, based on the lower set order relation.     

Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs

In this paper, an approximate augmented Lagrangian function for nonlinear semidefinite programs is introduced. Some basic properties of the approximate augmented Lagrange function such as monotonicity and convexity are discussed. Necessary and sufficient conditions for approximate strong duality results are derived. Conditions for an approximate exact penalty representation in the framework of augmented Lagrangian are given. Under certain conditions, it is shown that any limit point of a sequence of stationary points of approximate augmented Lagrangian problems is a KKT point of the original semidefinite program and that a sequence of optimal solutions to augmented Lagrangian problems converges to a solution of the original semidefinite program.     

Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

Robust truss topology optimization via semidefinite programming with complementarity constraints: a difference-of-convex programming approach

The robust truss topology optimization against the uncertain static external load can be formulated as mixed-integer semidefinite programming. Although a global optimal solution can be computed with a branch-and-bound method, it is very time-consuming. This paper presents an alternative formulation, semidefinite programming with complementarity constraints, and proposes an efficient heuristic. The proposed method is based upon the concave–convex procedure for difference-of-convex programming. It is shown that the method can often find a practically reasonable truss design within the computational cost of solving some dozen of convex optimization subproblems.     

Approximate Optimal Control of Nonlinear Fredholm Integral Equations

In this article, a numerical scheme on the basis of the measure theoretical approach for extracting approximate solutions of optimal control problems governed by nonlinear Fredholm integral equations is presented. The problem is converted to a linear programming in which its solution leads to construction of approximate solutions of the original problem. Finally, some numerical examples are given to demonstrate the efficiency of the approach.     

Semidefinite programming relaxations for semialgebraic problems

 A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples from diverse application fields. Received: May 10, 2001 / Accepted May 2002 Published online: April 10, 2003 Key Words. semidefinite programming – convex optimization – sums of squares – polynomial equations – real algebraic geometry The majority of this research has been carried out while the author was with the Control & Dynamical Systems Department, California Institute of Technology, Pasadena, CA 91125, USA.     

Robust solutions of uncertain complex-valued quadratically constrained programs

In this paper, we discuss complex convex quadratically constrained optimization with uncertain data. Using S-Lemma, we show that the robust counterpart of complex convex quadratically constrained optimization with ellipsoidal or intersection-of-two-ellipsoids uncertainty set leads to a complex semidefinite program. By exploring the approximate S-Lemma, we give a complex semidefinite program which approximates the NP-hard robust counterpart of complex convex quadratic optimization with intersection-of-ellipsoids uncertainty set.     

Penalty and Barrier Methods for Convex Semidefinite Programming

In this paper we present penalty and barrier methods for solving general convex semidefinite programming problems. More precisely, the constraint set is described by a convex operator that takes its values in the cone of negative semidefinite symmetric matrices. This class of methods is an extension of penalty and barrier methods for convex optimization to this setting. We provide implementable stopping rules and prove the convergence of the primal and dual paths obtained by these methods under minimal assumptions. The two parameters approach for penalty methods is also extended. As for usual convex programming, we prove that after a finite number of steps all iterates will be feasible.     

一些约束规划问题的近似全局最优解

首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题．最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解．     

Approximate factoring of the inverse

Computation of approximate factors for the inverse constitutes an algebraic approach to preconditioning large and sparse linear systems. In this paper, the aim is to combine standard preconditioning ideas with sparse approximate inverse approximation, to have dense approximate inverse approximations (implicitly). For optimality, the approximate factoring problem is associated with a minimization problem involving two matrix subspaces. This task can be converted into an eigenvalue problem for a Hermitian positive semidefinite operator whose smallest eigenpairs are of interest. Because of storage and complexity constraints, the power method appears to be the only admissible algorithm for devising sparse–sparse iterations. The subtle issue of choosing the matrix subspaces is addressed. Numerical experiments are presented.     

Optimization over structured subsets of positive semidefinite matrices via column generation

We develop algorithms to construct inner approximations of the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.     

Semidefinite programming and arithmetic circuit evaluation

We address the exact semidefinite programming feasibility problem (SDFP) consisting in checking that intersection of the cone of positive semidefinite matrices and some affine subspace of matrices with rational entries is not empty. SDFP is a convex programming problem and is often considered as tractable since some of its approximate versions can be efficiently solved, e.g. by the ellipsoid algorithm.We prove that SDFP can decide comparison of numbers represented by the arithmetic circuits, i.e. circuits that use standard arithmetical operations as gates. Our reduction may give evidence to the intrinsic difficulty of SDFP (contrary to the common expectations) and clarify the complexity status of the exact SDP—an old open problem in the field of mathematical programming.     

Semidefinite diagonal directions Monte Carlo algorithms for detecting necessary linear matrix inequality constraints

Hit-and-run algorithms are Monte Carlo methods for detecting necessary constraints in convex programming including semidefinite programming. The well known of these in semidefinite programming are semidefinite coordinate directions (SCD), semidefinite hypersphere directions (SHD) and semidefinite stand-and-hit (SSH) algorithms. SCD is considered to be the best on average and hence we use it for comparison.We develop two new hit-and-run algorithms in semidefinite programming that use diagonal directions. They are the uniform semidefinite diagonal directions (uniform SDD) and the original semidefinite diagonal directions (original SDD) algorithms. We analyze the costs and benefits of this change in comparison with SCD. We also show that both uniform SDD and original SDD generate points that are asymptotically uniform in the interior of the feasible region defined by the constraints.