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.
7,622 questions
0
votes
0
answers
21
views
Existence and Uniqueness of MLE for a collection of Bernoulli Random Variables
Suppose $Y_1\cdots Y_{10}$ are independent Bernoulli-$\frac{\exp(\alpha+x_i\beta)}{1+\exp(\alpha+x_i\beta)}$ random variables. $x_1\cdots x_{10}$ are fixed and known, $x_1\neq0$, $x$ is not a scalar ...
- 303
0
votes
1
answer
60
views
What Optimization Methods Are Suitable for Solving This Problem? [closed]
am new to the field of optimization and have encountered the following optimization problem. I am curious to know what type of optimization problem this is and what methods are appropriate for solving ...
0
votes
0
answers
17
views
Location of the maximizer of the sum of two concave and maximizable functions
This question follows up on the discussion in "Does the sum of two concave maximizable functions is maximizable?". Given that the sum of two concave, maximizable functions is itself ...
- 475
-2
votes
0
answers
32
views
Boundness of a convex function
Statement:
Let f:R->R such that f is convex and bounded then f is constant. .
Here is my proof :
Let f be a bounded convex function on R
Let c, t be real numbers such that |t|≠0:
If t>0, then ...
1
vote
0
answers
46
views
Given $f$ convex, is there a meaningful family of curves $\alpha(t)$ such that $t\mapsto f(\alpha(t))$ is still convex?
If $f:\mathbb{R}^n \to \mathbb{R}$ is convex, then it is convex along at least these two types of curves:
Lines (obviously by definition);
Gradient flow trajectories. This is also easy to see, at ...
- 905
1
vote
1
answer
36
views
Biconjugate of a nonconvex function and global minimum
Since the convex biconjugate of a function is the largest convex function bellow it, I assume that the minimum of the biconjugate function is the same as the global minimum of the original function in ...
- 23
0
votes
0
answers
38
views
When is projection faster than linear minimization?
Let $C$ be a nonempty compact convex subset of $\mathbb{R}^n$. The projection operator of $C$ is
$$\textrm{proj}_C\colon \mathbb{R}^n\to\mathbb{R}^n\colon x\mapsto \underset{c\in C}{\textrm{Argmin}}\|...
- 4,461
0
votes
0
answers
18
views
Deriving DFP updating formula
In A.Γ.'s answer to the solution of the minimization problem in the question Quasi-newton methods: Understanding DFP updating formula, I'm confused as to where the formula for step 3 is derived from. ...
- 43
0
votes
1
answer
34
views
conditions for a cubic function to be quasiconvex
Under what conditions a cubic function $f(x)=ax^3+bx^2+cx+d$ can be considered quasiconcave or quasiconvex. Specifically, I am interested in finding conditions on the coefficients
𝑎
,
𝑏
,
𝑐
that ...
- 13
1
vote
1
answer
44
views
How to prove that $g(x)=\int_{0}^{x}sgn(t)\sqrt{|t|}dt$ is convex?
Let $g:\mathbb{R}\rightarrow \mathbb{R}$ such that $g(x)=\int_{0}^{x}sgn(t)\sqrt{|t|}dt$. Prove that $g(x)$ is a convex function.
I have proven that its second derivative is positive for all $x\in\...
- 123
0
votes
0
answers
38
views
Douglas Rachford operator
I am interested in applying the Douglas Rachford algorithm to the problem $\min_x \{h(x) + g(x)\}$. The Douglas Rachford operator is defined as
\begin{equation*}
F_{DR}(w) = \dfrac{1}{2}(w + R_h(R_g(w)...
- 69
-1
votes
0
answers
62
views
Convex conjugate of integral functionals
I want to compute the convex conjugate of the following class of functionals (Bolza integral):
$ F[u] = l(u(0), u(T)) + \int_a^b{L(t, u(t), u'(t))dt} $
I want to check whether there is a procedure for ...
- 23
1
vote
1
answer
38
views
Prove that a $d$-simplex has a nonempty interior directly.
I want to show that the $d$-simplex has nonempty interior in $\mathbb{R}^d$. The $d$-simplex is defined to be the set
$$S=\left\{\theta_0\mathbf{u_0}+\ldots+\theta_d\mathbf{u}_d\,:\,\sum_{k=0}^d\...
- 801
1
vote
0
answers
26
views
Solution to a Quadratically Constrained Quadratic Program (QCQP) with unit ball constraint
I am working on a Quadratically Constrained Quadratic Program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$
$$ \mathrm{subject\ to} \qquad x^{T}x \leq 1 $$
where $P \in S^{++...
- 13
2
votes
1
answer
39
views
Is it possible for the feasible regions of an LP problem and its dual to both be compact?
I'm sure this is easy for experts, but I'm not sure how to see it myself and I can't find an answer in any of the references I skimmed through.
We know that if a (maximizing) linear program is ...
- 333
0
votes
1
answer
35
views
Does the sum of two concave maximizable functions is maximizable?
Suppose $f,g:\mathbb{R}^n\rightarrow\mathbb{R}$ are strictly concave and maximizable functions, that is, there exists $x^f,x^g\in\mathbb{R}^n$ such that $\operatorname{argmax}_{x\in\mathbb{R}^n}f(x)=x^...
- 475
1
vote
0
answers
82
views
A conjecture about the convexity of matrix functions
$f: S_{++}^n \to \mathbf{R}$ is given, where $S_{++}^n$ denotes the set of all $n$-dimensional positive definite matrices.
Suppose that $f$ is convex when $n=1$.
The conjecture is whether $f$ is ...
- 21
0
votes
0
answers
27
views
Error bound for subgradient method
Consider the function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ defined as $f(x) = \max_{i = 1, \ldots, k+1} x_i + \dfrac{1}{2}||x||^2$. I am interested in applying the subgradient method to the ...
- 69
0
votes
1
answer
25
views
On the relationship between relative interior and core of a set in convex analysis
I encountered what seems to be the same theorem about the relationship between the relative interior and core of a set in two different books:
In "First-Order Methods in Optimization" by ...
- 11
2
votes
0
answers
103
views
Similar SVMs with only different misclassification weights!
I am working on understanding the relationship between the solutions of two related SVM optimization problems, defined as follows:
Problem 1:
\begin{equation}
\min \frac{1}{2} \|w\|^2 + C \sum_{i=...
- 381
0
votes
0
answers
40
views
Does approximately null gradient imply approximately global minimum for convex functions?
Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+}$ be a non-negative and differentiable convex function which vanishes in a non-empty convex set $\Omega$ -- possibly unbounded. Usually, when one ...
- 881
0
votes
0
answers
38
views
Question about quadratic convergence
I was reading through Nesterov's convex optimization lectures, and I noticed that in his analysis of Newton's method, he ends up with the relation
$$
r_{k + 1} \leq \frac{Mr_{k}^{2}}{2\left(\ell -Mr_{...
- 65
0
votes
0
answers
29
views
Characterizing the concave conjugate.
Can the following optimization to find the conjugate be analytically solved?
$$
\underset{\beta \in \Delta_m}{min} \langle \beta,y \rangle +\sum^{K}_{a=1}w_a \log \left(\prod^{M}_{i=1}(p_{a,i})^{\...
4
votes
0
answers
54
views
Convexity of functions on a Hilbert space
I am having some trouble finding a good reference on convex optimization on Hilbert spaces.
Let $(H, \langle \cdot, \cdot \rangle)$ be a Hilbert space and $f : H \to \mathbb{R}$.
If $f$ is twice ...
- 63
0
votes
1
answer
42
views
Why do we maximise the Lagrangian with respect to the multipliers (in Support Vector Machines)?
I've been reading about SVM's, and came across the method of solving the SVM Optimization Problem using Lagrangian multipliers to convert the constrained optimization problem into an unconstrained one....
2
votes
3
answers
213
views
Finding the minimum through a chain of inequalities
Assume I have a convex function $f$ over positive-valued numbers. For each $x$, we have $f(x)=f\left(\frac{1}{x}\right)$. How can I prove, using a chain of inequalities, that for each $x, f(x) \geq f(...
- 101
-1
votes
1
answer
68
views
Inequality involving sums [closed]
Suppose I have positive numbers $\alpha_1,\alpha_2,\dots,\alpha_k$ where each $0<\alpha_i<1$ and that they also sum 1:
\begin{align}
\sum_{i=1}^k\alpha_i=1
\end{align}
Given $k$ positive numbers ...
- 3
0
votes
0
answers
17
views
Dual problem of a convex problem from discrete mixing distribution
I'm studying the paper [1] and trying to understand the primal-dual problems introduced in the middle of page 4 of [1]. Below is the problem in question:
Let $A$ be a fixed $n \times m$ matrix, where ...
- 13
-1
votes
0
answers
15
views
Optimizing over a matrix variable of a quadratic form
I am trying to solve an optimization problem of the form:
$\underset{\mathbf{s}}{max} \quad \mathbf{h}^{T} Diag(\mathbf{O}\mathbf{s}) \mathbf{P}^{-1} Diag(\mathbf{O}\mathbf{s}) \mathbf{h}$
$\text{...
0
votes
0
answers
33
views
Joint optimization of a quadratic form with matrix and vector as optimization variables
I am trying to solve an optimization problem of the form:
$\underset{\mathbf{O}, \mathbf{s}}{max} \quad \mathbf{h}^{T} Diag(\mathbf{O}\mathbf{s}) \mathbf{P}^{-1} Diag(\mathbf{O}\mathbf{s}) \mathbf{h}$
...
0
votes
0
answers
17
views
The two form(include or exclude the non-negtive constraint) of KKT condition
I encountered two different forms of KKT conditions, mainly distinguished by the definition of optimization problem they correspond to:
the maximum question is defined in $\mathbb{R}_{+}$ and the KKT ...
1
vote
0
answers
38
views
Separability of LMI constraints
I have the following constraint:
$$
\Sigma \succeq A X A^\top,
$$
where $A$ is the decision variable that is also a lower-triangular matrix, and $X, \Sigma$ are both diagonal matrices. For example,
$$
...
- 11
1
vote
1
answer
126
views
An optimization problem involving a symmetric positive definite matrix.
Suppose that A, B are known real symmetric positive definite matrices, P is an unknown real symmetric positive definite matrice, how to solve the following optimization problem?
$$P=\operatorname{...
- 21
0
votes
0
answers
32
views
Could you review my algorithm to assess its conceptual and practical validity for maintaining primal feasibility?
Problem Formulation
We aim to solve the following convex quadratic optimization problem:
Objective Function:
Minimize:
$$
f(x) = \frac{1}{2} x^\top Q x + q^\top x,
$$
where:
( Q ) is a positive ...
- 1
0
votes
0
answers
42
views
Seek counterexample for local minimum of coordinate-wise convex functions
This question is related to this.
Let $f : \mathbb{R}^n \to \mathbb{R}$ be a function that is convex in each coordinate (coordinate-wise convex function). Suppose $f$ achieves the global minimum.
In ...
- 42.6k
0
votes
1
answer
44
views
constrained optimization problem with dominating weight
For a vector $a = (a_1, a_2, \ldots, a_n)$, define the function:
$$
\varphi(a) = \sum_{i<j} a_i^2 a_j^2 W_{i,j},
$$
where $W_{i,j}$ are predefined (real-valued) weights with $W_{1,n}$ being the ...
- 6,866
0
votes
0
answers
60
views
Minimize matrix trace norm $\| A - B \|$ for A and B subjected to $D \leq A \leq C$ and $E \leq B \leq F$ with $F \leq C$ and $E \leq D$
The problem can be phrased as,
\begin{align}
\text{minimize}\;\;& \| A - B \|\\[2pt]
\text{subject to}\;\;& D \leq A \leq C\\[2pt]
&E \leq B \leq F\\
&F \leq C \\
&E \leq D
\end{...
- 13
1
vote
0
answers
30
views
Effect of relaxing RHS of constraints in a convex optimization problem
I have a convex optimization problem of the form:
\begin{align}
\min\limits_{x\in\mathbb{R}^n} \quad&f(x)\\
\text{s.t. } \quad & g_i(x) \leq b_i, \forall i\in [m]
\end{align}
Let the primal-...
- 11
0
votes
0
answers
21
views
I‘m using CVXPY, how to write these function with disciplined convex programming rule？ $\log_2(2^x-1)$
How to write these function with disciplined convex programming rule? $\log_2(2^x-1)$.
$2^x$ here is not large enough to igore -1.
I've tried log_sum_exp(x*log(2)), but I can not deal with the -1 term
- 191
0
votes
1
answer
39
views
Optimize a convex difference of quad forms
I have an optimisation problem of the form:
$$\min_x c^T x + \| V x\|^2_2 + \| D x\|^2_2 - \| W x\|^2_2$$
Subject to linear constraints.
$D$ is diagonal and $V$, $W$ are non-square matrices. I know ...
0
votes
0
answers
38
views
Few questions on feasible and tangent cones at the boundary point of the closure of an open set: just brief answers with references are enough.
Let $U$ be an open domain in $\mathbb{R}^n.$ The setup I use for domains with $C^1$ boundary is [here][1]. The feasible cone at a boundary point $x\in \partial{U}$ is defined by:
$$F_x(\bar{U}):=\{v\...
- 2,556
0
votes
1
answer
52
views
Two questions on feasible cones of closures of open connected domains in $\mathbb{R}^n$ at a boundary point
Let $U$ be an open domain in $\mathbb{R}^n.$ The feasible cone at a boundary point $x\in \partial{U}$ is defined by:
$$F_x(\bar{U}):=\{v\in \mathbb{R}^n: \exists t_0 > 0 \text{ so that } x + tv \...
- 2,556
1
vote
0
answers
121
views
Solution of PDE $u_y - (u_x)^2 =0$
While working on an optimization problem I found that I could rewrite the constraint as having a convex function $u(x,y)$ such that
$u_y = u_x^2$
I wanted to know if there was a way to get a solution ...
- 11
1
vote
1
answer
52
views
p-norm minimization for single variable
When is there a closed form solution for $$\arg \min_{x\in\mathbb{R}} \|x u - v\|_p, \quad u,v\in\mathbb{R}^n?$$
More generally, if there is no closed form solution, how can this be solved numerically ...
- 2,386
0
votes
0
answers
30
views
Discrete LQR problem with LMI (solved using MATLAB)
I am trying to solve an LMI problem given in Page 265 in this book (https://link.springer.com/book/10.1007/978-3-319-09393-2). I have 3 LMI constraints Eq. (6.66), (6.67) and (6.68) and objective is ...
0
votes
0
answers
24
views
Proximal normals to a closed convex set.
I am interested in understanding the following infinite convex program:
$$ \underset{x \in R^{d}}{min} ||x-v||^2
$$
subject to the following infinite set of constraints:
$$ \langle \beta ,x \rangle \...
4
votes
1
answer
70
views
Polyhedron and their vertices as a function with respect to the constrains
Fix a matrix $A$ of size $n\times m$, and let $P(v):=\{w\in \mathbb{R}^m:Aw+v\geq 0\}$ where we view $v$ as an variable. Then let $E(P(v))$ be the set of vertices of the polyhedron $P(v)$, and let $I(...
- 283
1
vote
0
answers
32
views
How to maximize $l_1$ norm?
I have a problem of the form
\begin{align*}
\max \sum |a_i^T x + c_i| \text{ s.t. } x \in S
\end{align*}
My idea was to introduce auxiliary variables to remove the absolute value in the objective and ...
- 777
0
votes
1
answer
25
views
KKT-conditions of $\min t$ such that $t-x\geq0, t+x \geq 0, x^2 -4x + 4 = 0$
I want to solve
\begin{align*}
\min_{t,x} t\\
\text{s.t. } t-x &\geq 0 \\
t+x &\geq 0 \\
x^2 -4x + 4 &= 0
\end{align*}
with the help of KKT conditions. Obviously, the solution is given by $...
- 777
0
votes
1
answer
40
views
How to transform $\max |x|$ such that $x \in S$ in a problem without the absolute value?
Given an optimization problem $\max |x|$ such that $x \in S$, how can I transform it into an equivalent problem that does not require the absolute value condition?
I know that for a minimization ...
- 777