Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.
1
vote
0answers
36 views
Duality gap in cone programming
Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem
$$
(P)\quad \min\{\langle c, x\rangle: Ax\geq_K ...
1
vote
1answer
63 views
How does the two phase method for linear programs work…
I understand that by adding artificial variables the problem can be reformulated as a new problem where the "starting point" is readily found.
What I don't get is how when this extended problem is ...
2
votes
1answer
40 views
Why can't the hyperplane H intersected with polyhedral set S contain any line…
S is the polyhedral set
$ S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \} $
and
$ H : \mathbf{c}^{T}\mathbf{x} = \beta $
with
$ \min_S ( ...
0
votes
1answer
139 views
Global Min-Max Optimization
When is
\begin{equation}
\min_X \max_Y f(X,Y)
\end{equation}
globally solvable? (i.e. we can find global solution for the optimization problem?)
I am not looking for reformulations.
Is it only when ...
2
votes
3answers
74 views
Proof of Convexity
Is the function $Trace(AX^TBX)$ a convex function in $X$ or not ? Here, $X$ is a rectangular matrix and $A,B$ are square, symmetric, p.s.d matrices. The entries in $X,A,B$ are real valued.
0
votes
1answer
160 views
Joint Convexity
Is the problem
\begin{equation}
\min_X \max_Y -\operatorname{tr}(X^TY)-\operatorname{tr}(Y^TYX)
\end{equation}
Jointly convex in $X$ and $Y$? Can we solve it globally? Why or Why not? $X$ and $Y$ ...
1
vote
1answer
67 views
Convex Sets Versus Convex Functions
Can we specify all convex sets, in terms of convex constraints (convex inequality functions) on a variable?
0
votes
1answer
120 views
What Stopping Criteria to Use in Projected Gradient Descent
Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
1
vote
0answers
30 views
General properties of an optimal solution of a convex program
How do we seek certain properties for a solution of a convex minimization problem.
For example we want to make sure if the below objective has a symmetric optimal solution:
\begin{equation}
\min_X ...
0
votes
1answer
153 views
Strict convex function?
I try to prove that
$g(x)= K |x|^2/2 + z(x)$ is strictly convex, given that $z(x) \geq - m(1 + |x|^p)$ with $m \geq 0$, $0 \leq p \leq 2$, forall $x \in \mathbb{R}^n$, provided $K$ is sufficiently ...
0
votes
3answers
58 views
lower bound of a special type of convex functions
Suppose $f$ is a convex, differentiable and $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$. The minimum of $f$ is $0$. ($f$ may not be twice differentiable.)
How to show $f(x)\geq\frac{1}{2L}\|\nabla ...
0
votes
1answer
36 views
Concave optimal value?
Let $A \in \mathbb{R}^{n \times m}$ and $B \in \mathbb{R}^{m \times n}$. Consider a compact set $C \subset \mathbb{R}^n$.
For all $x \in C$ define
$$ f(x) := \min_{y \in \mathbb{R}^m} \{ x^\top A y ...
0
votes
1answer
43 views
Simple question about the solution of non-linear equations
Given, say $4$ non linear equations with $4$ positive parameters,
$$f_1(x,y,z,t)=a,\quad f_2(x,y,z,t)=b,\quad f_3(x,y,z,t)=c,\quad f_4(x,y,z,t)=d$$
for given $a,b,c,d$, If I am able to show that ...
0
votes
0answers
68 views
Max Quadratic Expression
Let $A \in \mathbb{R}^{n \times n}$, $A = A^\top$, $B \in \mathbb{R}^{m \times n}$, and $\mathcal{C} \subset \mathbb{R}^n$ be a compact, convex set.
For $A$ not negative semidefinite, how to globally ...
0
votes
1answer
65 views
A point which I couldnt understand in a paper.
Currently I am reading a paper and the author has an optimization problem
$$\max_w\frac{w^2\alpha}{w^2\beta+v}$$
Then he substitutes $w^2$ with $x$ and defines an objective function using a ...
0
votes
0answers
125 views
Convex Functions on 2 variables over an interval
It is required to show that $f(x) = x_1x_2$ is a convex function on $[a,ma]^T$ where $a\ge 0$
and $m\ge1$.To show convexity we need to show that for $\lambda \in [0,1]$:
$f(\lambda x + (1-\lambda ...
2
votes
1answer
38 views
Are all polytopes also convex hulls?
It seems, at least in the 2-D case, that all polytopes are going to be convex. Does this hold if the dimensions are increased?
2
votes
0answers
45 views
Prove that $\text{int}(\text{dom}(f))$ is a convex set.
Let $f$ be a convex function. I have to prove that $\text{int}(\text{dom}(f))$ is a convex set. (Be careful with $-∞$ )
6
votes
2answers
405 views
Please explain the intuition behind the dual problem in optimization.
I've studied convex optimization pretty carefully, but don't feel that I have yet "grokked" the dual problem. Here are some questions I would like to understand more deeply/clearly/simply:
1) How ...
0
votes
0answers
61 views
Explain $x^*$ of subgradient in KKT -conditions: primal optima or dual optima?
I asked this question here but I noticed that this notation $x^*$ may actually mean two things: primal optimality and dual optimality. Please, explain this notation particularly here: I understand ...
0
votes
1answer
56 views
Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$
Wikipedia here explains it like this:
I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here:
"If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
-1
votes
1answer
77 views
Finding an $O(n \log n)$ time algorithm for an optimization problem
Consider the following optimization problem:
Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ ...
1
vote
0answers
28 views
using the ellipsoid algorithm to find a poly time algorithm for the optimization problem
Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in
$\mathbb{R}^n.$ Find
$\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with $|S| ...
0
votes
1answer
38 views
property of cones and their duals
I am reading Convex Optimization by Boyd and Vandenberghe (free at http://www.stanford.edu/~boyd/cvxbook/) and I am trying to justifying their assertion (p. 53) that if $K$ is a proper cone, $K^*$ is ...
1
vote
0answers
99 views
sufficient condition for KKT problems
For the Karush-Kuhn Tucker optimsation problem, Wikipedia notes that:
"The necessary conditions are sufficient for optimality if the objective function f and the inequality constraints g_j are ...
3
votes
3answers
215 views
Prove $ax - x\log(x)$ is convex?
How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function.
Any ideas?
1
vote
1answer
90 views
What does the statement “Optimality condition for convex problem” mean? KKT or other condition?
I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with ...
0
votes
1answer
59 views
Matrix computations problem: rank, pseudo inverse,…
Suppose we are given two arbitrary $m \times n$ matrices, $A$, $B$, where we know $B$ has full column rank. Let $m>>n$.
Can we always find a square $m \times m $ matrix $X$, such that $A=XB$? I ...
0
votes
0answers
70 views
Is positively weighted sum of eigenvalues of a matrix X, convex function of X?
Is positively weighted sum of eigenvalues of a matrix X, convex function of the matrix X?
0
votes
0answers
235 views
Calculation/Estimate of Lipschitz Constant for Strictly Convex Function
I have a strictly convex function
$ f(\bf{x}) = \dfrac{1}{2}\bf{x'Ax + b'x} $
where $ \bf{f} : \mathbb{R^n} \rightarrow \mathbb{R} $
and I was wondering how I can find/estimate the Lipschitz ...
1
vote
1answer
141 views
Why does a positive definite matrix defines a convex cone?
I've been working on convex optimization and got stuck.
What exactly does a positive definite(p.d) matrix represent geometrically ? what kind of vector space it forms ?
If I have a p.d matrix which ...
1
vote
1answer
87 views
Convex Combination of Hermitian Matrices
Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
2
votes
1answer
85 views
Positive values for a set of quadratic forms of Hermitian Matrices. (To find a set of vectors in which a hermitian matrix is positive definite)
Assume all matrices I discuss about are $N \times N$ and the vectors conform with dimensions. Consider the following set of Quadratic inequalities where all the matrices $A_i$ are hermitian.
...
2
votes
1answer
207 views
Lagrangian Multipliers
I have a fundamental question about Lagrange multipliers. Here it is:
I have a function to maximize with respect to a parameter say $\theta$, subject to two constraints. Lets assume that the first ...
0
votes
1answer
20 views
unstable optimizer, stable objective
I am trying to minimize a convex objective numerically using gradient descent. I select the starting point randomly. I repeat the experiment multiple times. The optimal objective value I get each time ...
1
vote
0answers
95 views
Upper bound for L1-L2 optimization problem
I am interested in the following convex optimization problem:
\begin{align*}
\max & ||x||_1 \\
\text{s.t.} & ||x-a||_1 \le K \\
& ||b\circ x||_2 \le 1\\
& x \in R^n
\end{align*}
where ...
3
votes
0answers
142 views
Global optimum of sum of convex functions
Take two real differentiable convex functions, $f_1$ and $f_2$, defined on the unit interval $[0; 1]$. I want to find the global optimum of: $\min_{x \in [0;1]} af_1(x)+bf_2(x)$, for given $a, b \in ...
0
votes
2answers
39 views
Convexity of a function and constraint
Consider the quadratic function $f(x_1,x_2,x_3,x_4)=x_1+2x_2+4x_4+x_1^2+5x_2^2+3x_3^2x_4^2-4x_1x_2-2x_2x_3+2x_3x_4$. Is f a convex function?
Consider a constraint defined using the above function f: ...
2
votes
2answers
136 views
definition of strongly convex
There are several equivalent definitions for strongly convex.
For example, some literature said:
A function $f$ is strongly convex with modulus $c$ if either of the following holds
$$f(\alpha ...
2
votes
0answers
71 views
Branch-and-Price algorithms for IP/MIP
I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
0
votes
1answer
74 views
what math topic is this kind of example part of? or what is needed to understand how to solve it? [closed]
we 100000000 sets/locations. each set has,
A = % chance of finding a cure (there are many different types of cures) for cancer
B = time it takes to extract a cure to caner
C = the optimal % chance (IN ...
1
vote
0answers
89 views
minimum of the function over symmetric body
Let $X$ be a normed space.
Let $K$ be centrally symmetric convex body with $M$ known vertices and with $Vol(K)=V$.
We subdivide body $K$ be $M$ equal pieces, $P_i, i=1, \ldots, M$, such that each ...
0
votes
1answer
69 views
Parametric Linear Program: Continuous Solution?
Consider the parametric linear problem
$$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$
$$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$
where $Y \in \mathbb{R}^{m \times s} $, $Z \in ...
0
votes
1answer
135 views
Numerical optimization with nonlinear equality constraints
A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there ...
1
vote
1answer
85 views
Gradient of Moreau-Yosida Regularization
Let $f(x):\Re^n\rightarrow \Re$ be a proper and closed convex function. Its Moreau-Yosida regularization is defined as
$F(x)=\min_yf(y)+\frac{1}{2}\|y-x\|_2^2$
$Prox_f(x)=\arg\min_y ...
0
votes
0answers
28 views
construction of a packing for polytope
Let $C=[-1,1]^n$ and $H$ be a plane with equation $\sum_{i=1}^nr_i=s, 1\le s\le n.$ (Here $r_i$ are such that $Proba(r_i=1)=Proba(r_i=-1)=1/2$). The intersection $C \cap H$ is a polytope, $P(n, s)$.
...
6
votes
3answers
302 views
Why is the affine hull of the unit circle R^2?
In Boyd's "Convex Optimization" it defines the affine hull of a subset $C$ of $R^n$ as
$$\text{aff} C = \left\{\theta_1 x_1 + \ldots +\theta_k x_k \mid x_1, \ldots x_k \in C, \theta_1 + \ldots ...
0
votes
0answers
93 views
Formulation and solution of non-linear optimzation problem with inequality constraints
I'd like to know if the following problem is well formulated and has solutions. I'm very new to the subject of nonlinear optimization with inequality constraints ('teaching myself the Kuhn-Tucker ...
0
votes
1answer
79 views
Intuition behind gradient VS curvature
In Newton's method, one computes the gradient of a cost function, (the 'slope') as well as its hessian matrix, (ie, second derivative of the cost function, or 'curvature'). I understand the intuition, ...
1
vote
3answers
184 views
Summary of Optimization Methods.
Context: So in a lot of my self-studies, I come across ways to solve problems that involve optimization of some objective function. (I am coming from signal processing background).
Anyway, I seem to ...
