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)

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 ...
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
2answers
144 views

Convexity of $\log \det(I+(P-\text{tr}(X))\cdot X)$

where $P-\text{tr}(X)>0$ and $X$ is a diagonal matrix with diagonal elements are $(x_1,x_2,\dots x_m)$
0
votes
1answer
89 views
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 ...
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
295 views

Underlying assumption in a Primal/Dual table

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144. ...
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
3answers
171 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.
5
votes
3answers
4k views

Primal- degenerate optimal, Dual - unique optimal

Simple question- Is it possible for a linear programming optimization problem possible to have a degenerate optimal solution whereas the dual has a unique optimal solution? I can't find a scenario ...
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
83 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, ...
2
votes
2answers
51 views

Maximum of $3x^2e^{-x^3}$

I have a PDF which looks like: $f(x) = 3x^2e^{-x^3}, \quad x \geq 0 $ I need to find it's maximum (to sample from it using the rejection method), so I differentiate and set the result to $0$: ...
2
votes
0answers
51 views

Linear Program Transformations

I have a Linear Program with constrains of the form: $$a_{11}x_1+a_{12}x_2+\ldots\le 0$$ $$a_{21}x_1+a_{22}x_2+\ldots\le 0$$ $$a_{31}x_1+a_{32}x_2+\ldots\le 0$$ My problem is that if I try to ...
2
votes
2answers
117 views

Analytical Solution to a simple l1 norm problem

Can we solve this simple optimization problem analytically? $ \min_{w}\dfrac{1}{2}\left(w-c\right)^{2}+\lambda\left|w\right| $ where c is a scalar and w is the scalar optimization variable.
1
vote
1answer
93 views

Question on the perimeter of any quadrilateral

Is it true that the perimeter of any convex quadrilateral inside a unit circle is no more than $4\sqrt{2}$?
7
votes
1answer
998 views

Looking to find the largest rectangle, by area, inside a polygon

I'm looking to print text inside a polygon, programmatically. I'd like to find the largest rectangle to position the text inside the polygon out of a sub set of rectangles, ie those oriented with ...
1
vote
1answer
139 views

Properties of shortest walks and simple paths during optimization

Let $G=(V,E)$ denote a digraph, $s,t\in V$ two different vertices in $G$ and $w:E\to\mathbb R$ the weighting function for all edges. Moreover $\mathcal K$ denotes the set of all walks, $\mathcal E$ ...
2
votes
1answer
106 views

Formulate optimization problem

My research area has "nothing to do with mathematics" but I still find it full of optimization problems. Therefore, I would like to learn to formulate and solve such problems, even though I am not ...
1
vote
0answers
20 views

Issues with solving large sparse linear equations

I have some issues solving sparse linear equations Ax = b My matrix A is sparse with dimension of 5 million by 5 million. Actually, it is a combination of two matrices. One is tridiagonal and the ...
0
votes
1answer
223 views

Infeasible start Newton's method

I am implementing infeasible start Newton's method from the information in the slides (slide 11 of the link) posted here. It requires us to calculate primal and dual Newton steps, denoted by, $\Delta ...
2
votes
2answers
82 views

What is going on with this constrained optimization?

I'd like to figure out what is going on when trying to maximize a function (below $a_i$ are real numbers) $F = a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1;$ When we have active constraints ...
1
vote
0answers
56 views

need help with raw distance function

I need help with the following function: $$ \rho(x,\theta)=\min_{\lambda\in [0,\infty]} d(x ,x+\lambda[\cos \theta, \sin \theta]^T),$$ such that $$ x+\lambda[\cos \theta,\sin \theta]^T\in \bigcup_i ...
0
votes
1answer
56 views

Time bound for gradient descent

Have you seen any analytic bound on gradient descent (for number of iterations to achieve to $\epsilon$ error, and possibly based on the form of cost function and initial value)? Here is the problem; ...
0
votes
3answers
153 views

Maximizing triangle area

Here is the problem: We start with a triangle ABC with area 1. We choose a point (F) on side AB, then someone else chooses a point (G) on side BC. We then choose the last point (H) on side CA. Our ...
0
votes
1answer
45 views

on the sufficiency of Lagrange multipliers

Suppose that we have a nonnegative polynomial $f(x) \in \mathbb{R}[x_1,\cdots,x_n]$ and we want to minimize it subject to the polynomial constraint $h(x)=0$ with $h(x) \in \mathbb{R}[x_1,\cdots,x_n]$. ...
2
votes
0answers
149 views

Least Squares Fit for Accelerometer Data

I am in the process of calibrating a triaxial Accelerometer. I have placed the Accel into 12 positions, each position should give the following 'ideal' G Values (X,Y,Z): $0.7071000, 0.0000000, ...
3
votes
0answers
136 views

How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?

I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
2
votes
1answer
145 views

Optimal strategy puzzle

Play a game with an urn. $75$ blue balls. $25$ red balls. $1$ yellow ball. you get a dollar for every red and if you select the yellow you lose everything. what should be your strategy in the game. ...
3
votes
4answers
230 views

Maximum surface inside a triangle

If I have a triangle with sides of length a, b, c and I have a rope of length L, what is the maximum surface of a boundary I can form with that rope that is entirely inside the triangle. Normally, ...
0
votes
2answers
475 views

Transpose of matrix inverse: $(AA^T)^{-1}A^Tb \stackrel{?}{=} (A^TA)^{-1}A^Tb$

Given the matrix equation: $$ x^TA^TA = b^TA $$ I'm trying to find the least squares solution (i.e.; trying to minimize $r=||Ax-b||$). The matrix $A$ is not necessarily symmetric. When I solve it ...
2
votes
0answers
672 views

Optimization with symmetric matrix constraint

Consider the following optimization problem: ''Minimize some objective $f(A)$ over all matrices $A$ s.t. $A \mathbf{1} = \mathbf{1}$ and $A = A^T$.'' I wonder in which ways one can handle the ...
3
votes
2answers
708 views

Jacobian of Reprojection Error

I am writing a program to find the transformation between two sets of 3D points extracted from a moving stereo camera. I am using an 'out of the box' Levenberg-Marquardt implementation to find this ...
1
vote
0answers
68 views

Revised Simplex: reduced cost and related constraint

In the revised simplex method, you can get the reduced costs straightforward from the tableau. I know which they are, but I don't know which reduced cost I should "relate" to which constraint. Will ...
1
vote
2answers
112 views

find maximum and minimum for any function

I'm writing an optimization algorithm thats supposed to find the maximum and minimum value of any given function. Whats the fastest numerical approuch to do so?
3
votes
3answers
189 views

Finding the minimum of $\frac pq + \frac rs$ for distinct integers $p, q, r, s$ from $\{1,2,3,4,5,\ldots,16,17\}$

Here is the question: Four distinct integers $p$, $q$, $r$ and $s$ are chosen from the set $\{1, 2, 3, 4, 5, \ldots, 16, 17\}$. The minimum possible value of $\frac pq + \frac rs$ can be written ...
2
votes
2answers
428 views

genetic algorithm binary encoding

I am trying to write a program for maximizing a function using a genetic algorithm. The function has $n$ integer variables $x_1 \dots x_n$, such that each variable is in the range [-n,n]. What is ...
3
votes
1answer
99 views

Maximizing a convex function

The following problem is exercise I.6 from Bellman's Dynamic Programming. Consider the problem of maximizing the function $$ F(x_{1} , \ldots , x_{N}) = \sum_{i = 1}^{n} \varphi(x_{i}), $$ subject to ...
0
votes
2answers
79 views

Anyone saw this interesting function before?

Say $\theta\in\Re^n$ and $\theta_i\in(0,1)$ for all $i$. Define $$ f(\theta) = \frac{1}{n}\sum_i^n\{(1-\theta_i)\log(1-\theta_i)+\theta_i\log\theta_i\} $$ It is easy to see the minimizer of ...
0
votes
1answer
166 views

Epigraph of a function f: D $\rightarrow$ R is convex iff epif(f) is a subset of D*R which is a convex set

As in the topic, how to show that $epi(f)$ is convex iff $epi(f)$ belongs to D*R which is a convex set.
2
votes
0answers
84 views

How to project points in 3-space into a 2D subspace while minimizing the maximum change in Euclidean distance?

We have a small set of points in $\mathbb{R}^3$ (around 4 to 10 points, say). I would like to project these points onto a 2D subspace such as to minimize the maximum change in Euclidean distances. ...
0
votes
2answers
179 views

Optimization and Rent

The manager of a large apartment complex knows from experience that 110 units will be occupied if the rent is 342 dollars per month. A market survey suggests that, on the average, one additional unit ...
-2
votes
2answers
3k views

Minimum ladder over wall optimization

A fence 6 feet tall runs parallel to a tall building at a distance of 2 feet from the building. We want to find the the length of the shortest ladder that will reach from the ground over the fence to ...
0
votes
1answer
78 views

Strict local minimiser

Let $\Omega$ be a convex subset of $R^n$ adm f is a real valued, twice differentiable function. Let $x^*$ to be a point in $\Omega$ and suppose that there exists $c \in R \, c >0$ s.t. for all ...
1
vote
1answer
2k views

Optimization: Minimize cost of pipeline

A small resort is situated on an island off a part of the coast of Mexico that has a perfectly straight north-south shoreline. The point P on the shoreline that is closest to the island is exactly 6 ...
0
votes
2answers
767 views

Optimization and window area

A Norman window has the shape of a rectangle with a semi circle on top; diameter of the semicircle exactly matches the width of the rectangle. Find the dimensions of the Norman window whose perimeter ...
2
votes
1answer
796 views

Minimum distance between $x = -y^2$ and $(0,-3)$

Find the minimum distance from the parabola $x + y^2 = 0$ (i.e. $x = -y^2$) to the point $(0,-3)$. This is a homework question. When I try to use the derivative and substitute $-y^2$ for $x$, I ...
1
vote
1answer
794 views

Optimization and fence size

A fence is to be built to enclose a rectangular area of 250 square feet. The fence along three sides is to be made of material that costs 6 dollars per foot, and the material for the fourth side costs ...
1
vote
0answers
165 views

Facets of the convex hull as solution of an optimization problem?

Given $N$ points $x_1, x_2, ..., x_N \in \mathbb{R}^n$, consider their convex hull $$\mathcal{C} = \text{conv}( \{ x_1, ..., x_n \} ) = \bigcap_{j=1}^{J} \{ x \in \mathbb{R}^n : \ A_j x \leq b_j \} ...
4
votes
1answer
137 views

What is the minimal isoperimetric ratio of a polyhedron with $5$ vertices?

I'm asking and answering this question to provide a partial answer to this question and a comment on this answer at MO. The isoperimetric ratio $\mu$ of a solid is the ratio $A^3/V^2$, where $A$ is ...