Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

1
vote
0answers
21 views

McCormick envelope of two variables which are also defined in terms of an envelope

I have a equation which is defined as $\langle\langle x_ix_j\rangle^M\langle \cos(\theta)\rangle^C\rangle^M$ where $M$ is the McCormick envelope of product of variables $x_ix_j$ and $C$ is defined as ...
0
votes
0answers
22 views

Why in Big M method there is no nonbasic variables with following condition

Consider following standard form linear optimization problem: P:$\hspace{4 ex}$ min $\hspace{1.5 ex}$ CX s.t. $\hspace{3 ex}$ AX=b $\hspace{7 ex}$ X $\geq$ 0, $\hspace{1 ex}$ b $\geq$ 0, And ...
0
votes
1answer
24 views

When is LICQ useful in KKT conditions?

KKT establishes a set of criteria for differentiable optimisation problems related to strong duality (i.e. when primal optimal equals dual optimal). In particular, KKT conditions are necessary for ...
2
votes
0answers
21 views

Find subgradient of $f(x)=\max\{f_1(x), f_2(x)\}$

Let $f(x)=\max\{f_1(x), f_2(x)\}$ where $f_1$ and $f_2$ are differentiable convex functions defined on $R^n$. Let $x'$ be such that $f(x')=f_1(x')=f_2(x')$. Show that $g$ is a subgradient of f at $x'$ ...
0
votes
1answer
24 views

maximizing concave function with parameter

We want to maximize the convex function: $$\vec{q} \cdot \vec{x} - \lambda||\vec{x} - \vec{1}||_2^2$$ where $\lambda$ is some parameter. I'm looking at a solution that states that the maximum is a ...
-1
votes
0answers
11 views

Projection onto the consensus set $C = \{(x_1,\ldots,x_m) : x_1 = \cdots = x_m \}$? [on hold]

How to prove that the projection onto the consensus set $C = \{(x_1,\ldots,x_m) \ : \ x_1 = \cdots = x_m \}$ is the average of all the variables $\overline{x} = (1/m) \sum_{i=1}^m x_i$, that is \...
0
votes
0answers
20 views

Design a LPNN for constrained optimization

I'm trying to build a neural network to solve this optimization problem minimize $f(x)$ s.t. $h(x)=0$ where $x =(x_1, x_2, \dots, x_n)^T \in R^n$, $f: R^n \rightarrow R$ and $h: R^n \rightarrow R^m$...
1
vote
1answer
26 views

How to imply the vanishing gradient condition in KKT?

In Boyd's Convex Optimisation, the following optimisation problem is considered $$ \begin{align} \min\quad & f_0(x)\\ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1:m,\quad m\in\Bbb Z_{\ge 0}\\ &...
0
votes
0answers
13 views

Find tangent cone to closed convex set

Let $X = \{x\in\mathbb{R}^5: x_i \geq 0, x_1+2x_2-x_3 = 6,x_1 + x_2 + 2x_4 -x_5 = 4\}$, and I am looking to find the tangent cone to $X$ at the point $(0,4,2,0,0)$. How would I go about this? I know ...
0
votes
0answers
23 views

Use simplex method to solve linear programming problem

The problem I am given is max $x_1 + 3x_2$ subject to $x_1 + x_2 \leq 5, 3x_1 - x_2 \geq -3, x_1,x_2 \geq 0$ The first step I took was to put this into standard form: max $x_1 + 3x_2$ subject to $x_1 ...
0
votes
1answer
24 views

minimize a function using SGD

I have to solve the following exercice : $$ min ||Ax - y||_2 + ||x||_2^2$$with respect to x, where A ∈ $R^{q×p}$, x ∈ $R^p$ and y ∈ $R^q$. Use stochastic gradient descent. My first question is how ...
1
vote
1answer
28 views

For a convex function, if $f$ is differential at $x$ then how is $\delta f(x) = \{\nabla f(x)\}$

I was going through concepts of subdifferential and would like to know the proof for following statement. If f is a convex function and $\delta f(x)$ is subdifferential of $f$ at $x$ and also $f$ is ...
-1
votes
1answer
16 views

Show that $f$ is differentiable at $x$ and $\nabla f(x) = g$ if the subdifferential $\partial f(x)$ is a singleton set $\{g\}$. [on hold]

I need some help in understanding the concepts of subdifferentials. I read somewhere that if $f$ is a convex function and the subdifferential $\partial f(x)$ is a singleton set $\{g\}$, then $f$ is ...
0
votes
1answer
33 views

Maximizing $x f(x)$ when $f$ is decreasing but not concave

When $f$ is concave, $f''<0$, the max can be easily found using simply the first order condition. What techniques should I apply if it is not? I'm especially thinking of a function $f$ that has ...
1
vote
1answer
36 views

Determining the dual problem

I want to figure out the dual problem for the following primal \begin{alignat*}{2} &\underset{x,t}{\text{mininimize}} &\qquad& t \\ &\text{subject to} & & x_1 \geq 1 \\ ...
1
vote
0answers
21 views

Mirror descent on a 1-ball

I have been recently reading about mirror descent, which essentially generalizes gradient descent to non-Euclidean spaces. Nearly every reference I find on this subject gives the same example for ...
1
vote
0answers
33 views

Prove that the dual of the norm approximation problem has the given form.

Consider the norm approximation: $$ (P) \begin{cases} \min_{x \in \mathbb{R}^n} \Vert Ax - b \Vert \end{cases} $$ where $A \in \mathcal{M}_{m \times n}(\mathbb{R})$ and $b \in \mathbb{R}^m$. ...
0
votes
0answers
31 views

Convergence of gradient descent method for functions without Lipschitz gradient

In Bertsekas' book "Parallel and Distributed Computation: Numerical Methods", it is stated in Exercie 2.1 that the Lipschitz condition on $\nabla f$, needed for gradient descent to converge, can be ...
0
votes
0answers
19 views

Is dynamic programming suitable for a specific optimization problem?

Let $c,\,\mathcal{P}_0,\,\mathcal{P}_1,\,\mathcal{P}_2,\ldots$ be a sequence of positive real numbers. Let $N\in\{1,\,2,\,3,\ldots\}$ and let $t\in\{0,\,1,\,2,\ldots\}$, with $N$ and $t$ fixed. ...
1
vote
1answer
32 views

minimize frobenius norm subject to rank condition

I'm trying to solve the following problem: Let A be (a, b) matrix. Given l < min ( a, b) , solve: \begin{align} \min_{rank(X)= l} || A - X ||_{Fro}^2 \end{align} I'm novice in optimization and ...
0
votes
0answers
11 views

What can be the convex relaxation of a quadratic matrix inequality?

I am trying to relax the Quadratic Matrix Inequality given as: $$W \leq X^TX+Y^TY \\ W\geq 0 $$ Here, $X,Y,W \in \mathbb{R}^{n\times n}$ matrices. These two are to be solved along with one linear ...
0
votes
0answers
10 views

Why can $X=qq^T \in S^n_+$ prove $Y \notin \mathbf K^*$?

$\mathbf K = S^n_+$ (nxn real symmetric positive semidefinite matrix). Show that the dual of $\mathbf K$ $\mathbf K^*=\{\mathbf Y | Tr(\mathbf X \mathbf Y) >0, \forall \mathbf X \ge \mathbf 0\}$ ...
0
votes
0answers
29 views

Conditions for $\Vert f \Vert_2^2$ to be convex

Question: I am currently looking for general conditions for the function $\Vert f \Vert_2^2$ to be convex, where $f:C \to C$ and $C \subset \mathbb{R}^n$ is compact. References on this problem or ...
2
votes
0answers
42 views

Finding the maximum value of the following equation

For $N\in \mathbb{N}$, $M\in \mathbb{N}$, and $K\in \mathbb{N}$, $f(K)$ is given by \begin{equation} f(K) = \sum\limits_{i = 1}^{K} {\left( {\frac{{\left( {M - K} \right)!\left( {M - i} \right)!}}{{\...
1
vote
0answers
23 views

Write problem containing inverses as Semi Definite Programming

Let $v\in\mathbb{R}^m$ and positive semidefinite $M\in\mathbb{S}^m$ be fixed. For all $x\in\mathbb{R}^n$, let $A(x)=A_0+\sum_{i=1}^nx_iA_i$, where $A_0,...,A_n\in\mathbb{S}^m$ are fixed. Write $$\...
0
votes
0answers
20 views

What does the $d^*$ and $P^*$ mean in the Slater's condition?why when they are equal means the strong duality holds?

Here is question and solution,but i didn't understand the solution,can anyone help me to understand it? min $-3x_1^2+x_2^2+2x_3^2$ $s.t. x_1^2+x_2^2+x_3^2=1$ Does the strong duality hold? ...
0
votes
0answers
55 views

Proving a linear algebra equivalence statement

The equation in the link above is from Boyd's Convex Optimization class. How is the last equality derived?
0
votes
0answers
49 views

Stability in convex optimization

Let $f:\mathbb{R}^n\to(-\infty,\infty]$ be a lower semicontinuous, proper, convex function such that $f(x)\ge 0$ for all $x\in\mathbb{R}^n$. Let $C\subseteq\mathbb{R}^n$ be a convex set, either ...
1
vote
1answer
35 views

optimization, change in constraint equation.

maximizing $z = 11x_1 + 4x_2 + x_3 +15x_4$ over $3x_1 + x_2 + 2x_3 +4x_4 \leq 28$ $8x_1 + 2x_2 - x_3 + 7x_4 \leq 50$ with $x_1,x_2,x_3,x_4 \geq 0$ gives us a max of 106 a $(0,4,0,6)$ so $x_1$ ...
0
votes
0answers
18 views

$\int x^k\ d\mu(x)\geq0$ for $k$ even?

I am studying convex optimization, and the truncated moment problem is being discussed. I have no background in measure theory so I don't understand things taken for granted such as $$\int x^k\ d\mu(x)...
0
votes
0answers
16 views

Strongly convexity of a nonlinear functional

I got the following nonlinear functional $$J\left(u\right)=\frac{1}{2}\int_{\Omega}\left[H\left(\nabla u\right)\right]^2\;dx-\int_{\Omega}f\cdot u\;dx,\;\forall\;v\in X$$, where $H$ is a Finsler norm, ...
0
votes
0answers
19 views

prove that the functional is $\alpha$-elliptic

I got a nonlinear functional who is convex and Gâteaux differentiable. Is there some property of these two that can bring me that the functional is $\alpha$-elliptic???
2
votes
1answer
43 views

why is $\sum\limits_{i=1}^{n}v_ix_i(1-x_i)=v^Tx+x^T diag(v)x?$ and its dual function

I saw the solution of this question,but i have some problem Q: min$_x c^T \mathbf x$ $s.t. \mathbf A \mathbf x \le \mathbf b,\mathbf x_i(1-\mathbf x_i)=0,i=1,...,n,$ where $\mathbf x =[x_1,...,x_n]^...
1
vote
2answers
44 views

Is $f(x,y) = x\log(x)+y\log(y)$ a coercive function?

From Peressini, Sullivan, Uhl, the mathematics of nonlinear programming, A function is coercive if $\lim\limits_{\|x\| \to \infty} f(x) \to \infty$ and super-coercive if, $\lim\limits_{\|x\| \to \...
2
votes
0answers
37 views

Show that $\prod_K(x)+\prod_{-K^*}(x)=x$ $\forall x \in \mathbb{R}^n$where $K$ is a cone in $\mathbb{R}^n$.

Let $K$ be a closed convex set in $\mathbb{R}^n$, $K^*$ be the dual cone of $K$, and $\prod_K(x)$ denote the Euclidean projection onto $K$. Show that $\prod_K(x)+\prod_{-K^*}(x)=x$ $\forall x \in \...
0
votes
0answers
7 views

Quasi-Newton Methods no-change Condition Requirement

In standard quasi-newton methods for fixed point iteration, it looks there is two required conditions. The first one is secant condition: $$J_{k+1} \Delta x_{k} = \Delta f_k $$ where $\Delta f_k = f(...
1
vote
1answer
25 views

Show minimum distance to a convex set is a convex function.

Show that $$ g(x)=\inf_{z \in C}\|x-z\| $$ where $g:\mathbb{R}^n \rightarrow \mathbb{R}$, $C$ is a convex set in $\mathbb{R}^n$ (nor close neither bounded), and $\|\cdot\|$ is a norm on $\mathbb{R}^...
1
vote
0answers
25 views

Maximizing a strictly concave function over a compact convex set

Let $f: S \to \mathbb{R}$ be a (strictly) concave function, where $S := \{y \in \mathbb{R}^m: y\geq 0,\, \sum_{i=1}^m y_i=1 \}$. I want to show that there is a $y^*\in S$, which maximizes $f$. $S$ ...
0
votes
1answer
30 views

How do I express this inequality as an LMI?

I have the following matrix inequality that I need to express as an LMI $ (AQ+BY) Q^{-1} (AQ+BY)^T - Q + \sum_i (A_i Q+B_i Y) Q^{-1} (A_i Q + B_i Y)^T < 0$ $Q > 0$ The matrices $A$, $A_i$, $B$...
0
votes
1answer
17 views

Understanding about $S^n_+=\cap_{z \in R^n}S_z$,so it is convex.

A set $S^{+}$ of positive semi-definite matrices (PSD) is defined as $S^+=\{\mathbf X \in S^n |\mathbf z^T \mathbf X \mathbf z \ge 0,\forall z \in R^n,\mathbf X^T=X \}$ Use the property of which ...
1
vote
1answer
25 views

Prove point is in closure of set

Consider the set $M=\{ (1,x,x^2):x \in \mathbb{R}\}$. We define $\text{cone}(M)$ as the conic hull of $M$, which admits conic combinations of its points, i.e. $\sum_i \lambda_i(1,x_i,x_i^2)\in M$ ...
1
vote
0answers
17 views

Nonlinear optimization of a matrix with the costraint to be orthonormal

I'm trying to find the matrix x which minimize the following cost function : $J =||B_b -x*B_n||^2$ with the constraint that x has to be an orthonormal matrix. I'm trying to use MATLAB fmincon tool, ...
0
votes
1answer
60 views

Prove that set is convex. [closed]

How to prove that these two sets are convex for certain $p$? And for what p they will not be convex? $$A= \{(x,y) \in \Bbb R^2 : |x|^p+|y|^p \le 1, p \in \Bbb R\}$$ $$B = \{(x,y) \in \Bbb R^2 : x>0,...
0
votes
1answer
45 views

why can we use this $x^\theta y^{1-\theta} \le \theta x+(1-\theta)y$ to prove the $\prod \limits_{i=1}^{n}x_i \ge 1$ is convex set?

Show that $\{x \in R^n_+|\prod \limits_{i=1}^{n}x_i \ge 1\}$ is convex set Hint : if $x ,y \ge 0$ and $0\le \theta \le 1$,then $x^\theta y^{1-\theta} \le \theta x+(1-\theta)y$ I don't understand the ...
0
votes
1answer
39 views

For a convex function $f$, is the following set convex: $X := \{x ∶ -f(x) \leq 1 \}$? [closed]

For a convex function $f$, is the following set convex: $X := \{x ∶ -f(x) \leq 1 \}$? I know that the set $X := \{x ∶ f(x) \leq 1\}$ is convex, but I'm unsure about the $-f(x)$ in the first set.
1
vote
1answer
22 views

why when $X=qq^T \in S^n_+$,then $tr(XY) \lt 0$,it means that $Y \notin \mathbf K^*$?

$\mathbf K = S^n_+$ (nxn real symmetric positive semidefinite matrix). Show that the dual of $\mathbf K$ $\mathbf K^*=\{\mathbf Y | Tr(\mathbf X \mathbf Y) >0, \forall \mathbf X \ge \mathbf 0\}$ ...
0
votes
0answers
16 views

Is there a time polynomial algorithm to solve a box-constrained quadratic convex program?

I am working on the following quadratic convex problem $min_{x}x^{T}Qx+f^{T}x$ subject to $a\leq x\leq b$ where $x,a,b,f\in\mathbb{R}^{n}$ and $Q$ is positive definite. Is there any algorithm that ...
1
vote
0answers
20 views

Second order necessary and sufficient conditions for convex nonsmooth optimization

For convex smooth optimization, first and second order necessary and sufficient conditions are well known. Does such standard second order necessary and sufficient conditions exist for convex ...
-1
votes
1answer
36 views

Show that the support function of a set and its convex hull are equal.

The support function of set $A$ is defined as the following $S_A(x)=\sup_{y \in A} x^Ty$, where $x \in \mathbb{R}^n$. Show that $$S_A(x)=S_{conv(A)}(x) \,\,\,\, \forall x \in \mathbb{R}^n$$
0
votes
0answers
27 views

Solve optimization problem using KKT conditions

I'm trying to understand the solution to Boyd and Vandenberghe Problem 5.30: Boyd and Vandenberghe Problem 5.30 The Lagrangian is $$L(X,\nu)=\text{tr}X-\log\det X+\nu'\left(Xs-y\right),$$ so the ...