Takayuki Okuno

Abstract We consider primal-dual pairs of semidefinite programs and assume that they are singular, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which would make them strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as the perturbation for regularization is driven to zero. Specifically, we fix two positive definite matrices, $$I_p$$ and $$I_d$$, say, (typically the identity matrices), and regularize the primal and dual problems by shifting their associated affine space by $$\eta I_p$$ and $$\varepsilon I_d$$, respectively, to recover interior feasibility of both problems, where $$\varepsilon $$ and $$\eta $$ are positive numbers. Then we analyze the behavior of the optimal value of the regularized problem when the perturbation is reduced to zero keeping the ratio between $$\eta $$ and $$\varepsilon $$ constant. A key feature of our analysis is that no further assumptions such as compactness or constraint qualifications are ever made. It will be shown that the optimal value of the perturbed problem converges to a value between the primal and dual optimal values of the original problems. Furthermore, the limiting optimal value changes “monotonically” from the primal optimal value to the dual optimal value as a function of $$\theta $$, if we parametrize $$(\varepsilon , \eta )$$ as $$(\varepsilon , \eta )=t(\cos \theta , \sin \theta )$$ and let $$t\rightarrow 0$$. Finally, the analysis leads us to the relatively surprising consequence that some representative infeasible interior-point algorithms for SDP generate sequences converging to a number between the primal and dual optimal values, even in the presence of a nonzero duality gap. Though this result is more of theoretical interest at this point, it might be of some value in the development of infeasible interior-point algorithms that can handle singular problems.

<p>The semi-infinite programming problem(SIP) is an optimization problem having an infinite number of inequality constrains and a finite number of variables. Since many important problems in the real world can be formulated in a natural manner as SIPs, many researchers have developed theories and algorithms for solving SIPs. In recent years, special SIPs involving infinitely many conic constraints (SICP) have been studied extensively because of its interesting structure and wide applications. In this paper, we introduce two algorithms for solving SICPs and observe their specific properties concerning global and local convergences.</p>

To solve the (linear) second-order cone programmes (SOCPs), the primal-dual interior-point method has been studied extensively so far and said to be the most efficient method by many researchers. On the other hand, the simplex-type method for SOCP is much less spotlighted, while it still keeps an important position for linear programmes. In this paper, we apply the dual-simplex primal-exchange (DSPE) method, which was originally developed for solving linear semi-infinite programmes, to the SOCP by reformulating the second-order cone constraint as an infinite number of linear inequality constraints. Then, we show that the sequence generated by the DSPE method converges to the SOCP optimum under certain assumptions. In the numerical experiments, we consider the situation to solve multiple SOCPs with similar structures successively. Then we observe that our simplex-type method can be more efficient than the existing interior-point method when we apply the so-called 'hot start' technique.

In this paper, we propose a new exchange method for solving convex semi-infinite programming problems (SIPs). The traditional exchange method solves a sequence of finitely relaxed subproblems, that is, subproblems with finitely many constraints chosen from the original constraints. On the other hand, our exchange method solves a sequence of new subproblems, in which the traditional finite subproblems are refined by the quadratic approximation. Under mild assumptions, the refined subproblems approximate the original SIP more precisely than the traditional subproblems. Moreover, although those subproblems are still SIPs, they can be solved efficiently by reformulating them as certain optimization problems with finitely many constraints. We establish the global convergence property of the proposed algorithm. Finally, we examine the efficiency of the algorithm by some numerical experiments.

The second-order cone program (SOCP) is an optimization problem with second-order cone (SOC) constraints and has achieved notable developments in the last decade. The classical semi-infinite program (SIP) is represented with infinitely many inequality constraints, and has been studied extensively so far. In this paper, we consider the SIP with infinitely many SOC constraints, called the SISOCP for short. Compared with the standard SIP and SOCP, the studies on the SISOCP are scarce, even though it has important applications such as Chebychev approximation for vector-valued functions. For solving the SISOCP, we develop an algorithm that combines a local reduction method with an SQP-type method. In this method, we reduce the SISOCP to an SOCP with finitely many SOC constraints by means of implicit functions and apply an SQP-type method to the latter problem. We study the global and local convergence properties of the proposed algorithm. Finally, we observe the effectiveness of the algorithm through some numerical experiments.

In this paper, we focus on the mathematical program with second-order cone (SOC) complementarity constraints, which contains the well-known mathematical program with nonnegative complementarity constraints as a subclass. For solving such a problem, we propose a smoothing-based sequential quadratic programming (SQP) method. We first replace the SOC complementarity constraints with equality constraints using the smoothing natural residual function, and apply the SQP method to the smoothed problem with decreasing the smoothing parameter. We show that the proposed algorithm possesses the global convergence property under the Cartesian p(0) property and the nondegeneracy assumptions. We finally observe the effectiveness of the algorithm by means of numerical experiments.

The semi-infinite program (SIP) is normally represented with infinitely many inequality constraints and has been studied extensively so far. However, there have been very few studies on the SIP involving conic constraints, even though it has important applications such as Chebyshev-like approximation, filter design, and so on. In this paper, we focus on the SIP with infinitely many conic constraints, called an SICP for short. We show that under the Robinson constraint qualification a local optimum of the SICP satisfies the KKT conditions that can be represented only with a finite subset of the conic constraints. We also introduce two exchange type algorithms for solving the convex SICP. We first provide an explicit exchange method and show that it has global convergence under the strict convexity assumption on the objective function. We then propose an algorithm combining a regularization method with the explicit exchange method and establish global convergence of the hybrid algorithm without the strict convexity assumption. We report some numerical results to examine the effectiveness of the proposed algorithms.