Questions tagged [convex-optimization]
Convex minimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. The convexity property can make optimization in some sense "easier" than the general case - for example, any local minimum must be a global minimum.
18
questions with no upvoted or accepted answers
6
votes
0answers
123 views
Is this a valid strong polynomial algorithm for deciding LP feasibility?
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
6
votes
0answers
51 views
Semi-definite Programming, non standard notation
The usual way to define a semi-definite program (SDP), e.g., as given in Boyd and Vandenberghe's convex optimization book, is:
$$
\begin{array}{cl}
\min & c^\top x \\
\mathrm{s.t.} & 0 \succeq ...
5
votes
0answers
71 views
Polyhedra to Simplex by using convex combination of vertices
Optimization problems over linear constraints (defining a convex polyhedron) can be written as optimization over a simplex in a higher dimension. Let $\mathcal{P}$ be a bounded polyhedron, and the ...
5
votes
0answers
451 views
Convexity of the projection of a convex set
Question:
A set $S \subset \mathbb{R}^m \times \mathbb{R}^n$ is convex. Using the fact that affine maps preserves convexity prove that $S(y) = \{x \in \mathbb{R}^m\mid (x,y)\in S \}$ and $\hat{S} = ...
3
votes
0answers
24 views
Stationary conditions for intersection
I wondered about this question for sometime.
Definition of Stationarity
(P)
$\mbox{min} f(x)$
s.t
$x\in C$
Let $f$ be $C^1$ function over a closed and convex set $C$ . then $x^*$ is called a ...
3
votes
0answers
62 views
Optimizing with a logistic function
I have a system in which I want to maximize the value of some function $f(x_T, y_T)$.
The time evolution of the system is described by some functions:
$$
\begin{align}
\frac{dx}{dt}&=\alpha \frac{...
3
votes
0answers
33 views
Linear functions in Lenstra's algorithm
I had asked this question at MathOverflow and was pointed here.
I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
3
votes
0answers
71 views
Strong Duality and Slater Condition
I am studying the Duality Chapter of Convex Optimization by Boyd. Is it possible that strong duality holds for non-convex optimization? If yes, is there any specific condition? And, what is the ...
2
votes
0answers
51 views
Prove $\sum_{i=1}^{m}\lambda_i^*\leq\frac{f(\hat{x})-f^*}{\underset{i=1,\ldots,m}{\min}(-g_i(\hat{x}))}$
Consider the primal problem \begin{align}f^*=\min&\quad f(x)\\\text{s.t.}&\quad g_i(x)\le0\tag P\end{align} where $f,g_i$ are convex functions. Suppose there exists $\hat{x}$ such that $g_i(\...
2
votes
0answers
69 views
How to linearize this multiplicative constraint?
I have a constraint in the form
$\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$
Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable).
$x$ and $\zeta$ are also optimization ...
2
votes
0answers
33 views
Optimization of strongly convex functions with approximate evaluations of gradient and Hessian
Suppose I want to find the minimum of a differentiable, strongly convex function $f:\mathbb{R}^n\to\mathbb{R}$ with constant $\mu>0$. That is, for all $x,y\in\mathbb{R}^n$, I have that:
$$f(y) \geq ...
2
votes
0answers
65 views
Can every convex problem use Lagrangian dual method?
If not all constraints satisfy equalities, does Lagrangian dual method make sense to a convex problem?
1
vote
0answers
64 views
Decomposition of Polyhedra
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
1
vote
0answers
91 views
Prove Non-Homogeneous Farkas' Lemma
Let $A\in\mathbb{R}^{m \times n}, c\in\mathbb{R}^{n}, b\in\mathbb{R}^{m}, d\in\mathbb{R}$. Suppose that there exists $y\geq0$ such that $A^Ty=c$.
Question: prove that exactly one of the following is ...
1
vote
0answers
38 views
active set method guaranteed convergence
I'm using Active Set Method to solve a nonlinear optimization function minimizing a convex function over a polyhedron of 2 linear inequalities starting at an interior point $x_o$ At this point is it ...
1
vote
0answers
55 views
How to solve this problem by Lagrange duality?
This is a convex problem and although it can be well solved by CVX, I want to know how it can be solved by the Lagrange duality method. The derivations with regard to $L_k$ and $B_k$ are constants, ...
1
vote
0answers
44 views
$\nabla_y\nabla_vf(x^*)\geq0$ for any concave $f$ if and only if $y=-v$
$f:\mathbb R^3\to\mathbb R$ is an arbitrary concave function.
$H$ is a plane. $v$ is a given vector on $H$.
$x^*=\max_{x\in H} f(x)$
Prove that $\nabla_y\nabla_vf(x^*)\geq 0$ if and only if $y=-v$.
I ...
1
vote
0answers
80 views
Question on quadratically constrained quadratic program
If the constrained optimization problem is a quadratically constrained quadratic program of the form \begin{align}\min&\quad x^HQx-a(x+x^H)+b|z^Hx|^2\\\text{s.t.}&\quad\|x\|^2\le1\end{align} ...
