Presentations
Homogeneous algorithms for conic complementarity problems
(PDF)
Date:
SIAM Conference on Optimization, May 12, 2008
Place:
TThe Boston Park Plaza Hotel & Towers, Boston, MA, USA
Abstract:
The author proposed a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and show that the following properties hold:
(a) There is a path that is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions.
(b) Any accumulation point of the path is a solution of the homogeneous model.
(c) If the original problem is solvable, then every accumulation point of the path gives us a finite solution.
(d) If the original problem is strongly infeasible, then, under the assumption of Lipschitz continuity, any accumulation point of the path gives us a finite certificate proving infeasibility.
In this paper, we propose a class of algorithms for numerically tracing the path in (a) above.
By introducing a parameter $\theta \geq 0$ for quantifying a scaled Lipschitz property of a function, we obtain the following results:
(e1) The (infeasible) NT method takes $O(\sqrt{r}(1+\sqrt{r}\theta)\log \epsilon^{-1})$ iterations for the short-step, and $O(r(1+\theta)\log \epsilon^{-1})$ iterations for the semi-long- and long-step variants.
(e2) The (infeasible) $xy$ method or $yx$ method takes $O(\sqrt{r}(1+\sqrt{r}\theta)\log \epsilon^{-1})$ iterations for the short-step, $O(r(1+\theta)\log \epsilon^{-1})$ iterations for the semi-long-step, and $O(r^{1.5}(1+\theta)\log \epsilon^{-1})$ iterations for the long-step variant.
If the original complementarity problem is linear then $\theta = 0$ and the above results achieve the best iteration-complexity bounds known so far for linear or convex quadratic optimization problems over symmetric cones.
対称錐上の相補性問題に対する内点写像と同次モデルについて(in Japanese)
(PDF)
Date:
日本オペレーションズ・リサーチ学会秋季発表会(文献賞受賞者講演会), September 28, 2007
Place:
政策研究大学院大学，東京
Abstract:
この発表では，第35回日本オペレーションズ･リサーチ学会文献賞を拝受した論文\cite{aYOSHISE06}の概要を述べる．
1990年代より，線形計画問題に対する内点法をより広い問題群に拡張する研究が行われている．
拡張のひとつの方向は，線形計画問題の制約領域が閉凸錐である非負領域とアフィン空間の共通部分で与えられることに
着目し，（非負領域以外の）閉凸錐とアフィン空間の共通部分上での最適化を考える「錐最適化問題」への拡張である．
与えられた内積$\lag , \rag$と線形写像$A:\Re^n \ra \Re^m$に対して，$A^*$をその随伴写像とする．
$K \subseteq \Re^n$を閉凸錐, $K^*$をその双対錐
\[
K^* := \{s: \forall x \in K, \ \lag x, s \rag \geq 0 \}
\]
とし，$b \in \Re^m$, $c \in \Re^n$とすると, 錐最適化問題(PC)とその双対問題(DC)は以下のように与えられる．
\begin{eqnarray*}
& \mbox{(PC)} & \mbox{最小化} \ \lag c, x \rag \ \ \mbox{制約} \ Ax = b, \ x \in K, \\
& \mbox{(DC)} & \mbox{最大化} \ \lag b, z \rag \ \ \mbox{制約} \ A^*z + y = c, \ y \in K^*.
\end{eqnarray*}
$K$を非負領域あるいは半正定値実対称行列錐とすれば，(PC)はそれぞれ線形計画問題，半正定値計画問題となる．
双対錐の定義よりただちに(PC)と(DC)の間に弱双対定理が成り立つが，さらに
\beq
\label{eq:interior}
Ax = b, \ x \in \mbox{int} K, \ \ A^*z + y = c, \ y \in \mbox{int} K^*
\eeq
をみたす$(x,y,z)$が存在するならば，強双対定理がなりたつ\cite{aRENEGAR01}.
特に$\inter K$がEuclid的Jordan代数における対称錐であるとき，$K^*=K$であり，
さらに内点法によって解が求められる\cite{aFAYBUSOBICH97}.
このときの最適性の条件を一般化した問題が対称錐上の相補性問題である．
対称錐の閉包は限定的な閉凸錐であるが，$n \times n$半正定値実対称行列全体からなる錐と
$n$次元の2次錐を含む\cite{aFARAUT94}．
論文\cite{aYOSHISE06}では，これらの問題に多様な内点法を提案するための基礎定理を導いている．
Interior point methods for conic complementarity problems
(PDF)
Date:
9th International Workshop on High Performance Optimization Techniques: In honour of Kees Roos' 65th birthday, June 16, 2006
Place:
Delft University of Technology, Delft, The Netherlands
Abstract:
The complementarity problem is a fundamental problem in optimization that includes many continuation problems as special cases.
Let $(V,\circ)$ be a Euclidian Jordan algebra and $K$ be the symmetric cone of $V$.
We consider the mixed conic complementarity problem over $K$
where the function $F:K \times K \times \Re^m \rightarrow V \times \Re^m$ is continuous.
The class of CPs covers a wide range of optimization problems such as primal-dual linear, quadratic, semidefinite, and second-order cone programs.
Among others, it is well known that the optimality condition for linear and convex quadratic programs can be reduced to a linear and monotone complementarity problem over the positive orthant.
Many primal-dual interior point methods have been proposed first to address a monotone complementarity problem over a certain symmetric cone, or have been extended to it.
In this talk, we summarize the studies of interior point methods for the CP in terms of algorithms, central trajectories, convex cones, generalizations of the monotonicity, and applications.
Mixed complementarity problems over symmetric cones and a homogeneous model for the problems
(PDF)
Date:
SIAM Conference on Optimization, May 17, 2005
Place:
City Coference Centre, Stockholm, Sweden
Abstract:
We provide a homogeneous model for solving nonlinear mixed complementarity problems over symmetric cones. For a class of problems, the model has a bounded path and every accumulation point of the path gives information whether the original problem is solvable or strongly infeasible or other cases. We also show some optimization problems over symmetric cones whose optimality conditions can be cast as a problem in the class.
Interior Point Trajectories and a Homogeneous Model for Nonlinear Complementarity Problems over Symmetric Cones
(PDF)
(DVI)
Date:
ICCOPT 2004, August 3, 2004
Place:
Rensselaer Polytechnic Institute, Troy, New York, U.S.
Abstract:
We study the continuous trajectories for solving monotone nonlinear mixed complementarity problems over symmetric cones.
While the analysis in \cite{aFAYBUSOVICH97} depends on the optimization theory of convex log-barrier functions, our approach is based on the paper of Monteiro and Pang \cite{aMONTEIRO98}, where a vast set of conclusions concerning continuous trajectories is shown for monotone complementarity problems over the cone of symmetric positive semidefinite matrices.
As an application of the results, we propose a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and discuss its theoretical aspects.
To our knowledge, this is the first homogeneous model even for the problems over the cone of symmetric matrices or over the second order cone.
Generalized Central Paths and a Homogeneous Model for Complementarity Problems over Symmetric Cones
(DVI)
Date:
CORS/INFORMS 2004, May 18, 2004
Place:
Banff, Canada
Abstract:
In this paper, we propose a homogeneous model for solving monotone nonlinear complementarity problems over symmetric cones in a finite dimensional real Euclidean space and investigate its properties, including the existence and the limiting behavior of trajectories. Our analysis is based on the study of Monteiro and Pang (1998) for nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices.
相補性問題に対する同次型アルゴリズム
(PPT)
Date:
「日本OR学会春季発表会」, March 17, 2004
Place:
早稲田大学大久保キャンパス
A Homogeneous Model for Complementarity Problems over Symmetric Cones
(DVI)
Date:
「最適化：モデリングとアルゴリズム」, March 15, 2004
Place:
統計数理研究所
A Homogeneous Model for $P_0$ and $P_*$ Complemenatity Problems
(DVI)
Date:
ISMP 2003, August 21, 2003
Place:
Copenhagen, Deanmark
Abstract:
The homogeneous model for linear programs provides a most simple and firm theory in interior point algorithms, and several computational experiences report its practical efficiency. In 1999, Andersen and Ye generalized this model to monotone complementarity problems (CPs) and showed that the model inherits most of desirable properties under the monotonicity of the problems. However, in contrast to primal-dual interior point methods for CPs, the analysis deeply depends on the monotonicity and the extension to more general classes of CPs, e.g., $P_*$ CPs or $P_0$ CPs, is difficult as it is. In this paper, we propose a new homogeneous model which can be applied to $P_0$ CPs, and show that (i) there exists a trajectory which leads to a complementarity solution of the homogeneous model, (ii) from the solution, we can obtain a complementarity solution of the original problem, under the assumption that the original problem is a strictly feasible $P_*$ CP and (iii) any positive point, feasible or infeasible, can be set as a starting point of the trajectory and it does not need to use any big-${\cal M}$ parameter.
A Homogeneous Model for $P_0$ Complemenatity Problems
(DVI)
Date:
ICIAM 2003, July 10, 2003
Place:
Sydney, Australia
Abstract:
The homogeneous model for linear programs provides a most simple and firm theory in interior point algorithms and the computational experiences report its practical efficiency. In 1999, Andersen and Ye generalized this model to monotone complementarity problems (CPs) and showed that the model inherits most of desirable properties under the monotonicity of the problems. However, in contrast to other interior point methods for CPs, the analysis deeply depends on the monotonicity and the extension to more general classes of CPs; \eg, $P_*$ CPs or $P_0$ CPs, is difficult as it is. In this paper, we propose a new homogeneous model which can be applied to $P_0$ CPs, and give a sufficient condition for the existence of a trajectory which leads to a complementarity solution of the original problem.
サポートベクターマシンにおけるカーネル行列の最適化
発表スライド(DVI)
リポート用原稿(PDF)
Date:
「最適化：モデリングとアルゴリズム」, March 27--28, 2003
Place:
国立学校財務センター
Abstract:
サベクターマシン（SVM)は近年注目を集めるデータ解析法であり,中でもカーネル法は入力空間では分離が難しいデータセットに対しても有効な方法として広く知られている．Lancliet, et al\cite{Lancriet2002}は，効率のよいカーネル法を選択するためのモデルを方法を提案し，半正定値計画問題として定式化すると共に，モデルの有効性の検証を与えた．本稿では，この結果を基盤として，これまで提案されてきた各種のSVMに対してもカーネル行列の最適化モデルを示し，それらの有効性について議論する．
Existence of a Trajectory of a Homogeneous Model for $P_*$ Complementarity Problems
(DVI)
(PS)
Date:
McMaster Workshop, May 23--24, 2002
Place:
Hamilton, Ontario, Canada
Abstract:
It is well known that the homogeneous algorithm enjoys many desirable
properties when we apply it to linear programs or monotone
complementarity problems. However, the algorithm is quite different
from other interior point algorithms:
the monotonicity of the problem plays an essential role in the analysis
and it seems difficult to extend the algorithm to more generalized
problems as it is. In this talk, we will provide a generalized homogeneous
model which can be applied to $P_*$ complementarity problems and discuss
the induced mapping, the existence of the trajectory, the solution set,
and so on.
Self_regular Proximities and Nonlinear Complementarity Problems
(DVI)
(PS)
Date:
SIAM Optimization, May 20--22, 2002
Place:
Toronto, Ontario, Canada
Abstract:
We deal with interior point methods (IPMs) for solving a class of
so-called $\Pstar$ complementarity problems (CPs). First of all,
several elementary results about $\Pstar$ mappings and $\Pstar$
CPs are presented. Then we extend some notions introduced
recently by Peng, Roos and
Terlaky~\cite{int:Peng-Roos-Terlaky2000} for linear optimization
problems to the case of CPs. New large-update IPMs for solving
CPs are introduced based on the so-called {\em self-regular}
proximities.
To build up the complexity of these new algorithms, we impose
a new smoothness condition on the underlying mapping and this
condition can be viewed as a natural generalization of the {\em
relative Lipschitz} condition for convex programs introduced by
Jarre~\cite{int:JarreTh}. By utilizing various appealing
properties of {\em self-regular} proximities, we will show that if
the undertaken problem satisfies certain conditions, then these
new large-update IPMs for solving CPs have polynomial
$\O\br{n^{\frac{q+1}{2q}}\log\frac{n}{\epsilon}}$ iteration bounds
where $q$ is the so-called barrier degree of the corresponding
proximity.
$P_0$, $P_*$, 単調な線形相補性問題に対する内点法 (in Japanese)
Date:
「最適化とアルゴリズム」研究部会 2000年12月9日（土） 14:00 〜 17:30
Place:
場所：上智大学 四ッ谷キャンパス7号館12階1215号室
Abstract:
線形計画問題に対する主双対内点法が提案されたごく初期の段階から，この内点法の
自然な拡張として，単調な線形相補性問題に対する内点法が提案されてきた．
タイトルにある$P_*$, $P_0$相補性問題を，この内点法との関連で性格付けるならば，
反復回数を同様な道具立てで導出できるクラスのひとつが$P_*$線形相補性問題であり，
内点法の各反復が定義可能であるクラスのひとつが$P_0$線形相補性問題であると位置
付けることができる．元来，単調な相補性問題の技術的な拡張と考えられて来た$P_*$
相補性問題であるが，最近の研究により，特に非線形な$P_*$相補性問題が，内点法の
成功に不可欠な中心パスと密接な関係をもつ，大きな役割をもつクラスであることが
わかってきた．本発表では，各クラスの相補性問題，応用例，内点法について概説した
のち，これらの最近の成果を紹介する．また，$P_*$(非線形)相補性問題に対する解法
として，自己正則(self-regular)な関数を用いた内点法についても言及する．
A Predictor--Corrector Smoothing Method Using CHKS Function for the LCP
Date:
Optimization Workshop at Tokyo Institute of Technology, June 29--30, 2001
Place:
Tokyo Institute of Technology, Oh-Okayama Campus
Abstract:
We propose a new smoothing method using
CHKS-functions for solving linear complementarity problems.
While the algorithm in \cite{HottaInabaYoshise1998} uses a quite
large neighborhood, our algorithm generates a sequence in a
relatively narrow
neighborhood and employs predictor and corrector steps at each iteration.
A complexity bound for the method is also provided under the assumption
that (i)the problem is monotone, (ii) a feasible interior point exists,
and (iii) a suitable initial point can be obtained.
As a result, the bound can be improved compared to the one in
\cite{HottaInabaYoshise1998}.
We also mention that the assumptions (ii) and (iii) can be removed
theoretically as in the case of interior point method.
$P_0$, $P_*$, 単調な線形相補性問題に対する内点法 (in Japanese)
Date:
「最適化とアルゴリズム」研究部会 2000年12月9日（土） 14:00 〜 17:30
Place:
場所：上智大学 四ッ谷キャンパス7号館12階1215号室
Abstract:
線形計画問題に対する主双対内点法が提案されたごく初期の段階から，この内点法の
自然な拡張として，単調な線形相補性問題に対する内点法が提案されてきた．
タイトルにある$P_*$, $P_0$相補性問題を，この内点法との関連で性格付けるならば，
反復回数を同様な道具立てで導出できるクラスのひとつが$P_*$線形相補性問題であり，
内点法の各反復が定義可能であるクラスのひとつが$P_0$線形相補性問題であると位置
付けることができる．元来，単調な相補性問題の技術的な拡張と考えられて来た$P_*$
相補性問題であるが，最近の研究により，特に非線形な$P_*$相補性問題が，内点法の
成功に不可欠な中心パスと密接な関係をもつ，大きな役割をもつクラスであることが
わかってきた．本発表では，各クラスの相補性問題，応用例，内点法について概説した
のち，これらの最近の成果を紹介する．また，$P_*$(非線形)相補性問題に対する解法
として，自己正則(self-regular)な関数を用いた内点法についても言及する．