Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

4
votes
2answers
4k views

Taking derivative of $L_0$-norm, $L_1$-norm, $L_2$-norm

I am a little confused about taking derivatives w.r.t. the norms. $L_0$-norm: $L_0$ means number of non-zero elements in a vector. Say, I am interested in an $x_i$. ...
0
votes
1answer
119 views

Partial linear relaxation yields an integer solution

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
2
votes
0answers
56 views

How to solve this type of equation with posynomial form?

I have an equation with the following form where the goal is to find $x$: $$ \sum_k c_k x^{\gamma_k} = 1$$ where $c_k, \gamma_k \in \Re^+$ and $\gamma_k > 1$ Alternatively using $y = \log(x)$ I can ...
0
votes
1answer
58 views

How to maximize $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?

Short Version of the Question: How do I maximize the value of $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$? Long Version of the Question: I'm currently attempting ...
0
votes
1answer
138 views

Notation minimum of a column vector

I'd like to know the notation to express the minimum of a column vector. Is this notation correct? \begin{equation} \min \left[\matrix{ \left|b_{n}-b_{n+1}\right| \cr ...
2
votes
1answer
51 views

Simplex with edges of length at least s having smallest circumradius

Is it true that of all $k$-simplices with edge lengths greater than or equal to some parameter $s$, the regular simplex with edge lengths $s$ has the smallest circumradius? Please supply a proof or ...
0
votes
0answers
118 views

KKT conditions of this convex optimization problem

Consider a continuous function $f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}$ such that $\forall y \in \mathbb{R}^m$ $f(\cdot,y)$ is convex, and $\forall x \in \mathbb{R}^n$ $f(x,\cdot)$ ...
1
vote
1answer
342 views

Cost minimization problem

The problem is as follows: A firm uses $k$ units of capital and $l$ units of labor to produce $(k^{\alpha}l^{1-\alpha})^{1/\beta}$ units of output, where $\alpha$ and $\beta$ satisfying $0 < ...
6
votes
0answers
86 views

Do balls optimize the boundary area for a fixed volume?

I recently saw this question, asking if the circle is the planar figure which has the least perimeter given the area. As far as I know, this is a classical problem, and the answer is affirmative. I am ...
1
vote
0answers
127 views

non-degenerate basic feasible of Polyhydron

I couldn't show this problem. Can somebody help me by this question? Consider a polyhedron $\{X \in \mathbb{R}^n | AX \leq b, X \geq 0 \}$ and a non-degenerate basic feasible solution $X^*$. We ...
0
votes
0answers
314 views

polyhedra and extreme points

I am stuck with solving this problem, does anybody has idea, how to solve it ? Let $P$ and $Q$ be polyhedra in $\mathbb{R}^n$. Let $P +Q := \{x+y ~\vert~ x \in P; y \in Q \}$ a) Show that $P + Q$ ...
2
votes
1answer
67 views

How to find the smallest bounding sphere when given a set of points?

I'm trying to figure this out using some variant of quadratic programming. I'm taking a class that covered optimization techniques, and I get the impression that this problem is solvable using ...
0
votes
1answer
67 views

How to re-parametrize for quadratic minimization?

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = \|S w\|^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...
1
vote
0answers
128 views

Simpson's rule characteristics

I just wanted to ask a quick question in regards to simpson's rule for integration. I have been reading up on the trapezoidal rule, and have found the notations and have an understanding such that: ...
1
vote
1answer
114 views

Optimization theory. active set

Consider an optimization problem where you have $$ \min_x f(x)\\ \mbox{s.t} \, \; h(x) = 0 \\ g(x) \leq 0$$ I have understood that the active set consists of the equality constraints together with ...
0
votes
2answers
591 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
1
vote
1answer
64 views

Is there an explicit solution to: $\arg \min mn : mn \geq k, l_0 \leq n \leq l_1$?

Is there an explicit solution or a fast algorithm to compute: $$\underset{(m, \ n) \in \mathbb{N}_{+}^2}{\arg \min} \ mn \ : \ mn \geq k,\ l_0 \leq n \leq l_1$$ for given constants $k, l_0, l_1 \in ...
1
vote
2answers
372 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
0
votes
2answers
569 views

Endowments & Utility Function to get Demand Function

We have two people, $A$ and $B$, A has $200$ units each of both good $X$ and $Y$ and $B$ has $100$ units each of both good $X$ and $Y$. $A$ has tastes providing a utility function such that $u(X,Y) = ...
1
vote
0answers
731 views

Optimization problem (rectangle inscribed in a right triangle)

I am stuck on this optimization problem: http://imgur.com/lpKmxvh . I am supposed to find the largest rectangle that can be fit into the right triangle. I think I am having trouble with setting up the ...
3
votes
1answer
389 views

Maximum likelihood estimators, hypergeometric and binomial

I'm trying to solve a two part problem. The set up is as follows: consider a bag with $\theta$ red marbles and $7-\theta$ blue marbles, with $\theta$ being unknown. Let $x$ denote the number of red ...
2
votes
1answer
75 views

Ask a question about an example in a course note on optimization problem with equality constraint

I have two difficulties on understanding the solution to an example in a course I took this semester on optimization. This example is given to illustrate the usage of Lagrange multiplier method ...
7
votes
5answers
627 views

Arithmetic mean is less than geometric mean (Spivak Calculus 3rd Chapter 2 Problem 22)

If $a_1, \ldots, a_n \ge 0$, the arithmetic mean $$A_n={a_1 + \cdots + a_n \over n}$$ and the geometric mean $$G_n = \sqrt[n]{a_1 \cdots a_n}$$ satisfy $G_n \le A_n$. As a first step to prove this ...
0
votes
1answer
158 views

How to solve an underdetermined linear system with variables limited to an interval

If I have an underdetermined linear system of equations, with the additional constraint that all of the variables are limited to the interval $[0, 1]$, what techniques are there to solve this in the ...
1
vote
0answers
171 views

Finding the fractional vertex-cover number ($\tau ^ \star$) for k-cycle hypergraphs.

Given a hypergraph $H$, we define $\tau (H)$ to be the minimum-vertex-cover number of $H$. That is, the size of the smallest $C \subseteq V(H)$ such that $C$ meets all edges in $E(H)$. A quite ...
0
votes
1answer
46 views

surface approximation using least squares

I am studying the following problem. Soppose you have two Bezièr patches with a common curve; suppose that the control points of the two patches are given by some initial guess (they are all known). ...
2
votes
3answers
239 views

A robust convex optimization problem

Consider a function $ f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R} $ such that $\forall x \in \mathbb{R}^n$ the map $f(x,\cdot)$ is convex, and $\forall y\in \mathbb{R}^m$ the map ...
0
votes
1answer
35 views

Mathematical generalization of the equilibrium point

Let $U$ be an open set $U \subset \mathbb R^n$. Let $f$ be a class-2 function $f: U → \mathbb R$. Prove or disprove the following statement. $∇^2 f=0$ and $∇f= 0$ at $x_0 \in U$ implies $x_0$ is ...
0
votes
1answer
52 views

How to build (and maximize) this equation

I'm trying to solve an economics problem but I cannot figure out how to build the equation system, or how to find the maximum in a piecewise function. A simplified version of the function would be ...
5
votes
1answer
1k views

Maximizing the volume of a rectangular prism

A rectangular prism has a surface area of $300$ square inches. What whole number dimensions give the prism the greatest volume? This is a math olympiad problem. It involves the volume and surface ...
0
votes
1answer
111 views

Efficient (approximate) projection onto the special orthogonal group

I need to carry out an optimization on the special orthogonal group $SO(n)$. For the line search I use a simple back-projection method $$\mbox{minimize}_\tau f(\pi(X+\tau Z))$$ where $X\in SO(n)$ ...
1
vote
0answers
78 views

Home work on linear optimization problem

I'm sorry I could not upload my homework because I'm too new to post images. The image can be obtained here: http://i40.tinypic.com/2u5rl80.png. I'm also sorry to ask such a big question. The ...
3
votes
1answer
75 views

Compute infimum

I want to compute the following infimum: $$ \inf\limits_{x_1,\ldots,x_n \geqslant 0} \dfrac{x_1 y_1 + \ldots + x_n y_n}{(a_1 x_1^\alpha + \ldots + a_n x_n^\alpha)^{\frac 1 \alpha}} $$ where $y = ...
5
votes
3answers
1k views

Lagrange multipliers and KKT conditions - what do we gain?

I'm working through an optimization problem that reformulates the problem in terms of KKT conditions. Can someone please have a go at explaining the following in simple terms? What do we gain by ...
3
votes
2answers
399 views

Gradient descent with inequality constraints

Suppose we are given a convex function $f(\cdot)$ on $[0,1]$. One wants to solve the following optimization problem: \begin{equation} \begin{aligned} & \text{minimize} && \sum_{i=1}^n ...
0
votes
1answer
38 views

How to solve Linear programs of the form Maximize v

I face difficulties in solving LPs in the form Maximize v subject to: a11x1+a12x2<=v ...........<=v The v is the variable I want to maximize. Should I ...
2
votes
2answers
134 views

Is there any way to find minimum without the use of derivatve?

The function is: $$\sqrt{(x+1)^2+\left(2x^2-\frac{1}{4}\right)^2}$$ It simplifies to: $$\sqrt{4x^4+2x+\frac{17}{16}}$$
3
votes
0answers
46 views

Optimization of Möbius transformation

Say I have a family of points $(w_i, z_i)$ for $i=1,2,...,n$, and I wish to find $a,b,c,d$ such that $\sum_i \left|\frac{a z_i -b}{c z_i - d} - w_i \right|^2 $ is minimized. I realize there are things ...
1
vote
0answers
32 views

“Buzzword” for approximate gradients (that form a positive scalar product with the real gradient)

Let $\vec g(\vec x)\in\mathbb R^N$ be the gradient of a convex function $L: \mathbb R^N\mapsto \mathbb R$ and $\vec h(\vec x)$ such that $$ \vec h(\vec x)^T\vec g(\vec x) \geq 0\quad\quad \forall \vec ...
0
votes
1answer
123 views

Maximum and minimum of determinant of matrices with entries from $\{0,1\}$ or $\{-1,0,1\}$

Maximal and Minimal value of $\bf{3^{rd}}$ order determinant whose elements are from the set $\bf{\{0,1\}}$. Maximal and Minimal value of $\bf{3^{rd}}$ order determinant whose elements are from the ...
0
votes
1answer
89 views

Show using duality that exactly one of the following systems has a solution

(I) $Ax=b$ ; $0≤ x ≤e$ (II) $uA +v ≥0 ; ub + ve = -1 ; v ≥ 0$
1
vote
0answers
77 views

Prove mathematically

Q.1 Consider the dual simplex method applied to a standard form problem with linearly independent rows. Suppose we have a basis which is primal infeasible, but dual feasible, and let i be such that ...
3
votes
0answers
109 views

Does convexity of a function guarantee tractability of finding its minimum?

Formulating a problem as a convex optimization problem usually implicitly considered to imply being able to find global minimizer of the objective. My question is that if it is true or not. ...
4
votes
1answer
169 views

Angular alignment of points on two concentric circles

I have two concentric circles $C_1$ and $C_2$ with radii $r_1,r_2$ such that $r_1< r_2$and a set of finite points $P=\left \{ p_1,p_2...p_n \right \}$ and $Q=\left \{ q_1,q_2...q_n \right \}$ are ...
1
vote
1answer
207 views

Orthogonal procrustes problem using quaternions

Hello I'm trying solve orthogonal procrustes problem in 3d with a help of quaternions. Original problem is: For matrix $A$ find orthogonal matrix $Q$ that $$||A-Q||_F =\min_{\Omega \in SO(3)} ...
0
votes
2answers
53 views

Show that $\min\{a_1,a_2,…,a_n\}$ is maximum when $a_1=a_2=…=a_n$.

Given $a_1,a_2,...,a_n\in\mathbb R$, and $a_1+a_2+...+a_n=A$. Show that $\min\{a_1,a_2,...,a_n\}$ is maximum when $a_1=a_2=...=a_n$. I feel this is quite a common sense but I don't know how to ...
0
votes
3answers
172 views

Underdetermined System and Minimizing Cost

I need to minimize 4x + 4y subject to the following constraints: $4x + 8y = 40$ $x + 2y = 10$ Any ideas? Answers must be integers, as they represent physical units.
2
votes
0answers
72 views

Nonlinear optimization of constraint parameter - subdifferential?

Disclaimer: I discovered that the FAQ suggests to post research-level to mathoverflow instead of math.stackexchange. I "moved" the question accordingly, cp. post at mathoverflow. Sorry for the ...
0
votes
1answer
45 views

Optimize winnings in a money making game.

So, given a continuous random variable A (with some density and CDF function), and a value I choose V, what is the equation to determine the best value V to maximize my earnings given that I will be ...
-1
votes
1answer
85 views

calc word optimization problem

a power line runs north-south. Town A is 3 miles due east from a point a on the power line, and town B is 5 miles due west from a point b on the power line that is 9 miles north of a. A transformer, ...