How to take a dual

by math_explorer, Oct 28, 2016, 5:44 AM

The dual of the linear program
\begin{align*} v^* &= \min \vec{\textbf{c}_1}^T\vec{\textbf{x}_1}+\vec{\textbf{c}_2}^T\vec{\textbf{x}_2}+\vec{\textbf{c}_3}^T\vec{\textbf{x}_3}\\ A_{11}\vec{\textbf{x}_1}+A_{12}\vec{\textbf{x}_2}+A_{13}\vec{\textbf{x}_3} &= \vec{\textbf{b}_1}\\ A_{21}\vec{\textbf{x}_1}+A_{22}\vec{\textbf{x}_2}+A_{23}\vec{\textbf{x}_3} &\geq \vec{\textbf{b}_2}\\ A_{31}\vec{\textbf{x}_1}+A_{32}\vec{\textbf{x}_2}+A_{33}\vec{\textbf{x}_3} &\leq \vec{\textbf{b}_3}\\ \vec{\textbf{x}_1} &\ge 0\\ \vec{\textbf{x}_2} &\le 0\\ \vec{\textbf{x}_3} &\;\text{(no restriction)} \end{align*}is (modulo human error)
\begin{align*} w^* &= \max \vec{\textbf{y}_1}\vec{\textbf{b}_1}+\vec{\textbf{y}_2}\vec{\textbf{b}_2}+\vec{\textbf{y}_3}\vec{\textbf{b}_3} \\ A_{11}^T\vec{\textbf{y}_1}+A_{21}^T\vec{\textbf{y}_2}+A_{31}^T\vec{\textbf{y}_3} &\leq \vec{\textbf{c}_1}\\ A_{12}^T\vec{\textbf{y}_1}+A_{22}^T\vec{\textbf{y}_2}+A_{32}^T\vec{\textbf{y}_3} &\ge \vec{\textbf{c}_2}\\ A_{13}^T\vec{\textbf{y}_1}+A_{23}^T\vec{\textbf{y}_2}+A_{33}^T\vec{\textbf{y}_3} &= \vec{\textbf{c}_3}\\ \vec{\textbf{y}_1} &\;\text{(no restriction)}\\ \vec{\textbf{y}_2} &\geq 0\\ \vec{\textbf{y}_3} &\leq 0 \end{align*}
I don't have anything else to say here
linear algebra

Comment

0 Comments

♪ i just hope you understand / sometimes the clothes do not make the man ♫ // https://beta.vero.site/

avatar

math_explorer
Archives
- May 2020
as ever-present as the moon in the sky
+ January 2020
The hexachordal theorem
+ September 2019
some unfinished business
+ February 2018
Ultimate combo breaker
+ December 2017
Differential
+ November 2017
Number theory is really hard
+ October 2017
Eighteenth-century nonsense
+ September 2017
Some really bad rings
+ August 2017
How to solve a differential equation
+ July 2017
algebra is hard
+ June 2017
If something seems impossible, don't just give up!
+ May 2017
14422-41064 13988-00242
+ April 2017
The abnormal Sorgenfrey plane
+ March 2017
post in march
+ February 2017
How to write up a functional equation solution
+ January 2017
Post in January
+ December 2016
I can still solve synthetic geo in my head?
+ November 2016
It's November
+ October 2016
How to take a dual
+ September 2016
why are there so many deep deep facts out there
Binomial theorem
Have a triangle
+ August 2016
I met briantix today
+ July 2016
def archive_filler(month: int, year: int) -> Post:
+ June 2016
Nothing makes sense
+ May 2016
"Are you math_explorer?"
A robust fact about 5-cycles
+ April 2016
Deep geometric facts
Irreducible polynomials in extensions of the wrong degree
Axioms of the wedge product and characteristics of fields
Quadratic Gauss sums, part 1 of whatever
Monoid/group algebras and representations: a fruitless intro
+ March 2016
I just want to multiply two big numbers modulo a big number
+ February 2016
The world is complicated
+ January 2016
Keeping the fire alive
+ December 2015
something Putnam something
+ November 2015
November 14
Cayley's formula via generating functions!?
+ October 2015
This is still relevant
Missed opportunities
+ September 2015
It happened!
+ August 2015
AoPSers I have met
pOSTCARDS
+ July 2015
lalala IMO 2015
+ June 2015
RIP mavropnevma
+ May 2015
how (actually) to prove Hilbert's Nullstellensatz
+ April 2015
Zariski's lemma (can't think of a witty title ):
Towers of commutative rings and finiteness criteria (edited)
Noetherian stuff
Ideal preliminaries
Field preliminaries
Principal ideal domain preliminary
NIMO April 2015
+ March 2015
Hilbert's nullstellensatz'^H'*15 basis theorem
why do I keep posting
My CSS haxx in case anybody wants 'em
"Subscribe to this topic"
Pop-pop-popsicle
+ February 2015
Hello AoPS!
how (not) to prove Hilbert's Nullstellensatz
+ January 2015
I
Triple Product
+ December 2014
Happy 11111011111₂ from UTC+11.00111001...₂!
Post in December
+ November 2014
Logout links
The Pokéball contour integral
akrasia.css
Approximating fractions with fractions
+ October 2014
Code tags
Why do people make their blogs only readable by logged in users?
Simple polygons can be triangulated with their diagonals
combinatoricsdisguisedasnumbertheorydisguisedascombinatorics
Amaζing πaϑoloΓical compleξ analyΣiΣ
+ September 2014
Rambling, and a cube with holes in it
+ August 2014
Must... not... break... streak...
+ July 2014
oh right IMO 2014
+ June 2014
inv
+ May 2014
Apparently I haven't forgotten as much synthetic geo as expected
+ April 2014
irc.esper.net/#aops
+ March 2014
Ancient spoilers, among other things
+ February 2014
Mellin transform of sin(z) and cos(z)
+ January 2014
darn what is this algorithm
Completely ridiculous bugs II
+ December 2013
help
+ November 2013
Colleges
+ October 2013
obligatory OMO
Does anybody actually read the serious math posts here?
PM highlights
+ September 2013
"Extreme Value Theorem"
+ August 2013
Complex analysis 101: hmm, a "Cauchy" tag might be a good idea
+ July 2013
IMO results out!
sketchsketchsketch
some blabbing about IMO 2013 just because
guys guys guys CiSRA puzzlehunt is out
hurrdurr
FactFictionFour
Poll
+ June 2013
Mystery sequence
Also, the bandwagon
iPSC 2013
+ May 2013
15354014, 21505010, 32423126
I touched a hard copy of an AoPS book today
Hey look APMO results
more halp (N vs N0 vs N* vs Z+ vs Z*+ vs Z>0 vs Z>=0 vs P)
halp
AP(j)MO 2013
Hmm I actually expected more USAMO blog posts than this
+ April 2013
Well, that escalated quickly
Troll exercise
lol
+ March 2013
Entropy Teaser 4
Seven
Axioms, "describability", random philosophical ideas about math
Problem writing
Bah
+ February 2013
Another milestone
Z[√6]
+ January 2013
Achievement Greed Control... 2!
Abstract functional equation
Magic
Axiom reduction
URLs
OMO 2013 winter
Syyyyylooooow
More subgroups of index 2
+ December 2012
3x11x61
Subgroups of index 2
DistractionPuzzle
More procrastination/game-teasers
Project Euler
BTM^2/9
3,7,2,3,0
Completely ridiculous bugs
+ November 2012
Procrastination
Sums of pth powers of first n positive integers
Pfaffian
code_7.6: A Small Variation
+ October 2012
One day
SUMS puzzlehunt 2012
Suddenly realized
+ September 2012
Ok I stopped resisting let's join CiSRA
code_7.5: One Lonely Array
| Wedge |
code_7.4: Graphical Logic
code_7.3: Dimensional Analysis
More hunts
code_7.2: Simple Arithmetic, Take 2
code_7.1: Segments
+ August 2012
H.soav
List
Function pointers
+ July 2012
IMO 2012 Close
IMO 2012 Coordination Midpoint
IMO 2012 Day 2
IMO 2012 Day 1
Just another isogonal property
+ June 2012
Annoying
Cauchy
Projective harmony
Sums of one quadratic residue and one quadratic nonresidue mod p
+ May 2012
4 subsets (Iran 1999)
+ April 2012
Lessons
 
+ March 2012
Impatience
Stage 1 Complete! (camp)
475020
wallbash.speed += 117%
Mario is NP-Hard (no, really)
Almost apropos of nothing
+ February 2012
The mess of common tangents to two circles: a revisit
Playing with incentral harmonic ratios
lolamcpost
Geometrical red herrings
Homothety compositions
Homothetic circles and t10 quads
+ January 2012
...Sonnhard
Advertising, sort of
████
Return
+ December 2011
*link*
Annoying
*sigh*
Bashing
Forty
+ November 2011
Usernames
Achievement Greed Control
11/11/11
Midterms
+ October 2011
Brute Force
10/10/100
November is coding season
code_7 Reject #2: Simple Arithmetic
+ September 2011
...forgetting all my calculus
XD (pretend this parenthetical comment doesn't
Hey look another school post
My first nightmare
Quantum Mechanic Mafia
+ August 2011
5.00
Tags
Private Message Archives
code_7 Reject Puzzle #1: Missing
Gmail Password
code_7
+ July 2011
Headlines? Seriously?
+ June 2011
it's an underscore.
not a one-liner
procrastination
/throw my hands up in the air sometimes
fail streak
achievement unlocked
one moment of silent appreciation
+ May 2011
Directed Angles Modulo Pi
Complete Solutions
aaaaand another random vid
why internal tangent whyyyyy
Ellipses
Agony2
Muirhead
Triangle Post
Linear Algebra
(also very important)
Intuition
Agony1
noooooo
mind blown
Small experiment
How have I not heard this before?
Anecdotes
+ April 2011
Contrib Points
Incircle
Number theory
o_O
Firefox is crashing 4 times per day
Isogonals all over the place
O(n log n) of awesomeness
Newton
ohsnap
Post distribution 2
Eisenstein
Turán
1,7/7,7/7,7/7,2,7/7,7,7;2,7/7,3/1,7/0,5,0/7,1,1
Vomiting
Pascal
+ March 2011
Camp
?
Some obviousness about harmonic divisions
Firefox 4 RC!
combo breaker
(b = 40844)
Complex number bash, finally possible
bah
"implies Santa Claus exists when preceded by itself quoted"
++
Kiepert's Theorem
Cyclic bashing
two hard blockers
http://canweshipyet.com/
+ February 2011
.-.. . . - - .-. .. --.
Triple and half-angle formulas
omgis
Quadrilateral midlines
One-liner
Fermat distances
Power of a Point, v2.0
Binomial coefficients
reading one's old posts is a nightmare
bored?
RB3x3x7
more random big primes
partial adjustment
Homothecies actually do work
+ January 2011
628 posts
The other way to avoid seizures
JBwT
angle chasing
must do more algebra
trig fail
speed
must do more math
+ December 2010
Whoa, paperless!
Complicated dependencies
+ November 2010
Fail streak starts here.
14
Preflow-Push-Lift
Dinic/Blocking-Flow
Edmonds-Karp
The Reaper timer is glitchy.
Metafail
Juggling concurrent cevian ratios (ft. Asymptote)
Plane isometries and one-liners
13 37 2
Midterms
+ October 2010
Reaper visualization
Something special about this blog
2^9 posts
Why
Red-Black Trees: Deletion
Asymptote
Red-Black Trees
bored
Fermat point, take 3(D)
Fermat point, take 2
Fermat point
One more random problem
8 hours on Reaper!
Sketchpad doodling
+ September 2010
Triangle Inequality
Triangle Center X(1337)
Trig Ceva, for hexagons this time
Another common-sense lemma
Vector+Trig Bash (meh)
Lagrange Multipliers Bash (ha!)
One of those hand-waving proofs
I'm awesome at
Awkward inversion
Yes, this is deliberate
Painfully simple trig bash
Post distribution
Wins and fails are not mutually exclusive
Randomly generated title
1996 AjHSME
First spam
Oops
Common Sense
Oh, I'm supposed to write the solutions too.
+ August 2010
A vanilla translation problem
Combinatorial Geometry
Shouts
Submit

  • how do you have so many posts

    by krithikrokcs, Jul 14, 2023, 6:20 PM

  • lol⠀⠀⠀⠀⠀

    by math_explorer, Jan 20, 2021, 8:43 AM

  • woah ancient blog

    by suvamkonar, Jan 20, 2021, 4:14 AM

  • https://artofproblemsolving.com/community/c47h361466

    by math_explorer, Jun 10, 2020, 1:20 AM

  • when did the first greed control game start?

    by piphi, May 30, 2020, 1:08 AM

  • ok..........

    by asdf334, Sep 10, 2019, 3:48 PM

  • There is one existing way to obtain contributorship documented on this blog. See if you can find it.

    by math_explorer, Sep 10, 2019, 2:03 PM

  • SO MANY VIEWS!!!
    PLEASE CONTRIB
    :)

    by asdf334, Sep 10, 2019, 1:58 PM

  • Hullo bye

    by AnArtist, Jan 15, 2019, 8:59 AM

  • Hullo bye

    by tastymath75025, Nov 22, 2018, 9:08 PM

  • Hullo bye

    by Kayak, Jul 22, 2018, 1:29 PM

  • It's sad; the blog is still active but not really ;-;

    by GeneralCobra19, Sep 21, 2017, 1:09 AM

  • dope css

    by zxcv1337, Mar 27, 2017, 4:44 AM

  • nice blog ^_^

    by chezbgone, Mar 28, 2016, 5:18 AM

  • shouts make blogs happier

    by briantix, Mar 18, 2016, 9:58 PM

91 shouts
Contributors
james4l • ksun48 • math_explorer
Tags
geometry
geo problem
algebra
procrastination
geo theorem
computers
one-liner
abstract algebra
combinatorics
puzzles
lolwut
code_7
algorithms
IMO
number theory
stats
trigonometry
programming
geo solution
complex analysis
linear algebra
Reaper
calculus
achievement
algebraic geometry
APMO
Python
AoPS
Cauchy
complexity theory
functional equation
generating functions
jargon
javascript
Quadratic Residues
rants
streak
topology
analysis
code metaphors
college
complex numbers
group theory
lisp
permutations
Pokemon
poll
proof-writing
Putnam
quadruple entendre
representation theory
troll
Unicode
weirdqedsymbols
About Owner
  • Posts: 583
  • Joined: Dec 16, 2006
Blog Stats
  • Blog created: May 17, 2010
  • Total entries: 327
  • Total visits: 355795
  • Total comments: 368
Search Blog
a