高级优化理论与方法（十五）

Algorithms for Constrained Optimization

基本思路：沿用无约束优化问题中的迭代方法：$x^{k+1}=x^k+{\alpha }^k{d}^k$。但是问题在于如何使得迭代满足约束条件。

Projection

Idea

If $x^k+{\alpha }^k{d}^k\in \Omega$, then $x^{k+1}=x^k+{\alpha }^k{d}^k$
else $x^{k+1}=“project” on $\Omega$.

Example

Ω = { x : l i ≤ x i ≤ u i , ∀ i } , l i , u i ∈ Ω \Omega=\{x:l_i\leq x_i\leq u_i,\forall i\},l_i,u_i\in\Omega Ω={x:li​≤xi​≤ui​,∀i},li​,ui​∈Ω
$y_i=\{\begin{array}{l}{u}_i,x_i\ge u_i\\ x_i,l_i<x_i<u_i\\ l_i,x_i\le l_i\end{array}$

Method

“Projection of $x$ on $\Omega$”: $\pi [x]:=$ the closest point of $\Omega$ to $x$.
$\pi [x^k+{\alpha }^k{d}^k]=argmi{n}_{z\in \Omega }||z-(x^k+{\alpha }^k{d}^k)||$

Project gradient method: $x^{k+1}=\pi [x^k-{\alpha }^k\nabla f(x^k)]$, where ${\alpha }^k=argmi{n}_{\alpha \ge 0}f(x^k-\alpha \nabla f(x^k))$

Problem

min$||z-(x^k+{\alpha }^k{d}^k)||$ s.t. $z\in \Omega$ is difficult to solve.

Solution

Orthogonal Projector

min $f(x)$
s.t. $Ax=b$

$A\in {\mathbb{R}}^{m\times n},m\le n,rankA=m$

Definition

Def: Orthogonal Projector: $P=I_n-A^T(A{A}^T{)}^{-1}A$

Remark

$P=P^T,P^2=P\times P=P$

Lemma

$v\in {\mathbb{R}}^n$. Then, P v = 0 ⇔ v ∈ { x : x = A T y } P_v=0\Leftrightarrow v\in\{x:x=A^Ty\} Pv​=0⇔v∈{x:x=ATy}

Theorem

$x^{\ast }\in {\mathbb{R}}^n$ is a feasible solution. $P\nabla f(x^{\ast })=0\iff x^{\ast }$ satisfies the Lagrange’s condition.

Projection

$x^{k+1}=\pi [x^k-{\alpha }^k\nabla f(x^k)]$
$=x^k-{\alpha }^{k}P\nabla f(x)$

Projected steepest descent

${\alpha }^k=argmi{n}_{\alpha >0}f(x^k-\alpha \nabla f(x^k))$

Properties

If $x^0$ is feasible, then $\forall k:x^k$ is feasible.

Theorem

$x^k$: generated by “projected steepest descent”. If $P\nabla f(x^k)\ne 0$, then $f(x^{k+1})<f(x^k)$.

Properties

$x^{\ast }$ is a global minimizer of a convex function $f$ over { x : A x = b } ⇔ P ∇ f ( x ∗ ) = 0 \{x:Ax=b\}\Leftrightarrow P\nabla f(x^*)=0 {x:Ax=b}⇔P∇f(x∗)=0

Lagrange’s Algorithm

min $f(x)$
s.t. $h(x)=0$

$h:{\mathbb{R}}^n\to {\mathbb{R}}^m,l(x,\lambda )=f(x)+{\lambda }^{T}h(x)$

Lagrange’s Algorithm: $\{\begin{array}{l}{x}^{k+1}=x^k-{\alpha }^k(\nabla f(x^k)+Dh(x^k{)}^T{\lambda }^k)\\ {\lambda }^{k+1}={\lambda }^k+{\beta }^{k}h(x^k)\end{array}$

Theorem

Provided $\alpha ,\beta$ sufficiently small. $\exists$ a neighborhood of $(x^{\ast },{\lambda }^{\ast })$ $((x^{\ast },{\lambda }^{\ast })$ satisfies $\nabla f(x^{\ast })+Dh(x^{\ast }{)}^T{\lambda }^{\ast }=0,L(x^{\ast },{\lambda }^{\ast })\ge 0)$ such that if $(x^{\ast },{\lambda }^{\ast })$ is in this neighborhood, the algorithm converges to $(x^{\ast },{\lambda }^{\ast })$ with at least a linear order.

min $f(x)$
s.t. $g(x)\le 0$

$l(x,\mu )=f(x)+{\mu }^{T}g(x)$
$x^{k+1}=x^k-{\alpha }^k(\nabla f(x^k)+Dg(x^k{)}^T{\mu }^k)$
μ k + 1 = [ μ k + β k g ( x k ) ] + = m a x { μ k + β k g ( x k ) , 0 } \mu^{k+1}=[\mu^k+\beta^kg(x^k)]_+=max\{\mu^k+\beta^kg(x^k),0\} μk+1=[μk+βkg(xk)]+​=max{μk+βkg(xk),0}

Theorem

$(x^{\ast },{\mu }^{\ast })$ satisfies the KKT-conditions. $L(x^{\ast },\mu )\ge 0$. Provided $\alpha ,\beta$ sufficiently small, $\exists$ a neighborhood, then the algorithm converges to $(x^{\ast },{\mu }^{\ast })$ with at least a linear order.

Penalty Function

min $f(x)$
s.t. $x\in \Omega$

$\Rightarrow$ min $f(x)+rP(x)$
$r\in {\mathbb{R}}^{+}:$ penalty parameter.
$P(x):{\mathbb{R}}^n\to \mathbb{R}$: penalty function

Definition

$P$ is a penalty function, if
(1)$P$ is continuous
(2)$P(x)\ge 0,\forall x\in {\mathbb{R}}^n$
(3)$P(x)=0\iff x\in \Omega$

min $f(x)$
s.t. $g_i(x)\le 0$
$\Rightarrow p(x)=\sum _i{g}_i^{+}(x)$
where g i + ( x ) = m a x { 0 , g i ( x ) } g_i^+(x)=max\{0,g_i(x)\} gi+​(x)=max{0,gi​(x)}

Example

$g_1(x)=x-2$
$g_2(x)=-(x+1{)}^3$
$g_1^{+}(x)=\{\begin{array}{l}0,x\le 2\\ x-2,\text{otherwise}\end{array}$
$g_2^{+}(x)=\{\begin{array}{l}0,x\ge -1\\ -(x+1{)}^3,\text{otherwise}\end{array}$
$P(x)=\{\begin{array}{l}x-2,x>2\\ 0,-1\le x\le 2\\ -(x+1{)}^3,x<-1\end{array}$

Def: Courant-Beltrami-Penalty: $P(x)={\sum }_{i=1}^p(g_i^{+}(x){)}^2$

Multi-objective Optimization

min $f(x)=\left[\begin{array}{c}{f}_1(x)\\ f_2(x)\\ \cdots \\ f_l(x)\end{array}\right]$
s.t. $x\in \Omega$

Pareto-optimal

Pareto-optimal: $x^{\ast }\in \Omega$. If $\nexists x\in \Omega$ s.t. for $i=1,\cdots ,l:f_i(x)\le f_i(x^{\ast })$ and $\exists i:f_i(x)\le f_i(x^{\ast })$

Multi to Single

①Weighted sum: $f(x)=\sum w_i{f}_i(x)$
②MiniMax: f ( x ) = max ⁡ i { f i ( x ) } f(x)=\max\limits_i\{f_i(x)\} f(x)=imax​{fi​(x)}
③p-norm: $f(x)=||f_i(x)|{|}_p=f_1^p(x)+\cdots +f_l^p(x)$
④satisfactory: min $f_1(x)$
s.t. $f_2(x)\le b_2,\cdots ,f_l(x)\le b_l$

总结

这节课主要介绍了约束优化问题的算法，分为投影法和惩罚函数法。在投影法中，为了解决迭代方法中难以求得满足限制条件的最小值问题，引入了正交投影算子。在惩罚函数法中，引入了惩罚函数，对落在约束区域外的点进行惩罚。最后简单介绍了多目标优化问题。多目标优化问题较难，现有的理论较少，只简单介绍了帕累托最优，以及将多目标优化问题转换成单目标优化问题的几种方法。至此，优化理论与优化方法的内容就全部结束啦。

课程考察重点

FONC,SONC,SOSC的应用。
Gradient method, Newton method, Conjugate method等优化方法的应用。
单纯形法，拉格朗日条件，KKT条件。
纯应用，没有证明。五道大题。
重点考察对方法是否熟悉，侧重过程，不侧重计算。