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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
7 views

Theorem of the Maximum for discrete sequences of constraint sets?

Suppose that $\{X_{n}\}_{n=1}^{\infty}$ is a sequence of sets that converges to $X$ in some sense. Let $f$ be a real-valued function. I am interested in conditions under which $$ \lim_{n \rightarrow \...
user avatar
  • 321
1 vote
1 answer
25 views

Euclidean projection on convex set of positive semidefinite matrices

Define the Euclidean projection for a convex set $C$ as follows $$\pi_C(y) := \min_{x \in C} \| y - x \|_2^2$$ How would we find the projection map when $C$ is the cone of positive semidefinite ...
user avatar
0 votes
0 answers
14 views

Danskins's theorem for non-continuous variable

Assume $g(𝑥,𝑧)$ is a continuous function of two arguments $$ g:\mathbb{R}^n \times Z \rightarrow \mathbb{R} $$ where $𝑍 \subset \mathbb{R}^m$ is a compact set. Further assume $g(x,z)$ is convex in $...
user avatar
0 votes
0 answers
28 views

Why is the following equation considered affine?

From Boyd and Vandenberghe - "Convex Optimization" question 3.20(b) and 3.20(c) state that $A_{0} + A_{1}x_{x} + \ldots + A_{n}x_{n}$ is an affine transformation on the set $\{x | A_{0} + \...
user avatar
5 votes
1 answer
76 views

Proof that sum of k-eigenvalues is convex

I saw a post https://mathoverflow.net/questions/98367/a-sum-of-eigenvalues that said It is well-known that $\sum^{r}_{i = 1} \lambda_{i}(X)$ is convex. and I saw an explanation in Boyd and ...
user avatar
0 votes
0 answers
9 views

Closed form solution of linear least square with penalty term and inequality constraint

I want to find a closed form solution of the following problem $$ \min_B \|V^T B- E \|^2 + \lambda \| B\|^2$$ $$s.t. V + B \geq 0, $$ where $B \in \mathbb{R}^{k \times n }$, $E \in \mathbb{S}^n$, and $...
user avatar
  • 710
0 votes
0 answers
26 views

Quadratic programming with diagonal matrix [closed]

I am working on an optimization engineering problem that can be transformed into a quadratic programming solution problem, which can be formulated as enter image description here Where H is a ...
user avatar
3 votes
1 answer
75 views

Counterexample for a convex problem

The convex optimization problem is as follows: \begin{align} \underset{\mathbb{X},\mathbb{Y}\in\mathbb{S}_n^+}{\min}\quad &\operatorname{Tr}(X)+ \operatorname{Tr}\left(D Y \right)\nonumber\\ \...
user avatar
0 votes
0 answers
14 views

How to characterise the extreme points of $A_t := \{u \in \mathbb{R}^n \mid u_1 = 0 \text{ and } \sum_{i=1}^n \lvert u_{i+1}-u_i \rvert \le t \}$

I do not know what to do in the following exercise: For $t > 0$ consider the set $$A_t := \bigg\{u \in \mathbb{R}^n \mid u_1 = 0 \text{ and } \sum_{i=1}^n \lvert u_{i+1}-u_i \rvert \le t \bigg\}.$...
user avatar
  • 2,452
0 votes
0 answers
24 views

How do we prove that a finite convex function f is Lipschitzian?

COROLLARY 10.5.1. A finite convex function $f$ is Lipschitzian relative to $R^{n}$ if $$ \liminf _{\lambda \rightarrow \infty} f(\lambda y) / \lambda<\infty, \quad \forall y . $$ ProoF. The limit ...
user avatar
1 vote
1 answer
27 views

Proving Convexity - or Not - for a Set

Let $\Omega = \left \{X \in \mathbb{R}^{m\times n}\;|\;X^TAX+B^TX+X^TB+C \succ 0\right \}$ where $A \in \mathbb{S}^m, B \in \mathbb{R}^{m\times n}, $ and $C \in \mathbb{S}^n$ I want to decide whether $...
user avatar
  • 335
0 votes
2 answers
33 views

Finding containment between convex polytopes

Given 2 polytopes, either by their H-representations: $p_1: Ax\le b, p_2: Cx\le d$, where $b,d$ are real-valued vectors, $A,C$ are real-valued matrices, or by their V-representations: $p_1 = conv(p_{...
user avatar
0 votes
1 answer
45 views

What is a convex combination of graphs?

For example in this paper, they refer to a "convex combination of trees" (pg. 2, first paragraph), and also, more generally, to "convex combination of graphs" (pg. 2, footnote). -&...
user avatar
0 votes
0 answers
9 views

Randomness in iterative algorithm

Let $(H, \langle, \rangle)$ be a Hilbert space. take a closed and convex set $K \subset H$ and $f: K\times K \longrightarrow \mathbb{R}$. The equilibrium problem $EP(f,K)$ consists of finding $\...
user avatar
0 votes
0 answers
13 views

Equivalent characterization of L-smooth function

If a function $f(x)$ is $L$-smooth, then is it equivalent to say that $$f(x) - \dfrac{1}{2L} || \nabla f(x)||^2 \geq 0 ?$$ Can someone help me prove this? I have the definition that a function $f(x)$ ...
user avatar
0 votes
1 answer
23 views

Optimizing a linear functional over nested sets

Let $F_0\supseteq F_1\supseteq F_2\supseteq\cdots$ be a sequence of nested closed convex sets in $\mathbb{R}^d$ with some $d\ge 1$. Assume that $0\in F_n$ for all $n\ge 0$. Let $a\in\mathbb{R}^d$ be a ...
user avatar
  • 41
-3 votes
0 answers
19 views

Two questions about Convex Sets [closed]

There are 2 questions that I can't make any idea while solving. Can you give an idea how I can solve it? For C convex, show that C is closed if and only if C $\cap$ L is closed, for any affine line L?...
user avatar
4 votes
0 answers
123 views
+50

Why $[(\mathbf{I}_N-\mathbf{A}^\top \mathbf{A})\mathbf{x}]$ is Gaussian with i.i.d. Gaussian $\mathbf{A}$?

1. Background: It is presented in the paper of approximate message passing (AMP) algorithm [Paper Link] that (the conclusion below is slightly modified without changing its original meaning): Given a ...
user avatar
  • 158
-3 votes
1 answer
25 views

Convex and Lipchitz continuity of functions [closed]

If a function is convex, is it true its gradient satisfies Lipchitz continuity?
user avatar
0 votes
0 answers
19 views

Proximal mapping and quadratique model [closed]

We define the proximal mapping with respect to a function $f$ by $$ T_{\alpha f }(x)= argmin \{ \alpha f(t) + \frac{1}{2 }\parallel t-x \parallel^{2}, t \in \mathbb{R^{n}}.\} $$ with $f : \mathbb{R^{n}...
user avatar
0 votes
1 answer
14 views

When will the minimiser of a convex objective not be unique?

Given a response $Y\in\mathbb{R}^n$ and design matrix $X\in\mathbb{R}^{n\times p}$ consider the regression estimator $$\hat{\beta}=\text{arg min}_{\beta\in\mathbb{R}^p}\frac{1}{2n}\|Y-X\beta\|_2^2+\...
user avatar
0 votes
0 answers
12 views

linear programming and the number of equality constraints

I am reading a paper on solving a problem using LP methods, it says "The linear problem has $n$ variables and $m$ constraints. From linear programming theory, we know that there is an optimal ...
user avatar
  • 385
1 vote
1 answer
79 views

Norm $\|x\|$ defined as the sum of largest $r$ absolute values, how to write $\min \|A x-b\|_{2}^{2}+\|x\|$ as QP?

This is a question from Boyd Convex Optimization, Additional Exercise 5.31 In this problem, $r$ is an integer between 1 and $n$, and $\|x\|$ denotes the norm $$ \|x\|=\max _{1 \leq i_{1}<\cdots<...
user avatar
  • 23
1 vote
2 answers
53 views

How to find a point to minimize the maximal difference of squared distances to a set of points?

Let me define my question formally. Suppose we have a set of points $C = \{x_i|x_i \in \mathbb R^d, i=1,\dots, n\}$, $n>d$. The goal is to find a "center" point $x\in \mathbb R^d$, such ...
user avatar
  • 23
0 votes
0 answers
5 views

Simplex : minimum of objective function is zero when ..

I run simplex (hopefully right) with break ties rules and everything for a minimisation problem. If I end up with the same base made of variables that are not in the cost function and there's no ...
user avatar
0 votes
0 answers
15 views

Convex optimization with linear constraints. Can I solve it through KKT?

I have a constrained convex optimization problem with linear equality and inequality constraints. Minimize \begin{equation} \label{eq:costf} f(x_1,\dots,x_m) = \sum_{i=1}^m \frac{1}{x_i} \end{...
user avatar
2 votes
0 answers
11 views

A question on the projection step of Generic Adaptive Method: $x_{t+1} = \Pi_{\mathcal{F},\sqrt{V_t}} (\hat{x}_{t+1}).$

I am reading the paper "ON THE CONVERGENCE OF ADAM AND BEYOND". In this paper, they proposed the following framework of adaptive methods. I was confused on the last step: $x_{t+1} = \Pi_{\...
user avatar
  • 601
0 votes
0 answers
35 views

$\min\{200x+100y\}$ such that $x+3y\geq12$, $3x+2y\geq12$, $x\geq0,y\geq0$

$\min\{200x+100y\}$ such that $2x+3y\geq12$, $3x+2y\geq12$, $x\geq0,y\geq0$ Attempt. I am using the lagrangian approach to attack this problem and I know the optimal solution is $(0,6)$, but I cannot ...
user avatar
  • 775
-2 votes
1 answer
17 views

Duality optimisation

enter image description here Questions. what does that symbol mean between Ax and b? he has moved the b to Ax-b in the subject too section is this because all constraints have to be on one side ? if ...
user avatar
2 votes
0 answers
61 views

Mysterious distributed optimization problem

Problem. Let $x = (x_1,...,x_N) \in K^{N}$, i.e., each element $x_i$ can take at most $K$ discrete values. Let $x_{(i)}$, for $i \in 1,...,I,$ possible overlapping subsets of $x$. For example, for $K =...
user avatar
2 votes
0 answers
59 views

Lagrange dual function for multivariable optimization problem

I wish to apply the duality theorem to the optimization problem: $$\text{minimize}~~s$$ $$\text{subject to}~~g_j(x)\leq{s},~~\text{for all}~~j=1,...,r,~~x\in{X},~~s\in{\mathbb{R}},$$ where $X\subseteq{...
user avatar
  • 85
1 vote
0 answers
84 views

Optimality condition for a convex function subject to a unit probability simplex

For the optimization problem: $$\text{minimize}~~f(x)$$ $$\text{subject to}~~x\in{\Delta_n}$$ where ${\Delta_n}=\{x\in\mathbb{R}^n|\sum_{i=1}^nx_i=1,x\geq0\}$, and $f$ is a proper convex function such ...
user avatar
  • 85
0 votes
1 answer
24 views

Minimize a function regarding two coupling variables

Given known matrics $A\in \mathbb R^{2\times 2}$ and known vectors $b\in \mathbb R^2, c\in \mathbb R^2$, for the two optimization variables $x\in \mathbb R^2$ and $y\in \mathbb R$, how to obtain the ...
user avatar
0 votes
1 answer
31 views

Strongly convexity of a loss function

I want to calculate the strongly convex parameter $\sigma$ for this loss function: $$ l_Z(Z)=||Z-A||^2_F+\lambda tr[Z^TBZ] $$ where $Z\in \mathcal{R}^{n\times m}$, the value of $A,B$ and $\lambda$ are ...
user avatar
  • 193
1 vote
0 answers
36 views

How do you represent the number of iterations in the formulation of an optimization problem?

Let's say I want to minimize some function for f(x), with respect to x, in the minimum number of iterations. How would I represent the number of iterations in the formulation of this optimization ...
user avatar
  • 133
0 votes
0 answers
25 views

Projecting a point onto a convex set given by Log-Sum-Exp

Motivated by a wish to encode signal temporal logic specs (with linear predicates) as optimization problems w/o mixed integer approaches, I've been attempting to find a way to define the projection ...
user avatar
  • 48
2 votes
0 answers
22 views

Modify maximum entropy problem to fix specific Lagrange multiplier

I have an optimization problem of the form $\min_p -H(p) \text{ s.t. } \sum_{x \in \mathcal{X}} p(x)=1 \text{ and } g_i(p)=c_i \text{ for } i=1, \dots, m$ where $p \in [0,1]^{|\mathcal{X}|} $ is a ...
user avatar
-1 votes
0 answers
26 views

How to prove the following Interior point equivalence ?(COROLLARY 6.4.1 in Convex Analysis, Rockafellar) [duplicate]

COROLLARY 6.4.1. Let $C$ be a convex set in $R^{n}$. Then $z \in$ int $C$ if and only if, for every $y \in R^{n}$, there exists some $\varepsilon>0$ such that $z+\varepsilon y \in C$. How to prove:...
user avatar
0 votes
0 answers
25 views

Why dim$(C_1)$ $ < $ dim$(C_2)$? Where $C_1$ is a convex subset of the relative boundary of convex set $C_2$.

How to understand "it would have interior points relative to $\text{aff}(C_2)$"? I only find that $\text{aff}(C_1)=\text{aff}(C_2)$ by assume dim$C_1$=dim$C_2$.
user avatar
0 votes
1 answer
44 views

How to prove aff(C)=aff(relint(C))

Let $C$ be any convex set in $\mathbb{R}^n$, then $\mathrm{cl}(C)$ and $\mathrm{relint}(C)$ having the same affine hull. I know $\mathrm{aff}(\mathrm{cl}(C))=\mathrm{aff}(C)$ . But how to prove that \...
user avatar
1 vote
0 answers
14 views

Strong convexity definition based on subgradient

Suppose that we have $f: \mathbb R^d \to \mathbb R$ is convex and satisfies $$f(\textbf y) \geq f(\textbf x) + \nabla f(\textbf x)^\top(\textbf y - \textbf x) + \frac{\mu}{2} \| \textbf x - \textbf y \...
user avatar
0 votes
0 answers
8 views

Finding the upper bound of $\tau$ involving $\frac{dy_t}{dt}=-A^T(Ax_t-b),y_t\in\partial\psi(x_t)$ and the Bregman divergence function.

Define a dynamical system $$\frac{dy_t}{dt}=-A^T(Ax_t-b),~~~(1a)\\y_t\in\partial\psi(x_t),~~~(1b)$$ where $A \in \mathbb R^{n×k}$ satisfies that $A^TA$ has smallest eigenvalue $\gamma > 0, b = Ax^∗$...
user avatar
  • 752
0 votes
0 answers
29 views

Computation of Nash equilibrium in a concave game

so we have the game $(N,(S_{i})_{i\in N},(\varphi_{i})_{i\in N})$ where : $\bullet\:N$ is the set of players $\bullet\:S_{i}=[a_{i},b_{i}]$ the set of strategies for each player $i\in N$ $\bullet\:\...
user avatar
  • 1
0 votes
1 answer
27 views

Existence of accelerated subgradient methods

Heavy Ball method and Nesterov's gradient method are two kinds of accelerated versions of gradient methods that achieve optimal convergence for smooth optimization. I wonder whether there is an ...
user avatar
  • 1
2 votes
2 answers
50 views

L1 Objective as a Linear Program

I am trying to determine how the following simple L1 objective can be written as a linear program: Minimize $(\| Mx - p \|_1) + (\| Mx - q \|_1)$ wrt to $x$ such that $\| x \|_1 = 1$ and all elements ...
user avatar
0 votes
1 answer
33 views

If a function is convex, then its subgradient set is non-empty

Theorem: A function $f: \textbf{dom}(f) \to \mathbb R$ is convex if and only if $\textbf{dom}(f)$ is convex and $\partial f(\textbf x)$ is not empty for all $\textbf x \in \textbf{dom}(f)$ I know the ...
user avatar
0 votes
0 answers
20 views

location of minimum of sum of convex functions in $\mathbb{R}^n$

Given two convex function $f$ and $g$ in $\mathbb{R}^n$ with unique minimum at $x_1$ and $x_2$ respectively, what information do I need to specify the exact location $x_3$ of the minimum of $f+g$? ...
user avatar
  • 83
0 votes
0 answers
18 views

Conjugate functions - general definition and understanding

I am currently studying Stephen Boyd, where the conjugate function is defined to be $f^*(y) = \underset{x \in Dom(f)}{sup} (y^Tx-f(x))$. I understand the definition, but when I search for more ...
user avatar
  • 1
0 votes
0 answers
20 views

Finding the dual of a problem $\min_{w,b} \sum_{j=1}^{n}{\max(0,w_j)}$

Consider the optimization problem for support vector machine with $(x_i,y_i),i=1,2,\ldots,m$ is the training data set $y_i=\{-1,1\}$ $w\in \mathbb R^n$ $\min_{w,b} \sum_{j=1}^{n}{\max(0,w_j)}\\\text{s....
user avatar
1 vote
1 answer
41 views

Convexity of Frobenius norm of inverse

I am working on a problem where I'm trying to characterize if a loss function is convex or not. The loss function is of the following form: $$f(\boldsymbol{W}) = ||\boldsymbol{S} - (\boldsymbol{I} - \...
user avatar

1
2 3 4 5
132