第1章引 言 题 解
1. 用定义验证下列各集合是凸集： 
（1） S={（x1,x2）|x1+2x2≥1,x1-x2≥1}； （2） S={（x1,x2）|x2≥|x1|}； 
（3） S={（x1,x2）|x21+x22≤10}.
证（1） 对集合S中任意两点x（1）=x（1）1x（1）2,x（2）=x（2）1x（2）2及每个数λ∈［0，1］，有


λx（1）+（1-λ）x（2）=


λx（1）1+（1-λ）x（2）1



λx（1）2+（1-λ）x（2）2

.


由题设，有


［λx（1）1+（1-λ）x（2）1］+2［λx（1）2+（1-λ）x（2）2］

=λ（x（1）1+2x（1）2）+（1-λ）（x（2）1+2x（2）2）≥λ+（1-λ）=1，

［λx（1）1+（1-λ）x（2）1］-［λx（1）2+（1-λ）x（2）2］

=λ（x（1）1-x（1）2）+（1-λ）（x（2）1-x（2）2）≥λ+（1-λ）=1，


因此，λx（1）+（1-λ）x（2）∈S,故S是凸集.
（2） 对集合S中任意两点x（1）=x（1）1x（1）2和x（2）=x（2）1x（2）2及每个数λ∈［0，1］，有


λx（1）+（1-λ）x（2）=


λx（1）1+（1-λ）x（2）1



λx（1）2+（1-λ）x（2）2

.


由题设，有


λx（1）2+
（1-λ）x（2）2
≥λ|x（1）1|+
（1-λ）|x（2）1|
≥|λx（1）1+
（1-λ）x（2）1|,


因此λx（1）+（1-λ）x（2）∈S,故S是凸集.
（3） 对集合S中任意两点x（1）=x（1）1x（1）2和x（2）=x（2）1x（2）2及每个数λ∈［0，1］，有


λx（1）+（1-λ）x（2）=


λx（1）1+（1-λ）x（2）1



λx（1）2+（1-λ）x（2）2

.


由题设，有


［λx（1）1+（1-λ）x（2）1］2+［λx（1）2+（1-λ）x（2）2］2

=λ2x（1）21+2λ（1-λ）x（1）1x（2）1+（1-λ）2x（2）21+λ2x（1）22+2λ（1-λ）x（1）2x（2）2

+（1-λ）2x（2）22=λ2［x（1）21+x（1）22］+（1-λ）2［x（2）21+x（2）22］+λ（1-λ）［2x（1）1x（2）1

+2x（1）2x（2）2］≤10λ2+10（1-λ）2+λ（1-λ）［x（1）21+x（2）21+x（1）22+x（2）22］

≤10λ2+10（1-λ）2+20λ（1-λ）=10,


因此λx（1）+（1-λ）x（2）∈S,故S是凸集.
2. 设CRp是一个凸集，p是正整数.证明下列集合S是Rn中的凸集： 
S={x|x∈Rn,x=Aρ, ρ∈C},
其中A是给定的n×p实矩阵.
证对任意两点x（1）,x（2）∈S及每个数λ∈［0,1］,根据集合S的定义，存在ρ1,ρ2∈C,使x（1）=Aρ1，x（2）=
Aρ2，因此必有λ
x（1）+（1-λ）
x（2）=λ
Aρ1
+（1-λ）Aρ2
=A
［λρ1+（1-λ）ρ2］.由于C是凸集，必有λρ1+（1-λ）ρ2
∈C,因此λx（1）+（1-λ）
x（2）∈S，故S是凸集.
3. 证明下列集合S是凸集： 
S={x|x=Ay,y≥0},
其中A是n×m矩阵,x∈Rn,y∈Rm.
证对任意的x（1）,x（2）∈S及每个数λ∈［0,1］,
存在y1,y2≥0,使x（1）=Ay1,x（2）=Ay2,因此有λx（1）+（1-λ）x（2）=
A
［λy1+（1-λ）y2］,而
λy1+（1-λ）y2≥0，故
λx（1）+
（1-λ）
x（2）
∈S,即S是凸集.
4. 设S是Rn中一个非空凸集.证明对每一个整数k≥2,若x（1）,x（2）,…，x（k）∈
S,则
∑ki=1λix（i）∈S,
其中λ1+λ2+…+λk=1（λi≥0,i=1,2，…,k）.
证
用数学归纳法.当k=2时，由凸集的定义知上式显然成立.设k=m时结论成立，当k=m+1时，有


∑m+1i=1λi
x（i）=
∑mi=1λi
x（i）+
λm+1x（m+1）
=∑mi=1λi
∑mi=1
λi∑mi=1λi
x（i）+
λm+1x（m+1）,


其中∑m+1i=1λi=1.根据归纳法假设，


x^=
∑mi=1
λi∑mi=1λi
x（i）
∈S.


由于∑mi=1
λi+λm+1=1,因此∑mi=1λix^+λm+1
x（m+1）∈S,即
∑m+1i=1λix（i）∈S.于是当k=m+1时结论也成立.从而得证.
5. 设A是m×n矩阵，B是l×n矩阵，c∈Rn,证明下列两个系统恰有一个有解： 
系统1Ax≤0,Bx=0,cTx＞0,对某些x∈Rn.
系统2ATy+BTz=c,y≥0,对某些y∈Rm和z∈Rl.
证由于Bx=0等价于



Bx≤0,



Bx≥0.



因此系统1有解，即




A
B
-B


x≤0,cTx＞0有解.


根据Farkas定理，得


（ATBT -BT ）
y
u
v
=
c,

y
u
v
≥0


无解.记u-v=z,即得


ATy+
BTz=c,y≥0


无解.反之亦然.
6. 设A是m×n矩阵，c∈Rn,则下列两个系统恰有一个有解： 
系统1Ax≤0,x≥0,cTx＞0,对某些x∈Rn.
系统2ATy≥c,y≥0,对某些y∈Rm.
证若系统1有解，即




A
-I


x
≤0,cTx＞0


有解，则根据Farkas定理，有


（AT -I）

y
u

=c，

y
u

≥0


无解，即ATy-u=c,y≥0,u≥0无解，亦即


ATy
≥c,y≥0


无解.
反之，若
ATy
≥c,y≥0有解，即


ATy
-u=c,
y≥0, u≥0


有解，亦即


（AT -I）

y
u

=c，

y
u

≥0


有解.根据Farkas定理，有




A
-I


x
≤0,cTx＞0


无解，即


Ax≤0,x≥0,cTx＞0


无解.
7. 证明Ax≤0,cTx＞0有解.其中
A=1-21
-111，c=2
1
0.

证根据Farkas定理，只需证明


ATy=c,y≥0


无解.事实上，ATy=c, 即




1-1

-21

11



y1
y2

=

2
1
0
.


对此线性方程组的增广矩阵做初等行变换： 




1-12

-211

110





1-12

0-15

02-2





1-12

01-5

008

.


此线性方程组ATy=c的系数矩阵与增广矩阵的秩不等，因此无解，即ATy=c，y≥0无解.根据Farkas定理，Ax
≤0,cTx＞0有解.
8. 证明下列不等式组无解： 
x1+3x2＜0,
3x1-x2＜0,
17x1+11x2＞0.
证将不等式组写作


Ax
＜0,其中A=


13

3-1

-17-11

.


根据Gordan定理，只需证明ATy=0，y≥0,y≠0有解.对系数矩阵AT做初等行变换： 




13-17

3-1-11





13-17

0-1040





10-5

01-4

.


ATy=0
的同解线性方程组为



y1=5y3,

y2=4y3,y3任意.




显然ATy=0，y≥0,y≠0有解.根据Gordan定理，原来的不等式组无解.
9. 判别下列函数是否为凸函数： 
（1） f（x1,x2）=x21-2x1x2+x22+x1+x2； 
（2） f（x1,x2）=x21-4x1x2+x22+x1+x2； 
（3） f（x1,x2）=（x1-x2）2+4x1x2+ex1+x2； 
（4） f（x1,x2）=x1e-（x1+x2）； 
（5） f（x1,x2,x3）=x1x2+2x21+x22+2x23-6x1x3.
解（1） 2f（x）=


2-2

-22

为半正定矩阵，故f（x1,x2）是凸函数.
（2） 2f（x）=


2-4

-42

为不定矩阵，故f（x1,x2）不是凸函数.
（3） fx1=2（x1-x2）+4x2+ex1+x2,
fx2=-2（x1-x2）+4x1+ex1+x2,
2fx21=
2+ex1+x2，
2fx1x2=

2fx2x1=
2+ex1+x2，
2fx22=
2+ex1+x2，

因此Hesse矩阵


2f（x）=


2+ex1+x22+ex1+x2

2+ex1+x22+ex1+x2

=（2+ex1+x2）


11

11




为半正定矩阵，因此f（x）是凸函数.
（4） fx1=e-（x1+x2）-x1e-（x1+x2）=（1-x1）
e-（x1+x2）,fx2=-x1e-（x1+x2）,


2fx21=（x1-2）e-（x1+x2）
,
2fx1x2=2fx2x1=（x1-1）e-（x1+x2）
,
2fx22=x1e-（x1+x2）,



于是Hesse矩阵


2f（x）=
e-（x1+x2）


x1-2x1-1

x1-1x1




为不定矩阵，故f（x）不是凸函数.
（5） f（x）的Hesse矩阵为


2f（x）=


41-6

120

-604

.


做合同变换： 




41-6

120

-604





400

07432

032-5





400

070

00-447

.


由此可得2f（x）为不定矩阵，因此f（x）不是凸函数.
10. 设f（x1,x2）=10-2（x2-x21）2,
S={（x1,x2）|-11≤x1≤1,-1≤x2≤1},
f（x1,x2）是否为S上的凸函数？
解fx1=8x1（x2-x21）,fx2=-4（x2-x21）,

2fx21=8（x2-3x21）,2fx1x2=
2fx2x1=8x1,2fx22=-4,

函数f（x1,x2）的Hesse矩阵为


2f（x）=


8（x2-3x21）8x1

8x1-4

.


易知2f（x）在集合S上不是半正定矩阵，如在点（0，1）处的Hesse矩阵是

80

0-4

，是不定矩阵.因此f（x1,x2）不是S上的凸函数.
11. 证明f（x）=12xTAx+bTx为严格凸函数的充要条件是Hesse矩阵A正定.
证先证必要性.设f（x）=12xTAx+bTx是严格凸函数.根据定理1.4.14，对任意非零向量x及x-=0，必有


f（x）＞f（0）+
f（0）Tx.（1）



将f（x）在x-=0处展开，有


f（x）=f（0）+f（0）Tx
+12xT
2f（0）x+o（||x||2）.（2）


由（1）式和（2）式知


12xT
2f（0）x+o（||x||2）＞0.


由于f（x）是二次凸函数，2f（0）=A，o（||x||2）=0，因此xTAx＞0，即A正定.
再证充分性.设A正定，对任意两个不同点x和x-，根据中值定理，有


f（x）=f（x-）+
f（x-）T（x-x-）+12（x-x-）T2f（x^）（x-x-）

=f（x-）+
f（x-）T（x-x-）+12（x-x-）TA
（x-x-）

＞f（x-）+f（x-）T（x-x-）.


根据定理1.4.14，f（x）=12xTAx+bTx是严格凸函数.
12. 设f是定义在Rn上的凸函数，x（1）,x（2）,…,x（k）是Rn中的点，λ1,λ2,…,λk是非负数，且满足λ1+λ2+…+λk=1，证明： 
f（λ1x（1）+λ2x(2)+…+λkx（k））≤λ1f（x（1））+λ2f(x(2))+…+λkf（x（k））.
证用数学归纳法.当k=2时，根据凸函数的定义，必有


f（λ1x（1）+
λ2x（2））
≤
λ1f（x（1））+
λ2f（x（2））.


设k=m时不等式成立.当k=m+1时，有


f（λ1x（1）+
λ2x（2）+
…+λmx（m）+
λm+1x（m+1））

=f
∑
mi=1
λi

λ1∑
mi=1
λi
x（1）
+
λ2∑
mi=1
λi
x（2）
+…+
λm∑
mi=1
λi
x（m）

+
λm+1
x（m+1）
.


记


x^=
λ1∑
mi=1
λi
x（1）
+
λ2∑
mi=1
λi
x（2）
+…+
λm∑
mi=1
λi
x（m）
.


由于f（x）是凸函数，∑
mi=1λi+λm+1=1,λi≥0,根据凸函数定义，有


f

∑
mi=1
λi

x^+λm+1x（m+1
）
≤

∑
mi=1
λi

f（x^）+λm+1
f（x（m+1））.


根据归纳法假设，有


f（x^）≤
λ1∑
mi=1
λi
f（x（1））
+
λ2∑
mi=1
λi
f（x（2））
+…+
λm∑
mi=1
λi
f（x（m））.


代入上式，则有


f（λ1x（1）+
λ2x（2）+…+
λm+1x（m+1））
≤
λ1f（x（1））+
λ2f（x（2））+…+
λm+1f（x（m+1））,


即k=m+1时，不等式也成立.从而得证.
13. 设f是Rn上的凸函数，证明： 如果f在某点x∈Rn处具有全局极大值，则对一切点x∈Rn,f（x）为常数.
证用反证法.设f（x）在点x-处具有全局极大值，且在点x（1）处有f（x（1））＜f（x-）.在过点x（1）和x-的直线上任取一点x（2），使得


x-
=λx（1）+
（1-λ）x（2）,
λ∈（0,1）.


分两种情形讨论： 
（1） 若f（x（2））
≤
f（x（1））,由于f（x）是凸函数，必有


f（x-）
=f（λx（1）+（1-λ）x（2））

≤λf（x（1））+
（1-λ）f（x（2））

≤λf（x（1））+（1-λ）f（x（1））=f（x（1）），矛盾.


（2） 若f（x（2））
＞
f（x（1））,由于f（x）是凸函数，必有


f（x-）
=f（λx（1）+（1-λ）x（2））

≤λf（x（1））+
（1-λ）f（x（2））

＜λf（x（2））+（1-λ）f（x（2））=f（x（2）），矛盾.


综上，f（x）必为常数.
14. 设f是定义在Rn上的函数，如果对每一点x∈Rn及正数t均有f（tx）=tf（x），则称f为正齐次函数.证明Rn上的正齐次函数f为凸函数的充要条件是，对任何x（1），x（2）∈Rn,有
f（x（1）+x（2））≤f（x（1））+f（x（2））.
证
先证必要性.设正齐次函数f（x）是凸函数，则对任意两点x（1），x（2）∈Rn,必有


f12x（1）+12x（2）
≤
12f（x（1））+
12f（x（2））.


由于f（x）是正齐次函数，有


f12x（1）+12x（2）
=
12f（x（1）+
x（2））.


代入前式得


12f（x（1）+
x（2））≤12f（x（1））+
12f（x（2）），


即


f（x（1）+
x（2））≤
f（x（1））+
f（x（2））.


再证充分性.设正齐次函数f（x）对任意的
x（1），x（2）∈Rn满足


f（x（1）+
x（2））≤
f（x（1））+
f（x（2）），


则对任意的x（1），x（2）∈Rn及每个数λ∈（0,1），必有


f（λx（1）+（1-λ）x（2））≤f（λx（1））+
f（（1-λ）x（2））
=λf（x（1））+（1-λ）f（x（2））.


因此f（x）是Rn上的凸函数.
15. 设S是Rn中非空凸集，f是定义在S上的实函数.若对任意的x（1），x（2）∈S及每一个数λ∈（0,1）,均有
f（λx（1）+（1-λ）x（2））≤max{f（x（1））,f（x（2））},
则称f为拟凸函数.
试证明：  若f（x）是凸集S上的拟凸函数，x-是f（x）在S上的严格局部极小点，则x-也是f（x）在S上的严格全局极小点.
证用反证法.设x-是严格局部极小点，即存在x-的δ邻域Nδ（x-）,对于每个x∈S∩Nδ（x-）且x≠x-，有f（x）＞f（x-）,但x-不是严格全局极小点，即存在点x^∈S,x^≠x-,使得


f（x^）≤
f（x-）.


由于f（x）是凸集S上的拟凸函数，对每个λ∈（0,1）有


f（λx^+（1-λ）x-）≤
f（x-）.


对充分小的λ，λx^+（1-λ）x-∈S∩Nδ（x-）,这与x-是严格局部极小点相矛盾.因此，x-也是严格全局极小点.
16. 设S是Rn中一个非空开凸集，f是定义在S上的可微实函数.如果对任意两点x（1），x（2）∈S，有（x（1）-x（2））Tf（x（2））≥0蕴含f（x（1））≥f（x（2）），则称f（x）是伪凸函数.
试证明：  若f（x）是开凸集S上的伪凸函数，且对某个x-∈S有f（x-）=0,则x-是f（x）在S上的全局极小点.
证设存在x-∈S使得f（x-）=0.由于f（x）是开凸集S上的伪凸函数，按伪凸函数的定义，对任意的x∈S，（x-x-）Tf（x-）=0蕴含f（x）≥f（x-）,因此x-是f（x）在S上的全局极小点.









第2章线性规划的基本性质题解
1. 用图解法解下列线性规划问题： 
（1） min5x1-6x2

s.t.x1+2x2≤10,

2x1-x2≤5,

x1-4x2≤4,

x1,x2≥0.
（2） min-x1+x2

s.t.3x1-7x2≥8,

x1-x2≤5,

x1,x2≥0.
（3） min13x1+5x2

s.t.7x1+3x2≥19,

10x1+2x2≤11,

x1,x2≥0.
（4） max-20x1+10x2

s.t.x1+x2≥10,

-10x1+x2≤10,

-5x1+5x2≤25,

x1+4x2≥20,

x1,x2≥0.
（5） min-3x1-2x2

s.t.3x1+2x2≤6,

x1-2x2≤1,

x1+x2≥1,

-x1+2x2≤1,

x1,x2≥0.
（6） max5x1+4x2

s.t.-2x1+x2≥-4,

x1+2x2≤6,

5x1+3x2≤15,

x1,x2≥0.
（7） max3x1+x2

s.t.x1-x2≥0,

x1+x2≤5,

6x1+2x2≤21,

x1,x2≥0.