All Questions
Tagged with convex-optimization optimization
3,669 questions
0
votes
1
answer
62
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 ...
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
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
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
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})^{\...
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
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
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
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
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
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
0
votes
1
answer
79
views
Solve $\max |x|$ such that $x^2 - 4x + 4 = 0$?
I want to solve
\begin{align}
\max |x| \text{ s.t } x^2 -4x + 4 = 0
\end{align}
Exercise 1 is to reformulate the problem without the norm. This yields
\begin{align*}
\max t \\
\text{s.t. } t-x &\...
- 777
0
votes
0
answers
16
views
Does the solutions yielded by augmented Lagrange function fulfill equality constraints?
Consider the following optimization problem,
\begin{equation}
\begin{aligned}
\min_{x}\ & f(x),\\
s.t.\ &g(x)=0,
\end{aligned}
\end{equation}
with the smooth functions~$f(x),g(x)$,
which can ...
- 11
0
votes
0
answers
20
views
Do we need LICQ for SOSC in KKT points?
I am currently reading Numerical Optimization by Wright and Nocedal.
I stumbled upon the second-order necessary and sufficient conditions.
and
What confuses me is that LICQ is apparently not needed ...
- 777
1
vote
0
answers
55
views
Seeking a Proof for Eigenvalue Bound in Theorem 8.3 from Nocedal & Wright (Broyden Class)
I am studying the Broyden class of quasi-Newton methods in Numerical Optimization by Nocedal and Wright, and I've come across Theorem 8.3, which does not include a detailed proof in the book. The ...
- 11
0
votes
0
answers
24
views
Does $\arg\min_{x \in C}g(x) = P_C (\arg \min_{x}g(x))$?
Let $C$ be a convex set, $g(x)$ a convex function, and $P_C(x)$ is the projection map onto $C$. Is the following statement true?
$$\arg\min_{x \in C}g(x) = P_C (\arg \min_{x}g(x))$$ If the statement ...
- 11
0
votes
0
answers
43
views
Finding Closed Form Solution
I am looking for a closed form solution to the problem
$\min_{W} \ AW - y \\$
$\text{such that} \\$
$\sum_{i} w_i \le 1 \\$
$w_i > 0 \quad \forall i \in W$
I am pretty new to optimization so I have ...
- 1
1
vote
1
answer
32
views
Solve $\min -x_1-x_2$ such that $x_1+2x_2 = 0, \| x\|^2 \leq 125$ with KKT conditions.
Given the following problem
\begin{align*}
\min -x_1-x_2 \\
\text{s.t.} x_1+2x_2=0 \\
\| x\|² \leq 125
\end{align*}
From the equality it follows that $x_1=-2x_2$. Plugging this into the norm ...
- 777
0
votes
0
answers
34
views
How to Add a Convex Function to a Nonconvex Function to Achieve Convexity
Assume that I have a nonconvex function $f(x)$ and I'm interested in finding a convex function $g(x)$ such that the sum $f(x) + g(x)$ is convex. One common approach I’ve seen is to add a term like $\...
- 57
0
votes
0
answers
21
views
Application of KKT conditions to 4-dimensional problem
For a given vector $y \in \mathbb{R}^4$ we state the following problem
\begin{align*}
\max_{\lambda, b} \lambda y_4 + b_4 \text{ s.t. } y^Tb = 0, (\lambda -1)² \|y\|² \leq 0, \|y\|² = \|b\|²
\end{...
- 777
0
votes
0
answers
20
views
Finding a convex function whose subdifferential is a hypercube
This is a HW problem for a class in convex optimization:
Find a convex $f:\mathbb R^n \to \overline{\mathbb R}$ such that $\partial f(0)=[1,2]^n$.
Here $\overline{\mathbb R}$ denotes the extended ...
- 2,827
1
vote
0
answers
64
views
How to tell if cost function (a sum of quadratics) is convex?
I have a mixed integer nonlinear programming optimization problem with the following characteristics:
All the constraints are linear
The cost function (which I want to minimize) is a sum of ...
- 226
0
votes
0
answers
13
views
Sub-differential at a point, nonlinear optimization
I've got some difficulties with computing the sub-differential.
I've got the following exercise:
Consider the problem to
$$
\begin{cases}
\text{minimize } -x_1 \\
\text{subject to }\\ (x_1+1)^2+x_2^2 \...
- 593
2
votes
1
answer
39
views
How to correctly apply KKT conditions to this specific problem?
I want to solve the following optimization problem:
\begin{align*}
\max a_4 \text{ s.t. } a_1^2 + 2a_1 + a_2^2 + 2a_2 + a_3^2 + 2a_2 + a_4^2 -2a_4 = 0
\end{align*}
I know that every optimal point ...
- 777
1
vote
1
answer
36
views
Bounded-variable simplex method
Bounded-variable simplex method's algorithm
From $\textit{'Linear and Nonlinear
Optimization'}\ $ by Igor Griva; Stephen G. Nash
; Ariela Sofer; p.219
I'm not sure how $x_2$ is chosen as the entering ...
- 1,163
0
votes
0
answers
41
views
How to transform this problem into a convex problem
We have the following optimisation problem:
\begin{align}\label{P1}
\underset{\mathbf{A,B,C,D,}\boldsymbol{\Theta }}{\mathrm{min}} &\quad f(\mathbf{A})\\
&\text{s.t.} \left[ \begin{...
- 31
0
votes
0
answers
72
views
Under which conditions does the system $Ax=0, x \geq 0$ have a non-trivial solution?
I have given a 4x4 system of the form $Ax = 0, x \geq 0$. I am interested in understanding under which conditions this system has a non-trivial solution.
Starting with $Ax=0$ it is a known result that ...
- 777
0
votes
0
answers
44
views
Dual LP: Show that l1 regularization term is equivalent to equality constraint.
Consider the primal and dual formulation of a linear optimization problem:
\begin{gather*}
\begin{split}
\text{maximize} \quad & {\langle \vec{b}, \vec{z} \rangle} \\
\text{subject to} \...
- 1
1
vote
0
answers
47
views
Nesterov Accelerated Gradient method for convex non-smooth objective functions
I need to solve an optimization problem involving an Extreme Learning Machine $z=W_2\sigma(W_1 x)$, where the weight matrix for the hidden layer $W_1$ is a fixed random matrix, $\sigma()$ is the ...
- 11
0
votes
1
answer
85
views
Proof using Farkas's lemma... $x$ is an optimal point if and only if $c_N^t - c_B^t B^{-1} N \geq0$
Consider the following problem:
\begin{align*}
\text{Minimize } c^t x\\
\text{subject to } A x = b\\
x \geq 0
\end{align*}
where $A$ is an $(m \times n)$ matrix of rank $m$. Let $x$ be an extreme ...
- 3
0
votes
1
answer
35
views
Unclear step in proof that convex functions are locally Lipschitz (Ruszczyński Lemma $2.70$)
The following is a Lemma from Ruszczyński "Nonlinear Optimization".
Question: I have reproduced the Lemma and its proof below in its entirety, however I just have a question about one step: ...
- 2,827
0
votes
1
answer
85
views
Projected Gradient Descent Applies on the Constraint $\boldsymbol{l} \leq \boldsymbol{X} \boldsymbol{t} \leq \boldsymbol{u}$
I understand that in projected gradient descent, I need to project my (intermediate) solution to the feasible set with shortest distance like here:
What is the difference between projected gradient ...
- 469
0
votes
0
answers
37
views
Optimization of affine invariant metric
Notations:
$\theta$: Rotation angle
$s$: Scale factor
$t = (t_x, t_y)$: Translation vector
$R(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$: ...
- 51
1
vote
0
answers
72
views
A discrete optimization problem
We have $\mathbf{A}\in \mathbb{C} ^{N\times K},\mathbf{A}=\left[ \begin{matrix}
a_{1,1}& …& a_{1,K}\\
…& a_{i,j}& …\\
a_{N,1}& …& a_{N,K}\\
\end{matrix} \right] ,|a_{i,...
- 31
0
votes
0
answers
35
views
Conditions for Convexity of a Product of Functions
I am studying the convexity of a product of functions and would like some assistance identifying additional conditions on one of the functions.
Let $ f: \mathbb{R} \rightarrow \mathbb{R}^+ $ be a non-...
- 11
0
votes
1
answer
66
views
A variational problem from physics / quantum mechanics?
I look at the problem of minimizing the functional $(a, b > 0$)
$$\int_{\mathbb R} (a x^2 f(x)^2 + b f'(x)^2)dx$$ over $L^2$ functions with ($L^2$-)norm $1$.
The solution is Gaussian but I do not ...
- 419
0
votes
0
answers
44
views
The value of supinf when infsup is infinity
I have an optimization problem of the form:
\begin{align*}
\text{minimize } f(x) \text{ s.t. } x \in X \text{ and } g(x) \le G.
\end{align*}
I have $f$ and $g$ as continuous and convex functions on $X$...
- 173